Рекурсивный WITH

Зачем нужен WITH RECURSIVE

Обычный WITH считает таблицу один раз. WITH RECURSIVE дописывает в неё строки, пока находятся новые: подчинённый подчинённого, следующий месяц, следующий узел дерева.

На учебной базе интернет-магазина дерева нет. Здесь берём базу Команда: у сотрудника есть manager_id — ссылка на руководителя.

SELECT e.id, e.name, m.name AS manager
FROM employees e
LEFT JOIN employees m ON m.id = e.manager_id
ORDER BY e.id;

Прямой JOIN по manager_id даёт только один уровень. Чтобы взять и Анну, и Тимура под Павлом, запрос должен спускаться по дереву сам.

Якорь и шаг

Рекурсивный WITH всегда из двух частей, склеенных UNION ALL.

WITH RECURSIVE имя AS (
  -- якорь: первые строки, без обращения к имени
  SELECT ...
  UNION ALL
  -- шаг: читает уже собранные строки и дописывает новые
  SELECT ... FROM имя ...
)
SELECT * FROM имя;

Якорь выполняется один раз. Шаг повторяется: каждый проход видит строки, которые добавили на предыдущем. Когда шаг не возвращает ни одной строки — конец.

Самый короткий пример — ряд чисел. Якорь даёт 1. Шаг прибавляет 1, пока не станет 4.

WITH RECURSIVE n AS (
  SELECT 1 AS x
  UNION ALL
  SELECT x + 1
  FROM n
  WHERE x < 4
)
SELECT x FROM n ORDER BY x;

Если забыть WHERE x < 4, шаг никогда не остановится. PostgreSQL оборвёт запрос по лимиту рекурсии, но в решении нужен явный конец: условие на шаге или соединение, которое в какой-то момент не находит строк.

Поддерево

Все, кто входит в команду Павла Чернова на любом уровне, кроме него самого. depth — сколько шагов вниз от Павла.

Якорь: люди, у которых manager_id — это Павел (id = 2). Это глубина 1: Анна Ким, Олег Сафин, Дмитрий Немов.

Шаг: люди, чей руководитель уже лежит в tree. Сначала так находится Мария Лосева (руководитель Олег) — глубина 2. Затем Тимур Волков (руководитель Мария) — глубина 3. У Тимура подчинённых нет — шаг пустой, конец.

WITH RECURSIVE tree AS (
  SELECT id, name, 1 AS depth
  FROM employees
  WHERE manager_id = (
    SELECT id FROM employees WHERE name = 'Павел Чернов'
  )
  UNION ALL
  SELECT e.id, e.name, t.depth + 1
  FROM employees e
  JOIN tree t ON e.manager_id = t.id
)
SELECT id, name, depth
FROM tree
ORDER BY depth, name;

По шагам:

• якорь: Анна, Дмитрий, Олег — глубина 1
• проход 1: Мария (руководитель Олег) — глубина 2
• проход 2: Тимур (руководитель Мария) — глубина 3
• проход 3: никого с manager_id = 13

Анна и Дмитрий листьев не дают: в таблице нет строк с их id в manager_id.

Путь по дереву

Якорь можно начать с главы компании: manager_id IS NULL — Ирина Белова. На шаге к пути руководителя добавляют имя подчинённого.

WITH RECURSIVE chain AS (
  SELECT id, name, name::text AS path, 0 AS depth
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT e.id, e.name, c.path || ' > ' || e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth, path
FROM chain
WHERE id IN (1, 2, 4, 5, 9, 13)
ORDER BY depth, id;

name::text в якоре нужен, чтобы тип колонки path был текстом: иначе PostgreSQL может не склеить его с || на шаге.

Максимальная глубина в этой базе — 4, и это только Тимур. Лист ближе к корню (Анна, глубина 2) максимальной глубиной не является.

Всё вместе

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

WITH RECURSIVE chain AS (
  SELECT id, name, 0 AS depth
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth
FROM chain
WHERE depth = (SELECT MAX(depth) FROM chain)
ORDER BY name;

Размер команды Павла — число строк в его поддереве, без него самого. Это те же пять человек, что в разделе про поддерево: 3 на глубине 1, плюс Мария и Тимур.

В учебной базе циклов нет: никто не является руководителем своего начальника. Если бы цикл был, шаг крутился бы бесконечно. Защита — не наступать на id, который уже есть в пути, или ограничить WHERE t.depth < 20.

Коротко: якорь даёт старт, шаг дописывает соседей через JOIN … ON потомок.manager_id = уже_найден.id, пока соединение не опустеет. Самого корня в поддереве нет, если якорь берёт только его прямых подчинённых.

На этом набор операторов из SQL-задач zedcode в справочнике закрыт.