How to filter SQL results in a has-many-through relationship

Question

Assuming I have student , club and student_club tables:

 student { id name } club { id name } student_club { student_id club_id } 

I want to know how to find all students both in football (30) and in a baseball club (50).
Although this query does not work, this is the closest I have so far:

 SELECT student.* FROM student INNER JOIN student_club sc ON student.id = sc.student_id LEFT JOIN club c ON c.id = sc.club_id WHERE c.id = 30 AND c.id = 50 

Answer 1

I was curious. And, as we all know, curiosity has a reputation for killing cats.

So what is the fastest way cat cats?

The exact environment of the sketas for this test:

• PostgreSQL 9.0 on Debian Squeeze with decent memory and settings.
• 6,000 students, 24,000 club members (data copied from a similar database with real-life data.)
• A slight deviation from the naming scheme in the question: student.id is student.stud_id and club.id here club.club_id .
• I named the queries after their author in this thread with an index in which there are two.
• Several times I ran all queries to fill the cache, and then I selected the best of 5 with EXPLAIN ANALYZE.

• Corresponding indexes (should be optimal - if we lack knowledge of which clubs will be requested):

   ALTER TABLE student ADD CONSTRAINT student_pkey PRIMARY KEY(stud_id ); ALTER TABLE student_club ADD CONSTRAINT sc_pkey PRIMARY KEY(stud_id, club_id); ALTER TABLE club ADD CONSTRAINT club_pkey PRIMARY KEY(club_id ); CREATE INDEX sc_club_id_idx ON student_club (club_id); 

  club_pkey not required for most requests here. Primary keys automatically implement unique indexes in PostgreSQL.
  The latter index should compensate for this well-known drawback of PostgreSQL multi-column indexes :

The B-tree multi-column index can be used with query conditions that include any subset of the index columns, but the index is most effective when there are restrictions on the leading (left) columns.

Results:

Total run time from EXPLAIN ANALYZE.

1) Martin 2: 44.594 ms

 SELECT s.stud_id, s.name FROM student s JOIN student_club sc USING (stud_id) WHERE sc.club_id IN (30, 50) GROUP BY 1,2 HAVING COUNT(*) > 1; 

---

2) Erwin 1: 33.217 ms

 SELECT s.stud_id, s.name FROM student s JOIN ( SELECT stud_id FROM student_club WHERE club_id IN (30, 50) GROUP BY 1 HAVING COUNT(*) > 1 ) sc USING (stud_id); 

---

3) Martin 1: 31.735 ms

 SELECT s.stud_id, s.name FROM student s WHERE student_id IN ( SELECT student_id FROM student_club WHERE club_id = 30 INTERSECT SELECT stud_id FROM student_club WHERE club_id = 50); 

---

4) Derek: 2.287 ms

 SELECT s.stud_id, s.name FROM student s WHERE s.stud_id IN (SELECT stud_id FROM student_club WHERE club_id = 30) AND s.stud_id IN (SELECT stud_id FROM student_club WHERE club_id = 50); 

---

5) Erwin 2: 2.181 ms

 SELECT s.stud_id, s.name FROM student s WHERE EXISTS (SELECT * FROM student_club WHERE stud_id = s.stud_id AND club_id = 30) AND EXISTS (SELECT * FROM student_club WHERE stud_id = s.stud_id AND club_id = 50); 

---

6) Sean: 2.043 ms

 SELECT s.stud_id, s.name FROM student s JOIN student_club x ON s.stud_id = x.stud_id JOIN student_club y ON s.stud_id = y.stud_id WHERE x.club_id = 30 AND y.club_id = 50; 

The last three do almost the same thing. 4) and 5) lead to the same tariff plan.

Late additions:

Unusual SQL, but performance cannot keep up.

7) ypercube 1: 148.649 ms

 SELECT s.stud_id, s.name FROM student AS s WHERE NOT EXISTS ( SELECT * FROM club AS c WHERE c.club_id IN (30, 50) AND NOT EXISTS ( SELECT * FROM student_club AS sc WHERE sc.stud_id = s.stud_id AND sc.club_id = c.club_id ) ); 

