lance-format / lance-format/lance

perf: prefilter builds a whole-dataset allow list on stable-row-id datasets

Open
#8,849 0 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

On a dataset with stable row ids, building the prefilter deletion mask requires an allow-list in the row-id domain. do_create_deletion_mask_row_id (rust/lance/src/index/prefilter.rs:149) produces it by loading the RowIdSequence and deletion vector for every fragment, converting each to a RowAddrTreeMap, and OR-ing them all into one whole-dataset allow list.

The cost is proportional to the size of the dataset, not to the selectivity of the query. A prefiltered vector search that touches one fragment still pays for all of them. The equivalent path without stable row ids builds a block-list of deleted addresses only, which is proportional to the number of deletions.

The result is cached under RowAddrMaskKey { version, restrict_hash }, so within one dataset version and one restrict_to set the fold happens once. That amortization is weaker than it looks:

  • Every commit bumps the version and invalidates the entry, so the first prefiltered query after any write rebuilds the whole thing.
  • Distinct restrict_to sets get distinct cache entries, so a workload with varying fragment restrictions rebuilds repeatedly at the same version.
  • The cached value is a RowAddrTreeMap covering every live row in the dataset, so resident memory also scales with dataset size.

For a large table this is the dominant cost of a prefiltered search. Moving indices to the address domain removes the need for this allow list on the index search path, but the path is also reached from merge_insert (see #6877), so it needs a fix of its own.

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/index/prefilter.rs at do_create_deletion_mask_row_id and trace the RowIdSequence, deletion-vector, RowAddrTreeMap, and RowAddrMaskKey paths. Compare the stable-row-id behavior with the address-domain block-list path, then inspect the merge_insert route noted in #6877. Done means prefiltered searches no longer require a whole-dataset allow list while preserving deletion-mask behavior and relevant caching.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases, performance, search
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.