Рекурсивные запросы в PostgreSQL (WITH RECURSIVE)
Как ни странно, чтобы понять рекурсию, в PostgreSQL не надо понимать рекурсию. Потому что WITH RECURSIVE, который присутствует в посгресе (и в других серьёзных базах) — это скорее вычисление чего-то итерациями до того, как будет выполнено некоторое условие.
Тем не менее это очень полезный функционал базы, который можно использовать, например, чтобы вывести все подкатегории заданной категории, если таблица задана в виде (id, parent_id, ...)
Давайте для простоты попробуем посчитать факториал. В javascript мы бы делали это примерно так:
function factorial(i) {
if (i > 1) {
return i * factorial(i-1);
} else {
return 1;
}
}
console.log(factorial(10));
В посгресе это вычисляется совсем по-другому. В рекурсивной части CTE обязательно должна быть стартовая часть и рекурсивная часть, разделенные словом UNION.
WITH RECURSIVE r AS (
-- стартовая часть рекурсии (т.н. "anchor")
SELECT
1 AS i,
1 AS factorial
UNION
-- рекурсивная часть
SELECT
i+1 AS i,
factorial * (i+1) as factorial
FROM r
WHERE i < 10
)
SELECT * FROM r;
i | factorial
----+-----------
1 | 1
2 | 2
3 | 6
4 | 24
5 | 120
6 | 720
7 | 5040
8 | 40320
9 | 362880
10 | 3628800
(10 rows)
Обратите внимание, что если читать этот запрос, так сказать, интуитивно, как есть, то кажется что посгрес должен уйти в вечный цикл и посчитать не пойми что.
Дело в том, что вот это вот FROM r не выполняет весь запрос снова, а работает так: в первый раз берет то, что в стартовой части рекурсии (anchor), а в следующие итерации берет результаты предыдущей итерации.
Алгоритм примерно такой:
- Берем стартовые данные
- подставляем в «рекурсивную» часть запроса.
- смотрим что получилось:
- если выхлоп рекурсивной части не пустой, то добавляем его в результирующую выборку, а также используем этот выхлоп как данные для следующего вызова рекурсивной части, т.е. goto 2
- если пусто, то завершаем обработку
Вообще, пример с факториалом не очень показателен, потому что postgresql и так умеет вычислять факториалы, даже очень большие (да и вообще хорошо работает с большими числами):
SELECT 10000!
-- результат приводить не буду, так как там получается примерно тридцатитысячезначное число
Возьмем обещанную выборку из дерева.
CREATE TABLE geo (
id int not null primary key,
parent_id int references geo(id),
name varchar(1000)
);
INSERT INTO geo
(id, parent_id, name)
VALUES
(1, null, 'Планета Земля'),
(2, 1, 'Континент Евразия'),
(3, 1, 'Континент Северная Америка'),
(4, 2, 'Европа'),
(5, 4, 'Россия'),
(6, 4, 'Германия'),
(7, 5, 'Москва'),
(8, 5, 'Санкт-Петербург'),
(9, 6, 'Берлин');
Выбираем всё, что относится к Европе:
WITH RECURSIVE r AS (
SELECT id, parent_id, name
FROM geo
WHERE parent_id = 4
UNION
SELECT id, parent_id
FROM geo
WHERE parent_id IN (
SELECT id FROM r
)
)
SELECT * FROM r;
ERROR: recursive reference to query "r" must not appear within a subquery
Упс, очередное ограничение, рекурсия не должна использоваться в подзапросах.
Ок, перепишем на join:
WITH RECURSIVE r AS (
SELECT id, parent_id, name
FROM geo
WHERE parent_id = 4
UNION
SELECT geo.id, geo.parent_id, geo.name
FROM geo
JOIN r
ON geo.parent_id = r.id
)
SELECT * FROM r;
id | parent_id | name
----+-----------+-----------------
5 | 4 | Россия
6 | 4 | Германия
7 | 5 | Москва
8 | 5 | Санкт-Петербург
9 | 6 | Берлин
(5 rows)
Еще пример. Можно, например выдать всё, что относится к Европе вместе с самой Европой, и еще посчитать уровень вложенности
WITH RECURSIVE r AS (
SELECT id, parent_id, name, 1 AS level
FROM geo
WHERE id = 4
UNION ALL
SELECT geo.id, geo.parent_id, geo.name, r.level + 1 AS level
FROM geo
JOIN r
ON geo.parent_id = r.id
)
SELECT * FROM r;
id | parent_id | name | level
----+-----------+-----------------+-------
4 | 2 | Европа | 1
5 | 4 | Россия | 2
6 | 4 | Германия | 2
7 | 5 | Москва | 3
8 | 5 | Санкт-Петербург | 3
9 | 6 | Берлин | 3
(6 rows)
Если вы знаете что-то интересное по этой теме, напишите, пожалуйста, в комментариях. Где вы на практике удачно использовали рекурсию в SQL? Какие подводные камни?
