SQL HowTo: обход дерева иерархии «по курсору» через двойную рекурсию / forpes.ru

Главная
SQL HowTo: обход дерева иерархии «по курсору» через двойную рекурсию

SQL HowTo: обход дерева иерархии «по курсору» через двойную рекурсию +14

29.06.2022 10:00

Kilor 24 2500 Источник

В предыдущих статьях "PostgreSQL Antipatterns: навигация по реестру", "PostgreSQL 13: happy pagination WITH TIES" и "SQL HowTo: курсорный пейджинг с неподходящей сортировкой" я уже рассматривал проблемы навигации по данным, представленных в виде плоского реестра.

Но что если мы хотим выводить данные не простым "бесконечным списком", а в виде иерархической структуры с быстрой навигацией по узлам - например, обширный каталог товаров или меню ресторана, как это делает Presto - наш продукт для автоматизации заведений питания?

Формируем датасет

Для начала сгенерируем наш тестовый иерархичный каталог на 100K позиций:

CREATE TABLE hier(
  id  -- PK
    integer
      PRIMARY KEY
, pid -- ссылка на "предка"
    integer
      REFERENCES hier
        ON DELETE CASCADE
, ord -- пользовательский порядковый номер внутри раздела
    integer
);

INSERT INTO hier
SELECT
  id
, nullif((random() * id)::integer, 0) pid
, (random() * 1e5)::integer ord
FROM
  generate_series(1, 1e5) id; -- 100K записей

Из размера уже становится понятно, что решения вроде "Давайте все сразу развернем в нужном порядке как описано тут, а потом спозиционируемся через OFFSET" адекватно работать не будут.

Теперь договоримся, что порядок вывода записей внутри одного раздела, определяемый полем ord, будет уникальным. Для этого нам надо вычистить все дубли пар (pid, ord), как мы делали это в статье "DBA: вычищаем клон-записи из таблицы без PK":

DELETE FROM
  hier
WHERE
  ctid = ANY(ARRAY(
    SELECT
      unnest((array_agg(ctid))[2:]) ctids
    FROM
      hier
    GROUP BY
      pid, ord
    HAVING
      count(*) > 1
  ));
-- теперь никто не мешает индексу по разделу быть уникальным
CREATE UNIQUE INDEX ON hier(pid, ord);

Алгоритм обхода

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

Взять первого по порядку потомка на уровень ниже:

Спуск на уровень
Если такого нет, взять "соседа" на текущем уровне:

На одном уровне
Если такого нет, взять "соседа" у ближайшего предка, у которого он есть:

Подъем на уровень

Если же ни у одного предка не оказалось "соседа" - все, мы обошли все дерево.

Собираем SQL

наш алгоритм итеративно переходит от одной записи к другой - то есть для SQL это будет рекурсивным запросом;
паттерн "если такого нет, возьми следующий вариант" легко реализуется с помощью кейса UNION ALL + LIMIT 1 (см. статью);
"ближайшего предка с соседом" придется искать тоже рекурсивно;
для ограничения количества набираемых N записей разумнее всего использовать обычный счетчик.

Звучит не слишком страшно, но надо учесть, что п.3 разделится еще на два - когда узел находится где-то в глубине дерева, и когда он находится в корне (pid IS NULL):

