JunRuiLee opened a new issue, #97:
URL: https://github.com/apache/paimon-vector-index/issues/97
## 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. Step 1 is a pure refactor
with no behaviour change; step 2 is the first one that adds a feature; steps
3-7 each depend only on step 2, so they can land in any order:
| # | Scope | Depends on |
|---|---|---|
| 1 | Generalize the scan seam so a collector other than the top-K heap can
plug in -- no behaviour change | -- |
| 2 | Range primitives (band, result container, boundary derivation) +
IVF-Flat range + docs | 1 |
| 3 | IVF-RQ range (estimate mode) | 2 |
| 4 | C / JNI / Python bindings and headers | 2 |
| 5 | Cosine and inner-product support | 2 |
| 6 | Result cap and early-stop controls | 2 |
| 7 | IVF-SQ and IVF-PQ range | 2 |
Step 1 is separated deliberately: it touches the existing top-K scan path and
nothing else, so the existing top-K tests passing is the whole of its
verification, and it can be reviewed without reading anything about range
search. Its only consumer is step 2 -- if reviewers would rather see the seam
change together with the collector that motivates it, steps 1 and 2 can be
sent
as one PR instead.
The ordering of steps 3-7 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 default behavior change**: nothing reaches the new code path unless a
caller asks for a range query.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
