You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "JunRuiLee (via GitHub)" <gi...@apache.org> on 2026/09/17 15:01:49 UTC

[PR] feat: add IVF-PQ L2 distance range search [paimon-vector-index]

JunRuiLee opened a new pull request, #107:
URL: https://github.com/apache/paimon-vector-index/pull/107

   ## Summary
   
   Part of #97.
   
   Add IVF-PQ L2 distance-range search to all four Rust reader entry points: single and batch queries, with and without a serialized Roaring allow-list.
   
   - Reuse `DistanceBand`, `VectorRangeSearchParams`, `RangeSearchResult`, and `RangeCollector`.
   - Support 4-bit and 8-bit PQ, residual/non-residual encoding, and OPQ.
   - Read each unique non-empty selected list once per call, share it across queries, and stream oversized lists through the existing bounded reader. Propagate collector failures without returning partial results or reading subsequent chunks.
   - Preserve the existing top-K paths and v1 storage format.
   
   ## Membership and validation
   
   Membership is half-open `[lower, upper)` in squared-L2 **estimated-distance** space. Both code widths use floating-point ADC: direct query-to-codebook subvector distances, after optional OPQ and coarse residual subtraction, summed in subquantizer order.
   
   The range path does not use u8 FastScan tables, precomputed norm identities, top-K truncation, or original-vector reranking. Membership is independent of list size, batch size, and `optimize_for_search`. Range estimates can differ from top-K's distances; probing every list removes the IVF coverage gap, not PQ quantization error.
   
   Results are uncapped and unordered. Each filter-eligible row is fully evaluated, so PQ `early_abandoned` is always zero. Non-finite transformed queries, any coarse distance (including unselected centroids), and consumed PQ estimates fail with `InvalidData`. Filtered-out and unprobed rows are not evaluated. Query shape, metric, probe width, and serialized filters are validated before empty-band shortcuts.
   
   ## Scope and independence
   
   - Based on community `main` at `643b4ed`, which already includes IVF-RQ #104 and IVF-SQ #106. SQ behavior and tests are preserved.
   - Does not include #92's 4-bit top-K scan scaling fix or #94's serialization allocation fix. `distance.rs` and the PQ writer are unchanged; `io.rs` changes only add fallible propagation to the existing streamed-reader callback while retaining its top-K wrapper.
   - No other metrics, language bindings, file-format changes, or separate performance optimizations.
   
   ## Verification
   
   The initial oracle test failed with PQ `Unsupported` before implementation.
   
   Twelve PQ regression tests cover both code widths (including rows beyond 200), an independent decoded-code oracle, residual/OPQ modes, exact boundaries and adjacent bands, non-finite data, cancellation and overflow, sparse/dense/empty filters, statistics, batch/single and query-permutation equivalence, optimization invariance, and unchanged top-K results. A synthetic index larger than 64 MiB also checks bounded streaming, shared physical reads, tail-code layout, and immediate collector-error propagation.
   
   On macOS/AArch64 with Rust 1.95.0:
   
   - `cargo test --offline --workspace`: 642 passed, 2 existing ignored.
   - `cargo test --offline --release --workspace`: 642 passed, 2 existing ignored.
   - The range integration suite contains 64 passing tests across the supported families.
   - `cargo fmt --all -- --check`: passed.
   - `cargo clippy --offline --all-targets --workspace -- -D warnings`: passed.
   - `python3 tools/check_license_headers.py`: passed.
   - `git diff --check`: passed.
   
   Linux/x86_64 and full cross-language integration remain for repository CI. There is no storage migration; reverting this additive change does not require rewriting index files.
   


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] feat: add IVF-PQ L2 distance range search [paimon-vector-index]

Posted by "JunRuiLee (via GitHub)" <gi...@apache.org>.
JunRuiLee commented on code in PR #107:
URL: https://github.com/apache/paimon-vector-index/pull/107#discussion_r4043694751


##########
core/src/ivfpq.rs:
##########
@@ -1665,6 +1668,401 @@ pub fn search_with_reader_roaring_filter<R: SeekRead>(
     search_with_reader_filter(reader, query, k, nprobe, Some(&filter))
 }
 
