From AST to rows: the query engine·5 min

Bindings, the execution model

0 / 1

A query result is a table of rows, and each row is a binding — a map from pattern variables to graph entities, like {bacon: node#0, m: node#65}. Execution is: start from an anchor (found via the indexes from Chapter 3), then for each pattern segment extend every partial binding by following adjacency (Chapter 2), filter by WHERE, and finally project the RETURN columns.

Choosing where to start is planning: a real optimizer anchors on the most selective variable so the search tree stays small. Ours uses a simple heuristic — anchor on the first node pattern that has a label or property bound (so (bacon:Person {name:'Kevin Bacon'}) seeds from the property index, one node, not all 57 people).

Binding extension

MATCH (bacon:Person {name:'Kevin Bacon'})-[:ACTED_IN]->(m)
anchor:  {bacon:#0}                          (property index)
extend:  {bacon:#0, m:#65}  {bacon:#0, m:#71}  ...   (adjacency: neighbors OUT ACTED_IN)
rows  -> RETURN m.title  ->  'A Few Good Men', 'Apollo 13', 'Frost/Nixon'

And the recurring warning: results are unordered sets unless ORDER BY is present. The grader canonicalizes both sides (key-sorted objects; rows sorted by a stable key) so set-equality is exact-equality — and every capstone query writes ORDER BY so the output is deterministic by construction.

Parse the whole query Execute a single hop