1

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.

  • Actually, the query you have should be among the fastest possible ways - with the right indexes present. Much faster than the accepted answer - even if not as convenient. Here are a couple of techniques: stackoverflow.com/a/7774879/939860 – Erwin Brandstetter Apr 24 at 0:00
  • Thanks for the link. I've given it a read, and what I gather is that I should stick to my old solution and check my indices instead. From what I gather, a unique constraint on UserGroup(user_id, group_id) should solve the performance problems. I'll try it out a little later. Thanks again – Eldamir Apr 24 at 4:11
  • From what I can tell, you are right, that the joins are more efficient, at least when there is a small amount of joins. In my case, I have some situations where it will produce upwards of 50 joins, and even with indices in place, it appears that the "group by * having *" solution is more efficient. – Eldamir Apr 24 at 7:43
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) @> 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

  • Nice. Haven't used having before. If I wanted to say: get all users that are in groups [1,2] OR [2,3], would it be valid to say ... HAVING array_agg(group_id) @> array[1,2] OR array_agg(group_id) @> array[2,3] ?? – Eldamir Apr 23 at 13:28
  • 1
    @Eldamir: yes that should work - at least if you don't mean an exclusive OR – a_horse_with_no_name Apr 23 at 13:32
1

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:

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:

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:

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.

  • That is a whole other level of detail, than I am used to working in. A lot of reading for me to make sense of all of this. I'll try to find some quiet time for it. Thank you for your effort here. Much appreciated – Eldamir Apr 25 at 11:21
0

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);
  • You're absolutely right, but you'll find the same solution in my question, along with a note that it doesn't scale well, if the list of groups become big. What if I want to check on 10, 50, 100 groups? That will be a tonne if joins and a performance degradation. – Eldamir Apr 23 at 17:40
  • Yes, but you'll always have that scaling issue, be your data in arrays, JSON, XML... whatever. You are, IMHO, far far better off keeping your data in a relational framework and using plain old vanilla SQL with proper indexes. I would only go to arrays, JSON, XML, Key-Value... whatever, if I had thoroughly exhausted all the possibilities available with SQL - which increase year on year - CTEs, Window functions...! Scaling problems will occur with any solution! – Vérace Apr 23 at 17:44
  • I can get behind that statement, for sure, but as it stands, your proposed solution simply isn't feasible for my usage. One of my worst datasets took 8s to finish, and with the accepted solution, it is at 0.2s. Any other suggestions you can provide is much appreciated :) – Eldamir Apr 23 at 17:46
  • How are your indexes on your tables? – Vérace Apr 23 at 17:49
  • The given tables are simply a contrived example, but for my actual db, each table has index on primary and foreign keys – Eldamir Apr 23 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.