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