WITH RECURSIVE T AS(
  SELECT
    h   -- тут будет лежать сразу цельная запись, чтобы не перечитывать ее повторно
  , 0 i -- счетчик найденных записей
  FROM
    hier h
  WHERE
    id = 10000 -- последняя прочитанная на предыдущей итерации запись
UNION ALL
  SELECT
    X._h
  , i + 1
  FROM
    T
  , LATERAL (
      -- первый потомок
      (
        SELECT
          _h
        FROM
          hier _h
        WHERE
          pid = (T.h).id
        ORDER BY
          ord
        LIMIT 1
      )
      UNION ALL
      -- ближайший "сосед"
      (
        SELECT
          _h
        FROM
          hier _h
        WHERE
          pid = (T.h).pid AND
          ord > (T.h).ord
        ORDER BY
          ord
        LIMIT 1
      )
      UNION ALL
      -- ближайший "сосед" ближайшего предка
      (
        WITH RECURSIVE _T AS(
          SELECT
            T.h p         -- берем текущую запись в качестве "предка"
          , NULL::hier _h -- "соседа" у нее заведомо нет
        UNION ALL
          SELECT
            __h
          , (
              -- сработает только один из блоков с противоположными условиями
              (
                SELECT
                  __h
                FROM
                  hier __h
                WHERE
                  (_T.p).pid IS NOT NULL AND -- мы еще не в корне
                  pid = (_T.p).pid AND
                  ord > (_T.p).ord
                ORDER BY
                  pid, ord -- подгоняем под индекс
                LIMIT 1
              )
              UNION ALL
              (
                SELECT
                  __h
                FROM
                  hier __h
                WHERE
                  (_T.p).pid IS NULL AND     -- уже в корне
                  pid IS NULL AND
                  ord > (_T.p).ord
                ORDER BY
                  pid, ord -- подгоняем под индекс
                LIMIT 1
              )
              LIMIT 1
            )
          FROM
            _T
          INNER JOIN
            hier __h
              ON __h.id = (_T.p).pid -- рекурсивный обход "вверх" по иерархии
        )
        SELECT
          _h
        FROM
          _T
        WHERE
          _h IS DISTINCT FROM NULL
        LIMIT 1
      )
      LIMIT 1
    ) X
  WHERE
    X._h IS DISTINCT FROM NULL AND
    i < 20 -- количество записей на странице
)
SELECT
  (h).*  -- разворачиваем поля записи
FROM
  T
WHERE
  i > 0; -- убираем "стартовую" запись

Проверим план запроса на explain.tensor.ru:

Все выполнение для поиска 20 записей заняло меньше полмиллисекунды! При этом никаких Seq Scan или Sort, все исключительно по индексам (всего 58 обращений):

А разве попроще нельзя?..

Конечно, можно! Достаточно заметить, что случаи #2 и #3 логически одинаковы - нужно взять ближайшего "соседа" по всей цепочке предков, но начиная с самой же записи. Поэтому второй блок из UNION ALL можно просто убрать - и результат останется ровно тем же самым!

Но вот план - немного ухудшится, и вместо 150 страниц данных для тех же записей придется читать уже 163, поскольку рекурсивный поиск первого предка теперь будет производиться для каждой записи - даже для той, у которой есть "сосед".

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

CoffinNail
29.06.2022 10:22
#24482202
+1
Вот блин! Вспомнил вариант своей древовидной базы, даже имена колонок одинаковые. Но в итоге был опыт отказа от таких конструкций, поскольку проект был приостановлен, и, месяц спустя, долго вспоминали что к чему, а дальнейшая разработка и вовсе стала колом. Короч, дерево можно использовать, но аккуратно, максимально просто, без наворотов. Пусть лучше пишется отдельный ключ поиска в дополнение к данным в конкретном месте проги - это куда оптимальнее и читабельнее, чем подгонять универсальность под всю базу, исходя из частного случая, который может и не возникнуть, ха-ха.

glagola
29.06.2022 10:27
#24482222
DEL
1. Kilor Автор
  29.06.2022 10:32
  #24482240
  И еще пара других вариантов. Но тут мы рассматриваем вариант, как жить в уже сложившейся структуре БД, для которой такая выборка - лишь "одна из".
  1. CoffinNail
    29.06.2022 11:25
    #24482414
    Нужна наглядность при сохранении наглядного функционала SQL. Тоже уже пройденный путь. Новичок легко сможет войти в систему, не зная нюансов, но зная SQL, и этого вполне достаточно, чтобы юзать базу без лишних приблуд.
    
    Kilor Автор
    29.06.2022 11:32
    #24482452
    Наглядность и производительность SQL, увы, редко ходят вместе.
    
    Как я и написал в статье, можно было бы каждый раз разворачивать всю иерархию и позиционироваться через OFFSET (да и без всякой иерархии любителей делать пейджинг через OFFSET предостаточно), но это ни разу не будет эффективным по производительности решением.
    
    И тут в игру вступают рассуждения вида "дешевле платить по $1K разработчику за поддержку сложного решения следующие 10 лет, чем вложить $100K в наращивание железа для работы простого в разработке, но неэффективного".
    
    CoffinNail
    29.06.2022 11:50
    #24482526
    Новичок не поймет твоё решение, и ему придется переделывать. В этом вся соль. Мы на практике избегаем неклассического функционала SQL, дописываем скриптом обработку. Ну, тут, конечно, всё упирается в нагрузку. Как пишут 1Сники - меняйте архитектуру решения, ха-ха, когда их ругают за тормозную работу их же проги.
    
    Kilor Автор
    29.06.2022 11:54
    #24482550
    +2
    Новичок не поймет твоё решение, и ему придется переделывать. В этом вся соль.
    
    А зачем вообще подпускать новичка к непростому коду? Еще более очевидно, что позволять "непонявшему новичку" что-то переделывать - чисто организационный fail.
    
    CoffinNail
    29.06.2022 12:58
    #24482816
    Мы тебя троллим, ведь это непрактично. Сколько раз уже видел, как чуваки перепиливают деревА в плоскую табличку, и, разумеется, свалка становится еще больше.

