How Lance Implements Stable Row IDs and Their Encoding

In Lance, stable_id (officially Stable Row ID) is a logical u64 identifier stored in the column _rowid, while address_id (Row Address) is the physical location stored in _rowaddr. When stable IDs are enabled, each row receives a monotonically increasing ID from the manifest's next_row_id that never changes across compaction or updates; only the physical address changes.

Without stable IDs, _rowid is merely an alias for _rowaddr, and both identifiers change after compaction or update, making them unsuitable as persistent primary keys.

The core problem solved by stable IDs is the mismatch between mutable physical addresses and the need for a stable row identifier for business logic, secondary indexes, CDC, and update handling. The table below summarizes scenarios:

Compaction : fragment offsets are reordered, invalidating row addresses; stable _rowid stays constant and only the RowIdIndex (mapping _rowid → new address) needs updating.

Update : the old physical row is tombstoned and a new row is written at a new address; the same stable _rowid is reused while the old address is recorded in a deletion vector.

CDC / Incremental processing : stable IDs allow reliable change capture when combined with _row_created_at_version and _row_last_updated_at_version.

Index maintenance : experimental indexes can store stable IDs so that compaction no longer requires a full remap.

Most secondary indexes (vector, scalar, full‑text) still use row address as the key; stable‑ID‑based indexes are experimental.

Encoding relationship between the two identifiers

The physical address is computed as:

row_address = (fragment_id << 32) | local_row_offset

For example, the first row of fragment 1 is (1 << 32) + 0.

During table loading, a RowIdIndex is built from each fragment's row_id_sequence:

row_id → (fragment_id, row_offset) → row_address

The row_id_sequence stores, for each physical offset 0..N in a fragment, the corresponding stable row ID. It can be inlined (< 200 KB) or external if larger.

Assigning IDs works by taking a contiguous range from next_row_id, serializing it into a RowIdSequence, writing it to row_id_meta, and advancing next_row_id.

Design of the RowIdSequence

Storing a raw u64 per row would be prohibitive (≈800 MB for 100 M rows). Observations:

Newly written IDs are naturally consecutive, forming a range.

Deletions and merges create holes, yielding a range with holes or a bitmap.

Compaction reorders offsets but retains IDs, which may become a sorted array.

IDs are unique within a table (except tombstones), enabling a global index.

Therefore the sequence is represented as RowIdSequence = Vec<U64Segment>, where each segment is encoded based on its density:

Ordered?
├─ Yes → Continuous?
│   ├─ Yes → Range (16 bytes fixed)
│   └─ No → Sparsity decision
│       ├─ Few holes → RangeWithHoles
│       ├─ Many holes → RangeWithBitmap
│       └─ Very sparse → SortedArray (bit‑packed)
└─ No → Array

Newly appended fragments are almost always a simple Range{start: next_id, end: next_id+N}, keeping metadata overhead near constant.

During compaction ( rechunk_stable_row_ids), old sequences are cleaned of deleted rows and rechunked into new fragments; logical IDs stay the same while physical order changes.

Building the RowIdIndex at table load

The index is constructed lazily the first time get_row_id_index is called, and then cached per version. The steps are:

1. Parallel load_row_id_sequences(all fragments)
   └─ Inline: deserialize bytes
   └─ External: read object‑store slice then deserialize
2. Parallel load deletion vectors (if any)
3. For each FragmentRowIdIndex:
   decompose_sequence:
     - Iterate each U64Segment
     - Compute start address = RowAddress::first_row(fragment_id)
     - For each row_id in the segment, if offset not deleted, emit (row_id, start_address + i)
     - For a Range segment without deletions, emit O(1) row_id and address ranges
4. Sort all chunks by row_id range and merge overlapping intervals (updates may temporarily produce duplicate IDs, filtered by deletion vectors)
5. Insert merged chunks into RangeInclusiveMap<u64, (row_id_segment, address_segment)>

Querying works as:

RowIdIndex.get(row_id):
  1. Locate the chunk covering the ID (O(log #chunks))
  2. Position the row_id within the segment
  3. Retrieve the address at the same position

This transforms a physically ordered ID sequence into an ID‑ordered searchable mapping.

Advantages and disadvantages (first‑principles view)

Advantages

Write path cheap: a new fragment needs only a single Range, almost zero metadata growth.

Locality: compaction rewrites only the affected fragment’s sequence, not a global table.

Encoding matches real data distribution: contiguous IDs → constant size; holes → holes/bitmap; disorder → fallback to array, worst‑case similar to a plain vector.

Orthogonal to deletions: tombstoned rows need not immediately modify the sequence; deletion vectors filter them at load time.

Forward lookup fast: known address → sequence[offset] is O(1), useful for scans projecting _rowid.

Disadvantages / costs

Reverse lookup requires building the index; the first query incurs latency to read all sequences (and deletion vectors) for large tables.

Query adds an extra indirection: row_id → address → data, compared with indexes that store address directly.

After compaction, sequences may degrade from Range to SortedArray or Array, increasing metadata size and build time.

Memory: the RowIdIndex stays resident per version; many fragments or highly shuffled IDs increase the number of chunks and memory usage.

Cannot be added retroactively; stable IDs must be enabled when the dataset is first created.

Update semantics are complex: updates write a new physical row and tombstone the old one; the index builder must combine deletion vectors correctly to avoid mapping to dead addresses.

Enabling stable row IDs

Stable IDs must be turned on when the dataset is first created; existing datasets cannot be switched on later. Example in Python:

import lance
import pyarrow as pa

table = pa.table({"name": ["Alice", "Bob"], "age": [20, 30]})
# Enable at creation
lance.write_dataset(table, "/path/to/dataset", enable_stable_row_ids=True)

ds = lance.dataset("/path/to/dataset")
assert ds.has_stable_row_ids is True

# Read both identifiers
tbl = ds.scanner(with_row_id=True, with_row_address=True).to_table()
# tbl["_rowid"]   → stable row ID
# tbl["_rowaddr"] → row address

The manifest records the flag FLAG_STABLE_ROW_IDS, which can be queried via dataset.manifest.uses_stable_row_ids() or ds.has_stable_row_ids.

Reverse conversion (row address → stable row ID)

There is no global reverse index; conversion requires two steps:

Decode the address: fragment_id = addr >> 32, row_offset = addr & 0xFFFFFFFF.

Read the fragment's row_id_sequence and fetch sequence.get(row_offset) to obtain the stable row ID.

In Rust the API is RowIdSequence::get(index: usize) -> Option<u64>, which maps a position to a row ID. If the offset is marked deleted in the deletion vector, the address should not be mapped to a valid row.