lance-format / lance-format/lance
perf: scope scalar prefilters to selected vector index segments
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
Problem
When vector search is restricted to selected index segments, the scanner already knows their fragment coverage. Scalar prefilters do not fully use this scope:
- A named scalar index can query physical segments that are disjoint from the selected vector segments.
- With explicit fragments, an exact scalar-index mask can be materialized as
_rowidvalues throughFilteredReadand then rebuilt into a mask for ANN.
Both costs grow with scalar-index fanout and the number of matching rows.
Expected scope semantics
Let S be the selected vector segments' fragment coverage, F the explicit fragment selection (if any), and C the common coverage of scalar indices used by the filter.
- Normal search: ANN/prefilter uses
S ∩ F;F - Suses flat KNN. - Without explicit fragments, selected vector segments imply scope
S. fast_search: preserve indexed-data-only behavior; the scalar prefilter scope isS ∩ F ∩ C, with no unindexed-fragment fallback.
Missing scalar-index coverage is not an empty result during normal search; those fragments still require the existing data-scan fallback.
Proposed optimization
- Before opening a named scalar index, retain only segments whose fragment coverage intersects the ANN prefilter scope. Partially overlapping segments must be retained.
- For exact prefilters with usable coverage and no overlay-stale rows, intersect the scalar result with the fragment/deletion mask and pass it directly to ANN, avoiding
mask -> FilteredRead(_rowid) -> row IDs -> mask.
The direct path must preserve stable row IDs, deletions, NOT/NULL semantics, coverage metadata, fast_search, and existing fallback behavior.
Prototype results
The prototype uses IVF_FLAT, one selected vector segment per task, and BTree scalar filters. Build time is excluded; OS page cache is not cleared. All 11,520 timed samples returned the same IDs as the baseline.
| Rows | Fragments / scalar segments | Samples | p50 improved | p50 speedup |
|---|---|---|---|---|
| 1,048,576 | 32 / 32 | 7,200 | 24 / 24 scenarios | 1.37x–5.02x |
| 4,194,304 | 64 / 64 | 4,320 | 24 / 24 scenarios | 1.57x–12.22x |
Representative disabled-index-cache, explicit-fragment, single-task results:
| Rows | Filter match rate | Baseline p50 / p95 | Optimized p50 / p95 | Speedup | IOPS |
|---|---|---|---|---|---|
| 1,048,576 | 50% | 29.27 / 57.83 ms | 7.95 / 22.53 ms | 3.68x | 502 -> 37 |
| 4,194,304 | 50% | 82.75 / 87.50 ms | 10.55 / 17.19 ms | 7.85x | 1,498 -> 49 |
| 4,194,304 | 100% | 129.10 / 151.67 ms | 10.65 / 13.28 ms | 12.12x | 2,397 -> 66 |
For the 4M-row, 50%-match plan, scalar-index work changed from 64 segments / 576 parts / 262.1K comparisons to 1 segment / 9 parts / 4.10K comparisons. The optimized plan also removed an intermediate read of 32.79K row IDs. Across a complete benchmark round, retired instructions fell from approximately 646–648B to 98B.
Correctness
The indexed result was compared with a flat-search oracle across segment-derived and explicit fragment scopes, fast_search coverage gaps, AND/OR/NOT, NULLs, stable row IDs, deletions, partial coverage, residual filters, and empty scopes. The focused matrix has 26 passing cases, with adjacent vector-search and scalar-overlay regressions also passing.
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
No files or tests are named. Start by tracing the named scalar-index opening, ANN prefilter, FilteredRead, and fragment/deletion-mask paths. Done means the scope semantics and fallback behavior are preserved, with the listed correctness matrix and adjacent regressions passing.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases, performance, search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100