Когда таблицы перестают справляться

Почему запрос «друзья моих друзей» в SQL превращается в лестницу из JOIN-ов, а в графе остаётся одной строкой.

Графовая база данных — это СУБД, где связи между записями хранятся явно, как объекты первого класса, а не вычисляются на лету через соединение таблиц по ключам.

Данные у нас давно есть. Проблема в связях

Реляционные базы — PostgreSQL, MySQL, Oracle — правят миром уже полвека, и не зря. Они великолепно хранят однородные записи: пользователей, заказы, товары. Но как только в предметной области главным становится не сам объект, а сеть отношений между объектами, реляционная модель начинает скрипеть. Социальная сеть — это не столько люди, сколько кто кого знает. Система рекомендаций — это не каталог товаров, а паутина «кто что покупал вместе». Граф знаний — это в первую очередь рёбра между понятиями.

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

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

Откуда берётся «взрыв» стоимости

Представьте, что у каждого человека в среднем 100 друзей. На первом уровне обхода мы смотрим на 100 записей. На втором — на 100×100 = 10 000. На третьем — миллион, на четвёртом — сто миллионов. Этот экспоненциальный рост называют fan-out (ветвление обхода). Реляционная база на каждом таком уровне выполняет соединение, которое в худшем случае просматривает большие части индексов и страниц данных. Граф же на каждом шаге просто берёт у узла его готовый список соседей и идёт дальше — он платит ровно за те узлы, которые реально посетил, а не за всю таблицу.

Маленький пример: социальная сеть

Представьте таблицы person и таблицу-связку friendship(a_id, b_id). Чтобы найти друзей друзей человека Алисы, на SQL придётся соединить friendship саму с собой:

CREATE TABLE person (id INTEGER PRIMARY KEY, name TEXT);
CREATE TABLE friendship (a_id INTEGER, b_id INTEGER);
INSERT INTO person VALUES (1,'Алиса'),(2,'Боб'),(3,'Вера'),(4,'Глеб');
INSERT INTO friendship VALUES (1,2),(2,3),(3,4);

SELECT DISTINCT p3.name
FROM friendship f1
JOIN friendship f2 ON f1.b_id = f2.a_id
JOIN person p3 ON f2.b_id = p3.id
WHERE f1.a_id = 1;

Вывод:

Вера

Это всего два шага по связи — и уже два самосоединения. Добавьте третий уровень — ещё один JOIN. Пятый уровень дружбы в реляционной базе на миллионах строк может работать минуты. А именно такие обходы — сердце соцсетей, антифрода и рекомендаций.

Обратите внимание на ещё одну деталь: чтобы соединение работало быстро, на friendship.a_id и friendship.b_id нужны индексы. Каждый из них — это отдельное дерево в памяти и на диске, которое надо поддерживать при каждой вставке и удалении дружбы. Чем больше уровней обхода вы хотите ускорить, тем больше составных индексов приходится держать, и тем дороже становится запись. Граф снимает этот компромисс: соседство хранится прямо в структуре узла, без отдельного индекса, который надо отдельно обслуживать.

А если связь не просто «есть»?

Реальные связи редко бывают голыми. У дружбы есть дата начала, у перевода денег — сумма и время, у оценки фильма — число звёзд. В реляционной модели эти атрибуты живут колонками в таблице-связке, и чтобы ими воспользоваться при обходе, к каждому JOIN добавляется ещё и условие WHERE. В графе же такой атрибут — это просто свойство на ребре, доступное мгновенно в момент перехода по нему. Когда мы дойдём до property graph, вы увидите, что связь со свойствами — это не костыль, а полноценный объект первого класса.

Как ту же задачу видит граф

В графовой модели Алиса, Боб, Вера и Глеб — это узлы, а дружба — связи между ними. Картинка буквально совпадает с тем, что мы рисуем на доске:

(Алиса)--ЗНАЕТ-->(Боб)--ЗНАЕТ-->(Вера)--ЗНАЕТ-->(Глеб)

