So filtern Sie SQL-Ergebnisse in einer Has-Viele-Durch-Beziehung

Ich war neugierig. Und wie wir alle wissen, hat Neugier den Ruf, Katzen zu töten.

Also, was ist der schnellste Weg, eine Katze zu häuten?

Die Cat-Skinning-Umgebung für diesen Test:

PostgreSQL 9.0 auf Debian Squeeze mit anständigem RAM und Einstellungen.
6.000 Studenten, 24.000 Clubmitgliedschaften (Daten kopiert aus einer ähnlichen Datenbank mit realen Daten.)
Kleine Abweichung vom Namensschema in der Frage:student.id ist student.stud_id und club.id ist club.club_id hier.
Ich habe die Abfragen in diesem Thread nach ihrem Autor benannt.
Ich habe alle Abfragen ein paar Mal ausgeführt, um den Cache zu füllen, und dann mit EXPLAIN ANALYZE die besten von 5 ausgewählt .
Relevante Indizes (sollte das Optimum sein - solange wir nicht wissen, welche Vereine abgefragt werden):

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 wird hier von den meisten Abfragen nicht benötigt.
Primärschlüssel implementieren eindeutige Indizes automatisch in PostgreSQL.
Der letzte Index soll diesen bekannten Mangel von mehrspaltige Indizes auf PostgreSQL:

Ein mehrspaltiger B-Tree-Index kann mit Abfragebedingungen verwendet werden, die eine beliebige Teilmenge der Indexspalten umfassen, aber der Index ist am effizientesten, wenn es Einschränkungen für die führenden (ganz links) Spalten gibt.

Ergebnisse

Gesamtlaufzeiten von 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;

Die letzten drei verhalten sich ziemlich gleich. 4) und 5) ergeben denselben Abfrageplan.

Nachträgliche Ergänzungen

Lust auf SQL, aber die Leistung kann nicht mithalten:

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

Wie erwartet, verhalten sich diese beiden fast gleich. Der Abfrageplan führt zu Tabellenscans, der Planer findet keine Möglichkeit, die Indizes hier zu verwenden.

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;

Schickes SQL, anständige Leistung für einen CTE. Sehr exotischer Abfrageplan.

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-Variante der Abfrage 2). Überraschenderweise kann dies zu einem etwas anderen Abfrageplan mit genau denselben Daten führen. Ich habe einen sequentiellen Scan auf student gefunden , wobei die Unterabfragevariante den Index verwendet.

11) ypercube 3:101,482 ms

Eine weitere späte Ergänzung ypercube. Es ist geradezu erstaunlich, wie viele Möglichkeiten es gibt.

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

ypercubes 11) ist eigentlich nur der verblüffende umgekehrte Ansatz dieser einfacheren Variante, die auch noch fehlte. Führt fast so schnell wie die Top-Katzen.

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

Kaum zu glauben, aber hier ist eine weitere, wirklich neue Variante. Ich sehe Potenzial für mehr als zwei Mitgliedschaften, aber auch mit nur zwei gehört es zu den Top Cats.

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

Dynamische Anzahl von Clubmitgliedschaften

Mit anderen Worten:unterschiedliche Anzahl von Filtern. Bei dieser Frage waren genau zwei gefragt Vereinsmitgliedschaften. Doch viele Use Cases müssen sich auf unterschiedlich viele einstellen. Siehe:

Gleiche verwenden Spalte mehrmals in der WHERE-Klausel