denis-isaev

29.06.2022 12:09

#24482626

Есть ощущение, что репрезентативное именование заметно помогло бы читабельности запроса.

Kilor Автор

29.06.2022 12:41

#24482740

Вроде как не особо...

альтернативное именование

WITH RECURSIVE rec_outer AS(
  SELECT
    recO   -- тут будет лежать сразу цельная запись, чтобы не перечитывать ее повторно
  , 0 iter -- счетчик найденных записей
  FROM
    hier recO
  WHERE
    id = 10000 -- последняя прочитанная на предыдущей итерации запись
UNION ALL
  SELECT
    X.recI
  , iter + 1
  FROM
    rec_outer RO
  , LATERAL (
      -- первый потомок
      (
        SELECT
          recI
        FROM
          hier recI
        WHERE
          pid = (RO.recO).id
        ORDER BY
          ord
        LIMIT 1
      )
      UNION ALL
      -- ближайший сосед
      (
        SELECT
          recI
        FROM
          hier recI
        WHERE
          pid = (RO.recO).pid AND
          ord > (RO.recO).ord
        ORDER BY
          ord
        LIMIT 1
      )
      UNION ALL
      -- ближайший сосед ближайшего предка
      (
        WITH RECURSIVE rec_inner AS(
          SELECT
            RO.recO prnt    -- берем текущую запись в качестве "предка"
          , NULL::hier nbgh -- "соседа" у нее заведомо нет
        UNION ALL
          SELECT
            recI
          , (
              -- сработает только один из блоков с противоположными условиями
              (
                SELECT
                  nbgh_w_prnt
                FROM
                  hier nbgh_w_prnt
                WHERE
                  (RI.prnt).pid IS NOT NULL AND -- мы еще не в корне
                  pid = (RI.prnt).pid AND
                  ord > (RI.prnt).ord
                ORDER BY
                  pid, ord -- подгоняем под индекс
                LIMIT 1
              )
              UNION ALL
              (
                SELECT
                  nbgh_no_prnt
                FROM
                  hier nbgh_no_prnt
                WHERE
                  (RI.prnt).pid IS NULL AND     -- уже в корне
                  pid IS NULL AND
                  ord > (RI.prnt).ord
                ORDER BY
                  pid, ord -- подгоняем под индекс
                LIMIT 1
              )
              LIMIT 1
            )
          FROM
            rec_inner RI
          INNER JOIN
            hier recI
              ON recI.id = (RI.prnt).pid -- рекурсивный обход "вверх" по иерархии
        )
        SELECT
          nbgh
        FROM
          rec_inner
        WHERE
          nbgh IS DISTINCT FROM NULL
        LIMIT 1
      )
      LIMIT 1
    ) X
  WHERE
    X.recI IS DISTINCT FROM NULL AND
    iter < 20 -- количество записей на странице
)
SELECT
  (recO).*  -- разворачиваем поля записи
FROM
  rec_outer
WHERE
  iter > 0; -- убираем "стартовую" запись

