PostgreSQL Antipatterns: устраняем вложенные интервалы

Недавно попался на глаза примерно вот такой запрос, которым хотели отобрать в таблице (очевидно, для последующего удаления) все id записей интервалов, которые полностью перекрыты каким-то другим интервалом того же owner‘а:

Как несложно заметить при анализе плана этого запроса на explain.tensor.ru, 98% всего времени ушло на достаточно бессмысленный Hash Join:

Бессмысленный он по той простой причине, что сформировав больше 100M соединенных пар записей, 99% из них он вынужден был отфильтровать по условию.

Как сделать этот запрос эффективнее?..

Для начала восстановим тестовую таблицу интервалов, которую мы использовали в статье «PostgreSQL Antipatterns: работаем с отрезками в «кровавом энтерпрайзе»«:

CREATE TABLE ranges(   id     serial , owner     integer , dtb -- начало интервала     date , dte -- окончание интервала     date );  INSERT INTO ranges(   owner , dtb , dte ) SELECT   (random() * 1e4)::integer -- 10K разных owner'ов , dtb , dtb + (random() * 1e2)::integer FROM   (     SELECT       now()::date - (random() * 1e3)::integer dtb     FROM       generate_series(1, 1e6) -- миллион записей   ) T;

В данном случае уникальный id записи нам дан по условию задачи, но он не является обязательным для устранения дубль-записей — можно воспользоваться ctid, как в статье «DBA: вычищаем клон-записи из таблицы без PK«, если никто не пытается активно менять данные у нас «под ногами».

«Смотрю — слева диск C:, справа диск C:… Зачем, думаю, мне два диска C: — и стер один нафиг.»

древний анекдот

По большому счету, никакой пользы от соединения таблицы с собой же, как и от сравнения записей с разными owner‘ами нам вообще нет, так что давайте сразу разложим имеющиеся интервалы на непересекающиеся сегменты за один проход:

SELECT   owner , array_agg(daterange(dtb, dte, '[]') ORDER BY id) rngs -- массив интервалов , array_agg(id ORDER BY id) ids                         -- массив id записей FROM   ranges GROUP BY   1

Тут мы сразу распределили интервалы и идентификаторы в два массива с [неважно каким, лишь бы] одинаковым порядком исходных записей (ORDER BY id).

Теперь в каждой такой группе надо всего лишь найти id интервалов, перекрытые каким-то из «соседей». Для этого развернем и пронумеруем массив интервалов с помощью unnest WITH ORDINALITY:

SELECT   ids[ni] id FROM   unnest(rngs)     WITH ORDINALITY X(i, ni) WHERE   i <@ ANY(rngs[:ni-1] || rngs[ni+1:]) -- покрыт кем-то из "соседей"

Факт покрытия установим, воспользовавшись оператором <@ ANY, а массив «соседей» соберем конкатенацией двух слайсов исходного массива до/после нужного элемента rngs[:ni-1] || rngs[ni+1:].

Все, наш запрос принял следующий вид:

SELECT   id FROM   (     SELECT       owner     , array_agg(daterange(dtb, dte, '[]') ORDER BY id) rngs     , array_agg(id ORDER BY id) ids     FROM       ranges     GROUP BY       1   ) X , LATERAL (     SELECT       ids[ni] id -- id в той же позиции соседнего массива     FROM       unnest(rngs)         WITH ORDINALITY X(i, ni) -- конкретный интервал и его позиция в массиве     WHERE       i <@ ANY(rngs[:ni-1] || rngs[ni+1:])   ) Y;

А вот и его план — почти в 7 раз быстрее!

Мы молодцы? Ну, почти…

Совпадение интервалов

Проблема тут, ровно как и в исходном запросе, в том, что если два диапазона полностью совпадают, то <@ вернет TRUE для обоих — и, потенциально, мы оба их удалим.

Причем, даже если мы добавим в исходном запросе условие AND daterange(i.dtb, i.dte, '[]') <> daterange(o.dtb, o.dte, '[]') — это не исправит ситуацию, просто теперь они оба вместе останутся — все потому, что исходный запрос «симметричен» относительно обоих чтений таблиц.

Исправить это можно, добавив условие, чтобы отбирался наименьший id для пары одинаковых интервалов:

SELECT DISTINCT   i.id FROM   ranges o JOIN   ranges i     ON i.owner = o.owner AND     i.id <> o.id AND     (       ( -- разбиваем условие по совпадению интервалов         daterange(i.dtb, i.dte, '[]') <> daterange(o.dtb, o.dte, '[]') AND         daterange(i.dtb, i.dte, '[]') <@ daterange(o.dtb, o.dte, '[]')       ) OR       (         daterange(i.dtb, i.dte, '[]') = daterange(o.dtb, o.dte, '[]') AND         i.id < o.id       )     );

Только вот его длительность, и так немалая, выросла втрое из-за многократного формирования daterange (это ой как недешево!):

Как можно организовать такое в нашем «быстром» варианте?

Помните замечание, что неважно в каком одинаковом порядке собирать записи в массивы? Давайте используем этот факт в свою пользу — отсортируем все интервалы одного owner‘а сначала по длине dte - dtb, а потом по id:

SELECT   owner , array_agg(daterange(dtb, dte, '[]') ORDER BY dte - dtb, id) rngs , array_agg(id ORDER BY dte - dtb, id) ids FROM   ranges GROUP BY   1

В этом случае очевидно, что «покрывающий» интервал может лежать в массиве только «правее» анализируемого (у него длина точно должна быть не меньше, а id — больше), и «клеить» слайсы нам больше нет необходимости:

SELECT   id FROM   (     SELECT       owner     , array_agg(daterange(dtb, dte, '[]') ORDER BY dte - dtb, id) rngs     , array_agg(id ORDER BY dte - dtb, id) ids     FROM       ranges     GROUP BY       1   ) X , LATERAL (     SELECT       ids[ni] id     FROM       unnest(rngs)         WITH ORDINALITY X(i, ni)     WHERE       i <@ ANY(rngs[ni+1:]) -- проверяем покрытие "соседями" справа   ) Y;

Мало того, что мы исправили досадную проблему с совпадающих интервалов, так еще и умудрились сделать «быструю» версию почти вдвое быстрее:

Не факт, что в реальных условиях вам придется зачищать интервалы подобным образом на «миллионных» таблицах, но разница времени исполнения запроса в 30 раз стоит того, чтобы знать и о такой методике.