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 raw_distances and DistanceBand::from_raw 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::{CutOperator, DistanceBand, DistanceEndpoint, VectorRangeSearchParams};

let band = DistanceBand::from_endpoints(
    Some(DistanceEndpoint { value: 0.5, op: CutOperator::Ge }),
    Some(DistanceEndpoint { value: 1.5, op: CutOperator::Lt }),
    MetricType::L2,
)?;
let result = reader.range_search(&query, VectorRangeSearchParams::new(band, 16))?;

let rows = result.query(0);
for (id, raw_distance) in rows.labels.iter().zip(rows.raw_distances) {
    let public_distance = MetricType::L2.public_distance(*raw_distance);
    println!("{id} raw={raw_distance} public={public_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::from_endpoints(
    Some(DistanceEndpoint { value: 2.0, op: CutOperator::Ge }),
    None,
    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 raw_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.

Language bindings and ownership

Every binding delegates to the same core entry points and endpoint conversion. All return raw internal distances and variable-length CSR results: lims has query_count + 1 offsets, and query i occupies [lims[i], lims[i + 1]) in the label and distance arrays. Results have no padding, sorting, top-K cap, or extra reranking. A batch must contain at least one query. One optional Roaring allow-list applies to every query; absent filters, valid serialized empty filters, and malformed zero-byte filters are distinct.

Results remain valid after the reader closes. In C, destroy each successful result exactly once, never free its individual arrays, and never access a view after destruction. Input queries and filter bytes are borrowed only for the call. Search sets a valid output pointer to NULL before doing work; an error returns -1, sets paimon_vindex_last_error(), and transfers no result. destroy(NULL) is safe. Callers must supply valid, aligned buffers and live handles; C callers must synchronize operations on a reader. C++, Java and Python retain their existing callback-aware handle locks.

Capability is available as paimon_vindex_reader_supports_range_search(reader, &supported), C++/Python reader.supports_range_search(), or Java reader.supportsRangeSearch(). DiskANN returns false. Invalid parameters, malformed filters, unsupported searches, I/O errors and non-finite evaluated distances fail rather than pretending there are no matches. Length multiplication, slice byte limits and language-specific array limits are checked instead of truncating offsets or counters.

All results expose per-query lists_probed, rows_scanned, rows_committed and early_abandoned, plus call-level list_reads (camelCase accessors in Java). These are core's logical counters, not binding-side estimates. In particular, list_reads is not the sum of a batch's per-query probe counts, and an IVF-SQ cache hit does not count as a payload read.

PaimonVindexDistanceEndpoint upper = {2.0, PAIMON_VINDEX_CUT_LE};
PaimonVindexRawDistanceBand band;
if (paimon_vindex_distance_band_from_endpoints(
        PAIMON_VINDEX_METRIC_L2, NULL, &upper, &band) != 0) {
    return -1;
}
PaimonVindexRangeSearchParams params = {band, 8};
PaimonVindexRangeSearchResult *result = NULL;
int status = paimon_vindex_reader_range_search(
        reader, query, dimension, params, &result);
if (status == 0) {
    PaimonVindexRangeSearchResultView view;
    status = paimon_vindex_range_search_result_view(result, &view);
    if (status == 0) {
        consume_rows(view.labels, view.raw_distances, view.hit_count);
    }
}
paimon_vindex_range_search_result_destroy(result);

using namespace paimon::vindex;
auto band = DistanceBand::from_endpoints(
        PAIMON_VINDEX_METRIC_L2, std::nullopt,
        DistanceEndpoint{2.0, PAIMON_VINDEX_CUT_LE});
auto result = reader.range_search_batch(queries, query_count, RangeSearchParams{band, 8});
auto first_begin = result.lims[0];
auto first_end = result.lims[1];
for (size_t hit_index = first_begin; hit_index < first_end; ++hit_index) {
    consume(result.labels[hit_index], result.raw_distances[hit_index]);
}

VectorDistanceBand band = VectorDistanceBand.fromEndpoints(
        "l2", null, null, 2.0, VectorDistanceBand.CutOperator.LE);
VectorRangeSearchParams params = new VectorRangeSearchParams(band, 8);
VectorRangeSearchResult result = reader.rangeSearchBatch(
        queries, queryCount, params, roaringFilter);
for (int queryIndex = 0; queryIndex < result.queryCount(); queryIndex++) {
    for (int hitIndex = result.queryStart(queryIndex);
            hitIndex < result.queryEnd(queryIndex); hitIndex++) {
        long label = result.labelAt(hitIndex);
        float rawDistance = result.rawDistanceAt(hitIndex);
        consume(label, rawDistance);
    }
    long rowsScanned = result.rowsScanned(queryIndex);
}
long listReads = result.listReads();

Range results are uncapped and still require storage proportional to the number of hits and queries. In Java, prefer indexed access for large results: the array-returning and per-query slice methods intentionally allocate copies. C views borrow result-owned storage, C++ vectors are directly accessible, and Python query slices share the result's owned NumPy arrays. Zero-copy consumption avoids another payload allocation; it is not streaming search or a bound on native search memory.

from paimon_vindex import DistanceBand, DistanceEndpoint, DistanceEndpointOp, RangeSearchParams

band = DistanceBand.from_endpoints(
    "l2", upper=DistanceEndpoint(2.0, DistanceEndpointOp.LE))
result = reader.range_search_batch(
    queries, RangeSearchParams(band, nprobe=8), roaring_filter=roaring_filter)
query_result = result.query(0)
labels, raw_distances = query_result.labels, query_result.raw_distances
stats = result.stats[0]

Use from_endpoints (fromEndpoints in Java) for public predicate endpoints. Explicit raw construction uses DistanceBand::from_raw in Rust/C++, DistanceBand.from_raw in Python, VectorDistanceBand.fromRaw in Java, or the C PaimonVindexRawDistanceBand type. Raw constructors take float32 cuts in internal distance space; they do not convert units or endpoint operators. Do not square L2 endpoints, round double literals to float32, or negate/reverse inner-product endpoints yourself. Missing endpoints are structural unboundedness, not infinities or sentinel numbers.

Range API migration: replace distances with raw_distances; Java uses rawDistances(), rawDistanceAt(), and rawDistancesForQuery(). Replace ambiguous raw-band construction with an explicit raw factory or, preferably, the public-endpoint factory. Python query views expose labels and raw_distances while retaining tuple unpacking. These are source API changes, including Rust; Java method renames also require recompiling callers. C field/type renames preserve the native layout and exported function symbols. Existing top-K names, result values, index formats, and ownership rules are unchanged.

Python can still import and run existing top-K calls with a native library predating the range ABI. If any required range export is absent, capability returns false and new range calls or endpoint conversion request a native-library upgrade with a clear error. Range operations never silently fall back to top-K. NumPy query inputs are normalized for both contiguity and alignment.

Cross-language verification

The core-only ffi/examples/range_search_fixture.rs generator writes the same index bytes and 168 oracle cases for C, C++, Java and Python: four IVF families, three metrics, bounded/unbounded/empty bands, single/batch queries, and absent/non-empty/empty Roaring filters. Each consumer opens a fresh reader and checks per-query label/distance-bit multisets, CSR offsets, and all statistics against core. Comparison does not impose ordering that core does not promise. Tests also cover invalid endpoints, shape/length errors, unsupported indexes, ownership and existing top-K behavior. CI generates and consumes the oracle in every binding job.

cargo fmt --all -- --check
cargo test --workspace
cargo build -p paimon-vindex-ffi -p paimon-vindex-jni
export PVI_RANGE_FIXTURES="$PWD/target/range-fixtures"
cargo run -p paimon-vindex-ffi --example range_search_fixture -- "$PVI_RANGE_FIXTURES"
export PAIMON_VINDEX_LIB_PATH="$PWD/target/debug"
cmake -S c -B c/build -DPAIMON_VINDEX_FFI_LIB="$PWD/target/debug/libpaimon_vindex_ffi.so"
cmake --build c/build && c/build/test_vindex
cmake -S cpp -B cpp/build -DPAIMON_VINDEX_FFI_LIB="$PWD/target/debug/libpaimon_vindex_ffi.so"
cmake --build cpp/build && cpp/build/test_vindex_cpp
mvn -f java/pom.xml test -Dpaimon.vindex.native.path="$PWD/target/debug/libpaimon_vindex_jni.so"
java -cp java/target/test-classes:java/target/classes org.apache.paimon.index.vector.VectorIndexNativeValidationTest "$PWD/target/debug/libpaimon_vindex_jni.so"
PYTHONPATH=python python3 -m pytest python/tests

Use .dylib library paths on macOS. Standalone binding tests still run without PVI_RANGE_FIXTURES; setting it enables the shared core oracle as well. No algorithm, index storage format or performance-tuning change is part of these additive bindings.

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 in Rust and every language binding. Query capability through core or the binding's reader capability method. DiskANN remains unsupported; storage-format and top-K behavior are unchanged.

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.