Sådan filtreres SQL-resultater i en har-mange-gennem-relation

Jeg var nysgerrig. Og som vi alle ved, har nysgerrighed ry for at dræbe katte.

Så hvad er den hurtigste måde at flå en kat på?

Kattehudmiljøet for denne test:

PostgreSQL 9.0 på Debian Squeeze med anstændig RAM og indstillinger.
6.000 studerende, 24.000 klubmedlemskaber (data kopieret fra en lignende database med virkelige data.)
Lille afvigelse fra navngivningsskemaet i spørgsmålet:student.id er student.stud_id og club.id er club.club_id her.
Jeg opkaldte forespørgslerne efter deres forfatter i denne tråd.
Jeg kørte alle forespørgsler et par gange for at udfylde cachen, derefter valgte jeg det bedste af 5 med EXPLAIN ANALYZE .
Relevante indekser (bør være det optimale - så længe vi mangler forhåndsviden om, hvilke klubber der vil blive forespurgt):

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 er ikke påkrævet af de fleste forespørgsler her.
Primære nøgler implementerer unikke indekser automatisk i PostgreSQL.
Det sidste indeks skal kompensere for denne kendte mangel ved indekser med flere kolonner på PostgreSQL:

Et B-træindeks med flere kolonner kan bruges med forespørgselsbetingelser, der involverer en hvilken som helst delmængde af indeksets kolonner, men indekset er mest effektivt, når der er begrænsninger på de førende (længst til venstre) kolonner.

Resultater

Samlede kørselstider fra 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;

De sidste tre præsterer stort set det samme. 4) og 5) resulterer i den samme forespørgselsplan.

Sene tilføjelser

Fancy SQL, men ydeevnen kan ikke følge med:

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

Som forventet præsterer de to næsten det samme. Forespørgselsplan resulterer i tabelscanninger, planlæggeren finder ikke en måde at bruge indekserne her.

9) vilde steder 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, anstændig ydeevne til en CTE. Meget eksotisk forespørgselsplan.

10) wildplaces 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 af forespørgsel 2). Overraskende nok kan det resultere i en lidt anderledes forespørgselsplan med nøjagtig de samme data. Jeg fandt en sekventiel scanning på student , hvor underforespørgselsvarianten brugte indekset.

11) ypercube 3:101.482 ms

Endnu en sen tilføjelse ypercube. Det er positivt, hvor mange måder der er.

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) er faktisk bare den tankevridende omvendte tilgang af denne simplere variant, som også stadig manglede. Præsterer næsten lige så hurtigt som topkattene.

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

Svært at tro, men her er en anden, virkelig ny variant. Jeg ser potentiale for mere end to medlemskaber, men den er også blandt de bedste katte med kun to.

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

Dynamisk antal klubmedlemskaber

Med andre ord:varierende antal filtre. Dette spørgsmål stillede præcis to klubmedlemskaber. Men mange use cases skal forberede sig på et varierende antal. Se:

Bruger samme kolonne flere gange i WHERE-sætning