очень высокая скорость выполнения запросов в Neo4j

Question

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

Чтобы вычислитьрасстояние, я использую около 500 узлов на основе местоположения, которые я извлек из KML, с взвешенными краями между узлами, классифицированными как PHYSICAL_CONNECTION.Ребра имеют свою длину и имя линии, которой они соответствуют в качестве свойств.Узлы являются либо TrackPoints, если они являются железнодорожными сегментами, либо станциями, если они представляют станцию.

Однако я обнаружил, что время моего запроса сильно варьируется - иногда это занимает 2 секунды, иногда порядкаиз сотен секунд, и я не могу понять, что я делаю неправильно с помощью профилирования!

Вот мой пример запроса:

MATCH (startNode:Station{name:"Station1"}) USING INDEX startNode:Station(name)  WITH startNode
MATCH (endNode:Station{name:"Station2"}) USING INDEX endNode:MetroArea(name) WITH startNode, endNode
MATCH p=(startNode)-[*2..7]-(endNode) WHERE ALL (node in nodes(p) WHERE node:Station OR node:TrackPoint)
WITH p AS shortestPath,
reduce(distance=0, r in [x IN relationships(p) WHERE exists(x.distance)] |  distance+r.distance) AS totalDistance
                ORDER BY totalDistance ASC LIMIT 1
RETURN extract(rel in [x IN relationships(shortestPath) WHERE type(x) = "PHYSICAL_CONNECTION"] | rel.LineName) as LineNames, totalDistance

Есть ли какая-то очевидная ошибка, которую я делаю

Answer 1

Запросы с путем переменной длины (например, p=(startNode)-[*2..7]-(endNode)) имеют экспоненциальную сложность [O(N**d), where N=(relationships per node), d=(depth of path)].

Таким образом, если конкретная пара startNode / endNode принадлежит небольшойподключен подграф, тогда запрос будет быстрым.Но если они являются частью большого связного подграфа, то ваш запрос может легко занять очень много времени или даже исчерпать память.

Одним небольшим предложением будет более конкретное описание типов отношений, которые вы разрешаете впуть переменной длины (если ваша модель данных имеет нежелательные типы отношений на пути к endNode).Это поможет при поисках короткого замыкания по неподходящим путям.Например (если вы хотите иметь только пути, которые содержат STOPS_AT и / или ENDS_AT типы отношений):

MATCH p=(startNode)-[:STOPS_AT|ENDS_AT*2..7]-(endNode)

Но следует заметить большее влияние, если вы сможете сократить верхнюю границузапроса пути переменной длины.Скажем, используйте 5 вместо 7.