Eliminating Cartesian Products in Spatial Cypher

A dispatch query that ran in milliseconds against a seed graph suddenly takes forty seconds in production, and the query log shows one operator responsible: a CartesianProduct sitting between two MATCH clauses that were never connected. The symptom is a routing endpoint whose latency scales with the product of two node sets instead of their sum — a thousand depots crossed against five thousand stops is five million intermediate rows built before a single distance predicate runs. The root cause is almost always a comma-separated MATCH (or two standalone MATCH clauses) that share no relationship or join variable, so the planner has no choice but to pair every row on the left with every row on the right. This page resolves it: how to see the blow-up in PROFILE, and the three rewrites — connect the patterns, pipeline with WITH, or scope the second set with OPTIONAL MATCH — that turn an O(N \times M) cross-join back into a bounded traversal. It is a focused case of the discipline in Cypher Performance Tuning.

Prerequisites & Versions

The plan operators and syntax below are stable on Neo4j 5.x. The Python side uses the official async driver and reads the PROFILE tree straight off the result summary — no APOC, no GDS.

pip install "neo4j>=5.18"

The graph is a fleet model over Greater London: :Depot nodes each :SERVES a set of :Stop nodes, every node carrying a native location point. A point index on Stop.location backs the bounding box, so the correct query seeks rather than scans — the same index discipline covered in distance filter query patterns.

Implementation

The script below profiles the same intent — “for each depot, its stops inside a search box, with the depot-to-stop distance” — written two ways. The first uses a comma MATCH that forgets to connect depot to stop and pays a Cartesian product; the second pipelines through WITH and expands the :SERVES relationship. A small helper walks the profile tree, flags any CartesianProduct operator, and reports the widest row count so the blow-up is visible as a number, not a guess.

import asyncio
from neo4j import AsyncGraphDatabase

# Accidental Cartesian: (d) and (s) share no relationship, so every depot
# is paired with every stop before the box filter or distance runs.
CROSS = """
PROFILE
MATCH (d:Depot), (s:Stop)
WHERE s.location.latitude  >= $min_lat AND s.location.latitude  <= $max_lat
  AND s.location.longitude >= $min_lon AND s.location.longitude <= $max_lon
RETURN d.id AS depot, s.id AS stop,
       point.distance(s.location, d.location) AS dist_m
"""

# Rewrite: WITH pipelines each depot, then the :SERVES expansion joins the
# patterns so only real depot-stop pairs are ever built.
JOINED = """
PROFILE
MATCH (d:Depot)
WITH d
MATCH (d)-[:SERVES]->(s:Stop)
WHERE s.location.latitude  >= $min_lat AND s.location.latitude  <= $max_lat
  AND s.location.longitude >= $min_lon AND s.location.longitude <= $max_lon
RETURN d.id AS depot, s.id AS stop,
       point.distance(s.location, d.location) AS dist_m
"""

PARAMS = {
    "min_lat": 51.470, "max_lat": 51.545,
    "min_lon": -0.170, "max_lon": -0.040,   # a box over central London
}


def walk(plan):
    """Depth-first walk over the nested PROFILE operator tree."""
    yield plan
    for child in plan.get("children", ()):
        yield from walk(child)


async def profile(session, cypher: str) -> dict:
    result = await session.run(cypher, **PARAMS)
    rows = [record async for record in result]        # drain before consume
    summary = await result.consume()
    plan = summary.profile
    has_cartesian = any(
        op.get("operatorType", "").startswith("CartesianProduct")
        for op in walk(plan)
    )
    widest = max((op.get("rows", 0) for op in walk(plan)), default=0)
    return {"rows_returned": len(rows), "widest_operator_rows": widest,
            "cartesian_product": has_cartesian}


async def main() -> None:
    driver = AsyncGraphDatabase.driver(
        "neo4j+s://your-cluster.databases.neo4j.io",
        auth=("neo4j", "secure-password"),
        connection_acquisition_timeout=5.0,
    )
    try:
        async with driver.session(database="neo4j") as session:
            cross = await profile(session, CROSS)
            joined = await profile(session, JOINED)
    finally:
        await driver.close()

    print(f"comma MATCH : {cross}")
    print(f"WITH join   : {joined}")
    assert not joined["cartesian_product"], "rewrite must not plan a CartesianProduct"


if __name__ == "__main__":
    asyncio.run(main())

Against a graph of a thousand depots and five thousand stops, CROSS reports cartesian_product: True and a widest_operator_rows in the millions, while JOINED reports False and a widest operator in the low thousands — the same rows returned, three orders of magnitude less work.

How It Works

The planner builds a CartesianProduct whenever two pattern fragments in the same query part have no variable in common. In MATCH (d:Depot), (s:Stop) the depot and the stop are independent, so the only join the engine can form is the full cross-product, evaluated before the WHERE clause can prune anything. This is the trap: the bounding-box predicate you added to cut the result set runs on the far side of the blow-up, so it filters five million rows down to a few thousand instead of preventing the five million from ever being built.