---

8) ypercube 2: 147.497 ms

 SELECT s.stud_id, s.name FROM student AS s WHERE NOT EXISTS ( SELECT * FROM ( SELECT 30 AS club_id UNION ALL SELECT 50 ) AS c WHERE NOT EXISTS ( SELECT * FROM student_club AS sc WHERE sc.stud_id = s.stud_id AND sc.club_id = c.club_id ) ); 

As expected, the two do pretty much the same thing. In terms of the query plan, when scanning tables, the scheduler does not find a way to use indexes here.

---

9) wildplasser 1: 49.849 ms

 WITH RECURSIVE two AS ( SELECT 1::int AS level , stud_id FROM student_club sc1 WHERE sc1.club_id = 30 UNION SELECT two.level + 1 AS level , sc2.stud_id FROM student_club sc2 JOIN two USING (stud_id) WHERE sc2.club_id = 50 AND two.level = 1 ) SELECT s.stud_id, s.student FROM student s JOIN two USING (studid) WHERE two.level > 1; 

Unusual SQL, decent performance for CTE. Very exotic query plan.
Again, it would be interesting how 9.1 handles this. I am going to upgrade the db cluster used here to 9.1 in the near future. Maybe I'll repeat the whole shaban ...

---

10) wildplasser 2: 36.986 ms

 WITH sc AS ( SELECT stud_id FROM student_club WHERE club_id IN (30,50) GROUP BY stud_id HAVING COUNT(*) > 1 ) SELECT s.* FROM student s JOIN sc USING (stud_id); 

CTE request variant 2). Surprisingly, this can lead to a slightly different tariff plan with the same data. I found a sequential scan on student where an index was used as a subquery.

---

11) ypercube 3: 101.482 ms

Another latest addition is @ypercube. It is amazing how many ways.

 SELECT s.stud_id, s.student FROM student s JOIN student_club sc USING (stud_id) WHERE sc.club_id = 10 -- member in 1st club ... AND NOT EXISTS ( SELECT * FROM (SELECT 14 AS club_id) AS c -- can't be excluded for missing the 2nd WHERE NOT EXISTS ( SELECT * FROM student_club AS d WHERE d.stud_id = sc.stud_id AND d.club_id = c.club_id ) ) 

---

12) erwin 3: 2.377 ms

@ypercube 11) is actually just the reverse of the reverse of this simpler option, which is also still missing. It runs almost as fast as the best cats.

 SELECT s.* FROM student s JOIN student_club x USING (stud_id) WHERE sc.club_id = 10 -- member in 1st club ... AND EXISTS ( -- ... and membership in 2nd exists SELECT * FROM student_club AS y WHERE y.stud_id = s.stud_id AND y.club_id = 14 ) 

13) erwin 4: 2.375 ms

It's hard to believe, but here's another, really new option. I see the potential of more than two members, but he is also among the best cats in just two.

 SELECT s.* FROM student AS s WHERE EXISTS ( SELECT * FROM student_club AS x JOIN student_club AS y USING (stud_id) WHERE x.stud_id = s.stud_id AND x.club_id = 14 AND y.club_id = 10 ) 

Dynamic number of club members

In other words: a different number of filters. This question asked exactly two club memberships. But many use cases need to be prepared for varying amounts.

Detailed discussion in this next later answer:

• Using the same column multiple times in the WHERE clause

Answer 2

 SELECT s.* FROM student s INNER JOIN student_club sc_soccer ON s.id = sc_soccer.student_id INNER JOIN student_club sc_baseball ON s.id = sc_baseball.student_id WHERE sc_baseball.club_id = 50 AND sc_soccer.club_id = 30 

Answer 3

 select * from student where id in (select student_id from student_club where club_id = 30) and id in (select student_id from student_club where club_id = 50) 

Answer 4

If you just want student_id, then:

  Select student_id from student_club where club_id in ( 30, 50 ) group by student_id having count( student_id ) = 2 

