Примеры рекурсивных запросов в PostgreSQL
23 марта 2020
Вот еще одна задача с PostgreSQL, возникшая по работе. Есть таблица с некими событиями. У событий есть уникальный id. В силу специфики приложения id событий не обязательно идут по порядку. Однако в каждом событии есть id следующего и предыдущего события. Требуется написать функции forward(id, steps) и backward(id, steps), возвращающие id события, произошедшего steps событий вперед или назад относительно заданного. Если такого события нет, требуется вернуть пустой результат.
Упрощенно таблица событий выглядит так:
"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;
Пример данных:
-----+------+------+-----------
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) может выглядеть так:
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:
То, что вернет этот запрос, помещается в результат рекурсивного запроса, а также во временную working table. При этом, если был использован UNION ALL, то все копируется как есть. Если же был использован UNION без ALL, то дубликаты кортежей отбрасываются.
Далее, до тех пор, пока в working table что-то есть, выполняется recursive term:
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, накопленной статистики, а также положения звезд на небе, планировщик не обязательно окажется достаточно умен для того, чтобы не сканировать все события. Поэтому будет не самой плохой идеей явно ограничить глубину рекурсии.
Сделать это можно так:
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.
Метки: PostgreSQL, СУБД.
Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.