Table format · Design sketch
Today a stable row id is a counter value with no structure, so finding a row means consulting a global index that is rebuilt in memory on every dataset version. This rework defines the id as the row's birth address — the fragment and offset where it was first written. A row that never moves resolves through pure identity; only moved rows appear in a small relocation view, transposed in memory from metadata the table already stores. Cost lands on movement, never on existence.
id → point entries → range entries → else id is the address. The counter in the manifest disappears; id allocation conflicts collapse into fragment id rebase. One spec change makes this sound: overwrite must inherit the fragment-id high-water mark instead of resetting to zero.The current design persists only the forward map — each fragment stores the id sequence of its rows. The reverse map, id to address, is rebuilt in memory from every fragment and every deletion vector, on every version. And because a counter id says nothing about where a row lives, whole-table scans creep into paths that should be cheap.
Every update rewrites one row under its old id, somewhere new. Each rewrite punches a hole in one interval and opens another — the map only ever gets more fragmented, and the whole thing is rebuilt in memory each time the dataset version advances.
| updates | index size | |
|---|---|---|
| 0 | 125 KB | |
| 1 000 | 5 MB | |
| 10 000 | 7.8 MB | |
| 100 000 ² | 75 MB | |
| 1 000 000 ² | 750 MB |
² extrapolated in the issue. The same shapelessness leaks into query paths: prefilters must materialize an allow-list of every live row, where the address world gets away with a block-list of deletions. Deletion and movement are sparse events; the common case ends up paying for them.
There is also a standing tax not visible in any single number: stable and non-stable ids are two id semantics threaded through scanner, take, prefilter, every index type, compaction and conflict resolution — and each operation × index × mode combination is its own bug surface. The mode is chosen at table creation and cannot be changed later.
Stability never required shapelessness. The id only has to survive moves — it can still remember where the row was born. Three rules make that identity almost free.
// minted once, at first write row_id = birth_fragment << 32 | birth_offset // invariants I1 id never changes while the row lives I2 fragment ids are never reused → ids are globally unique, no counter → requires: overwrite inherits max_fragment_id I3 a fresh fragment's id sequence is the implicit range frag<<32 .. frag<<32+len → zero metadata until something moves // resolution, in order resolve(id): point_entries[id]? // moved by update range_entries[id]? // moved by compaction else id is the address // never moved
Fragments written by update or compaction carry a positional RowIdSequence, exactly like today, so scans can emit _rowid and index builds can read it. Fragments where nothing moved don't need one at all.
The relocation view is the in-memory transpose of those forward sequences: range entries for whole compaction moves, point entries for updated rows. Dedup and run-collapsing happen during the transpose; an optional checkpoint snapshots the result as a standard Lance file.
Any rewrite rewrites the sequences of the rows it moves, so the transpose always yields the current address: one lookup, one answer. When the same id appears twice (a row updated twice), the larger (fragment, offset) wins — writes only ever land at newer positions.
A miniature dataset: two native fragments, ids shown as fragment·offset. Select a row, then mutate the table and watch what each operation contributes to the relocation view — entries derived from fragment metadata, never a persisted log — and what a read of that id has to touch afterwards.
Three things to notice. Updating the same row twice replaces its point entry — the view tracks current positions, never chains. Compaction reissues entries for everything it moves: contiguous survivors become one range entry each, previously-updated strays get fresh point entries; reads stay single-hop no matter the history. And the whole right-hand panel is derived — it is the in-memory transpose of the fragments' forward id sequences, recomputable at any time.
The structural change is where cost attaches: to rows that moved, not rows that exist. Everything below follows from that one shift.
| path | today | reworked |
|---|---|---|
| Cold start | rebuild O(table) in memory | O(moved) transpose; ≤1 GET with checkpoint |
| Commit overhead (S3) | sequences ride the manifest | same — zero extra requests |
| Prefilter mask | allow-list of all live rows | per-fragment ranges − tombstones + moves |
| Take by id | global index lookup | unmoved: none · moved: in-memory search |
| 1M-update footprint | ~750 MB, per version ² | ~16 MB resident, derived ³ |
A Lance table's file storage version is a table-level property, fixed at creation, forever. That single value is the whole gate — no new feature flag, no per-table mode.
Every table created at 2.3 has birth-address ids — not opt-in, not opt-out. Format 2.3 does not contain the counter-id mechanism at all; scanner, take, prefilter and conflict resolution carry a single id model.
Address tables stay address; counter-id stable tables keep their legacy ids for life — rewriting them under new ids would break a user-visible promise. The only path into the new model is rebuilding into a 2.3 table, with the id change stated, never silent.
One behavior fix: overwrite inherits the fragment-id high-water mark (the manifest field already exists). One new field: an optional checkpoint reference — and the checkpoint itself is a standard Lance file, not a new format.