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/18 01:54:17 UTC
[PR] feat: add cosine and inner-product range search for IVF indexes [paimon-vector-index]
JunRuiLee opened a new pull request, #108:
URL: https://github.com/apache/paimon-vector-index/pull/108
## Dependency and review baseline
**Depends on #107; please keep this PR as a draft until that dependency is merged.**
This branch starts at #107's head, `907072dfefd9b075ecfeea3377665c5688a0fa4f`, and adds one cosine/inner-product extension commit, `fb87cda`.
- [Extension-only diff against #107](https://github.com/JunRuiLee/paimon-vector-index/compare/907072d...fb87cda): 18 files, +1,675 / -245 lines. More than 75% of the additions are integration tests and documentation.
- Because #107 is still open, the comparison against upstream `main` also includes its IVF-PQ L2 range-search commit. That parent implementation is not a new implementation in this extension.
- After #107 merges, rebase this branch onto `main` to leave only the metric extension in the PR diff.
## Summary
- Support cosine and inner-product range search for IVF-Flat, IVF-SQ, IVF-PQ and IVF-RQ through all four typed/unified single, batch and Roaring-filtered entry points.
- Define shared public score conversion, exact f64 predicate-to-f32 band conversion, IP side/operator reversal, signed-zero/extreme endpoint handling, and range capability queries.
- Preserve the membership contract: Flat uses exact stored-vector distances; SQ/PQ/RQ use their declared estimates. Full probing does not remove quantization error.
- Extend #107's native PQ scanner rather than adding a separate scanner. Preserve PQ4/PQ8, residual coding, OPQ, lazy bounded LUT caching, scratch fallback, parallel query scans, shared filtering and bounded streaming.
- Normalize cosine queries before probing/scanning (and before PQ OPQ). PQ cosine uses half the floating-point ADC squared-distance estimate; IP uses negative estimated dot products with residual coarse contributions included once. No cosine/IP partial-sum pruning is used.
- Add oracle, ULP/boundary, nonfinite-data, zero-vector, filter, statistics, cache/streaming and L2/top-K regression coverage, and update the Rust/docs capability and estimator descriptions.
Existing L2 and top-K behavior, the storage format and C/JNI APIs remain unchanged. No original-vector reranking or top-K fallback is introduced.
## Validation
Run locally on macOS/AArch64:
- `cargo test --offline --locked --workspace`: **656 passed, 2 ignored**.
- `cargo test --offline --locked --release --workspace -- --test-threads=1`: **656 passed, 2 ignored**. This serializes the test harness, not the explicit 1/4-worker Rayon pools exercised by the tests.
- `cargo clippy --offline --locked --workspace --all-targets -- -D warnings`: passed.
- `cargo fmt --all -- --check` and `git diff --check`: passed.
- Local documentation links/anchors: 192 references passed across six changed HTML pages.
- PQ coverage includes all metrics, PQ4/PQ8, both residual modes, dense 64D OPQ, scalar-oracle comparisons, adjacent-ULP membership, single/batch/filter equivalence, 1/4 workers and `optimize_for_search` invariance. Streaming crosses the production 8 MiB LUT cache budget for PQ8; PQ4 scratch fallback is covered separately with a forced budget.
Local independent read-only agent reviews of shared semantics/Flat/SQ/RQ and the PQ extension found no remaining in-scope blockers. Maintainer review and hosted CI are still pending.
## Known validation limitation
Default-concurrent Release test runs intermittently fail unchanged top-K tests that assert work was observed on multiple Rayon workers. A clean archive of #107, compiled into a separate target directory, reproduced the same category of IVF-Flat worker-count assertion failure. Isolated tests and the complete serialized Release test harness pass. This is not a claim that default-concurrent Release is consistently green.
The expanded SQ range parallelism test uses a bounded worker handshake to avoid that scheduling race in its own coverage; unrelated top-K tests are not changed here.
## Rollback / follow-up
No data migration or format change is involved. Reverting only the extension commit leaves #107's L2 implementation intact. Before marking ready: merge #107, update this branch onto `main`, and inspect hosted CI and maintainer feedback.
--
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 cosine and inner-product range search for IVF indexes [paimon-vector-index]
Posted by "JunRuiLee (via GitHub)" <gi...@apache.org>.
JunRuiLee commented on code in PR #108:
URL: https://github.com/apache/paimon-vector-index/pull/108#discussion_r4056911480
##########
core/src/range.rs:
##########
@@ -135,17 +136,76 @@ impl DistanceBand {
}
}
-/// Only L2 is certified so far. Cosine and inner-product bands return
-/// `Unsupported`, which means "we cannot serve this request, please fall back",
-/// not "the call has a bug".
-pub(crate) fn ensure_certified_metric(metric: MetricType) -> io::Result<()> {
+pub(crate) fn prepare_range_queries(
+ queries: &[f32],
+ dimension: usize,
+ metric: MetricType,
+) -> io::Result<Cow<'_, [f32]>> {
+ if metric != MetricType::Cosine {
+ return Ok(Cow::Borrowed(queries));
+ }
+ let mut normalized = queries.to_vec();
+ for query in normalized.chunks_exact_mut(dimension) {
+ let norm = fvec_normalize(query);
+ if !norm.is_finite() || query.iter().any(|value| !value.is_finite()) {
+ return Err(io::Error::new(
+ io::ErrorKind::InvalidData,
+ "non-finite normalized query",
+ ));
+ }
+ }
+ Ok(Cow::Owned(normalized))
+}
+
+pub(crate) fn range_probe_lists(
+ queries: &[f32],
+ centroids: &[f32],
+ dimension: usize,
+ nlist: usize,
+ nprobe: usize,
+ metric: MetricType,
+) -> io::Result<Vec<Vec<usize>>> {
if metric == MetricType::L2 {
- return Ok(());
+ return Ok(kmeans::find_topk_batch(
+ queries,
+ queries.len() / dimension,
+ centroids,
+ nlist,
+ dimension,
+ nprobe,
+ )
+ .0);
+ }
+ if centroids.iter().any(|value| !value.is_finite()) {
+ return Err(io::Error::new(
+ io::ErrorKind::InvalidData,
+ "non-finite IVF centroid",
+ ));
+ }
+ queries
Review Comment:
Thanks, fixed in e404a85. Non-L2 probing now uses thresholded parallel iteration, retaining checked distances and query order. Added 1/4-worker and overflow regression tests.
##########
core/src/ivfpq.rs:
##########
@@ -1962,39 +1984,61 @@ fn scan_pq_range_list<C: Collector + Send>(
return Ok(());
}
let scan_query = |scratch: &mut PqRangeScratch, query: &mut PqRangeQuery<C>| {
+ let cached_ip_table =
+ query.query_index < cached_queries && query.metric == MetricType::InnerProduct;
+ let table_centroid = centroid.filter(|_| !cached_ip_table);
let table = if query.query_index < cached_queries {
if query.table_list.is_none()
- || (centroid.is_some() && query.table_list != Some(list_id))
+ || (table_centroid.is_some() && query.table_list != Some(list_id))
{
build_pq_range_table(
pq,
&query.query,
- centroid,
+ query.metric,
+ table_centroid,
&mut scratch.residual_query,
&mut query.table,
);
query.table_list = Some(list_id);
}
- &query.table
+ &mut query.table
} else {
build_pq_range_table(
pq,
&query.query,
+ query.metric,
centroid,
&mut scratch.residual_query,
&mut scratch.table,
);
- &scratch.table
+ &mut scratch.table
};
- scan_pq_range_codes(
+ let ip_offset = centroid
+ .filter(|_| cached_ip_table)
+ .map(|centroid| -fvec_inner_product(&query.query, centroid));
+ if let Some(offset) = ip_offset {
Review Comment:
Thanks, fixed in e404a85. Removed subtable copy/restore; the scanner applies the offset to the first selected entry, preserving rounding and signed zero. Kept the rounding test and added regression coverage.
--
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 cosine and inner-product range search for IVF indexes [paimon-vector-index]
Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 merged PR #108:
URL: https://github.com/apache/paimon-vector-index/pull/108
--
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 cosine and inner-product range search for IVF indexes [paimon-vector-index]
Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 commented on code in PR #108:
URL: https://github.com/apache/paimon-vector-index/pull/108#discussion_r4056656926
##########
core/src/ivfpq.rs:
##########
@@ -1962,39 +1984,61 @@ fn scan_pq_range_list<C: Collector + Send>(
return Ok(());
}
let scan_query = |scratch: &mut PqRangeScratch, query: &mut PqRangeQuery<C>| {
+ let cached_ip_table =
+ query.query_index < cached_queries && query.metric == MetricType::InnerProduct;
+ let table_centroid = centroid.filter(|_| !cached_ip_table);
let table = if query.query_index < cached_queries {
if query.table_list.is_none()
- || (centroid.is_some() && query.table_list != Some(list_id))
+ || (table_centroid.is_some() && query.table_list != Some(list_id))
{
build_pq_range_table(
pq,
&query.query,
- centroid,
+ query.metric,
+ table_centroid,
&mut scratch.residual_query,
&mut query.table,
);
query.table_list = Some(list_id);
}
- &query.table
+ &mut query.table
} else {
build_pq_range_table(
pq,
&query.query,
+ query.metric,
centroid,
&mut scratch.residual_query,
&mut scratch.table,
);
- &scratch.table
+ &mut scratch.table
};
- scan_pq_range_codes(
+ let ip_offset = centroid
+ .filter(|_| cached_ip_table)
+ .map(|centroid| -fvec_inner_product(&query.query, centroid));
+ if let Some(offset) = ip_offset {
Review Comment:
**[Ponytail][simplification]** The cached residual-IP path copies, mutates, and restores the entire first `ksub` subtable just to add one per-list scalar, which also requires special cleanup after collector errors. Since `scan_pq_range_codes` has only this caller, pass `ip_offset` into it and start the distance accumulation with that value instead. This removes `first_subtable`, the backup/restore work, and the restore-on-error test; keep the existing rounding test to guard the numerical behavior.
##########
core/src/range.rs:
##########
@@ -135,17 +136,76 @@ impl DistanceBand {
}
}
-/// Only L2 is certified so far. Cosine and inner-product bands return
-/// `Unsupported`, which means "we cannot serve this request, please fall back",
-/// not "the call has a bug".
-pub(crate) fn ensure_certified_metric(metric: MetricType) -> io::Result<()> {
+pub(crate) fn prepare_range_queries(
+ queries: &[f32],
+ dimension: usize,
+ metric: MetricType,
+) -> io::Result<Cow<'_, [f32]>> {
+ if metric != MetricType::Cosine {
+ return Ok(Cow::Borrowed(queries));
+ }
+ let mut normalized = queries.to_vec();
+ for query in normalized.chunks_exact_mut(dimension) {
+ let norm = fvec_normalize(query);
+ if !norm.is_finite() || query.iter().any(|value| !value.is_finite()) {
+ return Err(io::Error::new(
+ io::ErrorKind::InvalidData,
+ "non-finite normalized query",
+ ));
+ }
+ }
+ Ok(Cow::Owned(normalized))
+}
+
+pub(crate) fn range_probe_lists(
+ queries: &[f32],
+ centroids: &[f32],
+ dimension: usize,
+ nlist: usize,
+ nprobe: usize,
+ metric: MetricType,
+) -> io::Result<Vec<Vec<usize>>> {
if metric == MetricType::L2 {
- return Ok(());
+ return Ok(kmeans::find_topk_batch(
+ queries,
+ queries.len() / dimension,
+ centroids,
+ nlist,
+ dimension,
+ nprobe,
+ )
+ .0);
+ }
+ if centroids.iter().any(|value| !value.is_finite()) {
+ return Err(io::Error::new(
+ io::ErrorKind::InvalidData,
+ "non-finite IVF centroid",
+ ));
+ }
+ queries
Review Comment:
**[Major][performance]** This non-L2 branch runs `find_topk_checked` serially for every query, so Flat and SQ range searches do `O(nq * nlist * dimension)` coarse-assignment work on the caller thread before list I/O; `nprobe` and filtering cannot reduce it. For example, 1,024 queries, 4,096 lists, and 128 dimensions require about 537 million scalar component evaluations. Please reuse the thresholded `par_chunks_exact` pattern already used by PQ/RQ here, while retaining `find_topk_checked` so non-finite query-centroid distances remain rejected and collecting results in query order.
--
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