Anchor selection and cardinality

Because expansion is free but the starting fan-out is not, the planner's real job is anchor selection by cardinality — begin from the end that pulls the fewest nodes into memory — and a single WHERE clause that changes which end is most selective will flip the plan's direction entirely.

Previously

Cypher hid one decision: which end of the pattern to start from. The planner makes it by estimating cardinality and anchoring on the few, not the many — and a WHERE clause can flip that choice and reverse the whole walk. But this entire optimization rests on an assumption: that every node has a SMALL, comparable number of edges. What happens when one node has ten million?

Scene 08

Anchor selection and cardinality

Watch
Try it
Predict
Capture

What to watch for

Same pattern as last scene: Alice's RATED movies. But now look at the two ends. Each one gets a number — an estimate of how many nodes that end pulls into memory. Alice rated about 12 movies. The movie she rated, The Matrix, was rated by about a million people. The chooser compares those two numbers and starts from the SMALLER end — Alice — then expands outward. Step through it.

The same social graph and the same Cypher pattern from last scene, with one addition: each end of the pattern now carries an estimated-count badge — its cardinality estimation, the planner's guess of how many nodes that end pulls into memory.
Alice's RATED end is tiny (~12 movies); the popular Movie end is huge (~1,000,000 raters).
The query planner is the component that compares those estimates and anchors on the smaller end, then expands outward; the ringed node is the anchor it chose.
Add a WHERE clause that pins a single rare title and the Movie end shrinks to ~1 — now it's the smallest, so the planner re-anchors on the Movie and the whole walk reverses direction.

Implementation

Highlighted lines are the ones running in the diagram right now.

Planner.estimateEnds

the planner's only real cost question: how many nodes does each end pull in?

1def estimate_ends(pattern):
2    # cardinality estimate per BOUND end of the pattern
3    user_end = stats.out_degree(pattern.user, ':RATED')  # Alice ~12
4    if pattern.where:                  # WHERE m.title = '...'
5        movie_end = stats.selectivity(pattern.where)  # pins ~1
6    else:
7        movie_end = stats.in_degree(pattern.movie, ':RATED')  # raters
8    return {user_end, movie_end}       # the numbers on the badges

Planner.pickAnchor

no join planner for an expand — just pick the smaller end, SEEK it once, expand outward

1def pick_anchor(pattern):
2    ends = estimate_ends(pattern)
3    # anchor on the SMALLEST estimated end — the few, not the many
4    anchor = argmin(ends, key=estimate)
5    start = index_seek(anchor)         # the one index lookup
6    # expand AWAY from the anchor; direction follows the choice
7    return expand(start, ':RATED', toward=other_end(pattern, anchor))

Sources

Where this sits in Build a graph database (Neo4j / Dgraph-style)

Scene 08 of 16, in the The language act — Cypher is a shape; the planner picks an anchor.. The planner's real job is to anchor on the most selective node and estimate cardinality — start from the few, not the many — so flipping a WHERE filter can flip which end is cheapest and reverse the whole traversal direction.

Up next. Anchor selection assumed degrees are roughly comparable — start from the end with the fewest edges. But real graphs have celebrities. The Rock has 232M followers. The instant a traversal has to EXPAND through that node, its relationship chain isn't a quick hop — it's millions of edges to scan, and the O(1)-per-hop promise dies on that one node.

All 16 scenes in Build a graph database (Neo4j / Dgraph-style) · Every curriculum

Built with Arqly

Every scene in Build a graph database (Neo4j / Dgraph-style) builds on the one before it.All 16 Build a graph database (Neo4j / Dgraph-style) scenes