CODEWITHSUNDEEP
neo4jcypher
nicomp
nicomp

Reputation: 4647

Why does this cypher query never finish

This is the query:

MATCH (t:Table)-[*]-(a:Attribute) RETURN t,a

Here is the complete graph: The entire graph

Here is the query and what happens when I try to execute it: Browser locks up

Upvotes: 0

Views: 170

Answers (1)

InverseFalcon
InverseFalcon

Reputation: 30397

The reason is that you are performing a variable-length relationship without an upper bound. Cypher will attempt to find every possible path in existence that can be made no matter how long the path, provided that the path begins with a :Table node and ends with an :Attribute node. While a relationship will only be traversed once per path, there's no restriction to using a different relationship to return to a previously traversed node and then using another as-of-yet-untraversed-relationship-in-the-path to leave it and continue traversing.

Even on a small graph, the number of possible paths explodes. You can see for yourself how the number of paths grows, and how the db will get slower as the number of possible paths to explore explodes.

MATCH (:Table)-[*..6]-(:Attribute) 
RETURN count(*) as pathsFound

Now if that finishes quick, increase the upper bound and run it, and keep on doing it, and see how high you can go, and how high the paths found gets, before the db starts running into trouble.

I'll save you some time, though. I recreated your graph, and you hit the max possible paths when you have an upper bound of 23 hops, returning a count of 1371112 total distinct paths in your graph matching that pattern. The browser alone won't be able to cope with this many rows of data.

Here are two queries you can run to verify it (provided that this is your entire graph):

MATCH (:Table)-[*..23]-(:Attribute) 
RETURN count(*) as totalPathsFound

and

MATCH path = (:Table)-[*..23]-(:Attribute) 
RETURN length(path) as pathLength, count(*) as pathsFound
ORDER BY pathLength DESC

Note that expanding out and counting the number of possible paths isn't too strenuous, we can get that in a few seconds. But doing property access or additional computations that may multiplicatively increase the number of paths can be a problem, and streaming back this many rows of data, especially to a browser app, can be a problem.

More to the point, I don't think you really want to process over a million results anyway. What the query is actually doing is likely completely different than what you really want. So you may want to clarify what exactly you want the query to do, because the current approach isn't feasible.

Upvotes: 1

Related Questions