Рекурсия на сервере: как Интеграм обходит деревья и графы одним запросом

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

Интеграм умеет иначе: обойти всю структуру вглубь и сразу её отсортировать — за один серверный вызов.

Откуда берётся рекурсия

Движок отчётов Интеграма опирается на нативный механизм MySQL WITH RECURSIVE — стандартный способ писать рекурсивные запросы прямо в СУБД. Поверх него работает композиция: запись вида [имя_отчёта] подставляет один сохранённый отчёт внутрь другого как подзапрос. Вы собираете сложный обход из простых кирпичиков-отчётов, а сервер разворачивает его в один SQL-запрос. Никакого отдельного «движка обхода» и никакой выгрузки промежуточных уровней в приложение.

Как именно это делается: функция RECURSIVE

Рекурсия в Интеграме — это не отдельный тип объекта и не скрипт, а одна настройка обычной колонки запроса.

Шаг 1. Колонка с функцией RECURSIVE

В редакторе запроса у каждой колонки есть поле «Функция» — тот же список, откуда берутся SUM, COUNT, abn_ID. Среди них есть значение RECURSIVE. Поставьте его на первую колонку запроса, и движок перестаёт собирать для этого запроса обычный SELECT с джойнами — он целиком заменяет его рекурсивным CTE. Именно поэтому рекурсивный запрос делают маленьким и отдельным: у него ровно одна колонка, и его единственная работа — вернуть список ID обойдённых записей.

Источник этой колонки (поле «Таблица/реквизит») задаёт, что обходим: таблицу, по которой пойдёт спуск, или ссылочный реквизит, по которому пойдёт обход графа.

Шаг 2. Зерно — откуда начинать

Обход должен с чего-то начаться. Стартовый набор («зерно») задаётся полем колонки «Значение (от)», и вариантов три:

• [имя_другого_отчёта] — зерном становится результат вложенного запроса. Движок собирает SQL подзапроса (не выполняя его) и подставляет условие AND id IN (…). Это основной рабочий вариант.
• внешний фильтр в URL — report/{имя}?FR_{имя_колонки}={значение}: зерно приходит параметром вызова.
• пусто — зерном становится вся таблица.

Шаг 3. Что движок пишет в SQL

Здесь помогает устройство хранилища: все записи всех таблиц Интеграма лежат в одной физической таблице с колонками id, up (родитель), t (тип), val (значение). Поэтому один и тот же шаблон CTE работает для любого дерева и любого графа — меняется только шаг рекурсии.

Вариант А — дерево подчинённых таблиц (запись подчинена записи, спуск от родителя к детям):

-- ateh — таблица объектов базы (она называется по имени самой базы),
-- 151 — тип «Меню»
WITH RECURSIVE c AS (
    SELECT id, 0 t FROM ateh
     WHERE t = 151 AND up != 0 AND t != up AND val != ''
       AND id IN ( /* SQL вложенного запроса-зерна */ )
  UNION
    SELECT ref.id id, ref.t FROM ateh ref
     INNER JOIN c ON c.id = ref.up      -- дети тех, кто уже в наборе
     WHERE ref.t = 151
     LIMIT 80
)
SELECT DISTINCT id 'Меню' FROM c

Вариант Б — граф по ссылочному реквизиту (от записи к тем, что связаны с ней ссылкой). Отличается только шагом рекурсии — якорь и обёртка те же:

  UNION
    SELECT ref.up id, ref.t FROM mem ref
     INNER JOIN c ON c.id = ref.t       -- связанные ссылкой с тем, кто уже в наборе
     WHERE ref.val = '<реквизит-ссылка>'
     LIMIT 80

Первая часть CTE (до UNION) — якорь: зерно. Вторая — шаг рекурсии: он берёт то, что уже накоплено в c, и добавляет соседний слой. СУБД повторяет шаг, пока он даёт новые строки.

Шаг 4. Бюджет и защита от циклов

Две детали, которые делают это безопасным на боевых данных:

• UNION, а не UNION ALL. Дубликаты схлопываются, поэтому граф с циклами («A ссылается на B, B — обратно на A») не зацикливает обход: повторно пришедшая запись просто не добавляет новых строк.
• LIMIT внутри шага рекурсии — бюджет обхода, по умолчанию 80 записей на фронт. Переопределяется параметром ?LIMIT= при вызове. Сверху остаётся и штатный предохранитель MySQL cte_max_recursion_depth (по умолчанию 1000).

Шаг 5. Использовать результат

Рекурсивный запрос отдаёт один столбец ID — и дальше он подставляется в любой другой запрос через те же квадратные скобки: IN([rec]) в формуле, в фильтре, в условии джойна. Подстановка рекурсивна: вложенный запрос может сам содержать вложенные. На выходе получается один SQL-statement, который СУБД выполняет за один проход.

Кейс 1. Деревья: как устроено ролевое меню самого Интеграма

Лучший пример — тот, что есть в любой базе Интеграма: меню, которое пользователь видит согласно своей роли. Это три запроса, вложенные один в другой.

myMenus — зерно. Мастер-таблица «Пользователь», колонка отфильтрована по [USER_ID] (текущий пользователь), дальше джойн на «Роль» и на «Меню». Колонки пользователя и роли скрыты (Скрыть = X), поэтому в SELECT остаётся ровно один столбец — то, что и нужно подзапросу:

[{"Меню":"159"},{"Меню":"167"},{"Меню":"242"},{"Меню":"267"},{"Меню":"279"},
 {"Меню":"293"},{"Меню":"295"},{"Меню":"297"},{"Меню":"320"},{"Меню":"91736"},
 {"Меню":"91739"},{"Меню":"108646"}]

