Extremely slow Cypher query to generate all paths b/w 2 nodes

[arorashivamvp]

Hi,
Apologies as there are couple of similar questions previously asked. However in this use case, I have a very simple graph and a very simple query, I hope so.

I am trying to find path b/w 2 locations (origin --> destination) with defined maximum number of hops allowed. My graph is not too large, it contains around 1Lakh Location Nodes, which are connected with each other. These connections are not more than 1.5Lakh in total. The nodes have just one property called as "code" which is a string. For e.g. code : 'SEATTLE'. I have also added an unique constraint on this "code" property. The edge/relationship has 2 properties : origin, destination.

The size of the DB is also very less, it is approx. 30MB

The query I am trying to hit :

MATCH route=(origin:LOCATION{code:'SEATTLE'})-[:CONNECTS_TO*1..5]->(destination:LOCATION{code:'NEW_YORK'}) 
return route

With max hops as "2" I am getting the response in just 200ms.
With max hops as "3" I am getting the response in 2 seconds.
With max hops as "4" I am getting the response in 16 seconds.
With max hops as "5" I am not getting response, waited more than 30minutes and then killed the query.

[bennu_neo]

Hi @arorashivamvp !

It's not a game changer, but do you have an index on .code for :Location?

What's the cardinality of location per code? Is there more than one Location?

DO you have APOC installed? can you try something like?

MATCH(dest:LOCATION{code:'NEW_YORK'})
with collect(dest) as eN
MATCH (origin:LOCATION{code:'SEATTLE'})
CALL apoc.path.expandConfig(origin, {
   minLevel : 1,
   maxLevel : 5,
   relationshipFilter : 'CONNECTS_TO',
   uniqueness : 'NODE_GLOBAL'
   endNodes : eN
})

Bennu