The CSR index¶

The CSR is what makes lance-csr different from the project it was forked from. This page explains what it is, how to turn it on, which queries it speeds up, and how it keeps up with changing data.

Why joins are slow for traversal¶

Without a CSR, a hop such as (a:Person)-[:KNOWS]->(b:Person) is two hash joins: the a rows against the whole KNOWS table, then the result against the whole Person table to fetch b. A three-hop query repeats that three times, building a hash table and materializing every intermediate path at each step.

flowchart TB
    subgraph join ["Join path: two hash joins per hop"]
        direction LR
        A1["a rows"] --> J1["hash join<br/>KNOWS table"] --> J2["hash join<br/>Person table"] --> B1["b rows"]
    end
    subgraph csr ["CSR path: one lookup per hop"]
        direction LR
        A2["a rows"] --> C["CsrExpand: neighbours of a,<br/>take b rows by position"] --> B2["b rows"]
    end
    join ~~~ csr

What a CSR is¶

Compressed sparse row is the standard compact layout for a sparse matrix, and so for a graph's adjacency. It is two arrays:

• neighbours: every edge's target, grouped by source;
• offsets: one entry per source node, pointing at where its neighbours start.

For the graph 1→2, 1→3, 2→4, 3→4:

The neighbours of the node at position v are neighbours[offsets[v] .. offsets[v + 1]], so node 1's are neighbours[0..2] = [2, 3]. One lookup, no hashing of the edge table, and each node's neighbours sit next to each other in memory.

lance-csr builds two of these per relationship type, one outgoing and one incoming, so it can walk edges in either direction.

Turning it on¶

import pyarrow as pa
from lance_csr import CypherEngine, GraphConfig

config = (
    GraphConfig.builder()
    .node_table("Person", "id")
    .rel_table("KNOWS", "Person", "Person", "src", "dst")
    .build()
)
datasets = {
    "Person": pa.table({"id": [1, 2, 3, 4], "name": ["Alice", "Bob", "Carol", "David"]}),
    "KNOWS": pa.table({"src": [1, 1, 2, 3], "dst": [2, 3, 4, 4]}),
}

engine = CypherEngine(config, datasets, use_csr=True)  # (1)!

1. The CSR is built here, in the constructor, from the relationship tables alone. Nothing changes in how you write queries.

use_csr is False by default. With it on, the engine builds two indexes at construction:

CSR adjacency

Per relationship type with integer endpoints: outgoing and incoming neighbour lists. Built from the relationship table only.

Node index

Per node label with unique integer keys: a map from key to row position. It lets the CSR fetch target rows by position (Lance take_rows, or Arrow take for in-memory tables) instead of joining.

Which hops use it¶

The CSR answers a hop when all of these hold:

• the relationship has integer endpoint columns (int8, int16, int32, int64, uint8, uint16 or uint32);
• the hop has exactly one relationship type (alternation still qualifies, because each alternative is planned as its own branch);
• the relationship has no variable and no property map: -[:KNOWS]-> qualifies, -[k:KNOWS]-> and -[:KNOWS {since: 2020}]-> do not.

When those hold, it covers:

