Как распознать иерархическую задачу в SQL

Иерархические задачи в SQL часто пугают, ведь они отличаются от обычных задач на агрегацию. Когда я впервые столкнулся с задачей LeetCode 3482, я пытался решить её с помощью известных мне конструкций: JOIN, подзапросов, GROUP BY и оконных функций. Но организация может иметь неизвестное количество уровней: сотрудник может управлять другим, тот — третьим, и так далее. Фиксированное количество JOIN может обработать только фиксированное количество уровней. Мне нужен был запрос, который мог бы двигаться по иерархии, пока не найдутся все сотрудники. Именно для этого и предназначены рекурсивные обобщённые табличные выражения (CTE).

В этой статье я объясню:

как распознать иерархическую задачу;
как работает рекурсивный CTE;
зачем включать каждого сотрудника в собственную иерархию;
как запрос вычисляет размер команды и бюджет;
почему уровень иерархии должен отсчитываться от CEO;
почему рекурсивный JOIN здесь лучше коррелированного подзапроса;
как собрать полное решение.

Моё решение прошло лучше, чем 99% принятых решений на MySQL на момент отправки. Процентили времени выполнения могут меняться, но главное — эта задача помогла мне понять, как работает рекурсивный SQL.

Простое описание задачи

У нас есть таблица Employees с информацией о менеджере и зарплате каждого сотрудника. Пример данных:

+-------------+---------------+------------+--------+-------------+
| employee_id | employee_name | manager_id | salary | department  |
+-------------+---------------+------------+--------+-------------+
| 1           | Alice         | null       | 12000  | Executive   |
| 2           | Bob           | 1          | 10000  | Sales       |
| 3           | Charlie       | 1          | 10000  | Engineering |
| 4           | David         | 2          | 7500   | Sales       |
| 5           | Eva           | 2          | 7500   | Sales       |
| 6           | Frank         | 3          | 9000   | Engineering |
| 7           | Grace         | 3          | 8500   | Engineering |
| 8           | Hank          | 4          | 6000   | Sales       |
| 9           | Ivy           | 6          | 7000   | Engineering |
| 10          | Judy          | 6          | 7000   | Engineering |
+-------------+---------------+------------+--------+-------------+

Для каждого сотрудника нужно определить:

его уровень в иерархии компании;
количество сотрудников в его полной команде;
общий бюджет этой команды.

Полная команда включает прямых и косвенных подчинённых. Бюджет включает зарплату самого сотрудника и зарплаты всех прямых и косвенных подчинённых.

Визуализация организации

Прежде чем писать SQL, полезно преобразовать таблицу в дерево:

Alice (1)
├── Bob (2)
│   ├── David (4)
│   │   └── Hank (8)
│   └── Eva (5)
└── Charlie (3)
    ├── Frank (6)
    │   ├── Ivy (9)
    │   └── Judy (10)
    └── Grace (7)

Из этого дерева видно:

Алиса на уровне 1.
Боб и Чарли на уровне 2.
Дэвид, Ева, Фрэнк и Грейс на уровне 3.
Хэнк, Айви и Джуди на уровне 4.

Полная команда Алисы включает всех сотрудников ниже неё. Команда Боба включает Дэвида, Еву и Хэнка. Команда Чарли включает Фрэнка, Грейс, Айви и Джуди. Это важно, потому что обычный self-join находит только одно поколение за раз. Например, один self-join может найти прямых подчинённых Боба — Дэвида и Еву, но не продолжит от Дэвида к Хэнку.

Почему обычных JOIN недостаточно

Self-join может найти прямых подчинённых:

SELECT manager.employee_id, report.employee_id AS report_id
FROM Employees AS manager
JOIN Employees AS report ON report.manager_id = manager.employee_id;

Можно добавить ещё один JOIN, чтобы найти подчинённых второго уровня:

JOIN Employees AS second_level ON second_level.manager_id = report.employee_id

Но тогда понадобится ещё один JOIN для третьего уровня, ещё для четвёртого и так далее. Такой подход предполагает, что мы заранее знаем максимальную глубину организации. Рекурсивный CTE не требует знания глубины: он многократно применяет одно и то же отношение, пока не найдутся все сотрудники.

Как работает рекурсивный CTE

Рекурсивный CTE состоит из двух частей:

WITH RECURSIVE cte_name AS (
    -- Anchor query
    UNION
    -- Recursive query
)

Anchor query создаёт начальные строки. Он отвечает на вопрос: «Где начинается рекурсия?»

Recursive query использует строки, уже созданные CTE, для поиска следующего набора строк. Он отвечает на вопрос: «Учитывая сотрудников, найденных на предыдущем шаге, кого посетить следующим?»

