Как ни странно, чтобы понять рекурсию, в 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? Какие подводные камни?
ссылка на оригинал статьи http://habrahabr.ru/post/269497/
Добавить комментарий