Многошаговые обходы по связям

Как Cypher выражает то, ради чего берут граф: переходы на несколько шагов по связям.

Обход (traversal) — переход от узла к его соседям по рёбрам; цепочка таких переходов в Cypher записывается цепочкой паттернов со стрелками.

Два шага: друзья друзей

Соединяя паттерны, мы задаём маршрут. «Друзья друзей Алисы, которых она сама ещё не знает»:

MATCH (me:Person {name:'Алиса'})-[:ЗНАЕТ]->(friend)-[:ЗНАЕТ]->(fof)
WHERE fof <> me AND NOT (me)-[:ЗНАЕТ]->(fof)
RETURN DISTINCT fof.name AS recommendation

Разберём: первый шаг ведёт к прямым друзьям (friend), второй — к их друзьям (fof). Условие fof <> me отсекает саму Алису (она может быть чьим-то другом), а NOT (me)-[:ЗНАЕТ]->(fof) — тех, кого она уже знает. Это базовый движок «рекомендации знакомых».

Обход против направления

Связи направлены, но обходить их можно в любую сторону. «Коллеги по фильмам» — это шаг по стрелке вперёд (к фильму) и шаг против стрелки (к другому актёру):

(actor)──ACTED_IN──>(movie)<──ACTED_IN──(colleague)

MATCH (a:Person {name:'Tom Hanks'})-[:ACTED_IN]->(m)<-[:ACTED_IN]-(co)
RETURN DISTINCT co.name AS colleague, count(m) AS together
ORDER BY together DESC

Стрелка к m идёт вперёд, от m к co — назад. Так на одном ребре ACTED_IN мы ходим в обе стороны, не дублируя данные.

Зачем вообще граф, а не JOIN

Стоит понять мотивацию, прежде чем нырять в синтаксис. В реляционной базе «друзья друзей» — это таблица friendship, к которой нужно присоединить саму себя: friendship f1 JOIN friendship f2 ON f1.friend_id = f2.person_id. Каждый дополнительный шаг — ещё один self-JOIN, и планировщику приходится перебирать огромные промежуточные множества. Три шага — три JOIN-а, пять шагов — пять, и на каждом уровне СУБД сверяет ключи по индексу. В графе же сосед узла лежит «под рукой»: у каждого узла есть прямой указатель на его рёбра, и переход — это разыменование указателя, а не поиск по индексу. Эта разница и называется index-free adjacency (безиндексная смежность). Именно поэтому многошаговые запросы — родная стихия Neo4j, а не его слабое место.

Практический вывод: то, что в SQL вы боялись писать (рекурсивные CTE на пять уровней), в Cypher выражается одной строкой паттерна и выполняется предсказуемо быстро — пока вы не упрётесь в суперузлы (о них ниже).

Несколько типов связей

В одном шаге можно разрешить несколько типов через |: -[:ACTED_IN|DIRECTED]-> — «снялся ИЛИ срежиссировал». Это удобно, когда логически разные рёбра ведут к одному виду узлов. Например, «все люди, как-то причастные к фильму» — и актёры, и режиссёры, и сценаристы:

MATCH (m:Movie {title:'The Matrix'})<-[:ACTED_IN|DIRECTED|WROTE]-(person:Person)
RETURN DISTINCT person.name AS contributor

Стрелка тут идёт от фильма к человеку (<-), потому что физически рёбра направлены от человека к фильму, а мы хотим пройти их в обратную сторону. Перечисление типов через | не замедляет обход: движок всё равно разворачивает рёбра узла, просто пропускает не подошедшие по типу.

Фильтрация по свойствам на пути

Промежуточные узлы и рёбра можно сужать прямо в паттерне или в WHERE. «Коллеги Тома Хэнкса по фильмам, вышедшим после 2000 года»:

MATCH (a:Person {name:'Tom Hanks'})-[:ACTED_IN]->(m:Movie)<-[:ACTED_IN]-(co:Person)
WHERE m.released > 2000 AND co <> a
RETURN co.name AS colleague, collect(m.title) AS shared_films

Условие m.released > 2000 отсекает старые фильмы ещё на этапе обхода, а co <> a исключает самого Тома (он снимался в своих фильмах и иначе попал бы в коллеги к себе). Чем раньше отсечь лишние ветки, тем дешевле обход — фильтр на промежуточном узле лучше, чем на финальном результате.

Возврат пути целиком

Иногда нужен сам маршрут, а не только концы. Назовите путь переменной:

MATCH path = (a:Person {name:'Алиса'})-[:ЗНАЕТ]->(:Person)-[:ЗНАЕТ]->(b:Person {name:'Глеб'})
RETURN path, length(path) AS steps

length(path) вернёт число рёбер в маршруте. Над переменной пути работают и другие функции: nodes(path) вернёт список узлов, relationships(path) — список рёбер. Это пригодится, когда нужно не просто узнать, что связь есть, а показать саму цепочку посредников — например, «через кого Алиса знакома с Глебом».

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

Каждый шаг паттерна движок реализует как expand — разворачивание узла в его соседей нужного типа по спискам смежности. Многошаговый паттерн — это последовательность expand-ов, образующая дерево обхода. Стоимость растёт как произведение степеней узлов на пути (сколько у каждого соседей), а не как размер всей базы. Вот почему «суперузлы» с миллионами связей — отдельная боль: expand такого узла дорог.

Разберём числа на «друзьях друзей». Пусть у каждого человека в среднем 50 друзей. Первый expand из Алисы даёт ~50 узлов. Второй expand из каждого из них — ещё по ~50, то есть порядка 50×50 = 2500 кандидатов на втором уровне (с учётом пересечений меньше, но порядок такой). Третий уровень — уже ~125 000. Видно, как быстро растёт фронт обхода: каждый шаг умножает его на среднюю степень. Это полезная интуиция — она объясняет и силу графа (мы не трогаем остальную базу), и его опасность (на плотных данных глубокий обход взрывается, об этом отдельный урок про пути переменной длины).

Порядок шагов тоже важен. Планировщик Cypher старается начать обход с самого «узкого» конца — с того узла, которых в базе мало или который найден по индексу. Если стартовать с конкретной Алисы (один узел) и идти наружу, фронт растёт постепенно. Если же начать с многочисленного промежуточного класса, первый expand сразу даст гигантское множество. Поэтому привязка {name:'Алиса'} в начале паттерна — это не только фильтр, но и подсказка движку, откуда дешевле войти в граф.

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

Забыть исключить старт. В «друзьях друзей» сам человек может вернуться как fof — добавляйте fof <> me.
Лишнее направление. «Коллеги» требуют обхода против стрелки на втором шаге; если поставить обе стрелки вперёд, ничего не найдётся.
Пропуск DISTINCT. Несколько общих фильмов дадут повторы коллег.
Старт с «широкого» конца. Если не привязать конкретный узел в начале паттерна, первый expand пойдёт из множества узлов и фронт обхода раздуется. Якорьте старт по индексируемому свойству.
Фильтр в конце вместо середины. Условие на промежуточный узел (например год фильма) лучше ставить сразу в WHERE, а не отсеивать готовый результат — так движок не разворачивает заведомо лишние ветки.

Итоги

Цепочка паттернов = многошаговый обход; так выражаются «друзья друзей» и «коллеги».
Связь направлена, но обходить её можно в обе стороны — комбинируя -> и <-.
Несколько типов в шаге — через |; весь маршрут можно вернуть как path.
Под капотом каждый шаг — expand по смежности; цена зависит от степеней узлов, а не от базы.