The three rewrites all share one idea — give the planner a join key so it can pair rows selectively instead of exhaustively:

• Connect the patterns. The JOINED query replaces the comma with a MATCH (d)-[:SERVES]->(s) expansion. Now the second MATCH is anchored on d; the engine expands each depot’s relationships and only visits the stops that depot actually serves. The CartesianProduct operator disappears from the plan entirely, replaced by an Expand(All) whose cardinality is bounded by average out-degree.
• Pipeline with WITH. The WITH d between the two MATCH clauses is not cosmetic — it establishes d as the driving row of the downstream expansion, so the planner streams one depot at a time rather than assembling both sets and joining them. WITH is the seam where you can also ORDER BY, LIMIT, or aggregate before the second pattern runs, shrinking the frontier further.
• Scope the second set with OPTIONAL MATCH. When a depot may legitimately have no in-box stop and you still want the depot row, OPTIONAL MATCH (d)-[:SERVES]->(s:Stop) WHERE … keeps the depot and yields null for the missing side — again anchored on d, so no cross-product forms. This preserves left-join semantics without falling back to the comma form.

Whether a legitimate all-pairs join is ever what you want is a real question: sometimes it is, for example scoring every candidate depot against every open order. In that case the cross-product is not accidental, but it should still be an index-probe rather than a raw scan of both labels — the technique in index-probe spatial joins in Cypher, where one side seeks the other’s spatial index instead of materializing the full grid. The operator-ordering decisions behind all of this belong to graph query planner optimization.

Common Failure Patterns

1. The comma MATCH you didn’t mean to write. MATCH (a:A), (b:B) reads like “match A and B” but means “match every A paired with every B.” Split the concerns and connect them through a relationship or a shared property.

// Blows up: no shared variable between the two patterns
MATCH (d:Depot), (s:Stop) WHERE s.region = d.region RETURN d, s
// Fixed: join on the relationship, or pipeline the shared key
MATCH (d:Depot)-[:SERVES]->(s:Stop) RETURN d, s

Note that the WHERE s.region = d.region in the broken form does not save you — the equality is checked after the product is built, so the operator still materializes N×M rows first.

2. A correlated subquery missing its join key. A CALL { … } subquery that imports a variable but never uses it to constrain the inner pattern re-scans the whole inner label per outer row — a Cartesian product hiding inside the call.

// Bug: d is imported but the inner MATCH is unconstrained by it
MATCH (d:Depot)
CALL (d) { MATCH (s:Stop) RETURN s LIMIT 3 }
RETURN d.id, s.id
// Fix: tie the inner pattern back to d
MATCH (d:Depot)
CALL (d) { WITH d MATCH (d)-[:SERVES]->(s:Stop) RETURN s LIMIT 3 }
RETURN d.id, s.id

3. An Eager operator buffering the whole product. When a downstream DISTINCT, aggregation, or write forces an Eager operator above a CartesianProduct, the entire N×M set is buffered in heap before the next stage runs — turning a slow query into an OutOfMemoryError. Spot the Eager in PROFILE directly above the product; the cure is the same as for the product itself, since removing the cross-join removes the rows the Eager has to hold.

Performance Notes

A cross-join and a connected expansion differ not by a constant factor but by their growth law. For left and right sets of size $|A|$ and $|B|$, and an average out-degree $\bar{d}$ on the connecting relationship:

$$R_{\times} = |A|\cdot|B| \qquad\text{versus}\qquad R_{\bowtie} = |A|\cdot\bar{d}$$

With $|A|=10^3$, $|B|=5\times10^3$, and $\bar{d}\approx 4$, that is five million intermediate rows against four thousand — and because the product is built before the filter, heap and CPU both track $R_{\times}$, not the size of the final result. The lever is structural: connect the patterns so the planner joins on a key. Confirm it the same way the rest of Cypher Performance Tuning does — run PROFILE, read bottom-up, and treat any CartesianProduct on a query that should be a traversal as a defect to fix before it ships, not a latency figure to tune around. In CI, assert the plan is free of CartesianProduct for hot queries; a refactor that reintroduces the comma form changes only latency, so a correctness test alone will not catch it.

Related

• Distance Filter Query Patterns — bounding the candidate set with an index-seekable predicate before any join runs.
• Index-Probe Spatial Joins in Cypher — when an all-pairs correlation is intended, probe the index instead of building the grid.
• Keeping Spatial Queries in the Plan Cache — the sibling tuning concern of plan reuse and parameterization.
• Graph Query Planner Optimization — reading operator order and forcing the join shape you want.

This guide is part of Cypher Performance Tuning, one of the workflows in Cypher Spatial Queries & Pathfinding Patterns.

For authoritative reference, consult the Neo4j Cypher Manual and its Execution Plan Operators documentation.