Range search

Semantic contract

A band is left-closed and right-open. A row at exactly lower is returned; a row at exactly upper is not. This is what makes adjacent bands tile a range without overlapping or leaving gaps, so [a,b) and [b,c) together return exactly what [a,c) returns.

Either side may be unbounded, and unboundedness is a distinct state rather than a large or small number. A band with both sides unbounded is the whole space and is legal. An empty band where lower == upper is also legal and returns zero rows.

Units and ordering

Cuts are expressed in the index's own distance space, not in whatever unit the caller happens to think in.

For IVF-RQ under L2, this is the raw estimate in squared-L2 units. Negative estimates have no real-valued Euclidean radius. The L2 endpoint examples describe non-negative squared distances; endpoint conversion does not turn estimated membership into an exact predicate over the original vectors.

MetricType::public_distance defines this conversion. Returned distances and DistanceBand::new always use internal units; DistanceBand::from_endpoints takes public f64 endpoints. Cosine queries are normalized before both probe selection and scanning; zero queries remain zero. FLAT and SQ return cosine distance 1 when either vector has zero norm. PQ and RQ retain their unit-vector estimators even for zero queries, rather than claiming exact cosine membership.

Row order is not part of the contract. Within one list rows come back in physical order, but no order across lists is specified or promised, and two runs of the same query may differ. Do not depend on any observed order: sorting is the caller's job, and in SQL it is ORDER BY's. Results are neither padded nor sorted, which is how range search differs from Top-K.

"No cap" is not "complete"

Range search never truncates its result. That is a promise about not dropping rows it found, and it is not a promise that it found every in-band row in the file.

Only the nprobe nearest lists are probed, so a row lying inside the band but in an unprobed list is not returned. A smaller nprobe returns no more in-band rows, and potentially fewer: if every matching row already lies in the lists it still probes, the result is unchanged. At nprobe == nlist every list is probed and, because IVF-FLAT computes exact distances, the result is then the complete in-band set.

Endpoints and cuts

A predicate such as distance(v, query) < 0.5 compares against the value the engine displays, which for an L2 index is sqrt of the stored squared f32 distance, widened to double. Deriving a cut from that endpoint therefore belongs in this library rather than in the caller.

Pass the already-folded literal from the right-hand side of the predicate as-is. No squaring, no square root, and no binary search on the caller's part. Each endpoint carries its comparison operator, and the operator must match the side it is on:

A mismatch, such as a Lt operator on the lower side, is rejected rather than reinterpreted. Cosine searches the entire finite f32 axis, including negative values and signed zeros. Inner product negates endpoints and reverses their sides and comparisons: public ip >= e becomes internal distance <= -e. Endpoints are not rounded to f32 first. Out-of-domain cosine/IP cuts become empty or structurally unbounded bands, preserving inclusive membership at f32::MAX. L2 retains Unsupported when no representable square-root cut exists.

Usage

use paimon_vindex_core::distance::MetricType;
use paimon_vindex_core::range::{Bound, DistanceBand, VectorRangeSearchParams};

// Squared-L2 cuts, half-open: 0.5 is returned, 1.5 is not.
let band = DistanceBand::new(
    Bound::Finite(0.5),
    Bound::Finite(1.5),
    MetricType::L2,
)?;
let result = reader.range_search(&query, VectorRangeSearchParams::new(band, 16))?;

let rows = result.query(0);
for (id, distance) in rows.labels.iter().zip(rows.distances) {
    // `distance` is a squared L2 value; take sqrt for a Euclidean radius.
    println!("{id} {distance}");
}

use paimon_vindex_core::range::{CutOperator, DistanceEndpoint};

// WHERE distance < 0.5 -- pass the literal through unchanged.
let band = DistanceBand::from_endpoints(
    None,
    Some(DistanceEndpoint { value: 0.5, op: CutOperator::Lt }),
    MetricType::L2,
)?;

// A one-sided band: everything at or beyond 2.0, with no upper end.
let tail = DistanceBand::new(Bound::Finite(2.0), Bound::Unbounded, MetricType::L2)?;

let near_cosine = DistanceBand::from_endpoints(
    None,
    Some(DistanceEndpoint { value: 0.2, op: CutOperator::Le }),
    MetricType::Cosine,
)?;
let high_similarity = DistanceBand::from_endpoints(
    Some(DistanceEndpoint { value: 0.8, op: CutOperator::Ge }),
    None,
    MetricType::InnerProduct,
)?;

The inner-product predicate is a lower bound on public similarity, not on the returned negative-dot score. Endpoint conversion reverses the internal cut automatically.

Results use a CSR layout, so a batch of queries shares three contiguous buffers. lims holds query_count + 1 offsets, and query i owns labels[lims[i]..lims[i+1]] together with the matching slice of distances. Per-query counters are available through query(i).stats, and counters covering the whole call through call_stats().

