Рекурсивные запросы в 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? Какие подводные камни?
    Support the author
    Share post

    Similar posts

    Comments 13

      +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;
      
        0
        Ну вы же понимаете, что это работает только до десяти уровней вложенности :)
          +1
          Ещё нет, не понимаем (там где мы используем, у нас их всего два, да и объектов не очень много).
          Расскажете, почему не работает на большом уровне вложенности?
            0
            Чуть ошибся — не во вложенности дело, а в именах (думал, что вы в 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) старайтесь не использовать «синтетические значения» для функционирования системы.
            Выглядит, как заплатка, и работает так же.

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

        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 для быстрых выборок по индексу. Получается трудно читаемо, но очень быстро.
          0
          Здравствуйте.
          Не подскажете как такие конструкции работают на больших объемах(как по размеру так и по количеству)? Нам, например, пришлось отказаться от JOIN-ов.
            +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…
              +8
              image

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

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

                      Only users with full accounts can post comments. Log in, please.