Ztare
29.06.2022 12:36
#24482722
Сначала строим структуру под бесконечную вложенность — потом страдаем от наркомании в запросах. Решается вынесением в колонки ид каждого уровня, или обработкой уже после материализации. Да звучит не гибко, но выигрыш настолько огромный, что я рекомендовал бы всегда пробовать ограничить вложенность и распихать каждый уровень в свою колонку. В реальной жизни неограниченная вложенность нужна крайне редко (почти никогда), и там где она все же есть обычно выгодно пользоваться не реляционными хранилищами.
1. Kilor Автор
  29.06.2022 12:43
  #24482752
  +1
  В реальной жизни неограниченная вложенность нужна крайне редко (почти никогда)
  
  Расскажите это одному из наших клиентов с 60 уровнями вложенности в справочнике сотрудников. )) Понятно, что и самих сотрудников там не сотня.
  1. Ztare
    29.06.2022 13:13
    #24482876
    Но их и не миллионы, можно или все материализовывать или вынести часть уровней в колонки. Всяко лучше той дичи которую приходится городить натягивая сову на глобус, т.е. выражая запросы по дереву в sql
    
    Kilor Автор
    29.06.2022 13:21
    #24482902
    +1
    Тогда дичь придет с другой стороны, и для работы с разными уровнями иерархии придется либо делать автогенерируемые запросы, что сразу отсекает возможность использования prepared statement, либо костылить еще похлеще, сразу сворачивая все известные поля "уровней" в массив.
    
    Тогда уж проще по-честному использовать Materialized Path без лишних ограничений, но не факт, что жить с ним будет сильно удобнее.
  1. Ztare
    29.06.2022 13:23
    #24482904
    И чуть дополню. Обычно если ктото настаивает на большой вложенности, то возможно она проистекает из визуализации, а не из реальной структуры нужной в рассчетах запросов. Например 60 уровней сотрудников это 3-4 уровня на стороне бухгалтерии. 1 холдинг - 2 компания - 3 подразделение - 4 отдел
    
    Kilor Автор
    29.06.2022 13:31
    #24482934
    Обычно даже не из визуализации, а из непонимания, как решить какую-то задачу иначе.
    
    Например, хочется выделить начальника отдела, и создается структура с лишним узлом:
    
    -- Отдел -- ФИО начальник -- Сотрудники отдела -- ФИО подчиненный 1 -- ФИО подчиненный 2
    
    Как минимум, можно ведь сказать, что начальник в списке всегда первый, и сэкономить уровень иерархии:
    
    -- Отдел -- ФИО начальник (*) -- ФИО подчиненный 1 -- ФИО подчиненный 2
    
    Но иногда это бывает изменить "долго и дорого", особенно при всяких интеграционных проектах, когда нет возможности повлиять на исходную систему.
  1. mayorovp
    29.06.2022 13:33
    #24482938
    Но сотрудников и не нанимают-увольняют сотнями в секунду, эта таблица изменяется крайне редко. А потому её можно переделать в Nested Sets и вовсе забыть о рекурсивных запросах.
    
    Kilor Автор
    29.06.2022 13:46
    #24482994
    Если взять какой-нибудь условный Газпром с 500K сотрудников и текучкой на уровне хотя бы 15%/год, то это получится больше 300 человек/день - а Nested Sets очень не любят изменения структуры дерева.
    
    CoffinNail
    29.06.2022 13:50
    #24483010
    Я построил web-систему на nodejs с нуля (в терминах явы) и база (mysql) используется для хранения деревьев. Несколько лет перебирал варианты в поисках наилучшего и нашел - только тупо в лоб.
    
    mayorovp
    29.06.2022 13:54
    #24483018
    Можно вынести группирующие узлы в отдельную таблицу (отделы/группы) и применить Nested Sets для них.
    
    Или просто резервировать по 1000 слотов для каждого отдела.

ABHuman
30.06.2022 09:12
#24485096
Хочу сказать, что ваша статья кое-кому помогла (вернее, уже цикл статей) и вы не зря старались. Спасибо!
1. Kilor Автор
  30.06.2022 11:15
  #24485512
  Посмотрите по оглавлению в профиле - может, еще что интересное найдете.

Nick2022
30.06.2022 09:22
#24485118
Для чего в запросе удаления дублирующихся строк сначала разбивать массив на последовательность строк, затем снова собирать это в массив?

Массив можно сразу передать в ANY, а чтобы Postgres не считал подзапрос полседовательностью массивов, в которой нужно найти ctid, результат подзапроса можно кастануть:
```
DELETE FROM
  hier
WHERE
  ctid = ANY((
    SELECT
      (array_agg(ctid))[2:]
    FROM
      hier
    GROUP BY
      pid, ord
    HAVING
      count(*) > 1
  )::tid[]);
```
1. Kilor Автор
  30.06.2022 09:23
  #24485120
  В таком виде запрос перестает работать при наличии хотя бы двух дублирующихся пар:
  
  CREATE TABLE hier_test AS SELECT * FROM ( VALUES (1, 1) , (1, 1) , (2, 2) , (2, 2) ) T(pid, ord); DELETE FROM hier_test WHERE ctid = ANY(( SELECT (array_agg(ctid))[2:] FROM hier_test GROUP BY pid, ord HAVING count(*) > 1 )::tid[]); -- ERROR: more than one row returned by a subquery used as an expression