Cómo filtrar los resultados de SQL en una relación de varios tipos

Estaba curioso. Y como todos sabemos, la curiosidad tiene fama de matar gatos.

Entonces, ¿cuál es la forma más rápida de despellejar a un gato?

El entorno despellejador de esta prueba:

PostgreSQL 9.0 en Debian Squeeze con RAM y configuraciones decentes.
6.000 estudiantes, 24.000 miembros del club (datos copiados de una base de datos similar con datos de la vida real).
Leve desviación del esquema de nombres en la pregunta:student.id es student.stud_id y club.id es club.club_id aquí.
Nombré las consultas por su autor en este hilo.
Ejecuté todas las consultas un par de veces para llenar el caché, luego elegí la mejor de 5 con EXPLAIN ANALYZE .
Índices relevantes (debería ser el óptimo, siempre que no sepamos de antemano qué clubes se consultarán):

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 no es requerido por la mayoría de las consultas aquí.
Las claves primarias implementan índices únicos automáticamente en PostgreSQL.
El último índice es para compensar esta deficiencia conocida de índices de varias columnas en PostgreSQL:

Se puede usar un índice de árbol B de varias columnas con condiciones de consulta que involucren cualquier subconjunto de las columnas del índice, pero el índice es más eficiente cuando hay restricciones en las columnas principales (más a la izquierda).

Resultados

Tiempos de ejecución totales de EXPLAIN ANALYZE .

1) Martín 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.217ms

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) Martín 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.181ms

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.043ms

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;

Los tres últimos funcionan más o menos igual. 4) y 5) dan como resultado el mismo plan de consulta.

Adiciones tardías

Fancy SQL, pero el rendimiento no puede mantenerse:

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

Como era de esperar, esos dos funcionan casi igual. El plan de consulta da como resultado escaneos de tablas, el planificador no encuentra una manera de usar los índices aquí.

9) salvaje 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, rendimiento decente para un CTE. Plan de consulta muy exótico.

10) salvaje 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 de la consulta 2). Sorprendentemente, puede resultar en un plan de consulta ligeramente diferente con exactamente los mismos datos. Encontré un escaneo secuencial en student , donde la variante de subconsulta usó el índice.

11) ypercubo 3:101.482 ms

Otro ypercubo de incorporación tardía. Es positivamente sorprendente cuántas maneras hay.

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.377ms

ypercube's 11) es en realidad solo el enfoque inverso alucinante de esta variante más simple, que también faltaba. Funciona casi tan rápido como los mejores gatos.

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.375ms

Difícil de creer, pero aquí hay otra variante genuinamente nueva. Veo potencial para más de dos membresías, pero también se ubica entre los mejores gatos con solo dos.

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

Número dinámico de miembros del club

En otras palabras:número variable de filtros. Esta pregunta pedía exactamente dos membresías de clubes. Pero muchos casos de uso tienen que prepararse para un número variable. Ver:

Usando el mismo columna varias veces en la cláusula WHERE