Рекурсивные CTE: цепочки приглашений и иерархии

Бран · продюсер MMORPG «Хроники Пограничья»

Хочу награждать тех, кто приводит друзей. Но не только за прямых: если твой друг позвал своего, это тоже твоя заслуга. Кто у нас главный вербовщик? И сколько денег принесли все эти цепочки?

В players есть поле invited_by: id игрока, который прислал приглашение. Приглашённых в базе 459. Кто пригласил игрока напрямую, мы найдём соединением таблицы с самой собой, как в уроке про self join. А кто пригласил пригласившего? Ещё одно соединение. А дальше? Сколько соединений писать, если глубину цепочек мы не знаем заранее?

Письмо по цепочке

Помнишь письма «перешли десяти друзьям»? Ты получил письмо и разослал его. Каждый получатель разослал своим. Чтобы найти всех, до кого дошло твоё письмо, ты не пишешь план на десять шагов. Ты повторяешь одно действие: «кто получил письмо от тех, кого я нашёл на прошлом шаге?» И останавливаешься, когда новых имён нет.

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

WITH RECURSIVE days AS (
  SELECT date '2026-06-01' AS day       -- якорь: с чего начать
  UNION ALL
  SELECT day + 1                         -- шаг: следующий день
  FROM days
  WHERE day < date '2026-06-07'          -- условие остановки
)
SELECT day FROM days;

    day
------------
 2026-06-01
 2026-06-02
 ...
 2026-06-07

Три части, и у каждой своя роль:

1. Якорь стоит до UNION ALL и выполняется один раз. Он даёт первую строку, 1 июня.
2. Рекурсивная часть стоит после UNION ALL и ссылается на сам CTE days. Но видит она не всё, что накопилось, а только строки прошлого шага. На первом шаге это 1 июня, и она возвращает 2 июня. На втором видит 2 июня и возвращает 3-е.
3. Остановка: когда рекурсивная часть не вернула ни одной строки, всё заканчивается. Здесь её обеспечивает WHERE day < date '2026-06-07': от 7 июня новый день уже не родится.

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

Цепочки приглашений

Теперь игроки. Якорь: все, кого никто не приглашал, это корни цепочек. Шаг: игроки, которых пригласили найденные на прошлом шаге.

WITH RECURSIVE chain AS (
  SELECT id, id AS root_id, 0 AS depth, nickname AS path
  FROM players
  WHERE invited_by IS NULL

  UNION ALL

  SELECT p.id, c.root_id, c.depth + 1, c.path || ' > ' || p.nickname
  FROM chain c
  JOIN players p ON p.invited_by = c.id
)
SELECT depth, count(*) AS players
FROM chain
GROUP BY depth
ORDER BY depth;

 depth | players
-------+---------
     0 |    3633
     1 |     398
     2 |      56
     3 |       4
     4 |       1

Каждая строка рекурсивной части несёт с собой root_id предка без изменений, глубину увеличивает на единицу, а к пути path дописывает ник. Остановку здесь писать не нужно: на пятом шаге приглашённых у найденных игроков не нашлось, и рекурсия кончилась сама.

Самая длинная цепочка в пять человек, путь единственного игрока на глубине 4:

StoneRaven > HawkHawk > bear_garan > IronNight > MoonBlade

Сравни с решением одним соединением: оно правильно назовёт корень только 398 игрокам, приглашённым самим корнем. Ещё 61 игроку оно припишет в корни промежуточного пригласившего.

Дерево каждого пригласившего

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

WITH RECURSIVE tree AS (
  SELECT invited_by AS inviter_id, id AS player_id, 1 AS depth
  FROM players
  WHERE invited_by IS NOT NULL

  UNION ALL

  SELECT t.inviter_id, p.id, t.depth + 1
  FROM tree t
  JOIN players p ON p.invited_by = t.player_id
)
SELECT t.inviter_id, pl.nickname,
       count(*) AS tree_players,
       count(*) FILTER (WHERE t.depth = 1) AS direct
FROM tree t
JOIN players pl ON pl.id = t.inviter_id
GROUP BY t.inviter_id, pl.nickname
ORDER BY tree_players DESC, t.inviter_id
LIMIT 3;

 inviter_id |  nickname  | tree_players | direct
------------+------------+--------------+--------
          2 | Rianash    |            5 |      3
       3367 | STORM23    |            5 |      2
       2423 | StoneRaven |            4 |      1

У 429 пригласивших 526 игроков в деревьях. Rianash пригласил троих, а с их друзьями привёл пятерых. StoneRaven позвал одного, но этот один начал ту самую цепочку длиной четыре.

Деньги к дереву присоединяй осторожно. Если соединить дерево с покупками построчно и посчитать count(*), игрок с пятью покупками войдёт в дерево пять раз: это размножение строк. Сначала сверни покупки до игрока, потом присоединяй. Так выходит, что 459 приглашённых принесли 99 185 ₽ чистой выручки, 15,1% всей выручки игры, и платят из них 58 человек.