← назад к разделу

При выборе между реляционной и документной моделью правило простое: дерево, которое всегда читается целиком, — это документ; связанные сущности, которые надо соединять, — это таблицы. Но есть третий случай, о котором вспоминают реже: данные, где связей «многие-ко-многим» становится больше, чем самих сущностей. Люди знакомы с людьми, работают в компаниях, ходят на события; товары связаны с товарами («покупают вместе»); счета переводят деньги на счета. Это граф — и вопрос в том, чем его хранить и как по нему ходить.

обход вглубь: A → B → C → D WITH RECURSIVE: каждый шаг — соединение и новый поиск в индексе orders A B C D индекс orders(parent_order_id) A 1B 2C 3D глубже на шаг → ещё одно соединение и ещё один поиск в индексе графовая СУБД: индекс один раз, дальше — прямые ссылки на соседей индекс A B C D индексA Bсосед лежит рядом с узлом — в индекс не заходим C D глубже на шаг → ещё один переход по ребру, индекс уже не нужен

Цепочка одна и та же, а счёт разный. Рекурсивный запрос на каждом шаге делает соединение и заново ищет детей в индексе: ещё уровень вглубь — ещё один поиск, и каждый такой поиск тем дороже, чем больше таблица. Графовая СУБД тратит индекс один раз, на старт, а дальше идёт по прямым ссылкам от узла к соседям — её цена складывается из числа пройденных рёбер, а не из размера базы.

Обязательно

Как понять, что ваши данные — граф

Два признака, и оба они про запросы, а не про то, как данные лежат:

  • Запросы «на N шагов вглубь», где N заранее неизвестен. «Все подкатегории категории на любую глубину», «все, кто под этим руководителем по цепочке», «есть ли путь от счёта А к счёту Б через цепочку переводов». В обычном SQL количество JOIN-ов фиксируется в момент написания запроса; а здесь оно зависит от самих данных.
  • Связи разнотипные и живут своей жизнью. В графе соцсети рёбра «дружит», «работает в», «комментировал» соединяют вершины разных типов, да ещё и у самих рёбер есть свойства (с какого года дружат, в какой должности работает). Когда связи такие, таблица связей перестаёт быть скучной технической деталью и становится главным содержимым базы.

Если у вас только первый признак и одна-две иерархии — граф не нужен, хватит рекурсивного SQL. Если оба, да ещё и запросы по связям — это ядро продукта, читайте дальше.

Иерархия в PostgreSQL: adjacency list + WITH RECURSIVE

Самый простой способ хранить дерево — список смежности (adjacency list): каждая строка просто ссылается на своего родителя. В песочнице так устроены заказы-замены: parent_order_id ведёт на заказ, вместо которого оформили этот.

CREATE TABLE orders (
    id              varchar(36) PRIMARY KEY,
    parent_order_id varchar(36) REFERENCES orders (id),
    total_amount    numeric(15, 2) NOT NULL
);

Обычным JOIN-ом всю ветку не достать — глубина заранее неизвестна. Для этого в SQL есть рекурсивный запрос (рекурсивное обобщённое табличное выражение, CTE):

живой пример

WITH RECURSIVE subtree AS (
    SELECT id, parent_order_id, total_amount, 1 AS depth
    FROM orders
    WHERE id = 'ord-11'                             -- корень цепочки

    UNION ALL

    SELECT o.id, o.parent_order_id, o.total_amount, s.depth + 1
    FROM orders o
    JOIN subtree s ON o.parent_order_id = s.id      -- шаг рекурсии
)
SELECT * FROM subtree;
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

Читается так: стартовая часть (до UNION ALL) кладёт в результат корень; рекурсивная часть присоединяет детей к тому, что уже найдено, — и повторяется, пока находятся новые строки. Тем же приёмом решаются оргструктура («все подчинённые по цепочке» — та же таблица, только manager_id вместо parent_order_id), ветки вложенных комментариев, разбор состава изделия.

В песочнице цепочка короткая: ord-11 заменили на ord-12, и на этом всё — запрос вернёт две строки, то есть ровно один шаг рекурсии. Приём от этого не меняется: та же самая рекурсивная часть отработает и на цепочке из десяти звеньев, просто данных для неё в учебном магазине нет.

