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

Question

Assuming I have the tables student, club, and student_club:

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

I want to know how to find all students in both the soccer (30) and baseball (50) club.
While this query doesn't work, it's the closest thing 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, which is the fastest way to skin a cat?

The precise cat-skinning environment for this test:

• PostgreSQL 9.0 on Debian Squeeze with decent RAM and settings.
• 6.000 students, 24.000 club memberships (data copied from a similar database with real life data.)
• Slight diversion from the naming schema in the question: student.id is student.stud_id and club.id is club.club_id here.
• I named the queries after their author in this thread, with an index where there are two.
• I ran all queries a couple of times to populate the cache, then I picked the best of 5 with EXPLAIN ANALYZE.

• Relevant indexes (should be the optimum - as long as we lack fore-knowledge which clubs will be queried):

  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 is not required by most queries here.
  Primary keys implement unique indexes automatically In PostgreSQL.
  The last index is to make up for this known shortcoming of multi-column indexes on PostgreSQL:

A multicolumn B-tree index can be used with query conditions that involve any subset of the index's columns, but the index is most efficient when there are constraints on the leading (leftmost) columns.

Results:

Total runtimes 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 perform pretty much the same. 4) and 5) result in the same query plan.

Late Additions:

Fancy SQL, but the performance can't 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, those two perform almost the same. Query plan results in table scans, the planner doesn't find a way to use the 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;

Fancy SQL, decent performance for a CTE. Very exotic query plan.
Again, would be interesting how 9.1 handles this. I am going to upgrade the db cluster used here to 9.1 soon. Maybe I'll rerun the whole shebang ...

---

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 variant of query 2). Surprisingly, it can result in a slightly different query plan with the exact same data. I found a sequential scan on student, where the subquery-variant used the index.

---

11) ypercube 3: 101.482 ms

Another late addition @ypercube. It is positively amazing, how many ways there are.

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's 11) is actually just the mind-twisting reverse approach of this simpler variant, that was also still missing. Performs almost as fast as the top 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

Hard to believe, but here's another, genuinely new variant. I see potential for more than two memberships, but it also ranks among the top cats with 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 memberships

In other words: varying number of filters. This question asked for exactly two club memberships. But many use cases have to prepare for a varying number.

Detailed discussion in this related later answer:

• Using same column multiple times in WHERE clause

Answer 2

-- 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)
    ;

The query 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)

So it still seems to want the seq scan on student.

Answer 3

Different query plans in query 2) and 10)

I tested in a real life db, so the names differ from the catskin list. It's a backup copy, so nothing changed during all test runs (except minor changes to the catalogs).

Query 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

Query 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 4

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 5

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 to perform reasonably well, since the CTE-scan avoids the need for two separate subqueries.

There is always a reason to misuse recursive queries!

(BTW: mysql does not seem to have recursive queries)

Answer 6

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 easier to extend to n clubs and that avoids INTERSECT (not available in MySQL) and IN (as 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