All four families expose range_search, range_search_batch, and their _with_roaring_filter variants through both typed readers and VectorIndexReader. The filter is an allow-list and does not widen the fixed nprobe. Roaring filters admit only non-negative row IDs; a direct RowIdFilter may admit signed IDs. A query has the same label/distance multiset alone or in a batch; order remains unspecified. Unique non-empty lists are read at most once per call and shared across queries; IVF-SQ cache hits require no payload read.

For IVF-RQ, lists_probed includes empty selected lists; rows_scanned counts filter-eligible rows evaluated; rows_committed counts returned rows; and early_abandoned is zero. Call-level list_reads counts unique non-empty lists, not query/list pairs or storage read rounds. These result-owned counters leave the last top-K statistics unchanged.

Choosing an index type

Range search supports IVF-FLAT, IVF-SQ, IVF-PQ and IVF-RQ under L2, cosine and inner product, with fixed positive probe widths and Rust entry points. Query capability through IndexType::supports_range_search(metric) or reader.supports_range_search(). DiskANN remains unsupported; no storage-format, C/JNI binding or top-K behavior changes are included.

A reproducible boundary example is in core/tests/range_search.rs: with a one-dimensional centroid of zero and SQ bounds [0, 255], inputs 0.49 and 0.51 quantize to 0 and 1. For query zero, band [0, 0.1) includes the first estimate despite its true squared distance being outside; band [0.2, 0.3) misses both although both true squared distances lie inside. This demonstrates the membership gap, not a general recall estimate.

Performance and memory: Under L2, IVF-SQ keeps the existing SIMD block layout and uses a finite upper cut to abandon a block once all partial squared distances reach that exclusive cut. A lower cut alone cannot prune a partial sum; cosine and IP do not prune partial sums. Batch queries read each unique list once, reuse cached partitions, and keep query-owned collectors instead of materializing a list-by-query result matrix. Large single queries can scan lists in parallel and merge once per list, not per row. Oversized lists stream in bounded chunks, with reusable scan scratch. Output memory still grows with all admitted rows; there is no result cap.

IVF-PQ lazily caches query lookup tables within an 8 MiB cap, falling back to reusable worker scratch beyond that budget. Cached residual IP base tables are reused across lists, applying each list's coarse offset to the first subtable without changing floating-point addition order. Residual L2/cosine tables are reused across chunks of one list and refreshed when the list changes. Large batches scan queries in parallel. Membership is independent of list size, batch size, worker count and optimize_for_search.

Filtered SQ batches evaluate the allow-list once per list row and share compact, query-local block masks (one bit per row) across queries, including streamed chunks. These masks never enter the partition cache. An entirely excluded list or chunk skips distance evaluation; partially selected blocks retain the same SIMD arithmetic as unfiltered search.

call_stats().list_reads() excludes empty lists and IVF-SQ cache hits and counts a streamed list once. rows_scanned() counts allow-listed rows reaching collection or cutoff rejection; blocked arithmetic can also evaluate excluded lanes. Under L2, SQ's early_abandoned() includes estimates equal to or above the upper cut. It is zero for cosine/IP and for every PQ/RQ range search.

Fail-loud combinations

Invalid input means the call itself is wrong. Unsupported means the request cannot be served. Invalid data covers corrupt consumed index data and non-finite computed distances; no partial result is returned.

For cosine/IP every family validates all centroids and direct query-centroid distances before choosing lists, including unselected lists. Non-finite cosine vectors and norms cannot silently become distance 1 via zero-norm handling. Consumed PQ entries and RQ factors must produce finite estimates; unused codebook entries and filtered-out row estimates do not poison valid results. SQ bounds retain their existing metadata validation. No error returns a partial result.

IVF-RQ validates centroids and every direct query-centroid distance before selecting lists for a non-empty band, including distances to lists that would not be selected. It requires finite f_add and f_rescale for the estimate it consumes: coarse for one-bit codes, full for multi-bit codes. Multi-bit coarse factors, including f_error, are not used by range search and are not validated on this path. Filtered-out and unprobed rows are not evaluated. Finite inputs can still overflow during rotation, query-centroid distance calculation, or estimation, which also returns InvalidData.

An empty band is not an error: it returns zero rows. It also does not mask a bad call. The dimension, metric and width are all validated before the empty band takes its shortcut, and a family that cannot do range search at all rejects every band, the empty one included. A malformed Roaring filter is likewise rejected before that shortcut.

Why not DiskANN

The omission is deliberate and long-term, not a gap waiting to be filled. Graph traversal is inherently k-oriented: it walks towards the query and stops when a candidate list stops improving, which is a criterion in terms of a neighbour count rather than a radius. A band query has no such natural stopping point, so a radius termination rule and its recall characterisation would have to be built from scratch.

The cost also lands hardest here. DiskANN pages its graph, keeps quantized codes resident, and is designed for object-store reads, so an unbounded result set is the worst case for exactly the layout that makes it attractive. DiskANN therefore reports range search as unsupported.