lance-format / lance-format/lance
Add benchmarks for the stable row id feature
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
The stable row id feature (off by default) maintains a per-fragment RowIdSequence in fragment metadata and an aggregated RowIdIndex in memory that maps logical row ids to physical row addresses. It adds work on several hot paths: index lookup after search, scan-time row id materialization, prefilter construction, commit, and compaction. We have partial coverage in rust/lance-table/benches/row_id_index.rs (build, single-id get, and apply_row_id_and_deletes — the last with row_id_sequence: None, so the stable path is not exercised). We need broader coverage so we can quantify the on/off cost and catch regressions.
The tasks below are grouped by code path. Each task should land in the most natural existing bench file (or a new one when there is no obvious home).
Search-result mapping (post-index lookup)
- Batch
RowIdIndex::get— extendbench_get_singleinrust/lance-table/benches/row_id_index.rswith a batched variant that mirrorsAddRowAddrExec::compute_row_addrs(rust/lance/src/io/exec/rowids.rs:129). Vary batch size (1k / 10k / 100k / 1M) and access pattern (sequential, random, clustered). The current single-id bench under-reports cost because it doesn't capture cache behavior ofRangeInclusiveMap::getfollowed byU64Segment::position. -
RowIdSequence::mask_to_offset_ranges(rust/lance-table/src/rowids.rs:387) — called per fragment after every scalar-index match infiltered_read.rs:718,727,732. Not benched today. Vary segment shape (Range,RangeWithHoles,RangeWithBitmap,SortedArray) and mask selectivity (1%, 10%, 50%, 99%). -
RowIdSequence::select(rust/lance-table/src/rowids.rs:341) — hot path insideapply_row_id_and_deleteswhen stable row ids are on. The existingApplyRowIdbench skips this path (row_id_sequence: None). Add a variant that passes a real sequence so we measure the stable-row-id select cost per scan batch.
Index loading (cold-cache cost)
get_row_id_index (rust/lance/src/dataset/rowids.rs:73) is cached per manifest.version, so the first call after a commit pays the full cost.
- End-to-end "open dataset → first lookup" — load all fragment sequences (
load_row_id_sequence), proto-decode them (read_row_ids), and callRowIdIndex::new. Vary fragment count (10 / 100 / 1000) and rows per fragment. -
RowIdIndex::newwith realDeletionVectors — the existingBuildIndexbench applies deletions viaRowIdSequence::deleteand always passesDeletionVector::default(), so thedecompose_segment_with_deletionsslow path (rust/lance-table/src/rowids/index.rs:164) is never hit. Add a case that populates the deletion vector instead. -
RowAddrTreeMap::from(&RowIdSequence)— used inprefilter.rs:172,index/append.rs:69, andscalar_index.rs:647. Not benched. Vary segment shapes and sequence size.
Prefilter cost on vector search
-
do_create_deletion_mask_row_idvsdo_create_deletion_mask(rust/lance/src/index/prefilter.rs:130vs:80) — when stable row ids are on, every vector search that hits the prefilter loads all fragment sequences, masks deletions, builds an allow-listRowAddrTreeMap, and unions across fragments. This is likely the single largest production cost of the feature; we have no benchmark for it. Compare on/off at matched scale.
Commit / write overhead
-
Transaction::assign_row_ids(rust/lance/src/dataset/transaction.rs:2781) — per-commit serialization of aRowIdSequencefor each new fragment viawrite_row_ids. Bench K new fragments × N rows/fragment. -
write_row_ids/read_row_ids(rust/lance-table/src/rowids/serde.rs:195,201) — pure proto serde. Small but on both commit and read paths. Vary segment shape and size. - End-to-end
Dataset::write(Append) withenable_stable_row_ids: truevsfalse, varying number of fragments per commit. Lives inrust/lance/benches/.
Compaction overhead
-
rechunk_stable_row_ids(rust/lance/src/dataset/optimize.rs:1312) — loads old sequences, masks deletions, rechunks, re-serializes. Pure overhead on top of compaction when stable row ids are on. -
rechunk_sequences(rust/lance-table/src/rowids.rs:598) — not benched. Vary input/output chunking ratios. - End-to-end
compact_fileswith stable row ids on vs off, varying deletion fraction.
take_rows by row id
-
Take::get_row_addrs(rust/lance/src/dataset/take.rs:526) — single-callrow_id_index.getper id, similar shape to the search-result mapping case but a separate user-visible operation. Add torust/lance/benches/take.rs(or a new bench if it doesn't fit), comparing stable on/off.
Notes
- Where existing benches accept env vars (e.g.
BENCH_NUM_ROWSinrow_id_index.rs), keep the same convention. - For end-to-end benches, also report on-disk manifest size delta so we can track the storage cost of inline
RowIdMeta. - The
RowIdIndexis rebuilt per manifest version. Benches that target a singlegetormask_to_offset_rangescall should not include build cost; benches that target "first query after commit" should.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with rust/lance-table/benches/row_id_index.rs and compare the existing bench_get_single and ApplyRowId coverage with rust/lance/src/io/exec/rowids.rs:129. Choose one code path to scope first, preserve the existing BENCH_NUM_ROWS convention, and run the relevant benchmark; done means the selected stable-row-id path has coverage for the requested input sizes or shapes and reports comparable on/off cost.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data, performance, testing-qa
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100