Goal

We should stop rebuilding the CSR on every engine start: load it from a stored file instead and keep it in memory as today. No memory-mapping and no unsafe code; a graph whose topology doesn't fit in memory still runs out of memory, as it does today.

The design note below is the plan. It's staged so each part ships, and is benchmarked against main, on its own. Stage 1 shipped in #87, and Stage 2 shipped for the CSR in #109 (released in 0.6.0). What's left in this issue is storing node indexes the same way; Stage 3 is #81. The wider effort is tracked in #80.

Design note: a persisted CSR

Status: Stage 1 shipped in #87 (closing #73). Stage 2 shipped for the CSR in #109, in 0.6.0; node indexes are still built at every start. Stage 3 is tracked in #81 and blocked on Lance. First written: 2026-10-28. Updated: 2026-11-03, for main at 85fe9a1 (0.6.1).

This note describes how lance-csr's CSR index stops being rebuilt on every engine start. Stages 1 and 2 are done and are summarised below as built, including where Stage 2 differs from what this note first proposed.

Summary

The CSR is a derived index that lives in memory. Without stored files, every process builds it from a full scan of each relationship table's endpoint columns, in both memory and lazy mode. LadybugDB, by contrast, stores its relationship tables as CSR on disk, so opening a database builds nothing.

lance-csr can't copy that design, because Lance is the source of truth and any process can write to it. The CSR has to stay a derived index. So it stays in memory, as before, but can be loaded from a file instead of built:

