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.

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.

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.