Skip to content

[Feature] Distance range search for IVF indexes #97

Description

@JunRuiLee

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:

  1. 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.
  2. 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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions