lance-format / lance-format/lance

perf: scope scalar prefilters to selected vector index segments

Open
#9,282 0 comments 1 reaction 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

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:

  1. A named scalar index can query physical segments that are disjoint from the selected vector segments.
  2. With explicit fragments, an exact scalar-index mask can be materialized as _rowid values through FilteredRead and 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 - S uses flat KNN.
  • Without explicit fragments, selected vector segments imply scope S.
  • fast_search: preserve indexed-data-only behavior; the scalar prefilter scope is S ∩ 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

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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.