Как отфильтровать результаты SQL в сквозном отношении
Если у меня есть таблицы 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
13 ответов
Мне было любопытно. И как мы все знаем, любопытство имеет репутацию убийства кошек.
Итак, какой самый быстрый способ снять кожу с кошки?
Точная среда для кошачьей шкуры для этого теста:
- PostgreSQL 9.0 на Debian Squeeze с достойной оперативной памятью и настройками.
- 6.000 студентов, 24.000 членов клуба (данные скопированы из аналогичной базы данных с реальными данными.)
- Небольшое отклонение от схемы именования в вопросе:
student.idявляетсяstudent.stud_idа такжеclub.idявляетсяclub.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) Эрвин 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) Эрвин 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 справляется с этим. Я собираюсь обновить кластер БД, используемый здесь, до 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) Эрвин 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) Эрвин 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
)
Динамическое количество членов клуба
Другими словами: различное количество фильтров. Этот вопрос задали ровно для двух членов клуба. Но во многих случаях нужно готовиться к изменению числа.
Подробное обсуждение в этом связанном последующем ответе:
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 вещь:
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)
Я тестировал в реальной жизни БД, поэтому имена отличаются от списка кошачьих. Это резервная копия, поэтому ничего не менялось во время всех тестовых прогонов (кроме незначительных изменений в каталогах).
Запрос 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) @sean, просто чище, наверное.
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 имеет право жить. Таким образом, самый длинный запрос будет иметь только два столбца для вычисления, идея состоит в том, чтобы сделать запрос тонким.
-- 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 сканировал студента.