Why does the Neo4j query (s)<-[*]-(o) cause a timeout, whereas (o)-[*]->(s) work as expected?

Question

I'm working with Neo4j and running into a timeout issue with a particular query structure. I have two queries that look quite similar but produce different results in terms of performance.

Here are the queries:

1. This one works as expected and returns the desired result:

   MATCH (selected_method:Method{name:$neodash_method_name, class_name:$neodash_class_name, module_name:$neodash_module_name})
   MATCH (others:Method)-[all*]->(selected_method)
   RETURN *
   

2. However, the following query times out:

   MATCH (selected_method:Method{name:$neodash_method_name, class_name:$neodash_class_name, module_name:$neodash_module_name})
   MATCH (selected_method)<-[all*]-(others:Method)
   RETURN *
   

I expected both queries to have similar performance.

Is there any explanation for what happened?

I used the EXPLAIN command, and it returned the same execution plan for both queries:

Planner COST

Runtime PIPELINED

Runtime version 5.20

Batch size 1024

+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| Operator               | Id | Details                                                                                              | Estimated Rows | Pipeline            |
+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +ProduceResults        |  0 | all, others, selected_method                                                                         |      109067277 |                     |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+                     |
| +VarLengthExpand(Into) |  1 | (others)-[all*]->(selected_method)                                                                   |      109067277 | Fused in Pipeline 3 |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +CartesianProduct      |  2 |                                                                                                      |          67222 | In Pipeline 2       |
| |\                     +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| | +NodeByLabelScan     |  3 | others:Method                                                                                        |          23190 | In Pipeline 1       |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +Filter                |  4 | (selected_method.name = $neodash_method_name AND selected_method.class_name = $neodash_class_name AN |              3 |                     |
| |                      |    | D selected_method.module_name = $neodash_module_name)                                                |                |                     |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+                     |
| +NodeByLabelScan       |  5 | selected_method:Method                                                                               |          23190 | Fused in Pipeline 0 |
+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+

Total database accesses: ?

Planner COST

Runtime PIPELINED

Runtime version 5.20

Batch size 1024

+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| Operator               | Id | Details                                                                                              | Estimated Rows | Pipeline            |
+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +ProduceResults        |  0 | all, others, selected_method                                                                         |      109067277 |                     |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+                     |
| +VarLengthExpand(Into) |  1 | (selected_method)<-[all*]-(others)                                                                   |      109067277 | Fused in Pipeline 3 |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +CartesianProduct      |  2 |                                                                                                      |          67222 | In Pipeline 2       |
| |\                     +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| | +NodeByLabelScan     |  3 | others:Method                                                                                        |          23190 | In Pipeline 1       |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+---------------------+
| +Filter                |  4 | (selected_method.name = $neodash_method_name AND selected_method.class_name = $neodash_class_name AN |              3 |                     |
| |                      |    | D selected_method.module_name = $neodash_module_name)                                                |                |                     |
| |                      +----+------------------------------------------------------------------------------------------------------+----------------+                     |
| +NodeByLabelScan       |  5 | selected_method:Method                                                                               |          23190 | Fused in Pipeline 0 |
+------------------------+----+------------------------------------------------------------------------------------------------------+----------------+---------------------+

Total database accesses: ?

I’ve also tried using different runtime settings, but the second query consistently leads to a timeout.

Answer 1

The two queries represent the same thing and would produce the same result. We know that writing (s)<-[*]-(o) means the same thing as writing (o)-[*]->(s). And as you write, the query plans are the same, with the same operators and cardinality estimations.

However, the procedure of getting to the result can differ. You see that the details of the VarLengthExpand(Into) operator differs in which direction the pattern is written (just as in the query). When doing a VarLength expand, the query runtime has to decide on one node to start expanding from, and where to start may depend on what order it is written in (at least I think it could). And depending on the graph structure, it could be a quick operation when starting with one, but a huge when starting with the other.

Imagine if (o) just had a single connection to (s), while (s) had connections with everything. If you now start with (o) you would follow the one relation, find (s) and know you are done, while if you start with (s) you would have to traverse everything before knowing that it only had one connection to (o).

Now, there are more to it, like statistics of the graph and the cardinality estimations that are very different between (s) and (o) in this case. So I can't say for sure that this is the case, but the order in which you write a query can impact how long it takes to run, or even if it is solvable, even if the end result would be the same.

Now, with all that said it could also be due to some issue in the query execution. Without knowing what the graph looks like, it would seem like it should know where it would be best to start. It looks like you run on 5.20, I would recommend that you try upgrading to the latest version (which currently is 5.25.1) and try there, it may be that it solves it (if you are on Aura you would already be on 5.25.1 so you wouldn't need to do anything, just try again).