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

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

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

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

  • Запросы «на 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-ом всю ветку не достать — глубина заранее неизвестна. Для этого в SQL есть рекурсивный запрос (рекурсивное обобщённое табличное выражение, CTE):

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. Вторая — производительность: рекурсивный запрос быстр, только когда на каждом шаге срабатывает индекс (CREATE INDEX ON categories (parent_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);

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