Como filtrar resultados de SQL em uma relação de muitos-através

Supondo que eu tenha as tabelas student , club e student_club :

 student { id name } club { id name } student_club { student_id club_id } 

Eu quero saber como encontrar todos os alunos no clube de futebol (30) e de beisebol (50).
Enquanto esta consulta não funciona, é a coisa mais próxima que tenho até agora:

 SELECT student.* FROM student INNER JOIN student_club sc ON student.id = sc.student_id LEFT JOIN club c ON c.id = sc.club_id WHERE c.id = 30 AND c.id = 50 

Eu estava curioso. E como todos sabemos, a curiosidade tem a reputação de matar gatos.

Então, qual é o caminho mais rápido para esfolar um gato?

O ambiente preciso de esfola de gato para este teste:

  • PostgreSQL 9.0 no Debian Squeeze com RAM decente e configurações.
  • 6.000 alunos, 24.000 associações de clubes (dados copiados de um database semelhante com dados da vida real).
  • Desvio leve do esquema de nomeação na questão: club.id é club.id e club.id é club.club_id aqui.
  • Eu nomeei as consultas após seu autor neste segmento, com um índice onde existem dois.
  • Eu executei todas as consultas algumas vezes para preencher o cache, depois escolhi o melhor de 5 com EXPLAIN ANALYZE.
  • Índices relevantes (devem ser os ótimos – contanto que nos falte conhecimento prévio sobre quais clubes serão questionados):

     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 não é exigido pela maioria das consultas aqui.
    As chaves primárias implementam índices exclusivos automaticamente no PostgreSQL.
    O último índice é para compensar essa falha conhecida de índices multi-colunas no PostgreSQL:

Um índice B-tree de várias colunas pode ser usado com condições de consulta que envolvam qualquer subconjunto das colunas do índice, mas o índice é mais eficiente quando há restrições nas colunas iniciais (mais à esquerda).

Resultados:

Total de tempos de execução de 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; 

Os últimos três executam praticamente o mesmo. 4) e 5) resultam no mesmo plano de consulta.

Adições tardias:

Fancy SQL, mas o desempenho não pode acompanhar.

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

Como esperado, os dois executam quase o mesmo. O plano de consulta resulta em varreduras de tabela, o planejador não encontra uma maneira de usar os índices aqui.


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; 

Fancy SQL, desempenho decente para um CTE. Plano de consulta muito exótico.
Novamente, seria interessante como o 9.1 lida com isso. Eu vou atualizar o cluster do database usado aqui para 9.1 em breve. Talvez eu execute novamente a coisa toda …


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

Variante CTE da consulta 2). Surpreendentemente, isso pode resultar em um plano de consulta ligeiramente diferente com os mesmos dados exatos. Eu encontrei uma varredura sequencial no student , onde a variante de subconsulta usava o índice.


11) ypercube 3: 101,482 ms

Outra adição tardia @ypercube. É positivamente incrível, quantas maneiras existem.

 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

O 11 do ypercube é, na verdade, apenas a abordagem reversa de distorção mental desta variante mais simples, que também estava faltando. Executa quase tão rápido quanto os melhores 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.375 ms

Difícil de acreditar, mas aqui está outra variante genuinamente nova. Eu vejo potencial para mais de dois membros, mas também está entre os top cats com apenas dois.

 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 dynamic de afiliações no clube

Em outras palavras: número variável de filtros. Esta pergunta pediu exatamente dois membros do clube. Mas muitos casos de uso precisam se preparar para um número variável.

Discussão detalhada nesta resposta posterior relacionada:

  • Usando a mesma coluna várias vezes na cláusula WHERE
 SELECT s.* FROM student s INNER JOIN student_club sc_soccer ON s.id = sc_soccer.student_id INNER JOIN student_club sc_baseball ON s.id = sc_baseball.student_id WHERE sc_baseball.club_id = 50 AND sc_soccer.club_id = 30 
 select * from student where id in (select student_id from student_club where club_id = 30) and id in (select student_id from student_club where club_id = 50) 

Se você quer apenas student_id então:

  Select student_id from student_club where club_id in ( 30, 50 ) group by student_id having count( student_id ) = 2 

