DataFusion internals¶

This section is for contributors and for readers who want to know how lance-csr extends Apache DataFusion to run graph queries. You don't need any of it to use the engine: How it works gives the short version.

lance-csr's goal is fast multi-hop traversal over data that already lives in Lance, with no import into a graph database and no second copy of the data. DataFusion is a strong relational engine, but a graph hop written relationally is two hash joins, and a five-hop query is ten of them. lance-csr keeps DataFusion for everything it already does well (filters, projections, aggregates, sorts, joins, vectorized multi-threaded execution) and adds graph-aware pieces where relational plans fall short. The compressed sparse row (CSR) index is the data structure those pieces read.

What lance-csr added to lance-graph¶

lance-csr is a fork of lance-graph, and the two parts of the engine have different origins.

From lance-graph

The Cypher parser and semantic analysis, the graph logical plan's core operators (ScanByLabel, Expand, VariableLengthExpand, Filter, Unwind, Project, Distinct, Sort, Offset, Limit), and the planner that turns them into DataFusion scans and joins, with variable-length paths unrolled into one branch per length. Vector search functions, releasing the GIL from Python, and a compact CSR neighbour store that lance-graph's query planner didn't use. lance-csr has since extended and fixed much of this code.

Added in lance-csr

Everything this section describes as a DataFusion extension: the extension nodes and their operators, the extension planner, both optimizer rules, the deadline rule and the join statistics. Also the graph rewrites (re-rooting, alternation and multi-label branching), the OptionalMatch, ShortestPath, PathMatch and Apply operators, the CSR adjacency and node indexes with incremental refresh, engine snapshots, the plan template cache and the Cypher-specific functions.

lance-graph plans every hop as joins, and lance-csr keeps that planning as the fallback for any hop the CSR can't take. Each page in this section says what came from lance-graph where it matters.

Design principles¶

• The data stays in Lance. Tables are read through Lance's own LanceTableProvider. The graph indexes store Lance row addresses and row ids, so a hop fetches exactly the rows it needs with take, and an index never holds a copy of node or relationship properties.
• Every graph operator is a DataFusion extension node. It sits inside an ordinary DataFusion plan, so everything around it is still planned, optimized and executed by DataFusion.
• Results never depend on the fast path. Any hop the CSR can't express is planned as a hash join in the same plan. The test suite runs each supported shape with the CSR on and off and compares the answers.
• Bounded, streaming operators. The extension operators yield bounded output batches and resume where they left off, even inside a single high-degree node's neighbour list, and they check for cancellation as they go.
• Immutable snapshots. An engine holds a snapshot of pinned dataset versions plus the indexes built for them. refresh() builds a replacement next to it, reusing whatever didn't change, and swaps it in atomically, so running queries never see a half-updated index.

Where the extensions plug in¶

flowchart TD
    T["Cypher text"] --> P["Parse<br/><code>parser.rs</code>"]
    P --> S["Semantic analysis<br/><code>semantic.rs</code><br/>scopes, labels, $parameters"]
    S --> R["Graph rewrites<br/><code>pattern_order.rs</code><br/><code>pattern_alternatives.rs</code>"]
    R --> G["Graph logical plan<br/><code>logical_plan.rs</code><br/>ScanByLabel, Expand, VariableLengthExpand,<br/>ShortestPath, PathMatch, OptionalMatch, Apply"]
    G --> D["DataFusion logical plan<br/><code>datafusion_planner/</code><br/>scans + joins + extension nodes"]
    D --> O["DataFusion optimizer<br/>+ PushCsrTargetFilters<br/>+ PruneCsrTargetColumns"]
    O --> X["Physical planning<br/>CsrQueryPlanner → CsrExtensionPlanner"]
    X --> E["Execution<br/>CsrExpandExec, NodeLookupExec, ShortestPathExec,<br/>PathMatchExec, ApplyExec, KeyStatisticsExec"]
    E --> B["Arrow record batches"]

Parsing, semantic analysis and the core of both logical plans came from lance-graph. The graph rewrites, the extension nodes, the optimizer rules and the extension planner were added in lance-csr. engine.explain(query) prints the graph logical plan, the DataFusion logical plan and the physical plan, and every custom operator shows up in it by name.

Every extension point¶

Apart from the vector functions, every implementation in this table was added in lance-csr; lance-graph used no DataFusion extension points. CypherEngine builds one DataFusion session per snapshot (in engine.rs). It installs CsrQueryPlanner and adds PushCsrTargetFilters before PruneCsrTargetColumns, so that pruning can drop the columns a moved filter reads. Rust callers that bring their own SessionContext must install CsrQueryPlanner themselves; contexts created by CypherQuery and CypherEngine already have it.

Source map¶

All paths are under crates/lance-csr/src/.