Everything else in the query (filters, aggregations, sorts and any hop the CSR can't take) is planned by DataFusion as usual. You can mix: a three-hop query might run two hops on the CSR and one as a join.

Named path values and relationships(path) use a query-local inventory of actual edge occurrences because CSR neighbors do not carry edge identity or properties. This also preserves parallel edges when a path passes through collect() and UNWIND. The inventory materializes the participating node and relationship tables; bounded traversal batches do not bound that inventory. See path values. Shortest-path queries within one node label that only read length or node keys keep the CSR route below. Relationships crossing labels use typed identities, even for these queries, to distinguish equal keys from different labels.

For shortestPath and allShortestPaths, a source with one target in an input batch searches from both ends using the outgoing and incoming CSR. It expands the smaller frontier and finishes the whole layer before joining paths, so it keeps all shortest alternatives. Several targets for the same source share one forward search. Undirected searches can use both ends without a persistent CSR too; directed searches without a CSR keep their forward search over the adjacency built for that query.

Variable-length traversal¶

An eligible variable-length path keeps one cursor per hop and yields bounded output batches. Its plan contains one CsrExpandExec with iterative hops=..., rather than a branch for every possible length or sequence of relationship types. It preserves duplicate matches and skips missing nodes at intermediate hops. A node's label and key travel together, so the same integer key in two labels identifies two nodes.

The iterative path needs CSR indexes for every traversed type and direction, node indexes for every intermediate label, and resolved labels for the endpoints. Unsupported index shapes retain the join fallback. The 20-hop maximum still applies. *0.. includes a zero-hop identity match when both labels and keys agree. Undirected paths keep the existing rule that rejects immediate backtracking; neither execution path enforces full relationship uniqueness on longer cycles.

Traversal state grows with the hop limit, not the number of pending paths. Resident graph indexes, input batches, fetched target properties and downstream operators still contribute to query memory. Branching graphs can produce exponentially many matches even though traversal resumes between output batches.

The fused target lookup¶

When the target label has a node index, the CSR expansion also replaces the join that fetches the target's properties: each neighbour id is mapped to a row position and the row is read directly. In explain() output that shows as take=:

plan = engine.explain("MATCH (a:Person {id: 1})-[:KNOWS]->(b:Person) RETURN b.name")
print([line.strip(" |") for line in plan.splitlines() if "CsrExpandExec" in line])
# ['CsrExpandExec: key=a__id, edges=4, take=b[b__name]']

The fused lookup needs the target's key to be a unique integer. Duplicate keys, or a target that is already bound earlier in the query, keep the CSR hop but join for the target's properties.

Only requested target columns are read. A pushed-down target filter reads its own columns first; remaining properties are fetched only for neighbours that pass. When a column is used by both the filter and the projection, its filtered values are reused within that output batch. Target keys come directly from the neighbour IDs, including when a filter reads them. This reuse ends with the batch and keeps no property cache across queries or dataset versions.

Patterns start at the most selective node¶

The planner rewrites each MATCH so traversal starts at its most selective node, walking edges backwards where needed. That matters more with the CSR than without, because DataFusion can push a filter below a join but not below a CSR expansion:

plan = engine.explain("MATCH (a:Person)-[:KNOWS]->(b:Person {name: 'David'}) RETURN a.name")
print([line.strip(" |") for line in plan.splitlines() if "CsrExpandExec" in line])
# ['CsrExpandExec: key=b__id, edges=4, take=a[a__name]']

The expansion starts from b (key=b__id), the filtered node, and walks KNOWS incoming. Results are the same either way; only the order of work changes.

Inspecting the CSR¶

csr_stats()¶

One entry per relationship type that has a CSR:

print(engine.csr_stats()["KNOWS"])
# {'edges': 4, 'delta_edges': 0, 'tombstones': 0, 'update': 'build',
#  'version': None, 'build_ms': 0.41}  (build_ms varies)

A relationship type missing from csr_stats() has no CSR (its endpoints aren't integers) and always joins.

node_index_stats()¶

Per node label: rows, version and build_ms. A label is missing when its keys are not unique integers.

print(sorted(engine.node_index_stats()))  # ['Person']

Keeping the CSR current¶

In-memory PyArrow tables never change, so their CSR never needs updating. For Lance datasets, the engine is pinned to a version until you call refresh(), which updates the CSR incrementally:

flowchart TD
    R["engine.refresh()"] --> V{"Relationship dataset<br/>changed?"}
    V -- no --> U["reused"]
    V -- yes --> D{"Diff between the two<br/>Lance versions available?"}
    D -- no --> RB["rebuild"]
    D -- yes --> S{"Pending changes > 25%<br/>of the base CSR?"}
    S -- yes --> RB
    S -- no --> DL["delta: appended edges +<br/>tombstones for deleted ones"]

• Appends become delta edges and deletes become tombstones, both applied on top of the base CSR.
• Once the accumulated delta would exceed 25% of the base, or the dataset was overwritten, or the old version's files are gone, the CSR is rebuilt and the delta folded in.
• Node-table writes never touch the CSR: it stores raw target keys, not row positions. A changed node table rebuilds only its node index.
• The replacement is validated in full before it's swapped in. If anything fails, nothing changes and the previous snapshot stays usable. Queries already running finish on the snapshot they started with.

The 25% threshold is fixed: lookups pay a little for every pending delta edge, and a rebuild clears them. python/benchmarks/csr_delta_accumulated.py measures that trade-off.

Should I turn it on?¶

The benchmarks were all run with use_csr=True.