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

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

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

Два признака, оба про запросы, а не про хранение:

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

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

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

Классическое хранение дерева — adjacency list: каждая строка ссылается на родителя.

CREATE TABLE categories (
    id        bigint PRIMARY KEY,
    parent_id bigint REFERENCES categories (id),
    name      text NOT NULL
);

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

WITH RECURSIVE subtree AS (
    SELECT id, parent_id, name, 1 AS depth
    FROM categories
    WHERE id = 42                          -- корень ветки

    UNION ALL

    SELECT c.id, c.parent_id, c.name, s.depth + 1
    FROM categories c
    JOIN subtree s ON c.parent_id = s.id   -- шаг рекурсии
)
SELECT * FROM subtree;

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

Две практические детали. Первая — защита от циклов: если в данных есть петля (А родитель Б, Б родитель А), запрос зациклится; страховка — либо накапливать путь в массив и проверять id <> ALL(path), либо ограничить depth. Вторая — производительность: рекурсивный CTE эффективен, когда на каждом шаге работает индекс (CREATE INDEX ON categories (parent_id)); без него каждый шаг — полный проход таблицы.

Для иерархий у PostgreSQL есть и другие инструменты — materialized path на ltree, closure table, — но adjacency list + 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);

Хранится — прекрасно. Проблемы начинаются в запросах. «Найти людей, родившихся в США и живущих в Европе», где место рождения указано с разной детализацией (город → штат → страна → континент), — это обход рёбер «находится в» на произвольную глубину в двух направлениях сразу. На рекурсивном 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-фичи, граф знаний) — графовая СУБД оправдана: и язык запросов, и хранение оптимизированы под обход, и таких запросов много.

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

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

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

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

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

Что почитать дальше: PostgreSQL или MongoDB — соседняя развилка про модель данных; составные индексы — чтобы шаг рекурсии работал по индексу; моделирование документов в MongoDB — embed vs reference. Первоисточник — Мартин Клеппман, «Высоконагруженные приложения», глава 2.