Se você também precisar do nome do aluno, então:

 Select student_id, name from student s where exists( select * from student_club sc where s.student_id = sc.student_id and club_id in ( 30, 50 ) group by sc.student_id having count( sc.student_id ) = 2 ) 

Se você tiver mais de dois clubes em uma tabela club_selection, então:

 Select student_id, name from student s where exists( select * from student_club sc where s.student_id = sc.student_id and exists( select * from club_selection cs where sc.club_id = cs.club_id ) group by sc.student_id having count( sc.student_id ) = ( select count( * ) from club_selection ) ) 
 SELECT * FROM student WHERE id IN (SELECT student_id FROM student_club WHERE club_id = 30 INTERSECT SELECT student_id FROM student_club WHERE club_id = 50) 

Ou uma solução mais geral mais fácil de estender a n clubes e que evita INTERSECT (não disponível no MySQL) e IN (como o desempenho disso é uma porcaria no MySQL )

 SELECT s.id, s.name FROM student s join student_club sc ON s.id = sc.student_id WHERE sc.club_id IN ( 30, 50 ) GROUP BY s.id, s.name HAVING COUNT(DISTINCT sc.club_id) = 2 

Outro CTE. Parece limpo, mas provavelmente irá gerar o mesmo plano que um groupby em uma subconsulta normal.

 WITH two AS ( SELECT student_id FROM tmp.student_club WHERE club_id IN (30,50) GROUP BY student_id HAVING COUNT(*) > 1 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) ; 

Para aqueles que querem testar, uma cópia da minha geração testdata thingy:

 DROP SCHEMA tmp CASCADE; CREATE SCHEMA tmp; CREATE TABLE tmp.student ( id INTEGER NOT NULL PRIMARY KEY , sname VARCHAR ); CREATE TABLE tmp.club ( id INTEGER NOT NULL PRIMARY KEY , cname VARCHAR ); CREATE TABLE tmp.student_club ( student_id INTEGER NOT NULL REFERENCES tmp.student(id) , club_id INTEGER NOT NULL REFERENCES tmp.club(id) ); INSERT INTO tmp.student(id) SELECT generate_series(1,1000) ; INSERT INTO tmp.club(id) SELECT generate_series(1,100) ; INSERT INTO tmp.student_club(student_id,club_id) SELECT st.id , cl.id FROM tmp.student st, tmp.club cl ; DELETE FROM tmp.student_club WHERE random() < 0.8 ; UPDATE tmp.student SET sname = 'Student#' || id::text ; UPDATE tmp.club SET cname = 'Soccer' WHERE id = 30; UPDATE tmp.club SET cname = 'Baseball' WHERE id = 50; ALTER TABLE tmp.student_club ADD PRIMARY KEY (student_id,club_id) ; 

Portanto, há mais de uma maneira de esfolar um gato .
Eu vou adicionar mais dois para torná-lo, bem, mais completo.

1) GRUPO primeiro, JOIN depois

Assumindo um modelo de dados sane onde (student_id, club_id) é exclusivo em student_club . A segunda versão de Martin Smith é parecida com algo semelhante, mas ele se junta primeiro, depois. Isso deve ser mais rápido:

 SELECT s.id, s.name FROM student s JOIN ( SELECT student_id FROM student_club WHERE club_id IN (30, 50) GROUP BY 1 HAVING COUNT(*) > 1 ) sc USING (student_id); 

2) EXISTE

E, claro, há o clássico EXISTS . Semelhante à variante de Derek com IN . Simples e rápido (No MySQL, isso deve ser um pouco mais rápido que a variante com IN ):

 SELECT s.id, s.name FROM student s WHERE EXISTS (SELECT 1 FROM student_club WHERE student_id = s.student_id AND club_id = 30) AND EXISTS (SELECT 1 FROM student_club WHERE student_id = s.student_id AND club_id = 50); 

Como ninguém adicionou esta versão (clássica):

 SELECT s.* FROM student AS s WHERE NOT EXISTS ( SELECT * FROM club AS c WHERE c.id IN (30, 50) AND NOT EXISTS ( SELECT * FROM student_club AS sc WHERE sc.student_id = s.id AND sc.club_id = c.id ) ) 

