[Feature] Distance range search for IVF indexes
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
Research direction
Start by tracing the existing VectorIndexReader top-K entry points, per-family scan kernels, and collector seam; inspect core/src/rq.rs and the existing top-K tests. Resolve the band API and estimator incompleteness decisions before implementing step 1, with IVF-Flat range support, capability errors, documentation, and no changes to STORAGE_FORMAT.md as the completion criteria.
Written by the indexing model from the issue text.
Description
Motivation
The unified reader exposes only top-K search. A predicate such as
vector_distance(col, q) < 0.5 therefore has to be answered by asking for a
large K and filtering afterwards, which either over-reads (K too large) or
silently drops matching rows (K too small). Neither is acceptable when the
predicate is pushed down from SQL, because the result set no longer equals the
predicate.
This is not a new idea for the families this crate mirrors. FAISS declares
range_search on Index itself and implements it across the IVF families, the
flat-codes indexes and HNSW, so the general semantics -- what a hit set
contains, how the boundary is treated, what the result container looks like --
have an established reference. The per-family internals differ enough from this
crate's that they are a reference for semantics, not for implementation. Where
this proposal deviates from FAISS it is called out explicitly (the two-sided
band in question 1 below, and the out-of-scope list at the end).
Scope of the proposal
Add distance-range search to the unified reader, alongside the existing top-K
entry points and following their existing shape (single and batch queries, with
and without a serialized Roaring filter).
Intended coverage, and where each family's reference behaviour comes from:
| Family | Range membership decided on | Closest FAISS analogue for semantics |
|---|---|---|
| IVF-Flat | exact distances | IndexIVFFlat |
| IVF-SQ | quantized estimate | IndexIVFScalarQuantizer |
| IVF-PQ | quantized estimate | IndexIVFPQ |
| IVF-RQ | quantized estimate | the IndexIVF range contract generally -- see the naming note below |
| DiskANN | not proposed -- see out of scope | -- |
A naming note, since an earlier version of that table named
IndexIVFResidualQuantizer: this crate's IVF-RQ is RaBitQ (core/src/rq.rs),
not Faiss's additive/residual quantizer family, despite the shared "RQ"
abbreviation. What carries over from Faiss is the IndexIVF range contract --
membership decided on whatever value the family's scanner produces -- not the
quantizer.
Exactness and completeness are separate properties. IVF-Flat computes exact
distances for the rows it visits, but a matching row in an unprobed list is
still missed whenever nprobe < nlist. Removing K removes truncation; it does
not by itself make any IVF family exhaustive. The compressed families add a
second and different gap on top of that one, which question 2 below is about.
Metrics: L2 first, then cosine and inner product (a later step). Both single and
batch queries, with and without a Roaring filter, for every supported family --
no entry point is left as a stub that silently behaves differently from its
top-K counterpart.
Two decisions shape the API rather than the implementation, so I would rather
settle them here than in code review. I have a leaning on both and give the
reasoning, but neither is something I am attached to:
- Should the index layer take a distance band, or SQL operators? A band
with two optional bounds keeps engine-specific operator vocabulary out of the
index layer, at the cost of asking callers to derive the boundary value.
Knowhere is the precedent for two bounds (radius+range_filter); FAISS,
Doris and OpenSearch each expose a single threshold instead. - How should the estimator families report incompleteness? IVF-Flat can
compute exact distances, but the compressed families compute quantized
estimates, so a row whose true distance lies inside the band can be absent,
and raisingnprobedoes not close that gap. This is a property of the
estimators that top-K already shares, but range search makes it
consequential: a row disappears rather than being mis-ranked. My leaning is to
state it per family in the docs and let callers pick the family accordingly,
rather than attempt a guarantee the estimators cannot provide. If reviewers
would rather range search stay restricted to the exact family until such a
guarantee exists, that changes the roadmap below and is worth knowing now.
Roadmap
Range support can be a per-family capability gate, so it does not have to
land all at once: a family that does not implement it yet fails loud with a
distinguishable error.
Top-K plus post-filtering is not an equivalent fallback, and is not offered
as one. It reintroduces the problem in the motivation above: with 100 vectors
satisfying the band and K = 10, at most 10 can come back, and that holds even
for an exact search. A caller that needs the result set to equal the predicate
needs an execution path that preserves it -- an exhaustive scan. A caller for
whom an incomplete answer is acceptable may opt into a capped top-K fallback
explicitly, knowing it is capped.
VectorIndexReader already narrows capabilities per family elsewhere -- for
instance ivfrq_search_stats() and diskann_search_stats() return Option
and yield None on the other families -- so the pattern is not new, though the
right signal for a search entry point (a typed error rather than an Option)
is worth confirming.
Each step below is intended as one reviewable PR. Steps 2-6 each depend only on
step 1, so they can land in any order:
| # | Scope | Depends on |
|---|---|---|
| 1 | Range primitives (band, result container, boundary derivation), the IVF-Flat scan seam, IVF-Flat range, docs | -- |
| 2 | IVF-RQ range (estimate mode) | 1 |
| 3 | C / JNI / Python bindings and headers | 1 |
| 4 | Cosine and inner-product support | 1 |
| 5 | Result cap and early-stop controls | 1 |
| 6 | IVF-SQ and IVF-PQ range | 1 |
Step 1 carries the scan seam it needs rather than landing it separately. Each
family has its own per-list scan kernel, so the seam is generalized per family:
steps 2 and 6 generalize their own against the same Collector trait rather
than inheriting a finished one. The edit to the shared top-K scan path is
verified by the existing top-K tests alone -- it adds no test there and
modifies none.
The ordering of steps 2-6 is a dependency statement, not a priority claim --
happy to take them in whatever order reviewers prefer, one at a time.
Explicitly out of scope, with reasons:
- DiskANN range -- graph traversal is inherently K-oriented and needs its
own radius termination rule and recall characterization. FAISS does show that
a graph index can support it (IndexHNSWimplementsrange_search), but the
disk-resident, paged, PQ-in-memory shape is where an unbounded result set
hurts most, so it is deliberately left out here rather than assumed to
transfer. Fails loud, documented. - An
IDSelector-style filter abstraction -- this repository's filtering
convention is a serialized Roaring bitmap; introducing a selector trait would
change the top-K public API. - Automatic radius shrinking (FAISS contrib's
range_search_max_results
style) -- it returns a band the caller did not ask for, so under SQL pushdown
the result set stops matching the predicate. That is a correctness problem. - Error-bound based determinism guarantees for the estimator families --
FAISS offers no such guarantee either. Its accuracy answer isIndexRefine,
which composes a second, more precise index over a base one; that composition
works for range queries too, but it is a way to build a more accurate index,
not a property of the range API. The defect it would address belongs to the
estimators, which top-K already shares, so improving estimator precision is a
separate feature with a different audience.
Compatibility
- Additive only: new entry points and new types; no existing signature
changes. - No on-disk format change;
STORAGE_FORMAT.mdis untouched. - No caller-visible behavior change: the range code path is reached only
when a caller asks for a range query. Top-K keeps its behaviour, though its
scan does now go through the shared collector seam.
- Dominant language
- Rust
- Stars
- 21
- Forks
- 22
- Avg merge
- 2d 1h
- Merged PRs (30d)
- 12
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.
More from apache/paimon-vector-index
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
apache/paimon-vector-index#100 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 38/100
-
Difficulty 5/5 Over a week Newbie friendliness 45/100
All issues in apache/paimon-vector-index
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Eynzof/Hermes-CN-Desktop#610 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
gitbutlerapp/gitbutler#15998 · 1 comment ·
-
bug triage:deciding
Difficulty 1/5 Under an hour Newbie friendliness 88/100
open-telemetry/otel-arrow#4132 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100