Point lookup by stable row id costs ~2 minutes of CPU when row-id sequences hold holes

[pengw0048]

Problem

LanceDataset._take_rows with a single stable row id costs about two minutes of pure CPU on a large dataset whose row-id sequences contain holes. The cost does not scale with the number of requested row ids. A second call on the same LanceDataset object returns immediately. The work therefore looks like a one-time resolution across the whole dataset, not a per-id lookup.

Measurements

pylance 9.1.0-beta.2, release wheel, Linux x86-64, dataset in the same AWS region.

Dataset A — 15.4B rows, 17,601 fragments. A compaction materialized its deletions, so its row-id sequences hold holes.

call	wall	cpu
lance.dataset(uri)	10.9 s
_take_rows(row_ids=[1 id], columns=["a_float_col"])	134 s
_take_rows(row_ids=[3 ids], columns=["a_float_col"])	137 s	136 s
_take_rows(row_ids=[10 ids], columns=["a_float_col"])	106 s
the same call again on the same object	0.00 s
ds.get_fragments()[0].take(range(10), columns=["a_float_col"])	0.23 s

Dataset B — 1.69B rows, 19,034 fragments, contiguous row-id sequences.

call	wall	cpu
lance.dataset(uri)	0.6 s
_take_rows(row_ids=[1 id])	0.4 s	0.3 s

Dataset B holds more fragments than dataset A and resolves in 0.4 s, so the fragment count is not the driver. On dataset A the cpu time equals the wall time, so the call does no IO.

A py-spy native profile of one cold call (152 s under the profiler, stripped wheel, so no symbol names): 75.6% inside the native _take_rows call, 18.0% in realloc, 2.3% in free and munmap.

Repro shape

This is not reduced to a script yet. The shape is:

1. Write a dataset with stable row ids and many fragments.
2. Delete a fraction of the rows in most fragments.
3. Compact, so the deletions become holes in the row-id sequences.
4. Open the dataset in a fresh process and call _take_rows with one row id.

Related

PR #8534 keeps the scan position when a segment is read in order. Its benchmark puts a single select at about 20 µs. That rate does not account for the two minutes measured above, so the cause here may be different. Both touch row-id resolution over segments with holes, so linking the two.

[pengw0048]

Mechanism

RowIdIndex::new → decompose_sequence has a cheap path for U64Segment::Range only. Every other encoding falls into the branch its own comment describes as must iterate to build address mapping: it materializes one (row_id, address) pair per row, unzips them, and re-encodes two segments. A fragment that carries a deletion file goes through decompose_segment_with_deletions, which also visits every row. get_row_id_index builds the index for the whole dataset, so a single row id pays for the whole table.

Version history of the dataset above lines up with that:

version	fragments	fragments with a deletion file	live rows	first _take_rows, 1 id
v150	9,978	0	10.39B	0.3 s
v176	14,593	0	14.90B	0.2 s
v220	14,593	4,699	13.80B	183.8 s
v282	17,601	0	15.43B	157.1 s

v176 is an UpdateConfig; v177 onward is a long run of Delete. So the fast versions hold Range sequences, v220 is slow through the deletion-vector branch, and v282 is slow through the holed-sequence branch after a compaction materialized those deletes. Row count is not the driver: v150 holds 10.39B rows and resolves in 0.3 s.

The manifest carries the sequences inline, so the same transition takes the manifest from about 13 MB to 2.7 GB and the dataset open from 0.6 s to 11 s.

#8624 keeps one entry per fragment with per-segment bounds and resolves on lookup: 154 s → 2.07 s on this dataset, peak RSS 3.0 GB → 2.1 GB.