ou similar:

 SELECT s.* 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.student_id = s.id AND sc.club_id = c.club_id ) ) 

Mais uma tentativa com uma abordagem ligeiramente diferente. Inspirado por um artigo no Explain Extended: Vários atributos em uma tabela EAV: GROUP BY vs. NOT EXISTS :

 SELECT s.* FROM student_club AS sc JOIN student AS s ON s.student_id = sc.student_id WHERE sc.club_id = 50 --- one option here AND NOT EXISTS ( SELECT * FROM ( SELECT 30 AS club_id --- all the rest in here --- as in previous query ) AS c WHERE NOT EXISTS ( SELECT * FROM student_club AS scc WHERE scc.student_id = sc.id AND scc.club_id = c.club_id ) ) 

Outra abordagem:

 SELECT s.stud_id FROM student s EXCEPT SELECT stud_id FROM ( SELECT s.stud_id, c.club_id FROM student s CROSS JOIN (VALUES (30),(50)) c (club_id) EXCEPT SELECT stud_id, club_id FROM student_club WHERE club_id IN (30, 50) -- optional. Not needed but may affect performance ) x ; 
 WITH RECURSIVE two AS ( SELECT 1::integer AS level , student_id FROM tmp.student_club sc0 WHERE sc0.club_id = 30 UNION SELECT 1+two.level AS level , sc1.student_id FROM tmp.student_club sc1 JOIN two ON (two.student_id = sc1.student_id) WHERE sc1.club_id = 50 AND two.level=1 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) WHERE two.level> 1 ; 

Isso parece funcionar razoavelmente bem, já que o CTE-scan evita a necessidade de duas subconsultas separadas.

Há sempre uma razão para usar mal consultas recursivas!

(BTW: o mysql não parece ter consultas recursivas)

Planos de consulta diferentes na consulta 2) e 10)

Eu testei em um db da vida real, então os nomes diferem da lista de catskin. É uma cópia de backup, então nada foi alterado durante todas as execuções de teste (exceto pequenas alterações nos catálogos).

Consulta 2)

 SELECT a.* FROM ef.adr a JOIN ( SELECT adr_id FROM ef.adratt WHERE att_id IN (10,14) GROUP BY adr_id HAVING COUNT(*) > 1) t using (adr_id); Merge Join (cost=630.10..1248.78 rows=627 width=295) (actual time=13.025..34.726 rows=67 loops=1) Merge Cond: (a.adr_id = adratt.adr_id) -> Index Scan using adr_pkey on adr a (cost=0.00..523.39 rows=5767 width=295) (actual time=0.023..11.308 rows=5356 loops=1) -> Sort (cost=630.10..636.37 rows=627 width=4) (actual time=12.891..13.004 rows=67 loops=1) Sort Key: adratt.adr_id Sort Method: quicksort Memory: 28kB -> HashAggregate (cost=450.87..488.49 rows=627 width=4) (actual time=12.386..12.710 rows=67 loops=1) Filter: (count(*) > 1) -> Bitmap Heap Scan on adratt (cost=97.66..394.81 rows=2803 width=4) (actual time=0.245..5.958 rows=2811 loops=1) Recheck Cond: (att_id = ANY ('{10,14}'::integer[])) -> Bitmap Index Scan on adratt_att_id_idx (cost=0.00..94.86 rows=2803 width=0) (actual time=0.217..0.217 rows=2811 loops=1) Index Cond: (att_id = ANY ('{10,14}'::integer[])) Total runtime: 34.928 ms 

