Как фильтровать результаты SQL в отношении has-many-through

Предполагая, что у меня есть таблицы student , club и student_club :

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

Я хочу знать, как найти всех учеников как в футболе (30), так и в бейсбольном (50) клубе.
Хотя этот запрос не работает, это самое близкое, что у меня есть до сих пор:

 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 

    Мне было любопытно. И, как мы все знаем, у любопытства есть репутация убийства кошек.

    Итак, что является самым быстрым способом кошки кошки?

    Точная скин-скин-среда для этого теста:

    • PostgreSQL 9.0 на Debian Squeeze с приличной памятью и настройками.
    • 6.000 студентов, 24 000 членов клуба (данные скопированы из аналогичной базы данных с данными реальной жизни.)
    • Незначительное отклонение от схемы именования в вопросе: student.id is student.stud_id а club.idclub.club_id .
    • Я назвал запросы после их автора в этом потоке с индексом, где есть два.
    • Несколько раз я запускал все запросы, чтобы заполнить кеш, а затем я выбрал лучшее из 5 с EXPLAIN ANALYZE.
    • Соответствующие индексы (должны быть оптимальными – пока нам не хватает знаний о том, какие клубы будут запрашиваться):

       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 .
      Первичные ключи автоматически реализуют уникальные индексы. В PostgreSQL.
      Последний индекс состоит в том, чтобы компенсировать этот известный недостаток многоколоночных индексов на PostgreSQL:

    Многоколоночный индекс B-дерева может использоваться с условиями запроса, которые включают любое подмножество столбцов индекса, но индекс наиболее эффективен, когда есть ограничения на ведущие (крайние слева) столбцы.

    Результаты:

    Общее время выполнения от EXPLAIN ANALYZE.

    1) Мартин 2: 44,594 мс

     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 мс

     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) Мартин 1: 31,735 мс

     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) Дерек: 2.287 мс

     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 мс

     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) Шон: 2.043 мс

     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; 

    Последние три выполняют почти то же самое. 4) и 5) приводит к такому же тарифному плану.

    Поздние дополнения:

    Необычный SQL, но производительность не может идти в ногу.

    7) ypercube 1: 148,649 мс

     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 мс

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

    Как и ожидалось, эти два выполняют почти то же самое. В результате запроса в табличном сканировании планировщик не находит способ использовать индексы здесь.


    9) wildplasser 1: 49.849 мс

     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; 

    Необычный SQL, достойная производительность для CTE. Очень экзотический план запросов.
    Опять же, было бы интересно, как 9.1 справляется с этим. Я собираюсь обновить кластер db, используемый здесь, до 9.1 в ближайшее время. Может быть, я повторю весь шэбэн …


    10) wildplasser 2: 36,986 мс

     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 вариант запроса 2). Удивительно, но это может привести к несколько другому тарифному плану с теми же данными. Я нашел последовательное сканирование на student , где в качестве подзапроса использовался индекс.


    11) ypercube 3: 101,482 мс

    Еще одно последнее дополнение @ypercube. Это потрясающе удивительно, как много способов.

     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 мс

    @ ypercube's 11) на самом деле просто обратный обратный подход этого более простого варианта, который также все еще отсутствует. Выполняется почти так же быстро, как и лучшие кошки.

     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 мс

    Трудно поверить, но вот еще один, действительно новый вариант. Я вижу потенциал более чем двух членов, но он также входит в число лучших кошек всего за два.

     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 ) 

    Динамическое количество членов клуба

    Другими словами: различное количество фильтров. Этот вопрос задал ровно два членства в клубе. Но многие варианты использования должны быть подготовлены для различного количества.

    Подробное обсуждение этого более позднего ответа:

    • Использование одного и того же столбца несколько раз в предложении 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) 

    Если вы просто хотите student_id, то:

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

    Если вам также нужно имя от ученика, тогда:

     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 ) 

    Если у вас более двух клубов в таблице club_selection, тогда:

     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) 

    Или более общее решение проще распространить на n клубов и избегать INTERSECT (недоступно в MySQL) и IN (как производительность этого отстой в 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 

    Другой CTE. Он выглядит чистым, но он, вероятно, будет генерировать тот же план, что и groupby в обычном подзапросе.

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

    Для тех, кто хочет протестировать, копия моего файла 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) ; 

    Таким образом, есть более чем один способ кошки кошки .
    Я добавлю еще два, чтобы сделать это, ну, более полным.

    1) ГРУППА сначала, ПРИСОЕДИНЯЙТЕСЬ позже

    Предполагая разумную модель данных, где (student_id, club_id) уникально в student_club . Вторая версия Мартина Смита похожа на несколько схожую, но сначала он присоединяется к группам. Это должно быть быстрее:

     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) СУЩЕСТВУЕТ

    И, конечно же, есть классические EXISTS . По аналогии с вариантом Дерека с IN . Просто и быстро. (В MySQL это должно быть немного быстрее, чем вариант с 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); 

    Поскольку никто не добавил эту (классическую) версию:

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

    или похожие:

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

    Еще одна попытка с немного другим подходом. Вдохновленный статьей в Explain Extended: несколько атрибутов в таблице EAV: GROUP BY или 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 ) ) 

    Другой подход:

     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 ; 

    Это, по-видимому, выполняется достаточно хорошо, поскольку CTE-сканирование устраняет необходимость в двух отдельных подзапросах.

    Всегда есть причина злоупотреблять рекурсивными запросами!

    (Кстати: mysql, похоже, не имеет рекурсивных запросов)

    Различные планы запросов в запросе 2) и 10)

    Я тестировал в реальной жизни db, поэтому имена отличаются от списка catskin. Это резервная копия, поэтому во время всех тестовых прогонов ничего не изменилось (кроме незначительных изменений в каталогах).

    Запрос 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 

    Запрос 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 Пожалуйста, сравните это:

     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; 

    Это как номер 6) by @sean, просто чище, я думаю.

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

    План запроса:

      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) 

    Таким образом, по-прежнему кажется, что SEQ сканирует студент.

     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 ; 

    Использование самого быстрого варианта (г-н Шон в диаграмме г-на Брандстретера). Может быть вариант с одним соединением только с матрицей student_club, имеющей право на жизнь. Таким образом, самый длинный запрос будет иметь только два столбца для расчета, идея состоит в том, чтобы сделать запрос тонким.