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 |
IndexIVFResidualQuantizer (additive-quantizer family) |
| DiskANN |
not proposed -- see out of scope |
-- |
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 raising nprobe does 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, and callers fall back to top-K plus post-filtering.
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 (IndexHNSW implements range_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 is IndexRefine,
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.md is 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.
Motivation
The unified reader exposes only top-K search. A predicate such as
vector_distance(col, q) < 0.5therefore has to be answered by asking for alarge 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_searchonIndexitself and implements it across the IVF families, theflat-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:
IndexIVFFlatIndexIVFScalarQuantizerIndexIVFPQIndexIVFResidualQuantizer(additive-quantizer family)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:
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.
compute exact distances, but the compressed families compute quantized
estimates, so a row whose true distance lies inside the band can be absent,
and raising
nprobedoes not close that gap. This is a property of theestimators 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, and callers fall back to top-K plus post-filtering.
VectorIndexReaderalready narrows capabilities per family elsewhere -- forinstance
ivfrq_search_stats()anddiskann_search_stats()returnOptionand yield
Noneon the other families -- so the pattern is not new, though theright 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:
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
Collectortrait ratherthan 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:
own radius termination rule and recall characterization. FAISS does show that
a graph index can support it (
IndexHNSWimplementsrange_search), but thedisk-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.
IDSelector-style filter abstraction -- this repository's filteringconvention is a serialized Roaring bitmap; introducing a selector trait would
change the top-K public API.
range_search_max_resultsstyle) -- 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.
FAISS offers no such guarantee either. Its accuracy answer is
IndexRefine,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
changes.
STORAGE_FORMAT.mdis untouched.when a caller asks for a range query. Top-K keeps its behaviour, though its
scan does now go through the shared collector seam.