JunRuiLee opened a new pull request, #99:
URL: https://github.com/apache/paimon-vector-index/pull/99
Adds range search to the unified reader alongside top-K: given a distance
band, return every row of the probed lists whose distance falls inside it.
There is no K and no truncation, matching faiss's range_search. Results are
neither sorted nor padded, because ordering is the caller's business.
Scope is IVF-Flat under L2. Every other family reports a distinguishable
error rather than silently behaving differently from its top-K counterpart,
so a caller can fall back to top-K plus post-filtering. All four entry point
shapes are covered -- single and batch, with and without a serialized
Roaring filter -- so none is left as a stub.
The scan seam
-------------
Top-K and range want the same per-list scan and differ only in what they do
with a row, so scan_flat_list and scan_flat_rows become generic over a
Collector trait: it reports an admission threshold, receives kept rows, and
is told when a row is abandoned early. ReaderTopKHeap and RangeCollector are
its two implementations. This mirrors faiss's
InvertedListScanner::scan_codes(..., ResultHandler&).
The seam is IVF-Flat's only. The other families have their own scan kernels
and are untouched here; each will generalize its own when its range support
lands, against this same trait.
Nothing about top-K changes:
- ReaderTopKHeap::cutoff() is worst_distance().unwrap_or(INFINITY), and the
kernel enters the early-abandon path only for a finite threshold. Before,
it was entered only inside `if let Some(threshold) =
heap.worst_distance()`,
so an unfilled heap skipped it either way. A non-finite threshold reaches
the same outcome by both routes: fvec_l2sqr_scaled_exceeds compares against
INFINITY or NaN and returns false, so such a row was computed rather than
abandoned before as well.
- note_abandoned() has an empty default body and ReaderTopKHeap does not
implement it. It is on the trait because an abandoned row never reaches
push(), so a collector counting scanned rows cannot recover the count
unless the kernel reports it.
- Collector::push is fallible, and the streamed-chunk callback used by the
oversized-list path becomes fallible with it, so a collector error can
propagate out instead of having to panic.
The existing top-K tests are the whole of the verification for that part:
this change adds no test to the top-K path and none was modified.
Range semantics
---------------
The API takes a two-sided band (DistanceBand with two optional Bounds)
rather than SQL operators, keeping engine-specific operator vocabulary out
of the index layer; DistanceEndpoint plus CutOperator derive the boundary
for callers that think in operators. Knowhere is the precedent for two
bounds.
Membership is decided by the band on the exact distance. The early-abandon
kernel only prunes, and its cutoff is widened by d * f32::EPSILON: the
pruning kernel reduces 128-element blocks across four accumulators while the
committed kernel reduces once, so "partial sum > upper implies full distance
> upper" holds in exact arithmetic only. For a sum of d non-negative terms
any two summation orders differ by at most (d-1) units in the last place,
which d * EPSILON exceeds. Widening can only prune less, never admit more.
Probe selection reuses kmeans::find_topk_batch, which recomputes every
selected centroid's distance with the direct kernel wherever its error bound
leaves the ranking ambiguous. Range search needs that: a query must select
the same lists alone or batched, or batch size becomes observable query
semantics. A focused kmeans test pins the property, and the IVF-Flat suite
guards it end to end.
Caller-bug checks are hoisted ahead of family dispatch, so an unsupported
family cannot mask a bad nprobe, a malformed filter or a metric mismatch as
a capability gap.
Part of #97, covering steps 1 and 2 together as that issue anticipated. The
compressed families, cosine and inner product, result caps and the bindings
each follow separately.
--
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]