If you also need a name from the student, then:

 Select student_id, name from student s where exists( select * from student_club sc where s.student_id = sc.student_id and club_id in ( 30, 50 ) group by sc.student_id having count( sc.student_id ) = 2 ) 

If you have more than two clubs in the club_selection table, then:

 Select student_id, name from student s where exists( select * from student_club sc where s.student_id = sc.student_id and exists( select * from club_selection cs where sc.club_id = cs.club_id ) group by sc.student_id having count( sc.student_id ) = ( select count( * ) from club_selection ) ) 

Answer 5

 SELECT * FROM student WHERE id IN (SELECT student_id FROM student_club WHERE club_id = 30 INTERSECT SELECT student_id FROM student_club WHERE club_id = 50) 

Or a more general solution is easier to extend to n clubs, and this avoids INTERSECT (not available in MySQL) and IN (as the performance of this sucks in MySQL )

 SELECT s.id, s.name FROM student s join student_club sc ON s.id = sc.student_id WHERE sc.club_id IN ( 30, 50 ) GROUP BY s.id, s.name HAVING COUNT(DISTINCT sc.club_id) = 2 

Answer 6

Another CTE. It looks clean, but it will probably generate the same plan as groupby in the regular subquery.

 WITH two AS ( SELECT student_id FROM tmp.student_club WHERE club_id IN (30,50) GROUP BY student_id HAVING COUNT(*) > 1 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) ; 

For those who want to test, a copy of my testdata thingy file:

 DROP SCHEMA tmp CASCADE; CREATE SCHEMA tmp; CREATE TABLE tmp.student ( id INTEGER NOT NULL PRIMARY KEY , sname VARCHAR ); CREATE TABLE tmp.club ( id INTEGER NOT NULL PRIMARY KEY , cname VARCHAR ); CREATE TABLE tmp.student_club ( student_id INTEGER NOT NULL REFERENCES tmp.student(id) , club_id INTEGER NOT NULL REFERENCES tmp.club(id) ); INSERT INTO tmp.student(id) SELECT generate_series(1,1000) ; INSERT INTO tmp.club(id) SELECT generate_series(1,100) ; INSERT INTO tmp.student_club(student_id,club_id) SELECT st.id , cl.id FROM tmp.student st, tmp.club cl ; DELETE FROM tmp.student_club WHERE random() < 0.8 ; UPDATE tmp.student SET sname = 'Student#' || id::text ; UPDATE tmp.club SET cname = 'Soccer' WHERE id = 30; UPDATE tmp.club SET cname = 'Baseball' WHERE id = 50; ALTER TABLE tmp.student_club ADD PRIMARY KEY (student_id,club_id) ; 

Answer 7

Thus, there is more than one way to throw a cat.
I will add two more to make this, well, more complete.

1) GROUP first, VIEW later

Assuming a reasonable data model where (student_id, club_id) unique in student_club . The second version of Martin Smith looks like something similar, but first he joins the groups. This should be faster:

 SELECT s.id, s.name FROM student s JOIN ( SELECT student_id FROM student_club WHERE club_id IN (30, 50) GROUP BY 1 HAVING COUNT(*) > 1 ) sc USING (student_id); 

2) EXISTS

And of course there is a classic EXISTS . Similar to the version of Derek with IN . Simple and fast. (In MySQL, this should be slightly faster than the IN option):

 SELECT s.id, s.name FROM student s WHERE EXISTS (SELECT 1 FROM student_club WHERE student_id = s.student_id AND club_id = 30) AND EXISTS (SELECT 1 FROM student_club WHERE student_id = s.student_id AND club_id = 50); 

Answer 8

Since no one has added this (classic) version:

 SELECT s.* FROM student AS s WHERE NOT EXISTS ( SELECT * FROM club AS c WHERE c.id IN (30, 50) AND NOT EXISTS ( SELECT * FROM student_club AS sc WHERE sc.student_id = s.id AND sc.club_id = c.id ) ) 

