perf: fix O(N²) version column scan with deletion vectors

[pengw0048]

Problem

Scanning _row_created_at_version or _row_last_updated_at_version is extremely slow on fragments with deletion vectors — 53 seconds for 1M rows (vs 0.03s for a regular data column on the same table).

This makes the delta() API (get_inserted_rows() / get_updated_rows()) unusable on any table that has had deletions.

Root Cause

In apply_row_id_and_deletes() (lance-table/src/utils/stream.rs), the version column is built by:

sequence.versions()
    .skip(r.start as usize)
    .take((r.end - r.start) as usize)

versions() creates a fresh iterator from the start of the RLE sequence. For each range in the selection, skip(r.start) walks through all prior elements — O(rows) per range. With deletion vectors creating many small ranges, this becomes O(rows × ranges).

Fix

Replace with version_values_for_selection() that:

• Fast-paths single-run fragments (common case: all rows same version) with vec![version; count] — O(1)
• Binary search over precomputed run offsets for O(log(runs)) per position in the multi-run case

Benchmark

1M rows, 33% deleted, _row_created_at_version scan:

	Before	After
Time	53s	0.02s
Complexity	O(rows × ranges)	O(rows × log(runs))

Minimal Reproduction

import lance, pyarrow as pa, numpy as np, time

uri = "/tmp/test_version_col_perf.lance"
lance.write_dataset(
    pa.table({"val": np.random.randint(0, 1000, 1_000_000)}),
    uri, mode="overwrite", enable_stable_row_ids=True,
)
ds = lance.dataset(uri)
ds.delete("val < 333")
ds = lance.dataset(uri)

t0 = time.time()
ds.scanner(columns=["_row_created_at_version"]).to_table()
print(f"_row_created_at_version with deletions: {time.time()-t0:.2f}s")

t0 = time.time()
ds.scanner(columns=["val"]).to_table()
print(f"normal column with deletions: {time.time()-t0:.2f}s")

[codecov]

Codecov Report

❌ Patch coverage is 96.17834% with 6 lines in your changes missing coverage. Please review.

Files with missing lines	Patch %	Lines
rust/lance-table/src/utils/stream.rs	96.17%	6 Missing ⚠️

📢 Thoughts on this report? Let us know!

[BubbleCal]

Thanks for the great improvements!

[BubbleCal]

i think we will get an error at https://github.com/lance-format/lance/pull/6375/changes#diff-e3ed3f2ff36ff45b28ec19c75b4b9fadcfd857e2ced681ceb22b07fdc4e705b4R360 if we don't have enough rows, but this would hide the error

[BubbleCal]

need one more test to cover this path

[BubbleCal]

Good to go once we have all greens

[pengw0048]

@BubbleCal could you approve the workflows again? Fixed the formatting and the windows test failure seemed unrelated.