lance-format / lance-format/lance
perf: change-data-feed queries scan every fragment instead of pruning on version metadata
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
DatasetDelta::get_inserted_rows, get_updated_rows, and get_upserted_rows (rust/lance/src/dataset/delta.rs:451, :509, :572) each build a filter string over the version columns and hand it to a plain full-dataset scan:
let mut scanner = self.base_dataset.scan();
scanner.project(&[WILDCARD, ROW_ID, ROW_CREATED_AT_VERSION, ROW_LAST_UPDATED_AT_VERSION])?;
let filter = self.build_inserted_rows_filter().await?; // "_row_created_at_version > A AND <= B"
scanner.filter(&filter)?;
scanner.try_into_stream().await
Nothing prunes fragments before the scan. A delta over two adjacent versions on a table with 20,000 fragments reads all 20,000, even when the range touched three of them. The cost scales with the size of the table rather than with the size of the change, which is backwards for a change feed — the whole point is that the answer is small.
The information needed to prune is already on hand and requires no data-file reads. RowDatasetVersionSequence is run-length encoded as Vec<RowDatasetVersionRun { span, version }> in the fragment metadata, so a per-fragment min/max over the run versions is a manifest-only computation. Any fragment whose maximum created_at version is <= begin_version cannot contain an inserted row in (begin, end], and the same argument applies to last_updated_at for the updated and upserted paths.
get_deleted_row_ids in the same file already does the right thing — it computes a fragment_delta between the two endpoints and only visits the candidates — which is both a precedent for the shape of the fix and evidence that the pruning information exists at this layer.
Two possible fixes, in increasing order of generality:
- Compute the surviving fragment set in
delta.rsand restrict the scan to it, mirroringget_deleted_row_ids. - Teach the scanner to derive zone-map-style statistics for
_row_created_at_versionand_row_last_updated_at_versionfrom the RLE runs, so an ordinary filter on those columns prunes without special-casing the delta API.
Related: the version sequences are one of the three families that grow the manifest without bound on large tables, so whichever fix lands should stay correct when those sequences move out of fragment metadata.
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 in rust/lance/src/dataset/delta.rs at get_inserted_rows, get_updated_rows, get_upserted_rows, and get_deleted_row_ids. Compare the existing fragment_delta approach with the version-run metadata, then establish pruning for the affected version ranges while preserving correct change-feed results and accommodating future movement of the sequences out of fragment metadata.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100