or similar:

 SELECT s.* FROM student AS s WHERE NOT EXISTS ( SELECT * FROM ( SELECT 30 AS club_id UNION ALL SELECT 50 ) AS c WHERE NOT EXISTS ( SELECT * FROM student_club AS sc WHERE sc.student_id = s.id AND sc.club_id = c.club_id ) ) 

---

Another attempt with a slightly different approach. Inspired by the article in Explanation Extended: several attributes in the EAV table: GROUP BY and NOT EXISTS :

 SELECT s.* FROM student_club AS sc JOIN student AS s ON s.student_id = sc.student_id WHERE sc.club_id = 50 --- one option here AND NOT EXISTS ( SELECT * FROM ( SELECT 30 AS club_id --- all the rest in here --- as in previous query ) AS c WHERE NOT EXISTS ( SELECT * FROM student_club AS scc WHERE scc.student_id = sc.id AND scc.club_id = c.club_id ) ) 

---

Another approach:

 SELECT s.stud_id FROM student s EXCEPT SELECT stud_id FROM ( SELECT s.stud_id, c.club_id FROM student s CROSS JOIN (VALUES (30),(50)) c (club_id) EXCEPT SELECT stud_id, club_id FROM student_club WHERE club_id IN (30, 50) -- optional. Not needed but may affect performance ) x ; 

Answer 9

 WITH RECURSIVE two AS ( SELECT 1::integer AS level , student_id FROM tmp.student_club sc0 WHERE sc0.club_id = 30 UNION SELECT 1+two.level AS level , sc1.student_id FROM tmp.student_club sc1 JOIN two ON (two.student_id = sc1.student_id) WHERE sc1.club_id = 50 AND two.level=1 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) WHERE two.level> 1 ; 

This seems good enough because CTE-scan avoids the need for two separate subqueries.

There is always a reason for the misuse of recursive queries!

(BTW: mysql doesn't seem to have recursive queries)

Answer 10

Different query plans in query 2) and 10)

I tested db in real life, so the names are different from the catskin list. This is a backup, so nothing has changed during all test runs (except minor changes to directories).

Request 2)

 SELECT a.* FROM ef.adr a JOIN ( SELECT adr_id FROM ef.adratt WHERE att_id IN (10,14) GROUP BY adr_id HAVING COUNT(*) > 1) t using (adr_id); Merge Join (cost=630.10..1248.78 rows=627 width=295) (actual time=13.025..34.726 rows=67 loops=1) Merge Cond: (a.adr_id = adratt.adr_id) -> Index Scan using adr_pkey on adr a (cost=0.00..523.39 rows=5767 width=295) (actual time=0.023..11.308 rows=5356 loops=1) -> Sort (cost=630.10..636.37 rows=627 width=4) (actual time=12.891..13.004 rows=67 loops=1) Sort Key: adratt.adr_id Sort Method: quicksort Memory: 28kB -> HashAggregate (cost=450.87..488.49 rows=627 width=4) (actual time=12.386..12.710 rows=67 loops=1) Filter: (count(*) > 1) -> Bitmap Heap Scan on adratt (cost=97.66..394.81 rows=2803 width=4) (actual time=0.245..5.958 rows=2811 loops=1) Recheck Cond: (att_id = ANY ('{10,14}'::integer[])) -> Bitmap Index Scan on adratt_att_id_idx (cost=0.00..94.86 rows=2803 width=0) (actual time=0.217..0.217 rows=2811 loops=1) Index Cond: (att_id = ANY ('{10,14}'::integer[])) Total runtime: 34.928 ms 

