Примеры рекурсивных запросов в PostgreSQL

23 марта 2020

Вот еще одна задача с PostgreSQL, возникшая по работе. Есть таблица с некими событиями. У событий есть уникальный id. В силу специфики приложения id событий не обязательно идут по порядку. Однако в каждом событии есть id следующего и предыдущего события. Требуется написать функции forward(id, steps) и backward(id, steps), возвращающие id события, произошедшего steps событий вперед или назад относительно заданного. Если такого события нет, требуется вернуть пустой результат.

Упрощенно таблица событий выглядит так:

CREATE TABLE events(
  "id" BIGINT PRIMARY KEY,
  "prev" BIGINT NOT NULL,
  "next" BIGINT NOT NULL,
  "descr" TEXT NOT NULL
);

INSERT INTO events
  SELECT id*10, (id-1)*10, (id+1)*10, 'Event ' || id*10
  FROM generate_series(1,20) AS id;

SELECT * FROM events;

Пример данных:

 id  | prev | next |   descr
-----+------+------+-----------
  10 |    0 |   20 | Event 10
  20 |   10 |   30 | Event 20
  30 |   20 |   40 | Event 30
  40 |   30 |   50 | Event 40
  50 |   40 |   60 | Event 50
  60 |   50 |   70 | Event 60
  70 |   60 |   80 | Event 70
  80 |   70 |   90 | Event 80
  90 |   80 |  100 | Event 90
 100 |   90 |  110 | Event 100
 110 |  100 |  120 | Event 110
 120 |  110 |  130 | Event 120
 130 |  120 |  140 | Event 130
 140 |  130 |  150 | Event 140
 150 |  140 |  160 | Event 150
 160 |  150 |  170 | Event 160
 170 |  160 |  180 | Event 170
 180 |  170 |  190 | Event 180
 190 |  180 |  200 | Event 190
 200 |  190 |  210 | Event 200
(20 rows)

На первый взгляд, можно просто сделать SELECT ... ORDER BY id OFFSET ... LIMIT ..., но такое решение неверно. Во-первых, как уже отмечалось, id событий не обязательно идут по порядку. Во-вторых, на самом деле события доезжают в базу с задержкой, и в некоторых случаях в двусвязном списке могут образовываться «дырки».

Выгружать событие с заданным id, смотреть на его next или prev, выгружать следующее событие, и так steps раз – более правильное решение. Проблема в том, что нам придется steps раз сходить в СУБД по сети, ей в свою очередь придется пропарсить steps запросов, steps раз взять локи, сходить в кучу, и вот это вот все. В общем, не звучит, как что-то эффективное. Особенно, если учесть, что forward и backward могут вызываться достаточно часто.

Оказывается, что PostgreSQL поддерживает рекурсивные запросы (они в свою очередь являются частью фичи под названием Common Table Expressions или CTE). Такие запросы в состоянии сами сделать обход двухсвязного списка, что позволяет решить задачу в один запрос. Например, простейшая реализация forward(10, 5) может выглядеть так:

WITH RECURSIVE tmp AS (
  SELECT "id", "next" FROM events WHERE "id" = 10
    UNION ALL
  SELECT e."id", e."next" FROM tmp t
  INNER JOIN events e ON e."id" = t."next"
) SELECT "id" FROM tmp OFFSET 5 LIMIT 1;

Сперва кажется, что запрос выглядит сложно и непонятно, но на самом деле все очень просто. Сначала выполняется так называемый non-recursive term:

SELECT "id", "next" FROM events WHERE "id" = 10

То, что вернет этот запрос, помещается в результат рекурсивного запроса, а также во временную working table. При этом, если был использован UNION ALL, то все копируется как есть. Если же был использован UNION без ALL, то дубликаты кортежей отбрасываются.

Далее, до тех пор, пока в working table что-то есть, выполняется recursive term:

SELECT e."id", e."next" FROM tmp t
INNER JOIN events e ON e."id" = t."next"

Здесь tmp как раз ссылается на working table. То есть, делается обычный INNER JOIN двух таблиц. Строки, которые вернет этот запрос, добавляются к результату рекурсивного запроса. Также они полностью заменяют собой working table, после чего мы снова переходим к выполнению recursive term. Дубликаты оставляются или удаляются в зависимости от того, был ли использован UNION или UNION ALL.

Таким образом, WITH RECURSIVE часть запроса выполняет обход двухсвязного списка, возвращая все элементы, начиная с заданного. Нам остается лишь сделать SELECT ... OFFSET ... LIMIT ... по этим элементам, и мы получаем результат.

Вдумчивый читатель мог обратить внимание на одну проблему. Дело в том, что, если читать запрос буквально, то рекурсивная часть сканирует все события до тех пор, пока они не закончатся. Затем из найденных событий мы отбрасываем все, кроме одного, которое нас интересовало. В зависимости от версии PostgreSQL, накопленной статистики, а также положения звезд на небе, планировщик не обязательно окажется достаточно умен для того, чтобы не сканировать все события. Поэтому будет не самой плохой идеей явно ограничить глубину рекурсии.

Сделать это можно так:

WITH RECURSIVE tmp AS (
  SELECT 1 AS "depth", "id", "next" FROM events WHERE "id" = 10
    UNION ALL
  SELECT t."depth"+1, e."id", e."next" FROM tmp t
  INNER JOIN events e ON e."id" = t."next"
  WHERE t."depth" <= 5
) SELECT "id" FROM tmp OFFSET 5 LIMIT 1;

В качестве упражнения читателям предлагается взять используемую ими версию PostgreSQL и (1) изучить планы выполнения двух запросов, а также (2) реальное время их исполнения на больших объемах данных. Также предлагается ответить на вопрос – что будет, если взять приведенные запросы и заменить в них INNER JOIN на LEFT JOIN? Ответы оставляйте в комментариях.

Аналогично, backward(60, 5) будет выглядеть так:

-- глупенькая версия
WITH RECURSIVE tmp AS (
  SELECT "id", "prev" FROM events WHERE "id" = 60
    UNION ALL
  SELECT e."id", e."prev" FROM tmp t
  INNER JOIN events e ON e."id" = t."prev"
) SELECT "id" FROM tmp OFFSET 5 LIMIT 1;

-- умненькая версия
WITH RECURSIVE tmp AS (
  SELECT 1 AS "depth", "id", "prev" FROM events WHERE "id" = 60
    UNION ALL
  SELECT t."depth"+1, e."id", e."prev" FROM tmp t
  INNER JOIN events e ON e."id" = t."prev"
  WHERE t."depth" <= 5
) SELECT "id" FROM tmp OFFSET 5 LIMIT 1;

Отмечу, что хотя рекурсивные запросы и позволяют совершать меньше хождений в СУБД, они не являются панацеей. Каждый случай уникален и требует вдумчивого анализа объемов данных, частоты выполнения тех или иных запросов, изучения вывода EXPLAIN, и так далее. В зависимости от специфики вашего приложения, рекурсивные запросы могут ухудшить производительность, а не улучшить. В общем, как любой другой инструмент, рекурсивные запросы (1) полезно держать на вооружении и (2) нужно использовать с умом.

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

Дополнение: В продолжение темы интересных фичей PostgreSQL вас могут заинтересовать посты о LATERAL JOIN и NOTIFY/LISTEN.