lance-format / lance-format/lance
perf: prefilter builds a whole-dataset allow list on stable-row-id datasets
Nobody has claimed this yet.
- 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_tosets get distinct cache entries, so a workload with varying fragment restrictions rebuilds repeatedly at the same version. - The cached value is a
RowAddrTreeMapcovering 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
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/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