Why does neo4j warn: "This query builds a cartesian product between disconnected patterns"?

Question

I'm defining the relationship between two entities, Gene and Chromosome, in what I think is the simple and normal way, after importing the data from CSV:

MATCH (g:Gene),(c:Chromosome)
WHERE g.chromosomeID = c.chromosomeID
CREATE (g)-[:PART_OF]->(c);

Yet, when I do so, neo4j (browser UI) complains:

This query builds a cartesian product between disconnected patterns. If a part of a query contains multiple disconnected patterns, this will build a cartesian product between all those parts. This may produce a large amount of data and slow down query processing. While occasionally intended, it may often be possible to reformulate the query that avoids the use of this cross product, perhaps by adding a relationship between the different parts or by using OPTIONAL MATCH (identifier is: (c)).

I don't see what the issue is. chromosomeID is a very straightforward foreign key.

Could you give an example of a particular match and their IDs? I'm trying to visualize the relationships you're creating. — jgloves
Also, do you have any other types of relationships besides [:PART_OF]? — jgloves
This is just a warning, and in your case there is nothing to do (due to the lack of relationship between these nodes, and that is exactly what you create in this query !). Warnings in neo4j browser have been added in 2.3, to notify user when he probably do a bad query (ie. with bad performance). — logisima

cybersam cybersam · Accepted Answer · 2015-10-26T20:14:14

The browser is telling you that:

It is handling your query by doing a comparison between every Gene instance and every Chromosome instance. If your DB has G genes and C chromosomes, then the complexity of the query is O(GC). For instance, if we are working with the human genome, there are 46 chromosomes and maybe 25000 genes, so the DB would have to do 1150000 comparisons.
You might be able to improve the complexity (and performance) by altering your query. For example, if we created an index on :Gene(chromosomeID), and altered the query so that we initially matched just on the node with the smallest cardinality (the 46 chromosomes), we would only do O(G) (or 25000) "comparisons" -- and those comparisons would actually be quick index lookups! This is approach should be much faster.

Once we have created the index, we can use this query:
```
MATCH (c:Chromosome)
WITH c
MATCH (g:Gene) 
WHERE g.chromosomeID = c.chromosomeID
CREATE (g)-[:PART_OF]->(c);
```
It uses a WITH clause to force the first MATCH clause to execute first, avoiding the cartesian product. The second MATCH (and WHERE) clause uses the results of the first MATCH clause and the index to quickly get the exact genes that belong to each chromosome.

[UPDATE]

The WITH clause was helpful when this answer was originally written. The Cypher planner in newer versions of neo4j (like 4.0.3) now generate the same plan even if the WITH is omitted, and without creating a cartesian product. You can always PROFILE both versions of your query to see the effect with/without the WITH.

Why does neo4j warn: "This query builds a cartesian product between disconnected patterns"?

2 Answers