1. Stage 1 (done, feat(csr)!: keep named relationships on the csr with edge rows #87). Store each edge's Lance row address next to its neighbour. Hops that name a relationship variable stay on the CSR, and a CSR can be brought up to date without the old dataset version's files.
2. Stage 2 (done for the CSR, feat(csr)!: store the csr inside each lance dataset and pack edge rows #109). With persist_csr=True, store the base CSR as an immutable file per dataset version inside the relationship dataset, and read it whole at engine start instead of building. Node indexes are the part still to do.
3. Stage 3 (Build the CSR as a native Lance adjacency index #81). Move the same layout into a native Lance index once Lance supports pluggable index kinds.

The CSR still has to fit in memory. A graph whose topology doesn't fit fails with an out-of-memory error, as it does today.

Where we are today

Two properties are worth keeping:

• Neighbours are raw keys. Writes to a node table rebuild only that label's node index, never the CSR. This is also why icebug-format was ruled out as the file layout (Evaluate icebug-format as the persisted CSR layout #77).
• Lance keys, CSR positions and row ids are separate. lance-graph's open native expand PR used one value for all three, and its review showed it returns the wrong rows when keys don't match physical offsets. We already avoid that.

The problem

Every process paid a full build before its first CSR query, even when the data hadn't changed since the last run: on GDC SF1 read lazily, about 1.7 s of engine start. Stage 2 removes that for the CSR. Node indexes are still built from a scan of each node table at every start, and are the remaining start-up cost this issue covers.

Goals and non-goals

Goals:

• Opening an engine over data whose CSR was already built costs a file read, not a scan of every edge. That holds after appends, deletes, compaction and old-version cleanup, as long as the pending changes stay under the rebuild threshold.
• No query returns a different answer than it does today, in either mode.
• Memory mode doesn't get slower.

Non-goals:

• Topology larger than memory. The CSR is loaded whole. No memory-mapping, no partial loading and no unsafe code. A graph that doesn't fit runs out of memory, as it does today. (Partial loading would need the async lookups in Look up CSR neighbours with async, batched calls #74.)
• Owning the write path. No in-place CSR updates, write-ahead log or buffer manager. Lance and its writers stay in charge of the data.
• A new storage format for users. Relationship tables stay ordinary Lance datasets with no required row order.
• Distributed execution, which is out of scope for the project.
• Factorized execution and multi-source BFS. Both matter for multi-hop speed but are independent of storage; see Related work.

The constraint everything follows from

The CSR is derived from a Lance dataset at a pinned version, and other processes can commit new versions at any time. So a stored CSR is only usable when it's provably about a specific dataset version, and the engine can either use it as is (same version) or bring it up to date (an older version of the same dataset). Every stage keeps that rule.

Stage 1: edge row addresses per slot (done)

Shipped in #87. Each CSR slot carries the Lance row address of its edge in an edge_rows array aligned with neighbors. That gave us:

• Relationship variables on the CSR, with only the requested columns of k fetched by row, and filters on k evaluated inside the expansion.
• Edge identity. Parallel edges keep separate rows and properties, as on the join path.
• Updates without the old dataset version. The edges of a removed or rewritten fragment are the slots whose address has that fragment id, and newly deleted rows are the slots whose address is in the new deletion vector. Only added fragments are read from Lance. Stage 2 depends on this: without it, a stored CSR would become a full build as soon as its version is cleaned up.

Measured costs: peak build memory went from about 62 to about 94 bytes per edge at 10M edges, and the build is about 1.35 times slower. #109 then packed the edge rows, which brought the resident CSR at SF1 from 926 to 732 MiB.

The planning risk this note flagged turned out real: IC5, which filters hasMember on joinDate, got 32% slower in memory mode and 69% slower in lazy mode in #87. #94 fixed the lazy case by reading target columns once for broad hops, and #100 recovered most of the memory-mode loss by filtering in-memory relationship columns per chunk (#92 is closed). The remaining cost is grouping after the hop, tracked in #99.

Still a later feature: cross-hop edge predicates inside variable-length paths.

Stage 2: stored CSR files (done for the CSR, #109)

Shipped in #109 and released in 0.6.0, behind persist_csr=True on CypherEngine (Python) and EngineOptions::persist_csr with CypherEngine::with_options (Rust). Both are marked experimental. Without the flag, nothing is written and behaviour is the same as before.

Where files live

Inside each relationship dataset's own directory, in a _lance_csr/ folder at its root, one file per dataset version:

knows.lance/
  _versions/  data/  _deletions/  _indices/  _transactions/
  _lance_csr/
    42.arrow

In a LanceDB database that's db/knows.lance/_lance_csr/, so the CSR stays with the table it belongs to: dropping the table removes it and copying the dataset carries it along. In Lance 13, cleanup_old_versions() only deletes files it recognises (cleanup_file_if_not_referenced in lance/src/dataset/cleanup.rs), so it leaves the folder alone. Compaction followed by cleanup was tested and stays a delta.

File format

One file holds both directions of the base CSR (not the delta), where this note first proposed a file per direction. It's an Arrow IPC file with a single UInt64 column and one zstd-compressed record batch per array, 6 arrays per direction, outgoing then incoming:

The schema metadata records lance_csr.format (currently "2"), lance_csr.version (the dataset version), lance_csr.endpoints and lance_csr.fields (the endpoint column names and Lance field ids), and lance_csr.fragments (the fragments the base was built from, which edge_changes_since compares against).

The arrays are the in-memory layout as is, so a load neither builds nor packs anything: it decompresses the batches with a zero-copy FileDecoder and rebuilds only the map from key to position, one insert per source. This answers the first open question: Arrow IPC as the container, but in lance-csr's own layout. The file opens in pyarrow, but its arrays aren't meant to be read on their own, and the docs say so.

Loading

flowchart TD
    O["Engine opens relationship<br/>dataset at version v"] --> F{"Newest stored file<br/>at or before v?"}
    F -- none or unusable --> B["Full build, then<br/>store it as version v"]
    F -- found --> D["Load it as the base, apply<br/>the changes since as a delta"]
    D --> T{"Delta > 25%<br/>of the base?"}
    T -- yes --> B
    T -- no --> Q["Ready"]
    B --> Q

• The engine looks for stored files only at construction. checkout_latest() brings the CSR it holds in memory up to date, as before, and doesn't read files.
• A file for the same version loads with no delta. An older one loads with the changes since applied as a delta, read from the added fragments only, under the same 25% threshold as checkout_latest(). csr_stats() reports update "loaded" and base_version as the stored version.
• Every full build is stored: at a start, from checkout_latest() past the threshold and from optimize_csr(). Files are never modified in place.

Writes, validation and cleanup

• Writes go through the dataset's own object store with put_if_absent. If a file for that version already exists, it's deleted and written again: the engine only stores after a build, so an existing file there either wasn't usable or holds the same content another process just wrote.
• Validation. A file is used only if it parses, has the current format, its dataset version is at or before the engine's, every array is well formed and its endpoint fields match. The delta compares fragments by id and data files, so a stale file from a dataset recreated at the same path shows up as a full rewrite and is rebuilt. Anything unusable is ignored and rebuilt, never trusted; a file that fails to decode also logs a warning.
• Read-only datasets. A failed write (read-only storage or credentials) logs a warning, and the engine keeps the in-memory build. The next start builds again.
• PyArrow inputs are never stored, including Lance data loaded with to_table(), so the benchmarks' memory mode doesn't use this.
• Cleanup. Instead of the explicit keep-the-newest method this note proposed, older files are deleted as soon as a newer one is written. delete_stored_csr() removes every stored file of the engine's relationship datasets and returns how many it deleted, for going back to in-memory builds only.

Results

On GDC SF1 read lazily (23 relationship types, 17.3M edges), fresh processes, medians, on an Apple M5:

The stored files take 134 MiB at SF1, against 711 MiB uncompressed. Compressing adds about 0.9 s to the first start, and decompression takes most of a load. python/benchmarks/csr_persist.py measures the same cases on a synthetic graph: at 10M edges, a load took 55 ms against 1.18 s for a build.

Both gates passed. Both suites, both modes, against main with the CONTRIBUTING.md harness: every answer matched, and every suite's geometric mean stayed within 3% of main, including lazy runs that loaded every stored CSR. IC3 in memory mode stayed about 3% slower in a five-process A/B; its hops don't read edge rows, so the cause isn't known.

Still to do: node indexes

The target-side key-to-row map (NodeRows, reported by node_index_stats()) is still built from a scan of each node table at every start, including when the CSR is loaded. How much of the 0.46 s load it accounts for hasn't been measured. It could go in the node table's own _lance_csr/ folder in the same format (keys plus row ids), validated the same way. Open question: use a Lance B-tree scalar index on the node table's ID column when one exists, instead of our own file?

Two smaller follow-ups:

• If loading many relationship types still adds up, an engine could load each type's file on the first query that uses it instead of at construction. That moves the cost; it doesn't remove it.
• A future Lance release could garbage-collect files it doesn't recognise, or claim the folder name. Validation turns either into a rebuild rather than a wrong answer, but it may be worth asking the Lance maintainers to reserve _lance_csr.

Stage 3: a native Lance adjacency index (#81)

lance-graph's roadmap (lance-format/lance-graph#159) argues that the right long-term home is a new Lance secondary index kind over a relationship dataset's endpoint columns. Lance would then build and update it as part of its own commits and tie it to a dataset version. That answers "who keeps the CSR in sync with writers we don't control" better than files lance-csr writes itself can.

It's blocked on Lance supporting pluggable index kinds. Until then, Stage 2's files are the stepping stone, and keeping their layout means the move is mostly a change of where the bytes live. The index would still be loaded whole into memory; partial loading stays out of scope.

Most of the user-facing side already follows Lance's index model:

• Freshness contract. An index covers some fragments; unindexed fragments are applied as a delta at load, so results stay exact. edge_changes_since already does this fragment comparison, for stored files too.
• Coverage reporting is done (feat(csr): report how far the base csr trails the data #93): csr_stats() reports base_version against version, and unindexed_edges, Lance's num_unindexed_rows.
• An explicit optimize step is done (feat(csr): fold the delta into a new base with optimize_csr() #98): optimize_csr() rebuilds a CSR that carries a delta into a new base and, with persist_csr, stores it, the way Lance pairs checkout_latest() with optimize_indices().

Ideas from lance-graph not taken

• One value as key, CSR position and row id (lance-graph#162's "dense ROWID" model). It only works when keys equal physical row offsets, and gives wrong answers otherwise.
• Separate topology and materialization operators (lance-graph#162's CsrExpandExec plus LanceTakeExec). Our fused lookup fetches only the requested columns and applies pushed-down target and edge filters before fetching the rest; splitting them would lose that.
• Partial, range-loaded adjacency reads (lance-graph#159). They need async lookups (Look up CSR neighbours with async, batched calls #74) and only pay off when the topology doesn't fit in memory, which is a non-goal here.

Related work not in this note

• Multi-source BFS (Run shortestPath from many sources with multi-source BFS #76), from the DuckPGQ paper cited in lance-graph#159: many breadth-first searches over the CSR at once using bitsets, for shortestPath from many start nodes.
• Factorized expansion (Expand multi-hop patterns without materializing every intermediate row #78, with Explore FFX-style packed factorized execution for multi-hop CSR #105 exploring an FFX-style design): operators that carry neighbour lists instead of expanded rows until a RETURN needs them. A first narrow step landed in perf(planner): count two-hop paths from per-node degrees #97, which counts two-hop paths from node degrees. This is likely where most of the remaining multi-hop gap to LadybugDB is, and it's independent of how the CSR is stored.
• Narrower neighbour IDs (Shrink the CSR's per-node map and neighbours #79). feat(csr)!: store the csr inside each lance dataset and pack edge rows #109 packed the edge rows, in memory and in the stored file. Packing neighbours the same way roughly halved them, but every hop reads neighbours and custom Q30 got about 22% slower, so they stay plain u64 for now. Shrink the CSR's per-node map and neighbours #79's u32 offset idea doesn't fit SF1, whose node keys span up to 2^45.

Open questions

1. Our own node index file, or a Lance B-tree index on the node ID column?
2. What does Lance's pluggable index API look like, and when? (Stage 3, Build the CSR as a native Lance adjacency index #81)

Answered:

• The file is Arrow IPC with zstd, in lance-csr's own layout rather than columns meant for pyarrow (feat(csr)!: store the csr inside each lance dataset and pack edge rows #109).
• The file won't follow icebug-format. It stores dense node positions, which would break the raw-key layout; see Evaluate icebug-format as the persisted CSR layout #77. Interchange with LadybugDB stays possible as a separate export step.