Проблема производительности postgres с вложенными подзапросами sql

Question

Для упрощения случая предположим, что есть следующие 3 таблицы

A(a_id), B(b_id,val_b), C(a_id,b_id,val_c)

Мне нужно найти все a_id, которые имеют определенные пары значений из B и C. Пример найти все a_id, которые имеют записи (val_b='1' и val_c='2' и B.b_id=C.b_id) AND (val_b='3' and val_c='4'и B.b_id = C.b_id) И...

select A.a_id
from A
where (A.a_id in 
        (select C.a_id 
         from B, C 
         where B.b_id=C.b_id and B.val_b='1' and C.val_c='2') and
       A.a_id in 
        (select C.a_id 
         from B, C 
         where B.b_id=C.b_id and B.val_b='3' and C.val_c='4') and
       A.a_id in 
        (select C.a_id 
         from B, C 
         where B.b_id=C.b_id and B.val_b='5' and C.val_c='6'));

Я заметил, что добавление еще нескольких (val_b, val_c) дополнительных пар postgres требует значительного времени для выполнения запроса. Отметим, что индексы присутствуют для идентификаторов, val_b и val_c.

Есть ли способ оптимизировать запрос? Пробовал явные внутренние объединения, но не помог улучшить производительность.

заранее спасибо

Больше информации:

• Postgres версия 8.2.4
• Только с одним парным критерием работает в 77.621 мс
• С 2 парными критериями - 151,588 мс

• С 3 парами критериев - 49483,979 мс <- производительность сводит с ума

• Обратите внимание, что отдельный подзапрос работает менее чем за 62 мс.

Обновить:

И отдельная версия запроса INTERSECT, предложенная ниже Владимиром Барановым, и версия с предложением, использующим функцию агрегации bool_or Клодоальдо Нето, работали намного лучше. Спасибо!

Тем не менее, остается вопрос, почему Postgres 8.2 имеет такой всплеск производительности, когда исходный запрос начинается с 3 парных критериев?

Кстати, я заметил такую ​​же искру и с первым предложением Владимира Баранова переписать запрос чистыми объединениями. Увидеть ниже:

SELECT A.a_id
FROM
    A
    INNER JOIN (SELECT C.a_id FROM B INNER JOIN C ON B.b_id=C.b_id WHERE B.val_b='1' and C.val_c='2') Set1 ON Set1.a_id = A.a_id
    INNER JOIN (SELECT C.a_id FROM B INNER JOIN C ON B.b_id=C.b_id WHERE B.val_b='3' and C.val_c='4') Set2 ON Set2.a_id = A.a_id
    INNER JOIN (SELECT C.a_id FROM B INNER JOIN C ON B.b_id=C.b_id WHERE B.val_b='5' and C.val_c='6') Set3 ON Set3.a_id = A.a_id
;

С 3 наборами этот запрос выполняется довольно быстро, но как только один добавляет еще 3-4, производительность запроса снижается до ~30-40 секунд.

Answer 1

Было бы интересно узнать, работает ли следующее быстрее:

SELECT A.a_id
FROM A
WHERE
    A.a_id IN
    (
        SELECT C.a_id
        FROM B INNER JOIN C ON B.b_id=C.b_id
        WHERE B.val_b='1' and C.val_c='2'

        INTERSECT

        SELECT C.a_id
        FROM B INNER JOIN C ON B.b_id=C.b_id
        WHERE B.val_b='3' and C.val_c='4'

        INTERSECT

        SELECT C.a_id
        FROM B INNER JOIN C ON B.b_id=C.b_id
        WHERE B.val_b='5' and C.val_c='6'
    )
;

Эффективно, вместо нескольких IN Здесь явное пересечение нескольких подмножеств.

Мой первоначальный ответ содержал запрос, который не был эквивалентен исходному запросу вопроса.

Вот SQL Fiddle с некоторыми примерами данных и исходным запросом, чтобы проверить, что мой вариант дает те же результаты, что и исходный запрос.

редактировать

Еще один путь для расследования. Если каждый из подзапросов выполняется быстро, но INTERSECT повторение много раз в одном длинном запросе становится очень медленным, затем вы можете попытаться заполнить временную таблицу результатами подзапросов, а затем использовать эту временную таблицу с основной таблицей. A, Эффективно внедрить INTERSECT вручную по одному, используя явную временную таблицу. В зависимости от количества строк, возвращаемых подзапросами, может быть полезно добавить индекс во временную таблицу.

