Developer

Графовые БД: Neo4j, Cypher и когда хватает рекурсивных запросов

↑ 4.3 Поиск и специализированные БД · ← Предыдущая · → Следующая

Желательно~6 мин чтенияУровень: middle

Зачем это на собесе

«Рекомендации друзей», «цепочка подчинения», «зависимости сервисов», «поиск мошеннических связей» — задачи про связи. Интервьюер хочет услышать, когда граф действительно нужен, а когда достаточно рекурсивного запроса в PostgreSQL.

Подтемы

  • Модель графа: узлы, рёбра, свойства
  • Cypher
  • Когда граф выигрывает
  • Рекурсивные запросы в SQL как альтернатива
  • Neo4j, Apache AGE и другие

Объяснение

Модель

Граф состоит из узлов (вершин), рёбер (связей) и свойств на тех и других. В property graph у ребра есть направление и тип, у узла метки.

flowchart LR
    A(("Анна<br/>:Person")) -- "FRIEND" --> B(("Борис<br/>:Person"))
    B -- "FRIEND" --> C(("Вера<br/>:Person"))
    A -- "LIKES" --> M["Фильм<br/>:Movie"]
    C -- "LIKES" --> M

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

Cypher

Язык запросов Neo4j, который описывает узор «рисунком»:

// друзья друзей Анны, которых она ещё не знает
MATCH (a:Person {name: 'Анна'})-[:FRIEND]->(:Person)-[:FRIEND]->(fof:Person)
WHERE NOT (a)-[:FRIEND]->(fof) AND fof <> a
RETURN DISTINCT fof.name;
 
// кратчайший путь между двумя людьми
MATCH p = shortestPath((a:Person {name: 'Анна'})-[:FRIEND*..6]-(b:Person {name: 'Вера'}))
RETURN p;

Когда граф действительно нужен

  • Рекомендации («люди, которые лайкали это, лайкали и то»).
  • Антифрод: кольца связанных аккаунтов и карт.
  • Зависимости и влияние: кто затронут, если упадёт сервис.
  • Знания и онтологии, связи сущностей в поиске.
  • Маршруты и сети.

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

Рекурсивные запросы в SQL

PostgreSQL умеет обходить иерархии и графы через WITH RECURSIVE:

CREATE TABLE emp (id int PRIMARY KEY, name text, boss_id int REFERENCES emp(id));
INSERT INTO emp VALUES (1,'Директор',NULL),(2,'Техлид',1),(3,'Бэкендер',2),(4,'Фронтендер',2),(5,'Стажёр',3);
 
-- цепочка руководителей снизу вверх
WITH RECURSIVE chain AS (
  SELECT id, name, boss_id, 0 AS depth FROM emp WHERE id = 5
  UNION ALL
  SELECT e.id, e.name, e.boss_id, c.depth + 1
  FROM emp e JOIN chain c ON e.id = c.boss_id
)
SELECT depth, name FROM chain ORDER BY depth;
-- 0 Стажёр, 1 Бэкендер, 2 Техлид, 3 Директор
 
-- все подчинённые техлида сверху вниз
WITH RECURSIVE tree AS (
  SELECT id, name, 0 AS depth FROM emp WHERE id = 2
  UNION ALL
  SELECT e.id, e.name, t.depth + 1 FROM emp e JOIN tree t ON e.boss_id = t.id
)
SELECT depth, name FROM tree ORDER BY depth, name;

Для графов с циклами в запрос добавляют массив посещённых узлов или ограничение глубины, иначе рекурсия не остановится.

Варианты

РешениеОсобенности
Neo4jсамая известная графовая БД, язык Cypher, сообщество и инструменты
Apache AGEрасширение PostgreSQL с запросами Cypher поверх таблиц
Amazon Neptune, JanusGraph, ArangoDBоблачный сервис, распределённый граф, мультимодельная БД
PostgreSQL WITH RECURSIVEиерархии и небольшие графы без новой системы

Нюансы и подводные камни

  • Граф не заменяет основную БД. Часто он живёт рядом как специализированный индекс связей, наполняемый из основной базы.
  • Суперузлы. Узел с миллионами связей (знаменитость, общий тег) замедляет обход. Ограничивайте степень и направление обхода.
  • Глубина обхода растёт экспоненциально. Всегда ограничивайте длину пути (*..6).
  • Масштабирование. Шардировать графы сложнее, чем таблицы; многие решения лучше масштабируются вверх, чем вширь.
  • Циклы. В SQL защищайтесь от зацикливания (UNION вместо UNION ALL, массив посещённых, лимит глубины).
  • Модель данных. Неверное разделение на узлы и рёбра (свойство вместо узла) усложняет запросы.

Вопросы с ответами

Связанные темы

Вид графа

Обратные ссылки