В книжном клубе десять участников. Аня хочет позвать на встречу новых людей и спрашивает: кто из друзей моих друзей ещё не знаком со мной? Вопрос звучит просто. В этом разделе мы научимся отвечать на него одной строкой, а в первом уроке разберёмся, почему в обычной таблице он неожиданно тяжёлый.
Как клуб выглядит в таблицах
Ты уже знаешь реляционную модель: данные лежат в таблицах, строки ссылаются друг на друга ключами. Знакомства в такой базе живут в отдельной таблице, где каждая строка это пара «кто знает кого»:
CREATE TABLE people (
id integer PRIMARY KEY,
name text NOT NULL
);
CREATE TABLE knows (
person_id integer REFERENCES people (id),
friend_id integer REFERENCES people (id),
PRIMARY KEY (person_id, friend_id)
);Таблица knows это связующая таблица: сама по себе она ничего не значит, в ней только пары номеров. Чтобы получить друзей Ани, базе нужно соединить people с knows и ещё раз с people:
SELECT f.name
FROM people a
JOIN knows k ON k.person_id = a.id
JOIN people f ON f.id = k.friend_id
WHERE a.name = 'Аня';Это один шаг по связям. Как работает JOIN, подробно разобрано в уроке про соединения.
Каждый шаг это ещё одно соединение
Теперь друзья друзей. Нужно пройти от Ани к её друзьям, а от них к их друзьям. В SQL каждый такой шаг добавляет ещё одно соединение с таблицей knows:
SELECT DISTINCT fof.name
FROM people a
JOIN knows k1 ON k1.person_id = a.id
JOIN knows k2 ON k2.person_id = k1.friend_id
JOIN people fof ON fof.id = k2.friend_id
WHERE a.name = 'Аня';Три шага дадут ещё одно соединение, пять шагов ещё два сверху. А если вопрос звучит как «связаны ли Аня и Илья хоть через кого-нибудь», глубина заранее неизвестна, и простой JOIN уже не помогает. Придётся писать рекурсивный запрос WITH RECURSIVE, следить, чтобы он не ходил по кругу, и надеяться, что база не захлебнётся. Рекурсию в SQL мы видели в уроке про подзапросы и CTE.
Проблема не только в длине текста. На каждом шаге база заново ищет пары в таблице knows. Если таблица большая, каждый поиск идёт через индекс, и чем глубже вопрос, тем больше таких поисков на каждую найденную строку. На трёх-четырёх шагах по большой соцсети число промежуточных строк растёт лавиной.
Записная книжка вместо картотеки
Представь две записные книжки.
В первой контакты разложены по алфавиту, а дружбы записаны в отдельном журнале: «3 знает 7», «7 знает 12». Чтобы найти друзей друга, ты открываешь журнал, ищешь там номер, переходишь в алфавит, снова в журнал. Это таблицы.
Во второй на странице каждого человека прямо написано: «друзья: страница 7, страница 12». Ты открываешь страницу Ани и сразу листаешь к её друзьям, оттуда к их друзьям. Журнал не нужен, связь лежит рядом с человеком. Это граф.
Графовая база данных устроена как вторая книжка. Каждая связь в ней хранится как отдельная запись, которая знает свой начальный и конечный узел, а узел знает свои связи. Переход от человека к его друзьям это движение по готовым ссылкам. В Neo4j такой способ хранения называют index-free adjacency: соседей узла находят без индекса, по ссылкам.
Отсюда главное следствие. В таблицах цена шага зависит от размера таблицы связей. В графе цена шага зависит только от того, сколько связей у тех узлов, через которые ты идёшь. Клуб на десять человек или соцсеть на сто миллионов, друзья друзей Ани находятся одинаково быстро, если у Ани и её друзей примерно столько же знакомых.
Тот же вопрос на языке графа
Neo4j это самая известная графовая база, а её язык запросов называется Cypher. Вот друзья друзей Ани:
MATCH (a:Person {name: 'Аня'})-[:KNOWS]->()-[:KNOWS]->(fof)
RETURN DISTINCT fof.name
ORDER BY fof.name;+----------+
| fof.name |
+----------+
| "Вера" |
| "Глеб" |
| "Дина" |
+----------+
3 rowsЧитай запрос как картинку: узел-человек по имени Аня, стрелка «знает», какой-то узел, ещё одна стрелка «знает», узел fof. База находит в графе все места, похожие на этот рисунок, и возвращает имена в конце цепочки. DISTINCT убирает повторы, ORDER BY сортирует по алфавиту. В ответе есть Глеб, хотя Аня и так с ним знакома: к нему ведёт и прямая стрелка, и цепочка через Бориса. Отсеивать уже знакомых мы научимся в уроке про многошаговые обходы.
Длина цепочки меняется одной цифрой, а не новым соединением. Синтаксис со звёздочкой разберём в уроке про пути переменной длины, а пока посмотри, как коротко выглядит вопрос «все, до кого можно дойти за один, два или три шага»:
MATCH (a:Person {name: 'Аня'})-[:KNOWS*1..3]->(x)
RETURN DISTINCT x.name
ORDER BY x.name;+---------+
| x.name |
+---------+
| "Аня" |
| "Борис" |
| "Вера" |
| "Глеб" |
| "Дина" |
| "Егор" |
+---------+
6 rowsЗвёздочка с пределами 1..3 значит «от одного до трёх шагов». В ответ попала и сама Аня: цепочка Аня, Борис, Вера замыкается обратно на Аню, потому что Вера знает её. Такие круги в графе встречаются постоянно, и в разделе мы ещё не раз на них наткнёмся.
Когда таблицы всё ещё лучше
Граф не замена реляционной базе. Таблицы сильнее, когда:
- Вопросы про множества строк, а не про связи. Выручка по месяцам, средний чек, отчёт по складу. Тут нужны агрегаты по большим объёмам, и колоночные базы вроде ClickHouse справятся лучше всех.
- Структура данных стабильна и плоская. Бухгалтерские проводки, заказы, платежи.
- Нужны строгие схемы и привычные инструменты. Отчётность, BI, миграции.
Граф выигрывает, когда главный вопрос звучит как «как это связано с тем»: друзья друзей, путь между двумя точками, цепочка зависимостей, кольцо подозрительных переводов. Таких задач много, о них следующий урок. Общую карту нереляционных моделей ты найдёшь в уроке про NoSQL.
Попробуй сам
Ниже песочница: эмулятор Neo4j прямо в браузере. В ней уже лежит граф книжного клуба. Запрос возвращает не имена, а целые цепочки «Аня, друг, друг друга», поэтому под ответом появится картинка.
Поменяй 'Аня' на 'Глеб' и посмотри, как изменилась картинка. Потом добавь третью стрелку -[:KNOWS]->() и подумай, сколько соединений понадобилось бы для такого запроса в SQL.
Проверь себя
Задание
Дальше
Друзья друзей это только первая из задач, которые хорошо ложатся на граф. В следующем уроке пройдёмся по рекомендациям, маршрутам, мошенничеству и зависимостям и научимся узнавать графовую задачу по формулировке.
домашка