Обновить

Что касается вашего вопроса, почему производительность Postgres ухудшается, когда запрос становится сложным... Ваша версия Postgres довольно старая, и маловероятно, что кто-то заинтересуется настолько, чтобы провести подробное расследование. Я могу предложить только некоторые общие мысли. Последняя версия, скорее всего, будет работать по-другому, с 8.2 было много изменений.

В каждой СУБД оптимизатор запросов имеет ограниченные ресурсы и время для анализа запроса, поэтому он использует много эвристик. Поскольку количество соединений в запросе увеличивает сложность задачи, поиск оптимального плана выполнения увеличивается экспоненциально, поэтому должен быть порог, после которого оптимизатор сдается и выбирает любой план, который у него есть.

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

Может случиться так, что когда дан запрос с несколькими joins оптимизатор может преобразовать его в вариант, эквивалентный использованию intersect, но с большим количеством объединений он больше не может этого делать и просто следует потоку запросов, выполняя объединение после объединения. Он может даже сделать это настолько неэффективно, что в конечном итоге выполнит цикл внутри цикла внутри цикла..., другими словами, сложность переместится с линейной на квадратичную или еще хуже.

Так что, на самом деле, единственный ответ на такие вопросы о производительности: изучить план выполнения.

Кстати, последние версии Postgres имеют WITH, который эффективно создает временную таблицу с промежуточными результатами. В вашем случае это должно сильно помочь, потому что каждый из ваших подзапросов прост, и если система сначала запускает их все по отдельности, тогда будет легко объединить результаты.

Answer 2

select a_id
from
    a
    inner join
    c using (a_id)
    inner join
    b using (b_id)
group by a_id
having
    bool_or((val_b, val_c) = (1,2)) and
    bool_or((val_b, val_c) = (3,4)) and
    bool_or((val_b, val_c) = (5,6))

http://www.postgresql.org/docs/8.2/static/functions-aggregate.html

Answer 3

1. обновить до последней версии
2. Использовать JOIN синтаксис для ясности
3. использование EXISTS(...) вместо IN(...) для скорости и комфорта
4. PK/FK и индексы помогают!

---

SELECT A.a_id
FROM A
WHERE EXISTS (
        SELECT *
        FROM B
        JOIN C ON B.b_id = C.b_id AND B.val_b = '1' 
        WHERE C.a_id = A.a_id AND C.val_c = '2'
        )
AND EXISTS (
        SELECT *
        FROM B
        JOIN C ON B.b_id = C.b_id AND B.val_b = '3' 
        WHERE C.a_id = A.a_id AND C.val_c = '4'
        )
AND EXISTS (
        SELECT *
        FROM B
        JOIN C ON B.b_id = C.b_id AND B.val_b = '5' 
        WHERE C.a_id = A.a_id AND C.val_c = '6'
        )
        ;

Answer 4

Каждый подзапрос должен снова попадать в индексы, что увеличивает издержки запроса в несколько раз. Если я понимаю, о чем вы спрашиваете, это касается оператора Or:

select a.a_id
from A
  join c on a.a_id = c.a_id
  join b on b.b_id = c.b_id
where 
(
  (b.val_b = '1' and c.val_c = '2')
  or (b.val_b = '3' and c.val_c = '4')
  or (b.val_b = '5' and c.val_c = '6')
)

Это даст вам все записи A, связанные с записью C, где значения c и b являются одним из упомянутых вами наборов. Надеюсь это поможет:)

edit Кажется, это много к одному:

Select a.a_id
    , sum(case when b.val_b = '1' and c.val_c = '2' then 1 else 0 end) as Condition1
    , Sum(case when b.val_b = '3' and c.val_c = '4' then 1 else 0 end) as Condition2
    , Sum(case when b.val_b = '5' and c.val_c = '6' then 1 else 0 end) as Condition3
from A
  join c on a.a_id = c.a_id
  join b on b.b_id = c.b_id
group by a.a_id
having sum(case when b.val_b = '1' and c.val_c = '2' then 1 else 0 end) > 0
    and Sum(case when b.val_b = '3' and c.val_c = '4' then 1 else 0 end) > 0
    and Sum(case when b.val_b = '5' and c.val_c = '6' then 1 else 0 end) > 0

Надеюсь, это поможет вам