Graph Data Modeling

Bounding variable-length path traversals in Cypher

You have written a traversal like (a)-[:REL*]->(b) to find everything reachable from a start node, and on a small graph it returns instantly — but against production data it runs for minutes or exhausts memory. The * with no upper bound licenses the planner to walk the entire reachable subgraph: on a densely connected component, one query can visit millions of relationships to answer a question whose real answer is a handful of nodes four hops away. This page shows you how to bound that traversal so its cost is proportional to the answer, not to the size of the graph — by adding an explicit upper hop bound, anchoring the expansion on an indexed start node, reaching for shortestPath when you only need connectivity, and capping the result with LIMIT — and how to prove the saving with PROFILE. It is one fix from the wider Cypher query tuning anti-patterns catalogue.

Prerequisites

Why an unbounded * walks the whole component

A variable-length relationship pattern with no upper bound tells the planner to expand outward until it can expand no further. In a graph with any real connectivity, the frontier grows geometrically: hop one visits the start node’s neighbours, hop two visits their neighbours, and within a few hops the traversal has touched most of the connected component. The work is not bounded by how many rows you return — a trailing LIMIT 20 prunes the output but only after the expansion has already visited everything, because the planner cannot know which 20 paths you want until it has produced them. Two levers actually cap the work: an explicit hop bound that stops the expansion, and an indexed anchor that starts it from one node instead of scanning the label first.

This task is part of Cypher query tuning anti-patterns; the unbounded path is the cardinality explosion that hides behind a correct-looking query and a deceptively small result.

Core implementation

Work from the worst form to the best, watching what each change does to the VarLengthExpand row count. The comments mark the load-bearing decision at each step.

cypher
// STEP 0 — THE ANTI-PATTERN. No anchor index (matched by label), no upper hop
// bound. PROFILE shows NodeByLabelScan feeding a VarLengthExpand(All) whose rows
// dwarf the 20 you return — it walked the component, then LIMIT threw most away.
PROFILE
MATCH path = (a:Account)-[:TRANSFERRED_TO*]->(b:Account)
WHERE a.account_id = $aid
RETURN b.account_id, length(path) AS hops
LIMIT 20;

// STEP 1 — ANCHOR THE START. Move the filter into the node pattern so the planner
// seeks the single start Account via its index instead of scanning the label.
// The leaf flips from NodeByLabelScan to NodeIndexSeek.
PROFILE
MATCH path = (a:Account {account_id: $aid})-[:TRANSFERRED_TO*]->(b:Account)
RETURN b.account_id, length(path) AS hops
LIMIT 20;

// STEP 2 — BOUND THE DEPTH. Cap the expansion at the domain's real maximum depth.
// *1..4 stops the frontier at four hops no matter how large the component is —
// this is the change that makes cost proportional to the answer.
PROFILE
MATCH path = (a:Account {account_id: $aid})-[:TRANSFERRED_TO*1..4]->(b:Account)
RETURN b.account_id, length(path) AS hops
LIMIT 20;

// STEP 3 — WHEN YOU ONLY NEED CONNECTIVITY, USE shortestPath. If the question is
// "is b reachable, and how far", shortestPath stops at the first path to each
// target instead of enumerating every path between the pair.
PROFILE
MATCH (a:Account {account_id: $aid}), (b:Account {account_id: $bid})
MATCH path = shortestPath((a)-[:TRANSFERRED_TO*1..6]->(b))
RETURN length(path) AS hops;

The order matters. Anchoring alone (Step 1) narrows the start but an unbounded * still fans out from that one node across the whole component, so the decisive fix is the hop bound in Step 2. Set the upper bound from the deepest path your domain can legitimately contain — not from whatever number happens to make the query fast, which is the correctness trap covered below. When you need only the existence or distance of a connection rather than every intermediate path, shortestPath with a bounded pattern is dramatically cheaper because it terminates on first arrival.

Unbounded expansion versus a bounded traversal Left: a start node whose expansion radiates outward through many concentric rings of nodes, covering the whole connected component, marked as an unbounded walk. Right: the same start node whose expansion stops after four hops at a small bounded frontier, marked bounded to one-to-four hops. Unbounded — whole component Bounded — *1..4 a frontier never stops a 12 stops at hop 4
The hop bound is what makes traversal cost track the answer instead of the component.

Validation & verification

Prove the bound worked by reading the expansion’s row count, not the wall-clock time.

cypher
// The VarLengthExpand row count should now be a small multiple of the result,
// not the size of the component. Compare this against the Step 0 PROFILE.
PROFILE
MATCH path = (a:Account {account_id: $aid})-[:TRANSFERRED_TO*1..4]->(b:Account)
RETURN b.account_id, length(path) AS hops
LIMIT 20;

Confirm three things in the plan: the leaf is a NodeIndexSeek on the start node (not a label scan), the VarLengthExpand reports rows on the order of the reachable set within four hops (not the whole graph), and the total db-hits has dropped by orders of magnitude versus the unbounded form. If db-hits is still enormous, the anchor index is missing or the bound is still too loose — the same db-hits discipline as in reducing db-hits in a slow Cypher query.

Also verify correctness: run the bounded query and the original unbounded query on a small test graph where the full traversal is affordable, and confirm the bounded result is a subset that includes every path within the chosen depth. A missing legitimate result means the bound is too tight.

Edge cases & gotchas

1. A bound set for speed instead of for the domain. Setting *1..2 because it runs fast, when real paths reach five hops, produces a query that is fast and wrong — it silently omits deeper answers. Derive the bound from the data’s true maximum depth:

cypher
// WRONG — bound chosen to make it fast, truncates valid 3+ hop paths
MATCH (a:Account {account_id: $aid})-[:TRANSFERRED_TO*1..2]->(b) RETURN b;
// RIGHT — bound reflects the deepest legitimate chain in the domain
MATCH (a:Account {account_id: $aid})-[:TRANSFERRED_TO*1..6]->(b) RETURN b;

2. LIMIT mistaken for a bound. A trailing LIMIT caps output rows but does not stop the expansion — the planner still enumerates paths before pruning. Only the hop bound in the pattern limits the traversal itself; use LIMIT in addition to, never instead of, the bound.

3. Cycles inflating path counts. In a graph with cycles, an unbounded or loosely bounded traversal can revisit nodes along different paths and multiply results. Where you need reachable nodes rather than every distinct path, shortestPath or a DISTINCT on the endpoint contains the blow-up — and modelling the graph to avoid unintended cycles in the first place is a property graph anti-patterns concern that predates the query.

Related pages