База данных продолжает выполнять рекурсивную часть для вновь сгенерированных строк. Рекурсия естественным образом останавливается, когда очередная итерация не даёт новых строк.

Ключевая идея моего решения

Вместо создания одной иерархии, начиная с CEO, я создаю отдельную иерархию для каждого сотрудника. Это означает: одна иерархия начинается с Алисы, другая — с Боба, третья — с Чарли, и так для каждого. Зачем? Потому что задача требует полную команду и бюджет для каждого сотрудника. Если построить только иерархию CEO, я буду знать, где все находятся глобально, но всё равно понадобится способ определить потомков каждого сотрудника. Построив иерархию для каждого сотрудника, все потомки конкретного сотрудника будут иметь одинаковый начальный employee_id. Затем можно сгруппировать по этому ID, чтобы вычислить размер команды и бюджет.

Шаг 1: Начинаем иерархию с каждого сотрудника

Anchor-запрос:

SELECT employee_id, employee_id AS reporter_id, 1 AS level, salary
FROM Employees

Полный рекурсивный CTE начинается так:

WITH RECURSIVE t AS (
    SELECT employee_id, employee_id AS reporter_id, 1 AS level, salary
    FROM Employees
    UNION
    SELECT t.employee_id, e.employee_id, t.level + 1, e.salary
    FROM t
    JOIN Employees AS e ON e.manager_id = t.reporter_id
)

Смысл колонок:

employee_id — сотрудник, для которого мы строим полную иерархию.
reporter_id — текущий человек, достигнутый внутри этой иерархии.
level — расстояние текущего человека от начального сотрудника, начальный сотрудник имеет уровень 1.
salary — зарплата текущего reporter_id.

Различие между employee_id и reporter_id — самая важная часть решения. employee_id остаётся фиксированным в пределах одной иерархии, а reporter_id меняется по мере движения вниз по рекурсии.

Для иерархии Боба строки концептуально выглядят так:

employee_id | reporter_id | level | salary
------------+-------------+-------+-------
2           | 2           | 1     | 10000
2           | 4           | 2     | 7500
2           | 5           | 2     | 7500
2           | 8           | 3     | 6000

Значение 2 остаётся фиксированным в employee_id, потому что все четыре строки принадлежат иерархии Боба. reporter_id меняется по мере посещения Боба, Дэвида, Евы и Хэнка.

Шаг 2: Понимание рекурсивного JOIN

Рекурсивная часть:

SELECT t.employee_id, e.employee_id, t.level + 1, e.salary
FROM t
JOIN Employees AS e ON e.manager_id = t.reporter_id

Для каждой текущей строки в t запрос ищет в Employees людей, у которых manager_id равен текущему reporter_id. Предположим, текущая строка в иерархии Боба:

employee_id = 2
reporter_id = 2
level       = 1

JOIN проверяет e.manager_id = 2 и находит Дэвида и Еву. Рекурсивный запрос создаёт строки:

2 | 4 | 2 | 7500
2 | 5 | 2 | 7500

Ключевая деталь: рекурсия продолжается не для одной возвращённой строки, а для каждой строки, возвращённой итерацией. Если итерация возвращает несколько строк, каждая из них участвует в следующей рекурсивной итерации. Поэтому Дэвид проверяется на наличие подчинённых, и Ева тоже. Дэвид управляет Хэнком, поэтому его строка даёт:

2 | 8 | 3 | 6000

Ева никим не управляет, её ветвь не даёт новых строк и завершается. Рекурсия продолжается независимо для каждой активной ветви, пока ни одна ветвь не сможет дать нового сотрудника. Это один из самых важных уроков: рекурсивный CTE расширяет каждую строку, возвращённую предыдущей итерацией, а не одну строку.

Шаг 3: Почему каждый сотрудник включает сам себя

В anchor-запросе я установил оба ID одинаковыми: employee_id, employee_id AS reporter_id. Это включает каждого сотрудника в его собственную иерархию. Сначала это может показаться лишним, ведь сотрудник не является собственным подчинённым. Однако это упрощает расчёт бюджета. Для Боба требуемый бюджет:

Боб     = 10000
Дэвид   =  7500
Ева     =  7500
Хэнк    =  6000
----------------
Бюджет  = 31000

Поскольку Боб уже включён в свою иерархию, бюджет вычисляется одним выражением: SUM(t1.salary). Не нужно отдельно считать зарплаты подчинённых и потом прибавлять зарплату Боба. Размер команды не должен включать самого Боба. Поскольку его иерархия содержит четыре строки, но только три подчинённых, размер команды вычисляется как COUNT(*) - 1. Это полезный паттерн: иногда намеренное включение строки упрощает одно вычисление, а небольшая корректировка делает другое вычисление правильным.

