Query "all of" across many-to-many relation

Question

Imagine a setup of three tables, User, Group, and UserGroup, where UserGroup consists of simple a foreign key to each of User and Group tables.

User
----
id
name

Group
-----
id
name

UserGroup
---------
user_id
group_id

Now, I want to write a query selecting all users that are in all of some specified groups. e.g. Select * from users where the user is part of every one of "group1", "group2", and "group3".

With a Django ORM query, I'd do something like

users = (
    User.objects
    .filter(user_group__group_id=group1.id)
    .filter(user_group__group_id=group2.id)
    .filter(user_group__group_id=group2.id)
)

Which would produce a join for each call to .filter, e.g.

SELECT * FROM users
INNER JOIN user_group g1 ON g1.user_id = id
INNER JOIN user_group g2 ON g2.user_id = id
INNER JOIN user_group g3 ON g3.user_id = id
WHERE g1.group_id = %s
  AND g2.group_id = %s
  AND g3.group_id = %s

This becomes a bit hairy if I were to query a bigger set to match by.

So what is a better way to do this? If I were to ask for "any" rather that "all", if would be a simple matter of

SELECT * FROM users
INNER JOIN user_group g1 ON g1.user_id = id
WHERE g1.group_id in %s

But that is not what I need.

A small note: My specific environment is on Postgres, so no fancy MSSql thing will help me here. Preferably, the answer should be general enough to use in any SQL flavour.

Answer 1

You can do it with "fancy Postgres" features - much easier than "fancy MS SQL features" ;)

You can aggregate all the group IDs into an array and then compare that.

If with "all of" you mean those users that are assigned to exactly those groups, you can use something like this:

SELECT u.id
FROM users u
  JOIN user_group ug on ug.user_id = u.id
group by u.id
having array_agg(ug.group_id order by ug.group_id) = array[1,2,3];

Note that the = operator for arrays depends on the order [1,2,3] is a different array than [3,1,2] that's why array_agg() uses an order by and the values in the array are sorted as well.

If with "all of" you mean those users that are assigned to at least those groups (but could be assigned to more) then you can use a simple "contains" operator:

SELECT u.id
FROM users u
  JOIN user_group ug on ug.user_id = u.id
group by u.id
having array_agg(ug.group_id order by ug.group_id) @> array[1,2,3];

The "contains" operator @ does not depend on the order of the elements.

---

If you need to return the complete row from the users table, you can do the aggregation in a derived table and join to that:

SELECT u.id
FROM users u
  JOIN (
    SELECT user_id
    FROM user_group 
    GROUP BY user_id    
    HAVING array_agg(group_id) @> array[1,2,3]
  ) ug on ug.user_id = u.id

---

The second query can also be done using standard SQL:

SELECT u.id
FROM users u
  JOIN (
    SELECT user_id
    FROM user_group 
    WHERE group_id in (1,2,3)
    GROUP BY user_id    
    HAVING count(distinct group_id) = 3
  ) ug on ug.user_id = u.id;

This solution has the disadvantages that you need to synchronize the values for the IN list and the count(..) = 3 expressions when you change the list of IDs

Answer 2

You mentioned in a later comment:

I have some situations where it will produce upwards of 50 joins

That many joins are a game changer.

Better base query

Normally, the order of joins is mostly irrelevant. Postgres will reorder them as it sees fit to achieve best performance. But that many joins are well beyond join_collaps_limit (default 8). Postgres does not try to find the optimal query plan any more. Too many possibilities. The order of joins becomes much more significant. Consider this query:

SELECT u.*
FROM   user_group g1
JOIN   user_group g2 USING (user_id)
JOIN   user_group g3 USING (user_id)
-- ...
JOIN   users u ON u.id = g1.user_id
WHERE  g1.group_id = %s               -- most selective first !
AND    g2.group_id = %s
AND    g3.group_id = %s
... 
;

