25.10.2015 18:32
varanio 13 8115 Источник

Как ни странно, чтобы понять рекурсию, в 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? Какие подводные камни?

Комментарии (13)


  1. Envek
    26.10.2015 10:18
    #8626889
    +2

    Как раз очень полезно для вывода вложенных структур с сортировкой по алфавиту:

    WITH RECURSIVE tree AS (
    SELECT
        id, short_name, parent_id, short_name AS sort_string, 1 AS depth
    FROM stations
    WHERE parent_id IS NULL
    UNION ALL
    SELECT
        s1.id, s1.short_name, s1.parent_id,
        tree.sort_string || '|' || s1.short_name AS sort_string, tree.depth+1 AS depth
    FROM
        tree
        JOIN stations s1 ON s1.parent_id = tree.id
)

SELECT depth, short_name, id, parent_id, sort_string FROM tree ORDER BY sort_string ASC;


    1. qasta
      27.10.2015 14:30
      #8629379

      Ну вы же понимаете, что это работает только до десяти уровней вложенности :)


      1. Envek
        27.10.2015 16:09
        #8629761
        +1

        Ещё нет, не понимаем (там где мы используем, у нас их всего два, да и объектов не очень много).
        Расскажете, почему не работает на большом уровне вложенности?


        1. qasta
          28.10.2015 12:06
          #8631039

          Чуть ошибся — не во вложенности дело, а в именах (думал, что вы в sort_string засовываете depth), но не суть.
          У вас просто соединяются строки с разделителем, и, если с ними будет что-то не так (например, в имени элемента встретится символ разделителя), то это может повлиять на сортировку и вы получите данные в неправильном порядке.

          Посмотрите на выборку вот такого набора данных:

          insert into stations 
values
(1, 'name', null),
(2, 'name|0', null),
(3, 'name|1', null),
(4, 'name0', null),
(5, '1', 1),
(6, '2', 2),
(7, '3', 3);


insert into stations 
values
(11, 'name', null),
(12, 'name2', null),
(13, 'name3', null),
(14, 'name4', null),
(15, '1', 11),
(16, '2', 12),
(17, '3', 13);


          Так что
          1) выделяйте 2 колонки — одну для «текущего пути» — не забудьте сделать rpad, дабы выровнять длины
          2) старайтесь не использовать «синтетические значения» для функционирования системы.
          Выглядит, как заплатка, и работает так же.


  1. Dein777
    26.10.2015 10:47
    #8626915

    Для того чтоб обойти ограничения в использовании рекурсивного подзапроса (нельзя использовать в подзапросах, можно ссылаться только один раз и т.д.), использую следующую конструкцию

    WITH RECURSIVE r AS (
   SELECT id, parent_id, name
   FROM tmp.geo
   WHERE parent_id = 4

   UNION all
   select *
      from
         (
         with rr as
            (
            select * from r
            )
         SELECT id, parent_id, name
         FROM tmp.geo
         WHERE parent_id IN (  SELECT id FROM rr   )
         ) a
)

SELECT * FROM r;
</source lang>
Часто использую recursive для быстрых выборок по индексу. Получается трудно читаемо, но очень быстро.


  1. 0xA0
    26.10.2015 10:56
    #8626919

    Здравствуйте.
    Не подскажете как такие конструкции работают на больших объемах(как по размеру так и по количеству)? Нам, например, пришлось отказаться от JOIN-ов.


  1. bobzer
    26.10.2015 11:37
    #8626969
    +2

    Добавлю: рекурсивных подзапросов может быть несколько в одном SQL-запросе. В начале объявляется WITH RECURSIVE, далее следуют как рекурсивные, так и обычные подзапросы, каждый со своим алиасом. Необязательно осуществлять выборку непосредственно из рекурсивного запроса, его можно, например, джойнить с обычной выборкой из таблицы. Использовал такой подход при формировании отчётов. Выглядит примерно так:

    WITH RECURSIVE
tree_query_1 AS (... --рекурсивный запрос
UNION ALL...
),
tree_query_2 AS (... --рекурсивный запрос
UNION ALL...
),
simple_query_1 AS (... --нерекурсивный запрос
--no UNION
)
--далее строим отчёт, используя объявленные выше запросы
SELECT
  t1.field1,
  (SELECT field2 FROM simple_query_1 WHERE id = t1.field2) --используем в блоке SELECT
FROM table_1 t1
INNER JOIN tree_query_1 t2 ON t1.field3 = t2.field4 --используем в JOIN
LEFT JOIN (SELECT * FROM tree_query_2 WHERE...) -- используем в подзапросе в JOIN

    Как видно из примера, возможности широкие, и это «рецепты» от не специалиста по СУБД и не знатока PostreSQL…


  1. zzashpaupat
    26.10.2015 11:49
    #8626985
    +8

    image

    Тут еще всякие интересные примеры есть.


  1. 4knowledge
    26.10.2015 12:57
    #8627053
    +2

    В документации по СУБД написано, что с помощью рекурсивных запросов можно добираться значительное прироста производительности по сравнению с использованием временных таблиц и хранимых процедур. Насколько верно такое утверждение?

    И вот как например можно решить последнюю задачу в статье про уровень вложенности в Европе без рекурсий, в частности с временными таблицами и хранимыми процедурами?


  1. utrack
    26.10.2015 18:07
    #8627601
    +3

    Рекурсия это здорово и удобно, но при поиске иерархичных структур на больших объёмах данных\большой вложенности очень быстро проседает производительность — в таких случаях удобней создавать суррогатное поле-массив айдишников с путём элемента от корня и изменять его триггерами. Если интересно — могу написать статью.
    Правда, такой подход должен плохо работать при mods > reads из-за постоянного переписывания индексов. Тут остаётся только сесть в угол и бояться :)


    1. stalkerg
      26.10.2015 18:18
      #8627633

      тут не честная рекурсия так что должно быть всё ок…


    1. varanio
      26.10.2015 18:28
      #8627651

      Ждем статью )


    1. JSmitty
      26.10.2015 18:43
      #8627673

      Т.е. вы расширение ltree вручную имитируете? Напишите, всё равно интересно.