Ответ на вопрос.

История вопроса.

Иерархические модели данных традиционно используют списки смежности или вложенные наборы для представления структур деревьев. В то время как списки смежности минимизируют хранилище и упрощают вставку, аналитическая отчетность часто требует "материализованных путей" (например, "Корень/Категория/Подкатегория"), чтобы обеспечить эффективную фильтрацию с помощью префиксных шаблонов. До SQL:1999 выравнивание этих иерархий требовало процедурных курсоров или рекурсии на стороне приложения. Введение рекурсивных Общественных Таблиц Выражений (CTE) в стандарт ANSI SQL позволило декларативное прохождение, но построение детерминированных, упорядоченных путей с ограничениями по глубине вводит сложности в отношении окончания рекурсии и устойчивости сортировки.

Проблема.

Необходимо преобразовать рекурсивный список смежности в денормализованный формат, в котором каждая строка содержит полное родословное параллельное в виде разделённой строки (например, "/A/B/C"). Решение должно накладывать три ограничения: (1) братья на каждом уровне должны появляться в лексикографическом порядке в пределах пути, (2) прохождение не должно превышать заданную максимальную глубину, чтобы предотвратить вызовы без конца на некорректных данных, и (3) реализация должна использовать строго синтаксис ANSI SQL без проприетарных расширений иерархии.

Решение.

Решение использует подход с двухступенчатым CTE. Во-первых, не рекурсивный CTE вычисляет ординальную позицию каждого узла среди его братьев, используя оконную функцию. Это предварительное вычисление необходимо, потому что ANSI SQL запрещает оконные функции в рекурсивном члене CTE для обеспечения монотонного окончания. Во-вторых, рекурсивный CTE проходит по дереву, конкатенируя имена узлов и заранее рассчитанные ключи сортировки, применяя ограничение по глубине и необязательное обнаружение циклов в предложении WHERE.

WITH RECURSIVE 
OrderedNodes AS (
  -- Этап 1: Назначить детерминированный порядок братьям
  SELECT 
    node_id, 
    parent_id, 
    node_name,
    ROW_NUMBER() OVER (PARTITION BY parent_id ORDER BY node_name, node_id) AS sibling_order
  FROM taxonomy
),
PathBuilder AS (
  -- Якорный член: Инициализировать корневые узлы
  SELECT 
    node_id,
    node_name,
    1 AS depth,
    CAST(node_name AS VARCHAR(1000)) AS materialized_path,
    CAST(sibling_order AS VARCHAR(100)) AS sort_key
  FROM OrderedNodes
  WHERE parent_id IS NULL
  
  UNION ALL
  
  -- Рекурсивный член: Добавить детей
  SELECT 
    c.node_id,
    c.node_name,
    p.depth + 1,
    p.materialized_path || '/' || c.node_name,
    p.sort_key || '.' || CAST(c.sibling_order AS VARCHAR(100))
  FROM OrderedNodes c
  INNER JOIN PathBuilder p ON c.parent_id = p.node_id
  WHERE p.depth < 5  -- Строгое ограничение по глубине
    AND p.materialized_path NOT LIKE '%/' || c.node_name || '%'  -- Защита от циклов
)
SELECT 
  node_id, 
  materialized_path,
  depth
FROM PathBuilder
ORDER BY sort_key;

Ситуация из жизни

Описание проблемы.

Глобальная платформа электронной коммерции поддерживает таксономию продукции с более чем 100 000 категориями в базе данных PostgreSQL (режим соответствия стандартам ANSI SQL). Команда маркетинга требует ежедневного экспорта в CSV для внешней рекламной платформы, которая ожидает полностью квалифицированных категорий путей (например, "Электроника/Компьютеры/Ноутбуки") с строго алфавитным порядком на каждом уровне для обеспечения последовательного таргетирования аудитории. Существующее решение использовало скрипт Python, который выполнял N+1 запросов, что привело к времени выполнения в 20 минут и частым таймаутам.

Разные решения, которые рассматривались.

Решение A: Кэширование на стороне приложения с запланированным восстановлением. Команда рассматривала возможность материализовать пути в кэше Redis через фоновую задачу каждые 6 часов. Плюсы включали простую реализацию на Python и снижение нагрузки на базу данных в часы пик. Однако недостатками были значительная устаревшая информация (до 6 часов), сложность недействительного кэша при изменении структуры категорий и чрезмерное потребление памяти для полного дерева.

