lance-format / lance-format/lance

perf: change-data-feed queries scan every fragment instead of pruning on version metadata

Open
#8,853 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance
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:

  1. Compute the surviving fragment set in delta.rs and restrict the scan to it, mirroring get_deleted_row_ids.
  2. Teach the scanner to derive zone-map-style statistics for _row_created_at_version and _row_last_updated_at_version from 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

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 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.