Шаг 4: Агрегация иерархии каждого сотрудника

После того как рекурсивный CTE сгенерировал все иерархии, следующий запрос вычисляет размер команды и бюджет для каждого сотрудника:

SELECT t1.employee_id, e.employee_name,
       COUNT(*) - 1 AS team_size,
       SUM(t1.salary) AS budget
FROM t AS t1
JOIN Employees AS e ON t1.employee_id = e.employee_id
GROUP BY t1.employee_id, e.employee_name

Для каждого начального employee_id:

COUNT(*) - 1 считает всех прямых и косвенных подчинённых.
SUM(t1.salary) складывает зарплату начального сотрудника и всех потомков.
JOIN получает имя начального сотрудника.

Для Боба результат:

employee_id | employee_name | team_size | budget
------------+---------------+-----------+-------
2           | Bob           | 3         | 31000

Для Чарли иерархия содержит Чарли, Фрэнка, Грейс, Айви и Джуди:

Чарли  = 10000
Фрэнк  =  9000
Грейс  =  8500
Айви   =  7000
Джуди  =  7000
----------------
Бюджет = 41500

У Чарли четыре подчинённых, поэтому его агрегированные значения:

employee_id | employee_name | team_size | budget
------------+---------------+-----------+-------
3           | Charlie       | 4         | 41500

Шаг 5: Тонкая проблема с уровнем

Рекурсивный CTE создаёт иерархию, начиная с каждого сотрудника. В результате значение level является относительным к начальному сотруднику. Например, допустимые строки в разных иерархиях:

employee_id | reporter_id | level
------------+-------------+------
1           | 4           | 3
2           | 4           | 2
4           | 4           | 1

Все три строки относятся к Дэвиду как reporter_id = 4, но описывают его с разных начальных точек:

Дэвид на уровне 3 с точки зрения Алисы.
Дэвид на уровне 2 с точки зрения Боба.
Дэвид на уровне 1 с его собственной точки зрения.

Для задачи требуется уровень сотрудника в иерархии компании, то есть расстояние от CEO. Поэтому нельзя использовать level из рекурсивного CTE напрямую. Нужно вычислить уровень отдельно, например, с помощью отдельного рекурсивного CTE, который начинается с CEO (у которого manager_id равен NULL), и распространяется вниз. В этом случае уровень будет абсолютным: CEO на уровне 1, его прямые подчинённые на уровне 2 и так далее. Это можно сделать так:

WITH RECURSIVE levels AS (
    SELECT employee_id, 1 AS level
    FROM Employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, l.level + 1
    FROM levels l
    JOIN Employees e ON e.manager_id = l.employee_id
)
SELECT * FROM levels;

Затем этот уровень можно объединить с основным запросом, чтобы получить итоговый результат.

Почему рекурсивный JOIN, а не коррелированный подзапрос

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

Полное решение

Собираем всё вместе. Сначала рекурсивный CTE для иерархий, затем агрегация, затем отдельный CTE для уровней, и наконец объединение. Вот полный запрос:

WITH RECURSIVE t AS (
    -- Начинаем с каждого сотрудника как с корня
    SELECT employee_id, employee_id AS reporter_id, 1 AS level, salary
    FROM Employees
    UNION
    -- Находим подчинённых
    SELECT t.employee_id, e.employee_id, t.level + 1, e.salary
    FROM t
    JOIN Employees AS e ON e.manager_id = t.reporter_id
),
levels AS (
    -- Вычисляем уровень от CEO
    SELECT employee_id, 1 AS level
    FROM Employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, l.level + 1
    FROM levels l
    JOIN Employees e ON e.manager_id = l.employee_id
)
SELECT e.employee_id, e.employee_name, l.level,
       COUNT(t.reporter_id) - 1 AS team_size,
       SUM(t.salary) AS budget
FROM Employees e
JOIN levels l ON e.employee_id = l.employee_id
LEFT JOIN t ON t.employee_id = e.employee_id
GROUP BY e.employee_id, e.employee_name, l.level
ORDER BY e.employee_id;

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

Практический вывод

Теперь вы знаете, как распознать иерархическую задачу и как применить рекурсивный CTE. Попробуйте решить задачу LeetCode 3482 самостоятельно, используя описанный подход. Начните с простого: постройте рекурсивный CTE, который находит всех подчинённых для одного сотрудника, затем расширьте его на всех сотрудников. Это отличная практика для закрепления материала. Удачи!

Решение иерархических задач SQL с помощью рекурсивных CTE