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.
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 theRowIdSequenceand deletion vector for every fragment, converting each to aRowAddrTreeMap, 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 onerestrict_toset the fold happens once. That amortization is weaker than it looks:restrict_tosets get distinct cache entries, so a workload with varying fragment restrictions rebuilds repeatedly at the same version.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.