Выполнение запроса транзитивного замыкания в Neo4j

Question

Я пытаюсь вычислить транзитивное замыкание неориентированного графа в Neo4j, используя следующий Cypher Query ("E" - метка, которую имеет каждое ребро графа):

MATCH (a) -[:E*]- (b) WHERE ID(a) < ID(b) RETURN DISTINCT a, b

Я пытался выполнить этот запрос на графе с 10k узлами и около 150k ребрами, но даже через 8 часов он не закончился. Я нахожу это удивительным, потому что даже самые наивные SQL-решения намного быстрее, и я ожидал, что Neo4j будет намного эффективнее для такого рода стандартных графовых запросов. Так что мне чего-то не хватает, может быть, какая-то настройка сервера Neo4j или лучший способ написать запрос?

редактировать

Вот результат EXPLAINв приведенном выше запросе:

+--------------------------------------------+
| No data returned, and nothing was changed. |
+--------------------------------------------+
908 ms

Compiler CYPHER 3.3

Planner COST

Runtime INTERPRETED

+-----------------------+----------------+------------------+--------------------------------+
| Operator              | Estimated Rows | Variables        | Other                          |
+-----------------------+----------------+------------------+--------------------------------+
| +ProduceResults       |          14069 | a, b             |                                |
| |                     +----------------+------------------+--------------------------------+
| +Distinct             |          14069 | a, b             | a, b                           |
| |                     +----------------+------------------+--------------------------------+
| +Filter               |          14809 | anon[11], a, b   | ID(a) < ID(b)                  |
| |                     +----------------+------------------+--------------------------------+
| +VarLengthExpand(All) |          49364 | anon[11], b -- a | (a)-[:E*]-(b)                  |
| |                     +----------------+------------------+--------------------------------+
| +AllNodesScan         |          40012 | a                |                                |
+-----------------------+----------------+------------------+--------------------------------+

Total database accesses: ?

Answer 1

Вы можете ограничить направление, но для этого требуется направление графика.

Проведя некоторое собственное тестирование и профилирование, я обнаружил, что даже для очень небольших наборов данных (случайно сгенерированных наборов из 10 узлов с 2 случайными ребрами в каждом) выполнение запроса сводится только к одному направлению, сокращающему количество обращений к базе данных. в 10000 раз (с 2266909 до 149 обращений к базе данных).

Добавление направления к вашему запросу (и, следовательно, принуждение к направлению графика) значительно сокращает пространство поиска, но требует направления графика.

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

К сожалению, вы не делаете ничего плохого, но ваш запрос огромен.

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

Написанный вами запрос является поиском неограниченного пути для каждой пары узлов. Пары узлов ограничены, но не очень осмысленным образом (граница ID(a)

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

Отправленный вами SQL-запрос не выполняет ту же операцию.

В комментариях вы упомянули, что пытались выполнить этот запрос в реляционной таблице в рекурсивной форме:

WITH RECURSIVE temp_tc AS (
  SELECT v AS a, v AS b FROM nodes
  UNION SELECT a,b FROM edges g
  UNION SELECT t.a,g.b FROM temp_tc t, edges g WHERE t.b = g.a
)
SELECT a, b FROM temp_tc;

Я должен отметить, что этот запрос не выполняет то же самое, что делает Neo4J, когда пытается найти все пути. Прежде чем Neo4J сможет начать сокращать ваши результаты, он должен сгенерировать набор результатов, который состоит из каждого отдельного пути во всем графике.

SQL и реляционный запрос этого не делают; он начинается со списка ссылок, но этот рекурсивный запрос приводит к удалению любых возможных дублирующих ссылок; он обнаруживает другие ссылки, так как ищет ссылки других; например, если график выглядит как (A)-(B)-(C), этот запрос обнаружит, что B соединяется с C в процессе обнаружения того, что A соединяется с C.

С Neo4J каждый путь должен быть обнаружен отдельно.

Если это ваш общий вариант использования, возможно, что Neo4J не является хорошим выбором, если скорость имеет значение.