§5.4 Fast row-ID lookup via a BTree index on _rowid

Part of #8931. See: https://docs.google.com/document/d/1x6Xon1XNZ5XaXHekk5kU0Ujg0A9FCOSLAP1Ry9XTMx8/edit?tab=t.0

Reverse lookup — row id → row address — is today served by RowIdIndex (rust/lance-table/src/rowids/index.rs), an in-memory structure built per manifest generation from every fragment's row id sequence. It is Θ(rows) to build and resident, which is the source of the large-table pathology that stable row ids introduce.

The goal is to replace it with an ordinary BTree scalar index over _rowid, so that the mechanisms that keep any scalar index correct and fast — training, optimize_indices, fragment reuse remap, partial-coverage fallback — serve this one too. The guiding principle is as little _rowid-specific code as possible.

Design

Index. A BTree on _rowid (reserved field id -3, supplied by #9250), keyed row id → row address. Not a bespoke system index and not a separate lifecycle. Opt-in via create_scalar_index initially; auto-creation when stable row ids are enabled is a later, independent decision.

_rowid as a column. FragmentReader serves _rowid uniformly, resolving per fragment whether the physical source is an inline U64Segment in the manifest or the spilled hidden column from #9250. This is the piece that makes training, the coverage fallback and everything downstream generic.

Lookup is a first-class take, not a filter. A filter has set semantics: unordered, dedup-prone, and a miss is indistinguishable from a non-match. The take contract is the SQL shape

SELECT v.ord, t._rowaddr
FROM UNNEST(:ids) WITH ORDINALITY AS v(rowid, ord)
LEFT JOIN t ON t._rowid = v.rowid
ORDER BY v.ord

— a left index-nested-loop join on a unique key, driving side ordered. LEFT preserves misses as null rather than dropping them, ordinality preserves input order, and a duplicate id in the list yields a duplicate output row. Describing it this way rather than as a bespoke TakeByRowIdExec keeps it a take-by-key over any unique indexed column, and makes the uniqueness assertion explicit — which matters because row ids are unique only per branch lineage.

AddRowAddrExec (rust/lance/src/io/exec/rowids.rs) already has this contract on the read side.

Rewrite/compaction. No _rowid-specific handling: once secondary indices store addresses (#8085), a Rewrite invalidates a BTree on _rowid exactly as much as one on a user column — the values are unchanged, the addresses move — and that is what the fragment reuse index exists to fix.

Prerequisites

• #8085 — secondary indices store row addresses. Before it, a BTree returns row ids and an index on _rowid maps rowid → rowid. Larger than it sounds: evaluate_with_options (rust/lance-index/src/scalar/expression.rs:1986) currently runs the translation in the opposite direction via row_addr_result_to_row_ids (rust/lance/src/io/exec/scalar_index.rs:65), gated on uses_stable_row_ids().
• #9250 — _rowid spilled as a hidden column, and given genuine schema presence (see below).
• Transaction V2 in-transaction index maintenance — see "Sequencing".

Work items

1. _rowid as a real schema field. scalar_index_info (rust/lance/src/index.rs:3481) errors for any index whose field id does not resolve in the schema, and that runs on the planning path of every filtered scan — so an index at field id -3 breaks all filter planning until _rowid is a Field. Index creation rejects it earlier for the same reason (index.rs:2044, resolve_index_column at :3722), and index_group_is_scalar (:2498) silently misclassifies an unresolvable field id as a vector index. Today _rowid is a name-matched boolean flag (is_system_column, ProjectionPlan setting with_row_id), not a field. This is one root cause behind ~6 separate breakages and belongs to #9250.
2. Unindexed-fragment fallback. Fragments outside the index's fragment_bitmap fall back to reading _rowid, the same partial-coverage fallback any BTree has. The union already exists at a single site: FilteredReadExec::apply_index_to_fragment (rust/lance/src/io/exec/filtered_read.rs:1050).
3. A per-key ordered probe. ScalarIndex::search returns a set — SearchResult::Exact(NullableRowAddrSet) (rust/lance-index-core/src/scalar.rs:347) — so it cannot say which input id produced which address. Either the take node joins over the returned set, or the scalar-index API gains an ordered-probe entry point.
4. Enable the remap path under stable row ids. needs_remapping is !dataset.manifest.uses_stable_row_ids() && … (rust/lance/src/dataset/optimize.rs:2851), and optimize.rs:814 hard-errors on defer_index_remap under stable row ids. An address-payload _rowid index is exactly the index that must be remapped after compaction.
5. Sorted-input fast path for BTree training. train_btree_index already requires pre-sorted input; the sort lives one layer up at rust/lance/src/index/scalar.rs:154. So this is a conditional around three lines — but U64Segment::Array is explicitly unsorted (rust/lance-table/src/rowids/segment.rs:80), so the precondition must be checked, not assumed: skipping the sort on unsorted input produces wrong page min/max with no error.
6. Port the RowIdIndex callers. Read-side: AddRowAddrExec, TakeExec::get_row_addrs (take.rs:197), DatasetTake::get_row_addrs (dataset/take.rs:557). Write-side, all running after new fragments are written but before commit: update.rs:495, dataset/utils.rs:120 (synchronous, and panics on a missing id), merge_insert.rs:2840 and :2961, delete.rs:328, Dataset::filter_deleted_ids (dataset.rs:3022).
7. Benchmark. rust/lance-table/benches/row_id_index.rs is the baseline.

Sequencing

#8085 → #9250 → TV2 in-transaction index maintenance → this.

The write-path callers in item 6 run during transaction construction, against fragments that no committed index can cover, so a stale-tolerant index would supplement RowIdIndex rather than retire it. Since retiring it is the point, this waits on in-transaction maintenance.

That in turn needs an answer to fragment-id minting, because an append's index entries all point into fragments whose ids do not exist yet:

1. a preceding ReserveFragmentIds transaction — still two transactions, but no index changes; or
2. Ref::Local fragment ids (Transaction V2, #7954), with committed index metadata carrying a "local fragment 0 was minted as fragment 42" mapping, applied on load by adding 42 << 32 to the address.

Open questions

• Does in-transaction maintenance actually serve the mid-transaction callers? It makes the index complete at steady state, but the callers in item 6 run during construction — the in-flight index delta has to be queryable before commit for them to use it. dataset/utils.rs:120 is synchronous regardless and needs porting to async either way.
• Index size. Θ(rows) on disk — a permutation is a BTree's worst shape. Mitigated by being paged rather than resident, unlike the rejected bloom filter. BTree data is stored in Lance files, so the lever is new Lance encodings, not an index-format special case. Gate: bytes/row measured on both an append-only and a shuffled table.
• Lookup latency. BTree IO granularity is a 4096-row page (DEFAULT_BTREE_BATCH_SIZE), against today's in-memory probe. The plan is sorted batched probes plus the existing page cache; unmeasured.
• A third coverage state. RowIdIndex is complete and deletion-aware — probe returns the address of the fragment holding the id live, and callers read "absent" as "deleted" (filter_deleted_ids). With a fragment_bitmap, "absent" becomes ambiguous between deleted and not-covered, and no call site can express that today.
• Re-entrancy, if #8085 lands incrementally. An address-domain _rowid index whose results are fed to row_addr_result_to_row_ids would be translated through the row id sequences — circular. Moot once #8085 removes that layer entirely.
• Whether DataFusion can carry the driving-side ordering as an output ordering equivalence, so a downstream sort is elided rather than materialized.