Come filtrare i risultati SQL in una relazione ha molti-attraverso

Ero curioso. E come tutti sappiamo, la curiosità ha la reputazione di uccidere i gatti.

Quindi, qual è il modo più veloce per scuoiare un gatto?

L'ambiente di scuoiatura del gatto per questo test:

PostgreSQL 9.0 su Debian Squeeze con RAM e impostazioni decenti.
6.000 studenti, 24.000 soci a club (dati copiati da un database simile con dati di vita reale.)
Leggera deviazione dallo schema di denominazione nella domanda:student.id è student.stud_id e club.id è club.club_id qui.
Ho chiamato le query in base al loro autore in questo thread.
Ho eseguito tutte le query un paio di volte per popolare la cache, quindi ho scelto la migliore delle 5 con EXPLAIN ANALYZE .
Indici pertinenti (dovrebbero essere l'ideale, a patto che non ci sia la conoscenza preliminare di quali club verranno interrogati):

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 non è richiesto dalla maggior parte delle query qui.
Le chiavi primarie implementano automaticamente indici univoci in PostgreSQL.
L'ultimo indice serve a compensare questa nota lacuna di indici a più colonne su PostgreSQL:

Un indice B-tree multicolonna può essere utilizzato con condizioni di query che coinvolgono qualsiasi sottoinsieme delle colonne dell'indice, ma l'indice è più efficiente quando ci sono vincoli sulle colonne iniziali (più a sinistra).

Risultati

Runtime totali da 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) Martino 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;

Gli ultimi tre si comportano più o meno allo stesso modo. 4) e 5) danno come risultato lo stesso piano di query.

Aggiunte in ritardo

Fancy SQL, ma le prestazioni non possono tenere il passo:

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

Come previsto, quei due si comportano quasi allo stesso modo. Il piano di query genera scansioni di tabelle, il pianificatore non trova un modo per utilizzare gli indici qui.

9) jolly 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, prestazioni decenti per un CTE. Piano di query molto esotico.

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

variante CTE della domanda 2). Sorprendentemente, può risultare in un piano di query leggermente diverso con gli stessi identici dati. Ho trovato una scansione sequenziale su student , dove la variante di sottoquery utilizzava l'indice.

11) ypercube 3:101.482 ms

Un altro ipercubo ad aggiunta tardiva. È davvero sorprendente, quanti modi ci sono.

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) è in realtà solo l'approccio inverso da capogiro di questa variante più semplice, anch'essa mancante. Si comporta quasi alla stessa velocità dei migliori gatti.

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

Difficile da credere, ma ecco un'altra variante davvero nuova. Vedo il potenziale per più di due abbonamenti, ma si colloca anche tra i migliori gatti con solo due.

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

Numero dinamico di iscritti al club

In altre parole:numero variabile di filtri. Questa domanda ne richiedeva esattamente due abbonamenti a club. Ma molti casi d'uso devono prepararsi per un numero variabile. Vedi:

Utilizzare lo stesso colonna più volte nella clausola WHERE