Consulta 10)

 WITH two AS ( SELECT adr_id FROM ef.adratt WHERE att_id IN (10,14) GROUP BY adr_id HAVING COUNT(*) > 1 ) SELECT a.* FROM ef.adr a JOIN two using (adr_id); Hash Join (cost=1161.52..1261.84 rows=627 width=295) (actual time=36.188..37.269 rows=67 loops=1) Hash Cond: (two.adr_id = a.adr_id) CTE two -> HashAggregate (cost=450.87..488.49 rows=627 width=4) (actual time=13.059..13.447 rows=67 loops=1) Filter: (count(*) > 1) -> Bitmap Heap Scan on adratt (cost=97.66..394.81 rows=2803 width=4) (actual time=0.252..6.252 rows=2811 loops=1) Recheck Cond: (att_id = ANY ('{10,14}'::integer[])) -> Bitmap Index Scan on adratt_att_id_idx (cost=0.00..94.86 rows=2803 width=0) (actual time=0.226..0.226 rows=2811 loops=1) Index Cond: (att_id = ANY ('{10,14}'::integer[])) -> CTE Scan on two (cost=0.00..50.16 rows=627 width=4) (actual time=13.065..13.677 rows=67 loops=1) -> Hash (cost=384.68..384.68 rows=5767 width=295) (actual time=23.097..23.097 rows=5767 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 1153kB -> Seq Scan on adr a (cost=0.00..384.68 rows=5767 width=295) (actual time=0.005..10.955 rows=5767 loops=1) Total runtime: 37.482 ms 

@ erwin-brandstetter Por favor, compare isso:

 SELECT s.stud_id, s.name FROM student s, student_club x, student_club y WHERE x.club_id = 30 AND s.stud_id = x.stud_id AND y.club_id = 50 AND s.stud_id = y.stud_id; 

É como o número 6) por @sean, apenas mais limpo, eu acho.

 -- EXPLAIN ANALYZE WITH two AS ( SELECT c0.student_id FROM tmp.student_club c0 , tmp.student_club c1 WHERE c0.student_id = c1.student_id AND c0.club_id = 30 AND c1.club_id = 50 ) SELECT st.* FROM tmp.student st JOIN two ON (two.student_id=st.id) ; 

O plano de consulta:

  Hash Join (cost=1904.76..1919.09 rows=337 width=15) (actual time=6.937..8.771 rows=324 loops=1) Hash Cond: (two.student_id = st.id) CTE two -> Hash Join (cost=849.97..1645.76 rows=337 width=4) (actual time=4.932..6.488 rows=324 loops=1) Hash Cond: (c1.student_id = c0.student_id) -> Bitmap Heap Scan on student_club c1 (cost=32.76..796.94 rows=1614 width=4) (actual time=0.667..1.835 rows=1646 loops=1) Recheck Cond: (club_id = 50) -> Bitmap Index Scan on sc_club_id_idx (cost=0.00..32.36 rows=1614 width=0) (actual time=0.473..0.473 rows=1646 loops=1) Index Cond: (club_id = 50) -> Hash (cost=797.00..797.00 rows=1617 width=4) (actual time=4.203..4.203 rows=1620 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 57kB -> Bitmap Heap Scan on student_club c0 (cost=32.79..797.00 rows=1617 width=4) (actual time=0.663..3.596 rows=1620 loops=1) Recheck Cond: (club_id = 30) -> Bitmap Index Scan on sc_club_id_idx (cost=0.00..32.38 rows=1617 width=0) (actual time=0.469..0.469 rows=1620 loops=1) Index Cond: (club_id = 30) -> CTE Scan on two (cost=0.00..6.74 rows=337 width=4) (actual time=4.935..6.591 rows=324 loops=1) -> Hash (cost=159.00..159.00 rows=8000 width=15) (actual time=1.979..1.979 rows=8000 loops=1) Buckets: 1024 Batches: 1 Memory Usage: 374kB -> Seq Scan on student st (cost=0.00..159.00 rows=8000 width=15) (actual time=0.093..0.759 rows=8000 loops=1) Total runtime: 8.989 ms (20 rows) 

Por isso, ainda parece querer o scan seq no aluno.

 SELECT s.stud_id, s.name FROM student s, ( select x.stud_id from student_club x JOIN student_club y ON x.stud_id = y.stud_id WHERE x.club_id = 30 AND y.club_id = 50 ) tmp_tbl where tmp_tbl.stud_id = s.stud_id ; 

Uso da variante mais rápida (Sr. Sean no gráfico do Sr. Brandstetter). Pode ser variante com apenas uma junit para que somente a matriz student_club tenha o direito de viver. Assim, a consulta mais longa terá apenas duas colunas para calcular, a idéia é tornar a consulta mais fina.