How to filter SQL results in a has-many-through relation
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 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.idisstudent.stud_idandclub.idisclub.club_idhere. - I named the queries after their author in this thread.
- 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 thatinvolve any subset of the index's columns, but the index is mostefficient 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.nameFROM student sJOIN student_club sc USING (stud_id)WHERE sc.club_id IN (30, 50)GROUP BY 1,2HAVING COUNT(*) > 1;2) Erwin 1: 33.217 ms
SELECT s.stud_id, s.nameFROM student sJOIN ( 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.nameFROM student sWHERE 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.nameFROM student sWHERE 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.nameFROM student sWHERE 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.nameFROM student sJOIN student_club x ON s.stud_id = x.stud_idJOIN student_club y ON s.stud_id = y.stud_idWHERE x.club_id = 30AND 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.nameFROM student AS sWHERE 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.nameFROM student AS sWHERE 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.studentFROM student sJOIN two USING (studid)WHERE two.level > 1;Fancy SQL, decent performance for a CTE. Very exotic query plan.
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 sJOIN 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.studentFROM student sJOIN 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 sJOIN 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 sWHERE 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. See:
SELECT s.*FROM student sINNER JOIN student_club sc_soccer ON s.id = sc_soccer.student_idINNER JOIN student_club sc_baseball ON s.id = sc_baseball.student_idWHERE sc_baseball.club_id = 50 AND sc_soccer.club_id = 30
select *from studentwhere 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)