Jak filtrować wyniki SQL w relacji ma wiele przejść?

Byłem ciekawy. A jak wszyscy wiemy, ciekawość ma reputację zabijania kotów.

Jaki jest najszybszy sposób na oskórowanie kota?

Środowisko skórowania kota dla tego testu:

PostgreSQL 9.0 na Debianie Squeeze z przyzwoitą pamięcią RAM i ustawieniami.
6000 studentów, 24 000 członkostwa w klubach (dane skopiowane z podobnej bazy danych z rzeczywistymi danymi).
Niewielkie odejście od schematu nazewnictwa w pytaniu:student.id to student.stud_id i club.id to club.club_id tutaj.
W tym wątku nazwałem zapytania imieniem ich autora.
Kilka razy uruchomiłem wszystkie zapytania, aby wypełnić pamięć podręczną, a następnie wybrałem najlepszy z 5 za pomocą EXPLAIN ANALYZE .
Odpowiednie indeksy (powinny być optymalne – o ile nie wiemy, które kluby będą przeszukiwane):

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 nie jest wymagane przez większość zapytań tutaj.
Klucze podstawowe automatycznie implementują unikalne indeksy w PostgreSQL.
Ostatni indeks ma na celu uzupełnienie tego znanego niedociągnięcia indeksy wielokolumnowe w PostgreSQL:

Wielokolumnowy indeks B-drzewa może być używany z warunkami zapytania, które obejmują dowolny podzbiór kolumn indeksu, ale indeks jest najbardziej wydajny, gdy istnieją ograniczenia dotyczące kolumn wiodących (najbardziej po lewej).

Wyniki

Całkowite czasy działania z EXPLAIN ANALYZE .

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

Ostatnie trzy zachowują się prawie tak samo. 4) i 5) dają ten sam plan zapytania.

Późne dodatki

Fantazyjny SQL, ale wydajność nie nadąża:

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

Zgodnie z oczekiwaniami te dwa działają prawie tak samo. Plan zapytań skutkuje skanowaniem tabel, planista nie znajduje tutaj sposobu na wykorzystanie indeksów.

9) dziki plasser 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;

Fantazyjny SQL, przyzwoita wydajność jak na CTE. Bardzo egzotyczny plan zapytań.

10) dziki plasser 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);

Wariant CTE zapytania 2). Co zaskakujące, może to skutkować nieco innym planem zapytań z dokładnie tymi samymi danymi. Znalazłem skan sekwencyjny student , gdzie pododmiana zapytania używa indeksu.

11) ypercube 3:101,482 ms

Kolejny późny dodatek ypercube. To naprawdę niesamowite, ile jest sposobów.

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) jest w rzeczywistości po prostu odwrotnym podejściem do tego prostszego wariantu, którego wciąż brakowało. Działa prawie tak szybko, jak najlepsze koty.

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

Trudno w to uwierzyć, ale oto kolejny, naprawdę nowy wariant. Widzę potencjał dla więcej niż dwóch członków, ale plasuje się również wśród najlepszych kotów z zaledwie dwoma.

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

Dynamiczna liczba członkostwa w klubach

Innymi słowy:różna liczba filtrów. To pytanie dotyczyło dokładnie dwóch członkostwa w klubach. Ale wiele przypadków użycia musi być przygotowanych na inną liczbę. Zobacz:

Korzystanie z tego samego kolumna wielokrotnie w klauzuli WHERE