Примеры рекурсивных CTE: практические задачи

Урок 6.6 · Время чтения: ~9 мин · Задачи для практики ↓

Рекурсивные CTE нужны не только для оргструктур. В этом уроке вы примените WITH RECURSIVE к четырём частым задачам: сгенерируете ряд дат, чтобы заполнить пропуски в ежедневном отчёте, посчитаете продажи по всем уровням дерева категорий, разузлуете спецификацию изделия в полный список деталей и найдёте все маршруты между двумя городами в дорожной сети с циклами.

В предыдущем уроке вы узнали, как работает рекурсивный CTE: якорная часть возвращает начальные строки, рекурсивная находит следующий уровень, а рекурсия останавливается, когда новых строк нет. Здесь тот же шаблон становится инструментом для повседневных задач. Каждый пример показывает приём, который можно использовать повторно: сгенерированную последовательность, пары «предок - потомок», перемножение количеств и путь с проверкой циклов.

Первый пример работает на учебной базе Sakila. Остальные создают собственные таблицы, поэтому запускайте их в песочнице на базе без учебных данных. Синтаксис - MySQL 8.0; он также работает в MariaDB 10.2+.

1. Ряд дат для заполнения пропусков

Отчёт «аренды по дням», построенный с GROUP BY, показывает только дни, когда аренды были. Дни без аренд просто пропадают, и график по таким данным скрывает провал. Решение - сгенерировать календарь из всех дней и присоединить к нему данные.

Календарь генерирует рекурсивный CTE: якорная часть возвращает первый день, а каждая итерация добавляет один день, пока не дойдёт до последнего:

WITH RECURSIVE calendar AS (
    SELECT DATE('2005-05-28') AS day
    UNION ALL
    SELECT day + INTERVAL 1 DAY
    FROM calendar
    WHERE day < '2005-06-16'
)
SELECT c.day, COUNT(r.rental_id) AS rentals
FROM calendar AS c
LEFT JOIN rental AS r
    ON r.rental_date >= c.day
   AND r.rental_date < c.day + INTERVAL 1 DAY
GROUP BY c.day
ORDER BY c.day;

Результат: 20 строк, по одной на каждый день с 28 мая по 16 июня 2005 года. С 1 по 13 июня аренд нет, и эти дни показывают 0, а не исчезают.

Важны три детали:

• LEFT JOIN сохраняет дни без аренд; COUNT(r.rental_id) считает только реальные аренды, поэтому у пустых дней получается 0.
• Соединение использует диапазон (>= day и < day + 1 day), а не DATE(r.rental_date) = c.day, поэтому индекс по rental_date по-прежнему может использоваться.
• Тот же шаблон генерирует любую последовательность: числа, часы, месяцы. Для ряда длиннее 1000 шагов нужно увеличить cte_max_recursion_depth.

2. Итоги по всему поддереву

В дереве категорий продажи записаны в конкретные категории, а отчёту нужны итоги по каждой ветке: «Computers» должна включать ноутбуки и настольные компьютеры, а «Electronics» - всё.

CREATE TABLE product_category (
    category_id INT PRIMARY KEY,
    parent_id INT,
    name VARCHAR(50) NOT NULL
);

INSERT INTO product_category VALUES
    (1, NULL, 'Electronics'),
    (2, 1, 'Computers'),
    (3, 1, 'Phones'),
    (4, 2, 'Laptops'),
    (5, 2, 'Desktops'),
    (6, 3, 'Smartphones');

CREATE TABLE sale (
    sale_id INT PRIMARY KEY,
    category_id INT NOT NULL,
    amount DECIMAL(10, 2) NOT NULL
);

INSERT INTO sale VALUES
    (1, 4, 1200), (2, 4, 800), (3, 5, 700),
    (4, 6, 500), (5, 6, 300), (6, 3, 150);

Приём в том, чтобы сначала построить все пары «предок - потомок». Якорная часть связывает каждую категорию с ней самой; каждая итерация добавляет детей уже найденных потомков:

