🙏 Нам нужна ваша помощь! SQLtest.online без рекламы и живёт только на донаты. Даже небольшая сумма помогает. Поддержать →
SQL код скопирован в буфер обмена

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

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

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

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

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

Применение рекурсивных CTE: иерархии категорий, оргструктуры, деревья меню, спецификации изделий и поиск путей на основе якорной части и рекурсивного шага

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, а не исчезают.

dayrentals
2005-05-30158
2005-05-31163
2005-06-010
......
2005-06-130
2005-06-1416
2005-06-15348

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

  • 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.

part_nametotal_quantity
Frame1
Wheel2
Rim2
Spoke72
Bolt8

Спицы: 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 км.

routetotal_km
Berlin,Prague,Vienna680
Berlin,Leipzig,Prague,Vienna770
Berlin,Leipzig,Munich,Vienna1020
Berlin,Prague,Leipzig,Munich,Vienna1430

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, которое автоматически отмечает и останавливает циклы.

Попробуйте решить следующие задачи, чтобы закрепить материал этого урока.

MySQL

  1. Создать таблицу дат
  2. Подсчитать количество выходных дней в месяце
  3. Платежи по месяцам с пустыми месяцами

DuckDB

  1. Поездки из зоны 34 по дням

Firebird

  1. Заказы по месяцам 1993 года

MariaDB

  1. Новые исследовательские проекты по месяцам

PostgreSQL

  1. Вылеты из Иванова по дням

SQLite

  1. Запуски экспериментов по месяцам

SQL Server

  1. Товары в каждом ценовом диапазоне