The USING keyword in the join clause at least avoids repeated user_id columns. But SELECT * would still include all other columns from all 50+ tables, making the SELECT list (and data transfer) huge and expensive, while you probably only need columns from users. (You did not clarify.)

Place the most selective predicate first to reduce the number of rows from the outset. That's the rarest group in your case. Can make the query a lot cheaper.

To make it more "dynamic", you can wrap this in a recursive CTE (and that in a function or prepared statement) as demonstrated in detail here:

• SQL query to find a row with a specific number of associations

Materialized view with index on array

A materialized view seems like a tempting option for your case with many predicates - if your write load and requirements allow it:

CREATE MATERIALIZED VIEW user_groups AS
SELECT user_id, array_agg(group_id) AS groups
FROM   user_group
GROUP  BY 1;

See:

• Materialized views Performance

Then you can add a GIN index on the derived array and query with array operators tapping into it to arrive at a completely different level of performance.

CREATE INDEX ON user_groups USING gin (groups);

SELECT user_id FROM user_groups WHERE groups @> '{1,2,3}';

intarray

If user_id is data type integer (as it probably should be), you can further optimize with the additional module intarray. See:

• Compare arrays for equality, ignoring order of elements

It may be advantageous to have sorted array then:

CREATE MATERIALIZED VIEW user_groups AS
SELECT user_id, array_agg(group_id) AS groups
FROM   (SELECT user_id, group_id FROM user_group ORDER BY 1,2) ug
GROUP  BY 1;

intarray provides additional operator classes and index options with them.

CREATE INDEX ON user_groups USING gin (groups gin__int_ops);

If your resulting arrays are are truly big, consider:

CREATE INDEX ON user_groups USING gist (groups gist__intbig_ops);

The query to go with it looks unchanged:

SELECT user_id FROM user_groups WHERE groups @> '{1,2,3}';

But, internally, it will now use the faster intarray operator @> instead of the generic array operator @> and the matching index. Should be considerably faster, yet.

Answer 3

This looks like a classic AND scenario - which will work with any database server that supports SQL. And, no need to use arrays or any "fancy MS SQL features" or, indeed, PostgreSQL ones or from any server!

What you want (in standard SQL) is (fiddle here):

SELECT u.id, u.name FROM the_user u
INNER JOIN user_group g1 ON g1.user_id = u.id
INNER JOIN user_group g2 ON g2.user_id = u.id
INNER JOIN user_group g3 ON g3.user_id = u.id
WHERE g1.group_id = 5
  AND g2.group_id = 6
  AND g3.group_id = 7;

Result:

id   name
 3  user3

This is the desired result - no arrays, no fancy stuff, just plain, honest SQL :-)

You can also use the INTERSECT set operator:

SELECT ug.user_id, u.name
  FROM user_group ug
  JOIN the_user u ON ug.user_id = u.id
  WHERE ug.group_id = 5

INTERSECT

SELECT ug.user_id, u.name
  FROM user_group ug
  JOIN the_user u ON ug.user_id = u.id
  WHERE ug.group_id = 6

INTERSECT

SELECT ug.user_id, u.name
  FROM user_group ug
  JOIN the_user u ON ug.user_id = u.id
  WHERE ug.group_id = 7;

Result:

user_id      name
      3     user3

ditto! May be better performance wise?

========= DML and DDL =========

Tables (DDL):

CREATE TABLE the_user -- not "user" - can be an SQL keywowrd
(
  id INT,
  name VARCHAR (10)
);

CREATE TABLE groupe -- use the French - GROUP being a keyword!
(
  id INT,
  name VARCHAR (10)
);

CREATE TABLE user_group
(
  user_id INT,
  group_id INT
);

Data (DML):

INSERT INTO the_user VALUES (1, 'user1'), (2, 'user2'), (3, 'user3');

INSERT INTO groupe VALUES (5, 'group1'), (6, 'group2'), (7, 'group3');

INSERT INTO user_group VALUES (1, 6), (1, 7), (2, 5), (2, 7), (3, 5), (3, 6), (3, 7);