+impl<R: SeekRead> IVFPQIndexReader<R> {
+    /// Returns every eligible probed row whose PQ estimate is in the L2 band.
+    ///
+    /// Both code widths use floating-point ADC: direct squared-L2 distances
+    /// from the query (after OPQ and optional coarse residual subtraction) to
+    /// each selected PQ centroid, summed in subquantizer order. Range search
+    /// does not use top-K's u8 FastScan tables or precomputed norm identities,
+    /// so membership is independent of list size and `optimize_for_search`.
+    /// This is an estimate of the original vector's distance, even at full
+    /// nprobe. Results are uncapped and unordered; top-K is unchanged.
+    ///
+    /// Non-finite transformed queries, coarse distances, or consumed PQ
+    /// distances return `InvalidData`. Filtered-out rows are not evaluated.
+    /// Every eligible row is fully evaluated, without early abandonment.
+    pub fn range_search(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_with_filter(query, params, None)
+    }
+
+    pub fn range_search_with_filter(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+        filter: Option<&dyn RowIdFilter>,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_batch_with_filter(query, 1, params, filter)
+    }
+
+    /// Range search restricted to a serialized Roaring allow-list.
+    pub fn range_search_with_roaring_filter(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+        roaring_filter_bytes: &[u8],
+    ) -> io::Result<RangeSearchResult> {
+        let filter = decode_roaring_filter(roaring_filter_bytes)?;
+        self.range_search_with_filter(query, params, Some(&filter))
+    }
+
+    /// Batched range search with the same estimates and membership as single
+    /// queries. Each unique non-empty probed list is read once per call.
+    pub fn range_search_batch(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_batch_with_filter(queries, query_count, params, None)
+    }
+
+    /// Batched range search restricted to a serialized Roaring allow-list.
+    pub fn range_search_batch_with_roaring_filter(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+        roaring_filter_bytes: &[u8],
+    ) -> io::Result<RangeSearchResult> {
+        let filter = decode_roaring_filter(roaring_filter_bytes)?;
+        self.range_search_batch_with_filter(queries, query_count, params, Some(&filter))
+    }
+
+    pub fn range_search_batch_with_filter(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+        filter: Option<&dyn RowIdFilter>,
+    ) -> io::Result<RangeSearchResult> {
+        validate_queries(queries, query_count, self.d)?;
+        if params.band().metric() != self.metric {
+            return Err(io::Error::new(
+                io::ErrorKind::InvalidInput,
+                format!(
+                    "band metric {:?} does not match index metric {:?}",
+                    params.band().metric(),
+                    self.metric
+                ),
+            ));
+        }
+        let nprobe = params.validate(self.nlist)?;
+        let mut builder = RangeResultBuilder::new(query_count);
+        if params.band().is_empty() {
+            return Ok(builder.build());
+        }
+        self.ensure_loaded()?;
+        let mut query_states = Vec::with_capacity(query_count);
+        let mut list_to_queries = vec![Vec::new(); self.nlist];
+        for (query_index, query) in queries.chunks_exact(self.d).enumerate() {
+            let mut prepared = query.to_vec();
+            if let Some(opq) = &self.opq {
+                opq.apply(query, &mut prepared);
+            }
+            if prepared.iter().any(|value| !value.is_finite()) {
+                return Err(io::Error::new(
+                    io::ErrorKind::InvalidData,
+                    "non-finite IVF-PQ rotated query",
+                ));
+            }
+            let probes = kmeans::find_topk_checked(
+                &prepared,
+                &self.quantizer_centroids,
+                self.nlist,
+                self.d,
+                nprobe,
+            )
+            .map_err(|list| {
+                io::Error::new(
+                    io::ErrorKind::InvalidData,
+                    format!("non-finite IVF-PQ query-centroid distance for list {list}"),
+                )
+            })?;

Review Comment:
   Fixed in 6e657d0. Larger batches now use parallel `find_topk_checked`, preserving non-finite checks for unselected centroids. Added regression tests for query ordering and overflow before payload I/O.



-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] feat: add IVF-PQ L2 distance range search [paimon-vector-index]

Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 commented on code in PR #107:
URL: https://github.com/apache/paimon-vector-index/pull/107#discussion_r4043430732


##########
core/src/ivfpq.rs:
##########
@@ -1665,6 +1668,401 @@ pub fn search_with_reader_roaring_filter<R: SeekRead>(
     search_with_reader_filter(reader, query, k, nprobe, Some(&filter))
 }
 
+impl<R: SeekRead> IVFPQIndexReader<R> {
+    /// Returns every eligible probed row whose PQ estimate is in the L2 band.
+    ///
+    /// Both code widths use floating-point ADC: direct squared-L2 distances
+    /// from the query (after OPQ and optional coarse residual subtraction) to
+    /// each selected PQ centroid, summed in subquantizer order. Range search
+    /// does not use top-K's u8 FastScan tables or precomputed norm identities,
+    /// so membership is independent of list size and `optimize_for_search`.
+    /// This is an estimate of the original vector's distance, even at full
+    /// nprobe. Results are uncapped and unordered; top-K is unchanged.
+    ///
+    /// Non-finite transformed queries, coarse distances, or consumed PQ
+    /// distances return `InvalidData`. Filtered-out rows are not evaluated.
+    /// Every eligible row is fully evaluated, without early abandonment.
+    pub fn range_search(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_with_filter(query, params, None)
+    }
+
+    pub fn range_search_with_filter(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+        filter: Option<&dyn RowIdFilter>,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_batch_with_filter(query, 1, params, filter)
+    }
+
+    /// Range search restricted to a serialized Roaring allow-list.
+    pub fn range_search_with_roaring_filter(
+        &mut self,
+        query: &[f32],
+        params: VectorRangeSearchParams,
+        roaring_filter_bytes: &[u8],
+    ) -> io::Result<RangeSearchResult> {
+        let filter = decode_roaring_filter(roaring_filter_bytes)?;
+        self.range_search_with_filter(query, params, Some(&filter))
+    }
+
+    /// Batched range search with the same estimates and membership as single
+    /// queries. Each unique non-empty probed list is read once per call.
+    pub fn range_search_batch(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+    ) -> io::Result<RangeSearchResult> {
+        self.range_search_batch_with_filter(queries, query_count, params, None)
+    }
+
+    /// Batched range search restricted to a serialized Roaring allow-list.
+    pub fn range_search_batch_with_roaring_filter(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+        roaring_filter_bytes: &[u8],
+    ) -> io::Result<RangeSearchResult> {
+        let filter = decode_roaring_filter(roaring_filter_bytes)?;
+        self.range_search_batch_with_filter(queries, query_count, params, Some(&filter))
+    }
+
+    pub fn range_search_batch_with_filter(
+        &mut self,
+        queries: &[f32],
+        query_count: usize,
+        params: VectorRangeSearchParams,
+        filter: Option<&dyn RowIdFilter>,
+    ) -> io::Result<RangeSearchResult> {
+        validate_queries(queries, query_count, self.d)?;
+        if params.band().metric() != self.metric {
+            return Err(io::Error::new(
+                io::ErrorKind::InvalidInput,
+                format!(
+                    "band metric {:?} does not match index metric {:?}",
+                    params.band().metric(),
+                    self.metric
+                ),
+            ));
+        }
+        let nprobe = params.validate(self.nlist)?;
+        let mut builder = RangeResultBuilder::new(query_count);
+        if params.band().is_empty() {
+            return Ok(builder.build());
+        }
+        self.ensure_loaded()?;
+        let mut query_states = Vec::with_capacity(query_count);
+        let mut list_to_queries = vec![Vec::new(); self.nlist];
+        for (query_index, query) in queries.chunks_exact(self.d).enumerate() {
+            let mut prepared = query.to_vec();
+            if let Some(opq) = &self.opq {
+                opq.apply(query, &mut prepared);
+            }
+            if prepared.iter().any(|value| !value.is_finite()) {
+                return Err(io::Error::new(
+                    io::ErrorKind::InvalidData,
+                    "non-finite IVF-PQ rotated query",
+                ));
+            }
+            let probes = kmeans::find_topk_checked(
+                &prepared,
+                &self.quantizer_centroids,
+                self.nlist,
+                self.d,
+                nprobe,
+            )
+            .map_err(|list| {
+                io::Error::new(
+                    io::ErrorKind::InvalidData,
+                    format!("non-finite IVF-PQ query-centroid distance for list {list}"),
+                )
+            })?;

Review Comment:
   <!-- dlf-review -->
   **[MAJOR] Batch coarse assignment instead of serializing it per query**
   
   `range_search_batch_with_filter` calls `find_topk_checked` once per query, and that helper scans all `nlist` centroids with individual distance calls. The public batch path therefore performs `O(query_count * nlist * dimension)` coarse-assignment work serially on the caller thread before any list I/O, bypassing the existing batched SGEMM/parallel path used by sibling readers.
   
   Please add or reuse a checked batched assignment helper (or at minimum the parallel checked pattern used by IVF-RQ), while preserving the current contract that rejects non-finite distances even for unselected centroids, then build `list_to_queries` from the batched result.



-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] feat: add IVF-PQ L2 distance range search [paimon-vector-index]

Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 merged PR #107:
URL: https://github.com/apache/paimon-vector-index/pull/107


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org