perf(table): avoid expanding compact row ID ranges when building RowIdIndex #9487

Description

PR #9311 introduced U64Segment::Ranges to keep row IDs with clustered gaps compact in memory. RowIdIndex::new can undo that saving while building its merged index. In decompose_segment_no_deletions, a plain Range has a compact path, but Ranges falls through to the general path. That path enumerates every live row ID, pairs it with a physical address, sorts the pairs, and encodes them again.

For a Ranges segment without a deletion vector, the row ID segment already knows each present ID's position. The corresponding physical addresses are contiguous in sequence order, so the merged index can retain Ranges and use an address Range.

Reproduction and measurement

The runnable benchmark and proposed change are in this commit. BuildIndexClusteredRanges constructs 100 fragments covering 1,000,000 row ID slots. Each fragment repeats 250 present IDs followed by 250 missing IDs, for 500,000 live IDs in total. The fixture serializes plain protobuf ranges and decodes them into compact Ranges segments before timing. All deletion vectors are empty.

Criterion times only RowIdIndex::new; fixture construction and protobuf decoding are outside the timed loop. I ran the same benchmark on the same machine and build profile with 30 samples per variant. To obtain the baseline, I removed only the U64Segment::Ranges match arm added by the linked commit, leaving the benchmark unchanged.

That is about 164 times faster for this index-build benchmark. It is not a measurement of dataset opening, storage I/O, or query latency. The benchmark deliberately uses nonoverlapping fragments and empty deletion vectors, so it exercises the compact merged-index path.

To run the optimized case from the linked commit:

BENCH_NUM_ROWS=1000000 cargo bench --profile release-with-debug -p lance-table --bench row_id_index -- BuildIndexClusteredRanges --sample-size 30 --measurement-time 3

Environment: Lance 13.0.0-beta.9 source, Linux x86_64, Intel Core i7-11700F, Rust 1.97.0. The benchmark case is in the linked commit and is not yet on upstream main.

Correctness conditions

For the present ID at position k in a Ranges segment, the existing expansion path assigns address start_address + k. Ranges::position(id) returns the same k, and a contiguous address Range yields the same address. IDs in gaps have no position and must still return no address. Chunks with overlapping bounding ranges must continue through the existing overlap merger, including its duplicate-ID check. Segments with deletion vectors must continue through the deletion-aware path.

The linked commit includes tests for gaps, a preceding segment that shifts physical offsets, overlapping bounding ranges, and batched lookups. cargo test -p lance-table rowids:: passes all 131 row ID tests on that commit. The change does not modify the on-disk format.

#6707 tracks broader stable row ID benchmarks. #9474 proposes a longer-term replacement for the current in-memory RowIdIndex.

Feedback

@Xuanwo, you reviewed #9311, and @westonpace, you opened #6707. I would value your views on whether this is the right improvement for the current index and whether there is a representative real-manifest workload we should measure alongside this benchmark.

I would like to work on this issue and follow up with a PR. The linked commit contains the current implementation and benchmark.