Две практические детали. Первая — защита от циклов: если в данных вдруг есть петля (А — родитель Б, а Б — родитель А), запрос зациклится. С PostgreSQL 14 страховка встроена в сам язык: сразу после закрывающей скобки рекурсивной части дописывают оговорку CYCLE id SET is_cycle USING path — и база сама запоминает пройденное, останавливается на повторе и помечает в ответе строку, на которой это случилось. Рядом живёт SEARCH DEPTH FIRST BY id SET ord, если нужен порядок обхода. На PostgreSQL 13 и старше того же добиваются руками: накапливают пройденный путь в массив и проверяют id <> ALL(path). И самый дешёвый вариант, годный в обоих случаях, — просто ограничить depth. Вторая деталь — производительность: рекурсивный запрос быстр, только когда на каждом шаге срабатывает индекс (CREATE INDEX ON orders (parent_order_id)); без него каждый шаг превращается в полный проход таблицы.

Для иерархий у PostgreSQL есть и другие инструменты — materialized path на ltree, closure table, — но связки «список смежности + WITH RECURSIVE» хватает на подавляющее большинство задач, и она не требует денормализации.

Где рекурсивный SQL упирается в предел

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

CREATE TABLE vertices (
    id         bigint PRIMARY KEY,
    kind       text  NOT NULL,   -- person, company, event…
    properties jsonb NOT NULL
);
CREATE TABLE edges (
    from_id    bigint NOT NULL REFERENCES vertices (id),
    to_id      bigint NOT NULL REFERENCES vertices (id),
    label      text   NOT NULL,  -- friend_of, works_at…
    properties jsonb  NOT NULL
);
CREATE INDEX ON edges (from_id);
CREATE INDEX ON edges (to_id);

Хранится это прекрасно. Проблемы начинаются в запросах. «Найти людей, родившихся в США и живущих в Европе», где место рождения указано с разной детализацией (город → штат → страна → континент), — это обход рёбер «находится в» на произвольную глубину и сразу в двух направлениях. Этот пример разбирает Мартин Клеппман в «Designing Data-Intensive Applications» — книге, по главам которой у нас собран раздел «Фундамент данных». У него на рекурсивном SQL запрос занимает под тридцать строк из четырёх CTE; на графовом языке Cypher — четыре:

MATCH
  (p:Person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (:Location {name:'United States'}),
  (p)        -[:LIVES_IN]-> () -[:WITHIN*0..]-> (:Location {name:'Europe'})
RETURN p.name

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

Когда честнее взять графовую СУБД

Графовые СУБД (Neo4j и другие) реализуют модель property graph: у каждой вершины и у каждого ребра есть идентификатор и набор свойств, рёбра типизированы, а схема не ограничивает, что с чем можно связать. Главная сила модели — лёгкость развития: новый тип связи — это просто новые рёбра с новой меткой, без миграций и без перекройки таблиц. (Любопытно, что похожая сетевая модель CODASYL была главным соперником реляционной ещё в 1970-х и проиграла; но графовые СУБД — не её реинкарнация: у них есть доступ к любой вершине по индексу и декларативные запросы вместо ручной навигации по указателям.)

Практические ориентиры для развилки:

  • Одна-две иерархии (категории, оргструктура, комментарии) — PostgreSQL + WITH RECURSIVE. Заводить отдельную СУБД ради дерева — лишняя инфраструктура.
  • Графовые запросы есть, но это 5 % нагрузки — тоже PostgreSQL: две таблицы, рекурсивные CTE, индексы по обоим концам ребра. По выразительности медленнее Cypher, зато без второй базы в эксплуатации.
  • Обход связей — это ядро продукта (рекомендации, антифрод по цепочкам переводов, social-фичи, граф знаний) — вот тут графовая СУБД оправдана: и язык запросов, и хранение заточены под обход, и таких запросов много.
запросы по связям PostgreSQL одна-две иерархии PostgreSQL обходы 5 % нагрузки графовая СУБД обход это ядро продукта

Три ориентира из текста стоят рядом: два из них возвращают в PostgreSQL, и только обход связей как ядро продукта оправдывает вторую базу.

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

Где это применяется

Развилка всплывает не в момент выбора базы, а позже — когда в живом проекте появляется первая иерархия или первый запрос «по цепочке». Правильный первый ход почти всегда один: WITH RECURSIVE в той базе, которая у вас уже есть. А переезд на графовую СУБД — это решение уровня продукта, и принимать его стоит по числам: сколько запросов-обходов, какой они глубины, какую долю нагрузки составляют.

Где спотыкаются начинающие:

  • Городят глубину костылями — пять self-join «на всякий случай» или выгрузка всей таблицы в память и обход в коде. WITH RECURSIVE решает это штатно.
  • Забывают про циклы — рекурсивный запрос по данным с петлёй зависает; проверка пути или лимит глубины обязательны для графов общего вида.
  • Тянут графовую СУБД под одну иерархию — вторая база в эксплуатации дороже тридцати строк SQL.
  • Моделируют граф в документной базе — вложенность хорошо выражает дерево «один-ко-многим», но связи «многие-ко-многим» между документами превращаются в ручные соединения в коде приложения.
Дополнительно: при первом чтении можно пропустить

Глубже: промежуточные варианты, о которых забываютрасширенное

Выбор не сводится к «рекурсивный SQL или отдельная графовая база»: между ними есть три решения, каждое дешевле второй базы.

Closure table — таблица всех путей. Вместо (или вместе с) ссылки на родителя держат таблицу «предок, потомок, глубина» со всеми парами, а не только соседними. Тогда «все потомки узла» — это обычный запрос по индексу, без рекурсии и на любой глубине. Цена — запись: перемещение узла означает перестройку всех его путей, и на глубоких деревьях это десятки строк на одну правку. Окупается там, где читают глубокие поддеревья постоянно, а правят структуру редко: каталог категорий, оргструктура, разделы документации.

ltree — путь как значение. Расширение PostgreSQL хранит путь строкой вида root.electronics.coffee.grinders и умеет по нему искать с индексом: все потомки — это path <@ 'root.electronics', все предки — path @> …. Быстро и просто, пока путь имеет фиксированную форму и узлы не переезжают часто (переезд означает обновление пути у всего поддерева). Для дерева с одним родителем это самый дешёвый вариант из всех.

Графовые расширения PostgreSQL. Apache AGE добавляет в PostgreSQL язык openCypher: графовые запросы пишутся почти как в Neo4j, а данные остаются в той же базе, с теми же резервными копиями и той же эксплуатацией. pgRouting решает более узкую, но частую задачу — маршруты и кратчайшие пути по сети дорог или зависимостей. Оба варианта не дают производительности специализированной базы, зато не добавляют второй системы.

Практический порядок выбора: дерево с одним родителем и редкими переездами — ltree; частое чтение глубоких поддеревьев — closure table; графовые запросы нужны, но их немного — расширение поверх PostgreSQL; обход связей стал повседневной и массовой операцией — графовая СУБД.

Глубже: где рекурсия упирается: цифрырасширенное

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

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

Отсюда практический тест, который можно провести до выбора: взять свой самый глубокий запрос, написать его на WITH RECURSIVE и посмотреть EXPLAIN (ANALYZE, BUFFERS) — число строк на выходе рекурсивной части и время. Если строк тысячи, вопрос закрыт в пользу SQL. Если миллионы и запрос нужен в интерактивном сценарии, начинается разговор про графовую базу.

Глубже: если графовую базу всё-таки взялирасширенное

Две базы — это всегда вопрос, кто из них прав. Ответ должен быть один и записанный.

Источник правды — основная база. Граф в этой схеме производный: он строится из данных PostgreSQL и может быть перестроен с нуля в любой момент. Это главное свойство, которое делает жизнь с двумя базами выносимой: при любом расхождении граф пересобирают, а не разбираются, чья версия вернее. Обратная схема (граф как источник правды) встречается, но требует от графовой базы того же уровня надёжности и резервного копирования, что от основной.

Как данные попадают в граф. Два способа, и обычно оба. Первичная загрузка — пакетная выгрузка из основной базы и массовая заливка (neo4j-admin database import). Дальше — поток изменений: либо через события приложения (проще и достаточно, если приложение одно), либо через захват изменений из журнала базы (надёжнее, когда в базу пишут несколько служб). Важно, чтобы обработка была идемпотентной: MERGE вместо CREATE, и тогда повтор события не плодит дубли.

Что делать при расхождении. Сверка по счётчикам: число узлов каждой метки против числа строк в таблице-источнике, число связей против числа строк в таблице связей. Расхождение больше порога — сигнал пересобрать затронутую часть. Плюс контроль задержки: если поток изменений отстал на часы, графовые ответы устарели, и об этом должен знать не только дежурный, но и интерфейс (например, отключением функции, которая опирается на граф).

Коротко

  • Признак графа — не «есть связи», а обход переменной глубины как повседневная операция: «кто на кого влияет через три шага», «есть ли путь», «кто рядом в сети».
  • Иерархия с одним родителем закрывается в PostgreSQL: ссылка на родителя плюс WITH RECURSIVE, а при глубоких чтениях — closure table или ltree.
  • Рекурсивный SQL упирается не в глубину, а в число промежуточных строк: тысячи — нормально, миллионы — уже секунды и минуты. Измеряется это EXPLAIN (ANALYZE, BUFFERS) до выбора базы.
  • Между SQL и отдельной базой есть графовые расширения PostgreSQL (Apache AGE, pgRouting) — графовые запросы без второй системы.
  • Графовая СУБД оправдана, когда обходы — ядро продукта, а не одна функция; тогда основная база остаётся источником правды, граф строится из неё и пересобирается при расхождении.

Что почитать дальше