WITH RECURSIVE subtree AS (
    SELECT category_id AS ancestor_id, category_id
    FROM product_category

    UNION ALL

    SELECT s.ancestor_id, c.category_id
    FROM subtree AS s
    INNER JOIN product_category AS c ON c.parent_id = s.category_id
)
SELECT a.name, SUM(sl.amount) AS total_sales
FROM subtree AS s
INNER JOIN product_category AS a ON a.category_id = s.ancestor_id
LEFT JOIN sale AS sl ON sl.category_id = s.category_id
GROUP BY a.category_id, a.name
ORDER BY a.category_id;

Результат: Electronics 3650.00, Computers 2700.00, Phones 950.00, Laptops 2000.00, Desktops 700.00, Smartphones 800.00.

Каждая продажа учитывается один раз для своей категории и по одному разу для каждого предка. «Phones» получает 950: 150 продано прямо в этой категории и 800 - в «Smartphones». Агрегация выполняется в итоговом запросе, потому что MySQL не разрешает GROUP BY и агрегатные функции в рекурсивной части.

3. Разузлование спецификации изделия

Спецификация изделия (BOM, bill of materials) перечисляет, из чего состоит продукт. У компонентов есть свои компоненты, и одна и та же деталь может встречаться в нескольких ветках. Чтобы заказать детали для одного велосипеда, нужно общее количество каждой детали:

CREATE TABLE part (
    part_id INT PRIMARY KEY,
    part_name VARCHAR(50) NOT NULL
);

INSERT INTO part VALUES
    (1, 'Bicycle'), (2, 'Frame'), (3, 'Wheel'),
    (4, 'Rim'), (5, 'Spoke'), (6, 'Bolt');

CREATE TABLE bom (
    parent_part_id INT,
    child_part_id INT,
    quantity INT NOT NULL,
    PRIMARY KEY (parent_part_id, child_part_id)
);

INSERT INTO bom VALUES
    (1, 2, 1),   -- у велосипеда 1 рама
    (1, 3, 2),   -- и 2 колеса
    (2, 6, 4),   -- у рамы 4 болта
    (3, 4, 1),   -- у колеса 1 обод
    (3, 5, 36),  -- 36 спиц
    (3, 6, 2);   -- и 2 болта

На каждом уровне количество компонента умножается на количество его родителя:

WITH RECURSIVE explosion AS (
    SELECT child_part_id AS part_id, quantity
    FROM bom
    WHERE parent_part_id = 1

    UNION ALL

    SELECT b.child_part_id, e.quantity * b.quantity
    FROM explosion AS e
    INNER JOIN bom AS b ON b.parent_part_id = e.part_id
)
SELECT p.part_name, SUM(e.quantity) AS total_quantity
FROM explosion AS e
INNER JOIN part AS p ON p.part_id = e.part_id
GROUP BY p.part_id, p.part_name
ORDER BY p.part_id;

Результат: Frame 1, Wheel 2, Rim 2, Spoke 72, Bolt 8.

Спицы: 2 колеса × 36 = 72. Болты приходят из двух веток: 4 в раме и 2 × 2 = 4 в колёсах, и SUM складывает их в 8. Чтобы получить только покупные детали, а не собираемые узлы, оставьте строки, у которых нет собственных компонентов: добавьте WHERE NOT EXISTS (SELECT 1 FROM bom AS c WHERE c.parent_part_id = e.part_id).

4. Маршруты в графе с циклами

У дерева к каждому узлу ведёт один путь. Дорожная сеть - это граф: дороги двусторонние и образуют циклы, поэтому наивная рекурсия ездила бы по кругу бесконечно. Найдём все маршруты из Берлина в Вену:

CREATE TABLE road (
    from_city VARCHAR(30),
    to_city VARCHAR(30),
    distance_km INT NOT NULL,
    PRIMARY KEY (from_city, to_city)
);

INSERT INTO road VALUES
    ('Berlin', 'Prague', 350),
    ('Berlin', 'Leipzig', 190),
    ('Leipzig', 'Prague', 250),
    ('Prague', 'Vienna', 330),
    ('Leipzig', 'Munich', 430),
    ('Munich', 'Vienna', 400);

Каждая дорога хранится один раз, поэтому обычный CTE edge сначала добавляет обратное направление. Рекурсивный CTE trip продлевает каждый маршрут на одну дорогу, пропускает города, которые уже есть в маршруте, и перестаёт продлевать маршрут, когда тот доходит до Вены:

WITH RECURSIVE edge AS (
    SELECT from_city, to_city, distance_km FROM road
    UNION ALL
    SELECT to_city, from_city, distance_km FROM road
),
trip AS (
    SELECT
        to_city AS city,
        CAST(CONCAT(from_city, ',', to_city) AS CHAR(500)) AS route,
        distance_km AS total_km
    FROM edge
    WHERE from_city = 'Berlin'

    UNION ALL

    SELECT e.to_city, CONCAT(t.route, ',', e.to_city), t.total_km + e.distance_km
    FROM trip AS t
    INNER JOIN edge AS e ON e.from_city = t.city
    WHERE FIND_IN_SET(e.to_city, t.route) = 0
      AND t.city <> 'Vienna'
)
SELECT route, total_km
FROM trip
WHERE city = 'Vienna'
ORDER BY total_km;

Результат: 4 маршрута; самый короткий - Berlin, Prague, Vienna, 680 км.

FIND_IN_SET(e.to_city, t.route) = 0 - это проверка циклов из предыдущего урока: маршрут никогда не возвращается в уже посещённый город. Обратите внимание, что WITH RECURSIVE пишется один раз, а CTE после него могут быть как обычными, так и рекурсивными.

Этот запрос перечисляет все возможные маршруты, и их число очень быстро растёт с размером сети. Для небольших графов это нормально, но в больших дорожных сетях кратчайшие пути ищут специализированными алгоритмами, например в графовых СУБД или в расширении PostgreSQL pgRouting.

Когда рекурсивный CTE - не лучший инструмент

• Глубокие деревья, которые часто читают. Если иерархию читают гораздо чаще, чем меняют, храните дополнительную структуру: материализованный путь (/1/2/4/) или таблицу замыкания (closure table) со всеми парами «предок - потомок», как CTE subtree выше, сохранённый в таблицу. Тогда поддерево - это простой JOIN без рекурсии.
• Большие графы. Перебор маршрутов растёт экспоненциально; используйте графовые алгоритмы.
• Фиксированное небольшое число уровней. Для «сотрудник и его руководитель» проще одно самосоединение (урок 5.7).

Ключевые выводы:

• Рекурсивный CTE генерирует последовательности: календарь дат, присоединённый через LEFT JOIN, заполняет пропуски в отчётах.
• Пары «предок - потомок», построенные рекурсивным CTE, позволяют считать итоги по всему поддереву.
• В спецификации изделия количества перемножаются по уровням и суммируются через GROUP BY в итоговом запросе.
• В графах с циклами храните посещённые узлы в пути и пропускайте их с помощью FIND_IN_SET().
• Агрегация - в итоговом запросе: MySQL не разрешает её в рекурсивной части.
• Для больших графов или часто читаемых деревьев рассмотрите таблицы замыкания или графовые алгоритмы.

Часто задаваемые вопросы

Как сгенерировать ряд дат в MySQL?

С помощью рекурсивного CTE: WITH RECURSIVE calendar AS (SELECT DATE('2024-01-01') AS day UNION ALL SELECT day + INTERVAL 1 DAY FROM calendar WHERE day < '2024-01-31') SELECT day FROM calendar;. В PostgreSQL есть также встроенная функция generate_series().

Как заполнить пропущенные даты в SQL-отчёте?

Сгенерируйте рекурсивным CTE календарь всех дат, затем присоедините к нему данные через LEFT JOIN и считайте столбец присоединённой таблицы, например COUNT(r.rental_id). Даты без данных получат 0, а не исчезнут.

Как посчитать итог для узла и всех его потомков?

Постройте рекурсивным CTE пары «предок - потомок»: якорная часть связывает каждый узел с ним самим, а рекурсивная добавляет детей каждого потомка. Затем присоедините значения к потомкам и сгруппируйте по предку.

Как избежать циклов при обходе графа рекурсивным CTE?

Храните путь из посещённых узлов в строковом столбце и добавьте в рекурсивную часть условие вида FIND_IN_SET(next_node, path) = 0. В PostgreSQL 14+ есть также предложение CYCLE, которое автоматически отмечает и останавливает циклы.