Request 10)

 WITH two AS ( SELECT adr_id FROM ef.adratt WHERE att_id IN (10,14) GROUP BY adr_id HAVING COUNT(*) > 1 ) SELECT a.* FROM ef.adr a JOIN two using (adr_id); Hash Join (cost=1161.52..1261.84 rows=627 width=295) (actual time=36.188..37.269 rows=67 loops=1) Hash Cond: (two.adr_id = a.adr_id) CTE two -> HashAggregate (cost=450.87..488.49 rows=627 width=4) (actual time=13.059..13.447 rows=67 loops=1) Filter: (count(*) > 1) -> Bitmap Heap Scan on adratt (cost=97.66..394.81 rows=2803 width=4) (actual time=0.252..6.252 rows=2811 loops=1) Recheck Cond: (att_id = ANY ('{10,14}'::integer[])) -> Bitmap Index Scan on adratt_att_id_idx (cost=0.00..94.86 rows=2803 width=0) (actual time=0.226..0.226 rows=2811 loops=1) Index Cond: (att_id = ANY ('{10,14}'::integer[])) -> CTE Scan on two (cost=0.00..50.16 rows=627 width=4) (actual time=13.065..13.677 rows=67 loops=1) -> Hash (cost=384.68..384.68 rows=5767 width=295) (actual time=23.097..23.097 rows=5767 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 1153kB -> Seq Scan on adr a (cost=0.00..384.68 rows=5767 width=295) (actual time=0.005..10.955 rows=5767 loops=1) Total runtime: 37.482 ms 

Answer 11

@ erwin-brandstetter Please compare this:

 SELECT s.stud_id, s.name FROM student s, student_club x, student_club y WHERE x.club_id = 30 AND s.stud_id = x.stud_id AND y.club_id = 50 AND s.stud_id = y.stud_id; 

This is like number 6) by @sean, just cleaner, I think.

Answer 12

 -- EXPLAIN ANALYZE WITH two AS ( SELECT c0.student_id FROM tmp.student_club c0 , tmp.student_club c1 WHERE c0.student_id = c1.student_id AND c0.club_id = 30 AND c1.club_id = 50 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) ; 

Request Plan:

  Hash Join (cost=1904.76..1919.09 rows=337 width=15) (actual time=6.937..8.771 rows=324 loops=1) Hash Cond: (two.student_id = st.id) CTE two -> Hash Join (cost=849.97..1645.76 rows=337 width=4) (actual time=4.932..6.488 rows=324 loops=1) Hash Cond: (c1.student_id = c0.student_id) -> Bitmap Heap Scan on student_club c1 (cost=32.76..796.94 rows=1614 width=4) (actual time=0.667..1.835 rows=1646 loops=1) Recheck Cond: (club_id = 50) -> Bitmap Index Scan on sc_club_id_idx (cost=0.00..32.36 rows=1614 width=0) (actual time=0.473..0.473 rows=1646 loops=1) Index Cond: (club_id = 50) -> Hash (cost=797.00..797.00 rows=1617 width=4) (actual time=4.203..4.203 rows=1620 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 57kB -> Bitmap Heap Scan on student_club c0 (cost=32.79..797.00 rows=1617 width=4) (actual time=0.663..3.596 rows=1620 loops=1) Recheck Cond: (club_id = 30) -> Bitmap Index Scan on sc_club_id_idx (cost=0.00..32.38 rows=1617 width=0) (actual time=0.469..0.469 rows=1620 loops=1) Index Cond: (club_id = 30) -> CTE Scan on two (cost=0.00..6.74 rows=337 width=4) (actual time=4.935..6.591 rows=324 loops=1) -> Hash (cost=159.00..159.00 rows=8000 width=15) (actual time=1.979..1.979 rows=8000 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 374kB -> Seq Scan on student st (cost=0.00..159.00 rows=8000 width=15) (actual time=0.093..0.759 rows=8000 loops=1) Total runtime: 8.989 ms (20 rows) 

Thus, it still seems that the SEQ is scanning the student.

Answer 13

 SELECT s.stud_id, s.name FROM student s, ( select x.stud_id from student_club x JOIN student_club y ON x.stud_id = y.stud_id WHERE x.club_id = 30 AND y.club_id = 50 ) tmp_tbl where tmp_tbl.stud_id = s.stud_id ; 

Using the fastest option (Mr. Sean in Mr. Brandstreeter's chart). There may be an option with one connection only with the student_club matrix, which has the right to life. Thus, the longest query will have only two columns for calculation, the idea is to make the query thin.