Двенадцать пунктов — те, что явно выданы ролям пользователя.

rec — собственно рекурсия. Одна-единственная колонка: источник — таблица «Меню», «Значение (от)» — [myMenus], «Функция» — RECURSIVE. Всё. Этого хватает, чтобы движок сгенерировал CTE из варианта А выше:

[…те же 12…, {"Меню":"299"}, {"Меню":"328"}]

Четырнадцать. Появились 299 («Задачи») и 328 («Мои карты») — дети пункта 320 («ОРГАНАЙЗЕР»), который был в зерне. Роли выдали раздел — рекурсия добрала всё, что внутри него, на любую глубину.

MyRoleMenu — витрина. Обычный запрос над «Меню» с колонками name, menu_id (abn_ID), menu_up (abn_UP), href, icon (формат HTML) и сортировкой по abn_ORD. Отбор делает вычисляемая колонка с формулой вида

IF(МенюID IN([rec]), <проверка пользователя и роли>, <проверка пользователя и роли>)

и полем «Значение (от)» = 1: строка попадает в ответ, только если выражение истинно. Результат — готовый JSON для отрисовки меню:

[{"name":"ОРГАНАЙЗЕР","menu_id":"320","menu_up":"145","href":"","icon":"<i class=\"pi pi-inbox\"></i>"},
 {"name":"Задачи","menu_id":"299","menu_up":"320","href":"table/446","icon":""}]

Фронтенду остаётся сложить плоский список в дерево по menu_up. Ни одного дополнительного обращения к серверу: MyRoleMenu → rec → myMenus разворачиваются в один SQL.

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

Кейс 2. Графы: память по смыслу

Связи бывают не древовидными, а сетевыми — «похоже на это». На этом построен наш эксперимент IME (Integram Memory Engine): дать приложению память по смыслу прямо в рабочей базе, без отдельной векторной СУБД.

Идея в трёх шагах. Текст превращается в вектор — набор чисел, у похожих по смыслу текстов наборы похожи. Близость векторов (косинус) считает обычный отчёт Интеграма. А чтобы не сравнивать запрос с миллионами записей, у каждой записи хранятся ссылки на несколько ближайших соседей — получается граф «знакомств», и поиск идёт по нему прыжками: спроси соседа, кто ещё ближе к теме.

Вот здесь рекурсия и решает. Раньше обход графа шёл из клиента: около 82 обращений к серверу, примерно 33 секунды на один поиск. Рекурсивный отчёт собирает окрестность графа (поиск вширь до заданного бюджета) и ранжирует её косинусом в одном запросе: зерно → рекурсивное расширение → косинус → top-k.

Устроено это той же композицией из трёх запросов, что и меню, — меняется только шаг рекурсии (вариант Б: обход по ссылочному реквизиту вместо спуска по подчинённым таблицам):

1. nghbrs — зерно: прямые соседи стартовой записи, джойн по мультиссылке «сосед».
2. recursion — одна колонка, «Значение (от)» = [nghbrs], «Функция» = RECURSIVE. Обход графа вглубь до бюджета LIMIT.
3. me_ann — витрина: SELECT label, <формула косинуса> WHERE id IN([recursion]) ORDER BY score DESC LIMIT k.

Сравните с меню: MyRoleMenu → rec → myMenus. Один и тот же скелет — «зерно → рекурсия → витрина с отбором по IN([…])».

Способ обхода	Обращений к серверу	Время
обход из клиента	~82	~33 с
один рекурсивный запрос	1	~0.3 с

Это около 100× по времени. На живой базе ideav.ru/mem выигрыш индексного поиска над полным перебором растёт с объёмом: 2.1× при 60 записях → 12.7× при 5000, при точности recall@1 95–100%.

Честно про границы

Рекурсия снимает боль «обхода вглубь», но не превращает Интеграм в векторную СУБД:

• рекурсия — это сбор окрестности вширь до бюджета (LIMIT на шаге), а не жадный best-first с отсечением: качество результата зависит от того, насколько удачно выбрано зерно;
• для миллисекундных задержек на больших корпусах выделенный ANN-индекс (FAISS, Qdrant, pgvector) всё равно быстрее по константе;
• нативного векторного индекса нет — близость считается сканом по тексту, и на больших объёмах он медленнее;
• инкрементальное сопровождение рёбер графа при каждой вставке мы пока не доказали — в прототипе граф строился пакетно.

Прямые аналоги, которые умеют и рекурсию, и вектора, — это Postgres с pgvector и Neo4j. На больших объёмах они мощнее, но это отдельная инфраструктура. Ценность подхода Интеграма не в самом примитиве WITH RECURSIVE, а в композиции: вектора, рёбра, рекурсия и косинус живут в одной таблице рядом с бизнес-данными — без новой базы и без бюджета сверху.

Что забрать с собой

Рекурсивные отчёты плюс композиция [имя] превращают связи в обходимые структуры: деревья — от корня до листа, графы — от записи к её соседям, и всё это одним серверным вызовом. Для иерархий это убирает ручные джойны по уровням; для «похоже на это» — открывает память по смыслу прямо внутри приложения.

Рецепт целиком умещается в три строки:

1. отдельный запрос из одной колонки: источник — таблица или ссылка, «Значение (от)» — [запрос-зерно], «Функция» — RECURSIVE;
2. запрос-зерно, отдающий один столбец ID (лишние колонки скрываются флагом «Скрыть»);
3. запрос-витрина, который отбирает строки по IN([имя_рекурсивного_запроса]) и показывает то, что нужно пользователю.

Подробности и цифры — в репозитории эксперимента ideav/ime: на пальцах, прототип и результаты, сравнение с векторными СУБД.