Решение B: Представление базы данных с использованием рекурсивного CTE. Этот подход создает представление, которое вычисляет пути по требованию, используя паттерн рекурсивного CTE ANSI SQL. Плюсы включают гарантированную свежесть данных (результаты в реальном времени), единый источник правды и использование оптимизатора запросов базы данных для соединений. Недостатками являются высокая нагрузка на CPU на сервере базы данных и риск бесконечной рекурсии, если данные содержат циклические ссылки (например, категория случайно связана со своим собственным потомком).

Решение C: Поддерживаемая триггером материализованная колонка. Это добавит колонку materialized_path в таблицу и обновит её через триггеры при вставке, обновлении или удалении. Плюсы включают исключительно быструю скорость чтения (простое индексированное сканирование). Недостатками являются значительная нагрузка на запись, сложная логика триггера для обработки перемещений или переименований поддеревьев, и сложность поддержания ограничения лексикографического порядка при изменении имён братьев.

Выбранное решение и результат.

Команда выбрала Решение B (Рекурсивное представление CTE), поскольку рабочая нагрузка, ориентированная на чтение (соотношение 100:1 чтение к записи), выиграла от вычисления по запросу без нагрузки на сопровождение триггеров. Чтобы минимизировать риск цикла, они реализовали проверку шаблона LIKE в предложении WHERE и добавили ограничение по глубине в 5 уровней на основе бизнес-правил. Они также создали составной индекс на (parent_id, node_name), чтобы оптимизировать сортировку оконной функции в якорном CTE. Результат свёл время экспорта с 20 минут до 8 секунд, одновременно обнаружив и изолировав 3 циклические ссылки в устаревших данных в ходе этапа развертывания.

Что кандидаты часто упускают

Почему не могут агрегатные или оконные функции появляться в рекурсивном члене CTE, и как это влияет на сортировку братьев?

Стандарты ANSI SQL ограничивают рекурсивный член от содержащих агрегатных функций (таких как SUM) или оконных функций (таких как ROW_NUMBER), чтобы гарантировать монотонность рекурсивного запроса и обеспечить его достижение фиксированной точки. Оконные функции требуют материализации и разделения всего рабочего набора, что может нарушить семантику потоковой передачи, необходимую для окончания рекурсии, и может вводить недетерминированность. Следовательно, нельзя рассчитывать сортировку братьев динамически в пределах рекурсии. Правильный подход — предварительно рассчитывать ординальные позиции в отдельном не рекурсивном CTE (как показано в решении), а затем ссылаться на этот вычисленный столбец в рекурсивном соединении. Кандидаты часто пытаются разместить ROW_NUMBER() непосредственно в рекурсивном SELECT, что приводит к синтаксическим ошибкам или непредсказуемым.execution plans.

Как вы обрабатываете циклические ссылки в иерархии без проприетарного синтаксиса обнаружения циклов, такого как оператор CYCLE PostgreSQL?

Чистый ANSI SQL не предоставляет встроенный механизм обнаружения циклов CYCLE (хотя SQL:2023 ввёл операторы CYCLE и SEARCH, они ещё не широко внедрены). Чтобы предотвратить бесконечную рекурсию, необходимо вручную отслеживать посещенные узлы. Стандартная переносимая техника включает накопление разделённой строки идентификаторов посещенных узлов (или массива, если поддерживается) и проверку, существует ли текущий node_id уже в этом аккумуляторе, прежде чем продолжить. Использование предиката, такого как WHERE p.materialized_path NOT LIKE '%/' || c.node_id || '%', эффективно отсеивает циклы, хотя этот метод предполагает разумные ограничения по глубине, чтобы предотвратить переполнение длины строки. В качестве альтернативы можно использовать битовую строку или хешированный путь для больших наборов данных.

Что обеспечивает детерминированный порядок, когда два узла-соседа имеют одинаковые имена, и почему полный порядок критичен для материализованных путей?

Детерминированность основывается на установлении полного порядка среди братьев. Если оконная функция использует только ORDER BY node_name и два соседа имеют одинаковое имя, база данных может вернуть их в любом порядке (определение реализации), что приводит к недетерминированным строкам пути в разных выполнениях запроса или версиях базы данных. Эта недетерминированность разрушает кэширование результатов запросов, усложняет тестирование и может вызвать "дрожащие" данные в downstream системах. Решение заключается в добавлении уникального показателя для разрешения Tie, обычно это первичный ключ node_id, к предложению ORDER BY: ORDER BY node_name, node_id. Это гарантирует, что každый брат имеет уникальную ординальную позицию, что обеспечивает воспроизводимость и стабильность материализованного пути и вспомогательный sort_key.