Рекурсивные запросы в 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), а в следующие итерации берет результаты предыдущей итерации.

Алгоритм примерно такой:

1. Берем стартовые данные
2. подставляем в «рекурсивную» часть запроса.
3. смотрим что получилось:
   
   • если выхлоп рекурсивной части не пустой, то добавляем его в результирующую выборку, а также используем этот выхлоп как данные для следующего вызова рекурсивной части, т.е. 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? Какие подводные камни?

Больше полезного можно найти на telegram-канале о разработке "Cross Join", где мы обсуждаем базы данных, языки программирования и всё на свете!