Cypher: describe a shape

Build a graph database (Neo4j / Dgraph-style) (16 scenes)

Scene 07 · Cypher: describe a shape

A Cypher MATCH (a:User {name:'Alice'})-[:FRIEND]->(b)-[:FRIEND]->(c) is a declarative description of a pattern, and for expansion it maps directly onto pointer-chasing — no join planner needed.

Previously

Raw pointer-walks don't scale to humans. Cypher fixes that: you draw the shape — Alice's friends' friends — and the engine turns the pattern straight into a traversal, no join planner for the expand. But that pattern has two ends, and the engine had to CHOOSE which one to start from. Pick wrong and even index-free adjacency can't save you.

Scene 07

Cypher: describe a shape

Watch

Diagram

The same social graph, with a Cypher pattern string typed across the top. A Cypher MATCH pattern is an ASCII-art drawing of the shape you want — `(a:User {name:'Alice'})-[:FRIEND]->(b)-[:FRIEND]->(c)` reads as 'a User named Alice, to a friend b, to b's friend c'. Writing the pattern is a declarative traversal: you describe the shape, not the step-by-step procedure — the engine decides how to walk it. Alice (ringed) is the bound anchor the engine starts from. From her, the animated path is the EXPAND: each `-[:FRIEND]->` arrow becomes one pointer follow, so the matched subgraph lights up exactly the people the shape reaches — no join planner, because the pattern already lays out the walk. The right inset is the persistent spine: this local pattern lights a few nodes; a whole-graph pass lights all 14.

Sources

the bound anchor (a value: name='Alice') → ringed

Nobody hand-writes pointer-walks. In Cypher you DRAW the shape you want, in ASCII-art: `(a:User {name:'Alice'})-[:FRIEND]->(b)-[:FRIEND]->(c)` — read it left to right: a User named Alice, an arrow to a friend `b`, another arrow to `b`'s friend `c`. Watch what the engine does with it. First it binds the anchor — the node with a concrete value, Alice — and rings her. Then it walks the pattern: each `-[:FRIEND]->` is one pointer follow from the node it's standing on, and the matched subgraph lights up hop by hop. The shape you typed and the walk that runs are the SAME thing.

Implementation

Planner.compileExpand

bind the anchor once, then one pointer follow per pattern arrow

1def run(pattern):
2    # the ONLY index lookup: find the bound anchor by value
3    start = index_seek(pattern.anchor)   # Alice, by name
4    frontier = {start}
5    for arrow in pattern.arrows:         # each -[:FRIEND]->
6        next = set()
7        for node in frontier:
8            # EXPAND: follow relationship pointers, no join
9            next |= follow(node, arrow.relType)
10        frontier = next
11    return frontier                      # the matched subgraph

Planner.bindAnchor

the pattern's one bound value (name:'Alice') becomes the start — found once, with an index

1def bind_anchor(pattern):
2    # the bound end has a concrete value; the other ends are free
3    bound = [p for p in pattern.nodes if p.has_value]
4    anchor = most_selective(bound)   # here: name='Alice'
5    # the ONE index lookup the whole expand needs
6    start = index_seek(anchor)       # O(log N), once
7    return start                     # ringed in the diagram

Store.followArrow

one pattern arrow = walk the node's relationship chain — pointer follows, no index

1def follow(node, rel_type):       # one -[:FRIEND]-> arrow
2    out = set()
3    rel = node.first_rel          # pointer on the node record
4    while rel is not None:        # the doubly-linked chain
5        if rel.type == rel_type:
6            out.add(rel.other_end(node))  # O(1) per edge
7        rel = rel.next_rel        # next pointer, not a seek
8    return out                    # the hop's reached nodes

Not sure what to ask? Tap a question — the staff engineer answers in the chat panel.

PreviousLinked list vs CSR adjacency NextAnchor selection and cardinality