Блог

Циклы в графе бывают разных форм. Они могут быть короткими или длинными. Например: питер -> билл -> том -> Питер; питер -> питер. Иногда наличие цикла вызывает неодобрение, но иногда необходимо представлять ваши данные таким образом.

Мне было интересно, каково влияние наличия цикла в графике (мои данные) при выполнении запроса в Neo4j.

Допустим, у меня есть запрос для определенного шаблона по моим данным. Может быть ситуация, когда у меня есть цикл, и ситуация, когда в моих данных нет цикла. Поскольку, по сути, цикл представляет собой бесконечный цикл (например, если бы я запускал алгоритм DFS, он продолжал бы цикл бесконечно, если я не приму меры предосторожности), я предполагаю, что СУБД Neo4j оснащена накладными расходами на обнаружение и выход из этого цикла.

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

Правильно ли я так думаю? Это действительная проблема или я преувеличиваю? Есть ли какие-либо материалы по этой теме в Neo4j?

tl; dr

Бесконечные циклы невозможны в Cypher, и, как таковые, циклы в вашем графике сами по себе не создают проблемы для производительности запросов.

Длинный подробный ответ

Это отличный вопрос, и начало ответа находится в документации об уникальности в обходах Cypher:

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

Хотя было бы точнее сказать:

где одна и та же связь с графом встречается несколько раз на одном пути

Поскольку пути пересекаются в соответствии с шаблоном сопоставления, определенное отношение может быть пройдено только один раз на этом пути. Направление обхода здесь не имеет значения. Также не имеет значения, имеет ли отношение присвоенную ему переменную или является ли отношение частью пути переменной длины. Как только связь пройдена для одного пути, она больше никогда не будет пройдена.

Это в значительной степени защищает вас от бесконечных циклов, которые по определению требуют, чтобы вы снова и снова просматривали одни и те же отношения.

Однако это не защищает вас от увеличения затрат, когда между узлами существует множество множественных путей из-за перестановки всех возможных взаимосвязей (все уникальные и никогда не повторяющиеся для каждого пути), которые могут быть пройдены.

Например, если вы возьмете график Movies из :play movies браузера Neo4j, вы можете выдать запрос типа, MATCH (n:Person)-[*]-(m:Person) RETURN count(*) и это, скорее всего, никогда не вернется, как количество возможных путей между любыми двумя узлами:Person, из-за перестановки всех возможных отношений, которые могут быть пройдены (при этом не повторяя ни одного в каждоминдивидуальный путь) становится непомерно дорогостоящим (и это делается для всех возможных комбинаций двух узлов: Person в графе).

Этот тип запроса в конечном итоге приведет к блокировке Neo4j, поскольку количество путей для оценки становится астрономическим, но опять же это не связано с бесконечными циклами.

Чтобы обойти такого рода ограничения (в конце концов, вы можете использовать очень похожий запрос для поиска достижимых отдельных узлов или количества достижимых отдельных узлов), вам нужно будет изменить уникальность обхода с уникальности Cypher ‘RELATIONSHIP_PATH’ на что-то другое.

Если вы используете фреймворк обхода на Java (который можно использовать, если вы создаете определяемую пользователем процедуру, расширение ядра или используете встроенный Neo4j), вы можете изменить уникальность обхода на другое поведение.

Что касается избежания бесконечных циклов, уникальность ‘NODE_PATH’ также предотвратит их, поскольку гарантирует, что узел может быть посещен только один раз для каждого отдельного пути.

Одним из наиболее полезных, которое также предотвращает бесконечные циклы, является уникальность ‘NODE_GLOBAL’, которая гарантирует, что узел посещается только один раз по всем путям, а не только по каждому пути. Именно эта уникальность лучше всего используется, когда вы хотите найти все отдельные узлы (или подсчитать все отдельные узлы), доступные из начального узла, и поэтому мы используем уникальность ‘NODE_GLOBAL’ в определенных процедурах расширения пути библиотеки процедур APOC (и при использовании apoc.path.expandConfig() вы можете явно установить уникальность себя, если вы хотите другой тип).

Итак, вкратце, по умолчанию бесконечные циклы не могут выполняться с использованием Cypher. Некоторые из наиболее серьезных проблем с производительностью Cypher, с которыми вы сталкиваетесь, могут быть связаны с резким увеличением числа возможных путей, соответствующих шаблону соответствия, особенно при неограниченном расширении переменной длины, поскольку это может занять место в куче или иным образом привести к необычайно большому количеству уникальных путей для оценки. С помощью API обхода или процедур расширения пути APOC вы можете изменить поведение уникальности обхода в соответствии с потребностями вашего запроса.