How to query exact path in neo4j and avoid cartesian product?

Question

I have around 3000 nodes with 7000 relationships in a graph but for a presentation, I'd like to plot a sub-graph of which I know exactly which nodes I need.

Therefore, I use the following query which sometimes gives me the correct path as a result (after a long waiting period) and sometimes depletes memory and cpu resources until I force-quit the neo4j-browser.

MATCH p1=(:DestinationNode)-[:IS_AT]->
(:CentiDegreeNode{x: 4714, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4715, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4716, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4717, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 844})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 844}),
p2=(:DestinationNode)-[:IS_AT]->
(:CentiDegreeNode{x: 4718, y: 839})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 840})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 840})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 841})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 842})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 844}),
p3=(:CentiDegreeNode{x: 4719, y: 844})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 845})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 846})
RETURN p1, p2, p3

What am I doing wrong? How would I have to rephrase the query in order to have it executed within seconds? Note that x and y of a CentiDegreeNode are indexed.

Initially I started with directed relationships (-[:CONNECTED_TO]->) but this wasn't any quicker.

Thank you very much!

You need to find these paths in three steps to avoid Cartesian product. — Rajendra Kadam, May 02 '19 at 11:53
Can you run and share time for only one of these path, say p1? — Rajendra Kadam, May 02 '19 at 11:54
Can you PROFILE the query (if it completes) or EXPLAIN it and provide the resulting query plan (after expanding all elements with the double-down arrow in the lower right corner of the pane)? My guess would be you may be missing indexes that could help you here. — InverseFalcon, May 02 '19 at 11:58

cybersam · Accepted Answer · 2019-05-02T19:04:08.367

When you say that "x and y of a CentiDegreeNode are indexed", hopefully you meant that both properties are used together in a single index: :CentiDegreeNode(x, y). That would be more performant.

Separating the 3 paths by WITH clauses might help (this could depend on the version of neo4j). Also, by collecting the paths along the way, you can avoid cartesian products.

MATCH p1=(:DestinationNode)-[:IS_AT]->
(:CentiDegreeNode{x: 4714, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4715, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4716, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4717, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 844})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 844})
WITH COLLECT(p1) AS p1s
MATCH p2=(:DestinationNode)-[:IS_AT]->
(:CentiDegreeNode{x: 4718, y: 839})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4718, y: 840})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 840})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 841})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 842})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 843})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 844})
WITH p1s, COLLECT(p2) AS p2s
MATCH p3=(:CentiDegreeNode{x: 4719, y: 844})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 845})-[:CONNECTED_TO*1]-
(:CentiDegreeNode{x: 4719, y: 846})
RETURN p1s, p2s, COLLECT(p3) AS p3s

I think this will still end up with cartesian product. So you might want to collect while using with. — MissingNumber, May 02 '19 at 18:41
Good point. I have modified my answer to avoid cartesian products. — cybersam, May 02 '19 at 19:05
Thank you Sam, this improves it. Unfortunately, no, they are not indexed in the same index, as I use the annotation in my Spring application like this: ´@Index private int x;´ ´@Index private int y;´ I wouldn't know how to have a composite index with those two...? — user3105453, May 11 '19 at 14:50
Composite indexes have been available in neo4j Enterprise Edition 3.2+, via the [@CompositeIndex](https://neo4j.com/docs/ogm-manual/current/reference/#reference:indexing:composite) annotation. — cybersam, May 11 '19 at 16:45

MissingNumber · Answer 2 · 2019-05-02T18:49:14.820

You can rephrase your query to avoid Cartesian product by using UNION

match path=(:A)-[:K]->(:B) 
return path
union
match path=(:D)-[:H]->(:C) 
return path
union
match path=(:F)-[:L]->(:G}) 
return path

This returns list of all the paths, which is good enough to plot graph with out cartesian.

But, This way you can not differentiate which path is of which type if we need to use such information in our application code. So we need to modify this query a bit(lil computationally expensive than last one). For achieving classification of paths by piping intermediate results using WITH.

match path=(:A)-[:K]->(:B) 
with collect( path)  as path_list_1
match path=(:D)-[:H]->(:C) 
with path_list_1, collect( path)  as path_list_2
match path=(:F)-[:L]->(:G})
with path_list_1, path_list_2 , collect( path)  as path_list_3
return path_list_1, path_list_2 , path_list_3

Now with this we can achieve optimal collection and classification of paths.

If you are on older version where WITH is not available, then you can do something like this and then aggregate based on path_types in your application.

match path=(:A)-[:K]->(:B) 
return path, 1 as path_type
union
match path=(:D)-[:H]->(:C) 
return path, 2 as path_type
union
match path=(:F)-[:L]->(:G}) 
return path, 3 as path_type

Cheers!!

How to query exact path in neo4j and avoid cartesian product?

2 Answers2

Linked