Как фильтровать результаты 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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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)

Ответ 4

Если вы просто хотите 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 ) )

Ответ 5

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

Ответ 6

Другой 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)
    ;

Ответ 7

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

1) GROUP сначала, ПОСМОТРЕТЬ позже

Предполагая разумную модель данных, где (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

И, конечно, есть классический 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);

Ответ 8

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

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

Еще одна попытка с немного другим подходом. Вдохновленный статьей в Объяснение 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 ;

Ответ 9

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-scan позволяет избежать необходимости в двух отдельных подзапросах.

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

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

Ответ 10

Различные планы запросов в запросе 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

Ответ 11

@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, просто чище, я думаю.

Ответ 12

-- 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 сканирует ученика.

Ответ 13

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, имеющей право на жизнь. Таким образом, самый длинный запрос будет иметь только два столбца для расчета, идея состоит в том, чтобы сделать запрос тонким.