Запрос «друзья друзей Алисы» на языке Cypher выглядит как этот же рисунок, записанный текстом:

MATCH (a:Person {name:'Алиса'})-[:ЗНАЕТ]->()-[:ЗНАЕТ]->(fof)
RETURN fof.name

Никаких JOIN. Глубину обхода задаёт сам паттерн стрелок. И — это ключевой момент — графовая база хранит у каждого узла прямые ссылки на его соседей. Перейти от Боба к его друзьям — это не поиск по таблице, а переход по указателю. Стоимость шага не зависит от того, сколько в базе всего людей.

Сравните два мысленных образа. В реляционном мире вопрос «кто друзья Боба» звучит так: «пройди по всей картотеке дружб и найди карточки, где в одной из граф стоит Боб». В графовом мире тот же вопрос звучит иначе: «возьми карточку Боба — на ней уже подшит список его дружб, читай его». Первый образ масштабируется с размером картотеки, второй — с числом друзей Боба. Именно эта разница, повторённая на каждом из пяти-шести уровней обхода, и даёт выигрыш в порядки.

Как работает под капотом

Главная идея графовых СУБД называется index-free adjacency (безындексная смежность). В реляционной базе, чтобы найти соседей записи, нужно обратиться к индексу внешнего ключа — а это логарифмический поиск по дереву. В графовой базе каждый узел физически хранит список указателей на свои рёбра, а каждое ребро — указатели на оба своих узла. Переход «сосед → сосед» становится операцией за константное время O(1) на шаг, независимо от размера всей базы.

Поэтому стоимость обхода в графе пропорциональна размеру обходимой области (сколько узлов мы реально посетили), а не размеру всей базы. В реляционной модели каждый JOIN, наоборот, в худшем случае смотрит на весь набор данных. Это и есть фундаментальная причина, по которой граф выигрывает на глубоких связях.

Полезно держать в голове грубую формулу сложности. Реляционный обход глубины d по таблице из N строк стоит примерно как d соединений, каждое из которых задевает порядка N записей в худшем случае. Графовый обход той же глубины при среднем ветвлении k стоит примерно как число реально посещённых узлов — порядка k в степени d, но без множителя N. Пока обходимая область меньше всей базы (а в локальных запросах вроде «соседи второго круга» это почти всегда так), граф выигрывает тем сильнее, чем больше сама база. То есть преимущество не исчезает с ростом данных, а растёт.

Чего это стоит графу

Бесплатных обедов не бывает. Index-free adjacency хорош для обхода, но за него платят в других местах. Хранить указатели на соседей прямо в узле означает, что массовые аналитические сканы («посчитай сумму по всем заказам») в графе обычно медленнее, чем в колоночной или реляционной базе, заточенной под такие сканы. Кроме того, граф сложнее равномерно «расшардить» по многим машинам: разрезать сильно связанный граф так, чтобы рёбра редко пересекали границу шарда, — отдельная нетривиальная задача. Поэтому граф — это специализированный инструмент, а не серебряная пуля, и относиться к нему стоит именно так.

Частые ошибки

• «Граф быстрее любой базы». Нет. На простой выборке «дай 100 последних заказов» реляционная база часто быстрее. Граф выигрывает именно на связях и обходах, а не вообще.
• «Граф = просто таблица связей». Дело не в том, что связи где-то записаны, а в том, что они хранятся как объекты со свойствами и обходятся по указателям, без поиска по индексу.
• Считать, что граф заменит реляционную базу везде. На практике граф берут под конкретный класс задач — связи, — а остальное часто оставляют в привычной СУБД.

Итоги

• Графовая база хранит связи явно, как объекты, а не вычисляет их соединениями.
• Глубокие обходы («друзья друзей», пути, рекомендации) в SQL дают лестницу JOIN-ов, а в графе — короткий паттерн.
• За скоростью обхода стоит index-free adjacency: переход к соседу — это шаг по указателю, а не поиск.
• Граф — инструмент под задачи со связями, а не универсальная замена реляционным СУБД.