| <!-- |
| Licensed to the Apache Software Foundation (ASF) under one or more |
| contributor license agreements. See the NOTICE file distributed with |
| this work for additional information regarding copyright ownership. |
| The ASF licenses this file to you under the Apache License, Version 2.0. |
| --> |
| <!doctype html> |
| <html lang="en"> |
| <head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1"><meta name="description" content="Distance range search semantics: half-open bands, squared-L2 units, cut derivation from SQL endpoints, supported index types, and the fail-loud combinations."><title>Range search · Paimon Vector Index</title><link rel="stylesheet" href="styles.css"><script src="docs.js" defer></script></head> |
| <body> |
| <a class="skip-link" href="#main">Skip to content</a> |
| <header class="site-header"><div class="header-inner"><a class="brand" href="index.html" aria-label="Paimon Vector Index documentation home"><span class="brand-mark">VI</span><span>Paimon Vector Index</span></a><nav class="site-nav" data-site-nav aria-label="Documentation"><a href="index.html">Overview</a><a href="api.html">API</a><a href="development.html">Development</a><a href="range-search.html" aria-current="page">Range search</a><a href="ivf-flat.html">IVF-FLAT</a><a href="ivf-pq.html">IVF-PQ</a><a href="ivf-rq.html">IVF-RQ</a><a href="ivf-sq.html">IVF-SQ</a><a href="diskann.html">DiskANN</a><a href="releases.html">Releases</a></nav><div class="header-actions"><button class="icon-button" type="button" data-theme-toggle aria-label="Switch color theme">◐</button><button class="nav-toggle" type="button" data-nav-toggle aria-expanded="false" aria-label="Open navigation">☰</button></div></div></header> |
| <main id="main"><div class="page-shell"> |
| <section class="hero detail-hero"><p class="eyebrow">Every row inside a distance band</p><h1>Range search</h1><p class="hero-lead">Return every eligible probed row whose family-specific distance falls inside a half-open band <code>[lower, upper)</code>, with no result limit. IVF-FLAT computes exact distances; IVF-SQ, IVF-PQ and IVF-RQ compute estimates. Range search answers "which rows are within this distance", where Top-K answers "which rows are closest".</p><div class="badge-row"><span class="badge strong">No limit, no cap</span><span class="badge">Half-open interval</span><span class="badge">IVF-FLAT / SQ / PQ / RQ</span><span class="badge">L2 / cosine / inner product · All bindings</span></div></section> |
| <div class="doc-layout"> |
| <aside class="toc" aria-label="On this page"><strong>On this page</strong><a href="#contract">Semantic contract</a><a href="#units">Units and ordering</a><a href="#completeness">"No cap" is not "complete"</a><a href="#endpoints">Endpoints and cuts</a><a href="#usage">Usage</a><a href="#bindings">Language bindings</a><a href="#binding-tests">Cross-language verification</a><a href="#selection">Choosing an index type</a><a href="#errors">Fail-loud combinations</a><a href="#diskann">Why not DiskANN</a></aside> |
| <article class="article"> |
| <section class="article-section" id="contract"> |
| <h2>Semantic contract</h2> |
| <div class="metric-strip"><div class="metric"><span class="label">Interval</span><span class="value">Half-open <code>[lower, upper)</code></span></div><div class="metric"><span class="label">Result size</span><span class="value">Unbounded</span></div><div class="metric"><span class="label">Row order</span><span class="value">Unspecified</span></div><div class="metric"><span class="label">Membership</span><span class="value">Exact (FLAT), estimated (SQ / PQ / RQ)</span></div></div> |
| <p>A band is <strong>left-closed and right-open</strong>. A row at exactly <code>lower</code> is returned; a row at exactly <code>upper</code> is not. This is what makes adjacent bands tile a range without overlapping or leaving gaps, so <code>[a,b)</code> and <code>[b,c)</code> together return exactly what <code>[a,c)</code> returns.</p> |
| <p>Either side may be unbounded, and unboundedness is a <strong>distinct state</strong> rather than a large or small number. A band with both sides unbounded is the whole space and is legal. An empty band where <code>lower == upper</code> is also legal and returns zero rows.</p> |
| <div class="callout"><strong>Why unboundedness is not a sentinel value</strong>A finite cut is not a substitute for an unbounded side. IVF-RQ squared-L2 estimates can be negative and are not clamped: a lower cut of <code>0.0</code> excludes them, while <code>Bound::Unbounded</code> includes them. Likewise, a finite upper cut excludes a value exactly at that cut. Use structural unboundedness to request every finite estimate.</div> |
| </section> |
| |
| <section class="article-section" id="units"> |
| <h2>Units and ordering</h2> |
| <p>Cuts are expressed in the <strong>index's own distance space</strong>, not in whatever unit the caller happens to think in.</p> |
| <p>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.</p> |
| <div class="table-wrap"><table><thead><tr><th>Metric</th><th>Internal value</th><th>Public predicate value</th></tr></thead><tbody><tr><td><code>l2</code></td><td>Squared Euclidean distance or estimate</td><td>f32 square root, then widened to f64</td></tr><tr><td><code>cosine</code></td><td><code>1 - cos</code> or family estimate; no clamping</td><td>Internal value widened to f64</td></tr><tr><td><code>inner_product</code></td><td><code>-inner_product</code> or family estimate</td><td>Negated internal value widened to f64</td></tr></tbody></table></div> |
| <p><code>MetricType::public_distance</code> defines this conversion. Returned <code>raw_distances</code> and <code>DistanceBand::from_raw</code> always use internal units; <code>DistanceBand::from_endpoints</code> 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.</p> |
| <p><strong>Row order is not part of the contract.</strong> 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 <code>ORDER BY</code>'s. Results are neither padded nor sorted, which is how range search differs from Top-K.</p> |
| <div class="callout"><strong>A row within a few ULP of the upper cut</strong>Under L2, IVF-FLAT can abandon a row when its partially accumulated squared distance passes the upper cut, using the same accumulation for pruning and collection. IVF-SQ similarly prunes blocked squared estimates at the exclusive upper cut. Cosine and inner product never use partial-sum pruning. PQ and RQ always evaluate complete f32 estimates, without top-K's FastScan or coarse-bound pruning. All four families use the supplied cuts without a margin.</div> |
| </section> |
| |
| <section class="article-section" id="completeness"> |
| <h2>"No cap" is not "complete"</h2> |
| <p>Range search never truncates its result. That is a promise about <em>not dropping rows it found</em>, and it is <strong>not</strong> a promise that it found every in-band row in the file.</p> |
| <p>Only the <code>nprobe</code> nearest lists are probed, so a row lying inside the band but in an unprobed list is not returned. A smaller <code>nprobe</code> returns <strong>no more</strong> in-band rows, and potentially fewer: if every matching row already lies in the lists it still probes, the result is unchanged. At <code>nprobe == nlist</code> every list is probed and, because IVF-FLAT computes exact distances, the result is then the complete in-band set.</p> |
| <div class="callout"><strong>Coverage and estimation are different gaps</strong>Raising <code>nprobe</code> improves list coverage; it does not remove the quantization error of IVF-SQ, IVF-PQ or IVF-RQ. An estimate can lie on the other side of a cut from the exact distance, producing missing or extra rows relative to an exact-distance predicate even at <code>nprobe = nlist</code>. A filter additionally excludes rows that were never eligible. None of these families truncates the rows admitted by its own distance calculation. Top-K plus post-filtering is not an equivalent fallback; exact, complete membership requires full-probe IVF-FLAT or an exhaustive raw-vector scan.</div> |
| </section> |
| |
| <section class="article-section" id="endpoints"> |
| <h2>Endpoints and cuts</h2> |
| <p>A predicate such as <code>distance(v, query) < 0.5</code> compares against the value the engine <em>displays</em>, which for an L2 index is <code>sqrt</code> of the stored squared <code>f32</code> distance, widened to double. Deriving a cut from that endpoint therefore belongs in this library rather than in the caller.</p> |
| <div class="callout"><strong>Why not just square the endpoint</strong><code>endpoint * endpoint</code> <em>can</em> land one or two ULP away from the correct cut, because it does not absorb the rounding that the displayed <code>sqrt</code> introduced. Some endpoints square exactly, so the discrepancy is data-dependent rather than universal, which is what makes it easy to miss. One ULP is enough to move a row sitting exactly on a bucket boundary into the neighbouring bucket. Cut derivation instead binary searches the <code>f32</code> bit patterns for the first value that the predicate admits, which absorbs that rounding exactly.</div> |
| <p>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 <strong>the operator must match the side it is on</strong>:</p> |
| <div class="table-wrap"><table><thead><tr><th>Public predicate side</th><th>Accepted operators</th><th>Predicate</th></tr></thead><tbody><tr><td><code>lower</code></td><td><code>Ge</code>, <code>Gt</code></td><td>Public value is at least, or strictly greater than, the endpoint</td></tr><tr><td><code>upper</code></td><td><code>Le</code>, <code>Lt</code></td><td>Public value is at most, or strictly less than, the endpoint</td></tr></tbody></table></div> |
| <p>A mismatch, such as a <code>Lt</code> 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 <code>ip >= e</code> becomes internal <code>distance <= -e</code>. Endpoints are not rounded to f32 first. Out-of-domain cosine/IP cuts become empty or structurally unbounded bands, preserving inclusive membership at <code>f32::MAX</code>. L2 retains <code>Unsupported</code> when no representable square-root cut exists.</p> |
| <div class="callout"><strong>Displayed values have plateaus</strong>Several adjacent squared <code>f32</code> values round to the same displayed value. So <code>></code> and <code>>=</code> can derive cuts several bit patterns apart when the endpoint sits exactly on such a plateau, and can derive the <em>same</em> cut when the endpoint falls between two displayed values. What holds in every case is that each cut is the smallest one satisfying its own predicate.</div> |
| </section> |
| |
| <section class="article-section" id="usage"> |
| <h2>Usage</h2> |
| <div class="code-block"><span class="code-label">Rust · a two-sided band</span><pre><code>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}"); |
| }</code></pre></div> |
| <div class="code-block"><span class="code-label">Rust · from a SQL predicate, and an unbounded side</span><pre><code>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, |
| )?;</code></pre></div> |
| <div class="code-block"><span class="code-label">Rust · cosine distance and inner-product similarity</span><pre><code>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, |
| )?;</code></pre></div> |
| <p>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.</p> |
| <p>Results use a CSR layout, so a batch of queries shares three contiguous buffers. <code>lims</code> holds <code>query_count + 1</code> offsets, and query <code>i</code> owns <code>labels[lims[i]..lims[i+1]]</code> together with the matching slice of <code>raw_distances</code>. Per-query counters are available through <code>query(i).stats</code>, and counters covering the whole call through <code>call_stats()</code>.</p> |
| <p>All four families expose <code>range_search</code>, <code>range_search_batch</code>, and their <code>_with_roaring_filter</code> variants through both typed readers and <code>VectorIndexReader</code>. The filter is an allow-list and does not widen the fixed <code>nprobe</code>. Roaring filters admit only non-negative row IDs; a direct <code>RowIdFilter</code> 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.</p> |
| <p>For IVF-RQ, <code>lists_probed</code> includes empty selected lists; <code>rows_scanned</code> counts filter-eligible rows evaluated; <code>rows_committed</code> counts returned rows; and <code>early_abandoned</code> is zero. Call-level <code>list_reads</code> counts unique non-empty lists, not query/list pairs or storage read rounds. These result-owned counters leave the last top-K statistics unchanged.</p> |
| </section> |
| |
| <section class="article-section" id="bindings"> |
| <h2>Language bindings and ownership</h2> |
| <p>Every binding delegates to the same core entry points and endpoint conversion. All return raw internal distances and variable-length CSR results: <code>lims</code> has <code>query_count + 1</code> offsets, and query <code>i</code> occupies <code>[lims[i], lims[i + 1])</code> 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.</p> |
| <div class="table-wrap"><table><thead><tr><th>Binding</th><th>API and lifetime</th></tr></thead><tbody> |
| <tr><td>C ABI / generated header</td><td><code>paimon_vindex_reader_range_search</code>, <code>_range_search_batch</code>, and both <code>_with_roaring_filter</code> variants return an owned opaque result through an output pointer. <code>paimon_vindex_range_search_result_view</code> borrows its buffers; <code>paimon_vindex_range_search_result_destroy</code> releases them. Query/filter lengths are explicit. The generated <code>include/paimon_vindex.h</code> is rebuilt by cbindgen, not maintained manually.</td></tr> |
| <tr><td>C++</td><td><code>Reader::range_search</code>, <code>Reader::range_search_batch</code>, and their <code>_with_roaring_filter</code> variants copy CSR buffers into owning vectors. A native-result RAII guard handles cleanup, including allocation exceptions. Existing top-K methods remain unchanged.</td></tr> |
| <tr><td>JNI / Java</td><td><code>VectorIndexReader.rangeSearch</code> and <code>rangeSearchBatch</code> accept <code>VectorRangeSearchParams</code> and optional filter bytes. <code>VectorRangeSearchResult</code> takes ownership of JNI-created Java arrays. Its public constructor and array-returning accessors still make defensive copies. <code>hitCount()</code>, <code>labelAt(int)</code>, <code>rawDistanceAt(int)</code>, <code>queryStart(int)</code>, <code>queryEnd(int)</code>, and per-query counter overloads provide allocation-free consumption. Native lengths are checked against JVM array limits; labels, stored offsets and counters use <code>long</code>, while Java hit indices and half-open query bounds use <code>int</code>.</td></tr> |
| <tr><td>Python</td><td><code>VectorIndexReader.range_search</code> and <code>range_search_batch</code> accept <code>RangeSearchParams</code> and optional <code>roaring_filter=</code>. <code>RangeSearchResult</code> owns copied NumPy arrays (<code>uintp</code> offsets, <code>int64</code> labels, <code>float32</code> distances). Native results are freed in <code>finally</code>, even if conversion fails.</td></tr> |
| </tbody></table></div> |
| <p>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 <code>NULL</code> before doing work; an error returns <code>-1</code>, sets <code>paimon_vindex_last_error()</code>, and transfers no result. <code>destroy(NULL)</code> 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.</p> |
| <p>Capability is available as <code>paimon_vindex_reader_supports_range_search(reader, &supported)</code>, C++/Python <code>reader.supports_range_search()</code>, or Java <code>reader.supportsRangeSearch()</code>. 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.</p> |
| <p>All results expose per-query <code>lists_probed</code>, <code>rows_scanned</code>, <code>rows_committed</code> and <code>early_abandoned</code>, plus call-level <code>list_reads</code> (camelCase accessors in Java). These are core's logical counters, not binding-side estimates. In particular, <code>list_reads</code> 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.</p> |
| <div class="code-block"><span class="code-label">C · public L2 distance <= 2.0</span><pre><code>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);</code></pre></div> |
| <div class="code-block"><span class="code-label">C++ · owning CSR vectors</span><pre><code>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]); |
| }</code></pre></div> |
| <div class="code-block"><span class="code-label">Java · shared filtered batch</span><pre><code>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();</code></pre></div> |
| <p>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.</p> |
| <div class="code-block"><span class="code-label">Python · shared filtered batch</span><pre><code>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]</code></pre></div> |
| <p>Use <code>from_endpoints</code> (<code>fromEndpoints</code> in Java) for public predicate endpoints. Explicit raw construction uses <code>DistanceBand::from_raw</code> in Rust/C++, <code>DistanceBand.from_raw</code> in Python, <code>VectorDistanceBand.fromRaw</code> in Java, or the C <code>PaimonVindexRawDistanceBand</code> 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.</p> |
| <div class="callout"><strong>Public endpoints are not raw results.</strong>For L2, a public radius of 4 can return a <code>raw_distance</code> of 9, whose public distance is 3. An inner-product predicate of at least 5 can return a raw value of -6, whose public similarity is 6. The <code>raw_lower</code>/<code>raw_upper</code> cuts (<code>rawLower()</code>/<code>rawUpper()</code> in Java) are transformed half-open boundaries, not the original endpoint values; inner product also reverses their sides. Cosine uses <em>cosine distance</em>, not cosine similarity.</div> |
| <p><strong>Range API migration:</strong> replace <code>distances</code> with <code>raw_distances</code>; Java uses <code>rawDistances()</code>, <code>rawDistanceAt()</code>, and <code>rawDistancesForQuery()</code>. Replace ambiguous raw-band construction with an explicit raw factory or, preferably, the public-endpoint factory. Python query views expose <code>labels</code> and <code>raw_distances</code> 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.</p> |
| <p>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.</p> |
| </section> |
| |
| <section class="article-section" id="binding-tests"> |
| <h2>Cross-language verification</h2> |
| <p>The core-only <code>ffi/examples/range_search_fixture.rs</code> 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.</p> |
| <div class="code-block"><span class="code-label">Linux · from the repository root</span><pre><code>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</code></pre></div> |
| <p>Use <code>.dylib</code> library paths on macOS. Standalone binding tests still run without <code>PVI_RANGE_FIXTURES</code>; setting it enables the shared core oracle as well. No algorithm, index storage format or performance-tuning change is part of these additive bindings.</p> |
| </section> |
| |
| <section class="article-section" id="selection"> |
| <h2>Choosing an index type</h2> |
| <p>Range search supports <strong>IVF-FLAT, IVF-SQ, IVF-PQ and IVF-RQ</strong> 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.</p> |
| <div class="callout"><strong>Choose according to the membership requirement.</strong>IVF-FLAT tests full-vector distances. IVF-RQ uses RaBitQ, with a one-bit estimate for one-bit files and the full multi-bit estimate otherwise, not Faiss's residual/additive quantizer. Its band predicate is precise relative to that estimate, not to the raw vector. Tests cover an independent estimated-distance oracle, single/batch equivalence, filters, statistics, parallel scans, and non-finite inputs/data; they do not establish exact-distance recall guarantees. See <a href="ivf-rq.html#range">IVF-RQ range semantics</a>.</div> |
| <div class="callout"><strong>IVF-SQ membership uses an estimate.</strong>IVF-FLAT computes exact distances from stored <code>f32</code> vectors. IVF-SQ instead reuses top-K's blocked scalar-quantized estimator, reconstructing residuals with each list's stored bounds and centroid. The same estimated value determines band membership and is returned in <code>raw_distances</code>; there is no original-vector reranking and no top-K fallback. Prefer IVF-FLAT if original-distance membership must be exact.</div> |
| <div class="callout"><strong>IVF-PQ uses complete floating-point ADC estimates.</strong>Both packed 4-bit and 8-bit codes, residual encoding and OPQ are supported. L2 sums direct squared subvector distances. Cosine uses half the ADC squared distance after query normalization, a unit-vector surrogate rather than exact cosine of a re-normalized reconstruction. Inner product uses negative estimated dot product. The range path does not reuse top-K's quantized FastScan tables, expanded L2 tables or cosine score scale, so scores need not be bit-identical to top-K. It never truncates or reranks raw vectors. Shared lists are read once, oversized lists stream in bounded chunks, and the allow-list is evaluated once per list row across the batch.</div> |
| <p>A reproducible boundary example is in <code>core/tests/range_search.rs</code>: with a one-dimensional centroid of zero and SQ bounds <code>[0, 255]</code>, inputs <code>0.49</code> and <code>0.51</code> quantize to <code>0</code> and <code>1</code>. For query zero, band <code>[0, 0.1)</code> includes the first estimate despite its true squared distance being outside; band <code>[0.2, 0.3)</code> misses both although both true squared distances lie inside. This demonstrates the membership gap, not a general recall estimate.</p> |
| <p><strong>Performance and memory:</strong> 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.</p> |
| <p>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 <code>optimize_for_search</code>.</p> |
| <p>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.</p> |
| <p><code>call_stats().list_reads()</code> excludes empty lists and IVF-SQ cache hits and counts a streamed list once. <code>rows_scanned()</code> counts allow-listed rows reaching collection or cutoff rejection; blocked arithmetic can also evaluate excluded lanes. Under L2, SQ's <code>early_abandoned()</code> includes estimates equal to or above the upper cut. It is zero for cosine/IP and for every PQ/RQ range search.</p> |
| </section> |
| |
| <section class="article-section" id="errors"> |
| <h2>Fail-loud combinations</h2> |
| <p><em>Invalid input</em> means the call itself is wrong. <em>Unsupported</em> means the request cannot be served. <em>Invalid data</em> covers corrupt consumed index data and non-finite computed distances; no partial result is returned.</p> |
| <div class="table-wrap"><table><thead><tr><th>Situation</th><th>Class</th></tr></thead><tbody><tr><td>Inverted band, non-finite cut, or negative squared-L2 cut</td><td>Invalid input</td></tr><tr><td>Operator on the wrong side or mismatched index/band metrics</td><td>Invalid input</td></tr><tr><td>Zero <code>nprobe</code>, wrong query dimensions, non-finite query values, or malformed Roaring filter</td><td>Invalid input</td></tr><tr><td>DiskANN</td><td>Unsupported</td></tr><tr><td>L2 endpoint with no representable square-root cut</td><td>Unsupported</td></tr><tr><td>Non-finite consumed distance, factor, vector or cosine norm; non-finite normalization or rotation</td><td>Invalid data</td></tr></tbody></table></div> |
| <p>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.</p> |
| <p>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 <code>f_add</code> and <code>f_rescale</code> for the estimate it consumes: coarse for one-bit codes, full for multi-bit codes. Multi-bit coarse factors, including <code>f_error</code>, 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 <code>InvalidData</code>.</p> |
| <p>An <strong>empty band is not an error</strong>: 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.</p> |
| </section> |
| |
| <section class="article-section" id="diskann"> |
| <h2>Why not DiskANN</h2> |
| <p>The omission is deliberate and long-term, not a gap waiting to be filled. Graph traversal is inherently <em>k</em>-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.</p> |
| <p>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.</p> |
| <nav class="pager" aria-label="Index navigation"><a href="api.html"><small>Back</small>API</a><a href="ivf-flat.html"><small>Next</small>IVF-FLAT →</a></nav> |
| </section> |
| </article> |
| </div> |
| </div></main> |
| <footer class="site-footer"><div class="footer-inner"><span>Apache Paimon Vector Index</span><span>Range search · IVF-FLAT, IVF-SQ, IVF-PQ and IVF-RQ</span></div></footer> |
| </body> |
| </html> |
