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

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

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

Доминирующий Hash Join — Доминирующий `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 у нас заведомо уникален, то порядок сортировки элементов однозначен.

В этом случае очевидно, что "покрывающий" интервал может лежать в массиве только "правее" анализируемого (длина у него точно должна быть не меньше, а 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 раз стоит того, чтобы знать и о такой методике.

UPD: 02.10.24 - сборка массива "по окну"

А можно ли быстрее?..

Давайте обратим внимание, что нам ведь нет разницы, с каким сегментом массива сравнивать - до элемента или после - главное, чтобы там оказались необходимые нам данные.

А что такое, по сути, слайс из предыдущих элементов массива? А это как раз "накопительный" массив, если формировать его на "предыдущих" записях "окна" с обращенными сортировками:

array_agg(daterange(dtb, dte, '[]'))
  OVER(
    PARTITION BY
      owner          -- сегментация по владельцу
    ORDER BY
      dte - dtb DESC -- обратная сортировка
    , id DESC
    ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING -- все "предыдущие" записи
  )

Остается отобрать лишь те id, интервалы которых полностью покрыты кем-то из собранного массива.

SELECT
  id
FROM
  (
    SELECT
      *
    , array_agg(daterange(dtb, dte, '[]'))
        OVER(
          PARTITION BY
            owner          -- сегментация по владельцу
          ORDER BY
            dte - dtb DESC -- обратная сортировка
          , id DESC
          ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING -- все "предыдущие" записи
        ) rngs
    FROM
      ranges
  ) T
WHERE
  CASE
    WHEN rngs IS NOT NULL THEN
      daterange(dtb, dte, '[]') <@ ANY(rngs)
  END;

Чтобы зря не формировать daterange (что, как мы уже выяснили, бывает весьма накладно) для записей, у которых все равно нет "предыдущих", проверку условия "спрячем под CASE".

И как эффект?.. А весьма неплох - мы отыграли еще 27% времени:

Так что даже если вы уже оптимизировали запрос в 30 раз - всегда можно попробовать ускорить в 40 раз!

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

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

UPD: 02.10.24 - сборка массива "по окну"

Публикации

Информация