lance-format / lance-format/lance

Add benchmarks for the stable row id feature

Open
#6,707 2 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

benchmark enhancement performance
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 — extend bench_get_single in rust/lance-table/benches/row_id_index.rs with a batched variant that mirrors AddRowAddrExec::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 of RangeInclusiveMap::get followed by U64Segment::position.
  • RowIdSequence::mask_to_offset_ranges (rust/lance-table/src/rowids.rs:387) — called per fragment after every scalar-index match in filtered_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 inside apply_row_id_and_deletes when stable row ids are on. The existing ApplyRowId bench 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 call RowIdIndex::new. Vary fragment count (10 / 100 / 1000) and rows per fragment.
  • RowIdIndex::new with real DeletionVectors — the existing BuildIndex bench applies deletions via RowIdSequence::delete and always passes DeletionVector::default(), so the decompose_segment_with_deletions slow 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 in prefilter.rs:172, index/append.rs:69, and scalar_index.rs:647. Not benched. Vary segment shapes and sequence size.

Prefilter cost on vector search

  • do_create_deletion_mask_row_id vs do_create_deletion_mask (rust/lance/src/index/prefilter.rs:130 vs :80) — when stable row ids are on, every vector search that hits the prefilter loads all fragment sequences, masks deletions, builds an allow-list RowAddrTreeMap, 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 a RowIdSequence for each new fragment via write_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) with enable_stable_row_ids: true vs false, varying number of fragments per commit. Lives in rust/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_files with 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-call row_id_index.get per id, similar shape to the search-result mapping case but a separate user-visible operation. Add to rust/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_ROWS in row_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 RowIdIndex is rebuilt per manifest version. Benches that target a single get or mask_to_offset_ranges call should not include build cost; benches that target "first query after commit" should.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.