You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "jerry-024 (via GitHub)" <gi...@apache.org> on 2026/08/28 09:43:39 UTC
[PR] perf: speed up IVF-RQ index build [paimon-vector-index]
jerry-024 opened a new pull request, #85:
URL: https://github.com/apache/paimon-vector-index/pull/85
(no comment)
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 commented on code in PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85#discussion_r3912120575
##########
core/src/ivfpq.rs:
##########
@@ -114,9 +116,40 @@ impl IVFPQIndex {
codes: vec![Vec::new(); nlist],
precomputed_table: Vec::new(),
fastscan_codes: Vec::new(),
+ coarse_assignment: CoarseAssignment::default(),
}
}
+ pub fn quantizer_centroids(&self) -> &[f32] {
+ &self.quantizer_centroids
+ }
+
+ /// Enables automatic Vamana coarse assignment for large centroid matrices.
+ /// Disable it to keep vector assignment exact.
+ pub fn set_approximate_coarse_assignment(&mut self, enabled: bool) {
+ assert!(
Review Comment:
Fixed in `0dd8915`. The coarse-assignment setters on all four direct IVF index types are now crate-private, so callers cannot switch policy after training (or on an index returned by `from_trained`). Public callers select the policy through `VectorIndexConfig` or `ivf.coarse-assignment=auto|exact` before the writer/training lifecycle starts. `from_trained` only copies the source index policy internally. The API and release documentation now state this lifecycle.
##########
core/src/index.rs:
##########
@@ -600,6 +625,20 @@ fn parse_nlist_options(
}
}
+fn parse_ivf_coarse_assignment_option(options: &mut ConfigOptions) -> io::Result<bool> {
+ match options
+ .optional("ivf.coarse-assignment")
+ .as_deref()
+ .map(str::trim)
+ {
+ None | Some("auto") => Ok(true),
Review Comment:
I investigated the corresponding Lance behavior and am intentionally retaining `auto` as the default because it aligns with Lance’s existing IVF build contract introduced by [lance-format/lance#4089](https://github.com/lance-format/lance/pull/4089):
- Lance defaults its indexing speedup status to `Auto` and enables it when `nlist × dimension >= 1,000,000` ([source](https://github.com/lance-format/lance/blob/742e6a317c95840ca18adf47646ea79e0070c57b/rust/lance-index/src/vector/utils.rs#L24-L103)).
- Build-time partition assignment uses HNSW top-1 ([source](https://github.com/lance-format/lance/blob/742e6a317c95840ca18adf47646ea79e0070c57b/rust/lance-index/src/vector/ivf/transform.rs#L46-L116)), while query-time `find_partitions` still uses exact centroid top-k ([source](https://github.com/lance-format/lance/blob/742e6a317c95840ca18adf47646ea79e0070c57b/rust/lance-index/src/vector/ivf.rs#L343-L353)).
- Lance provides an exact opt-out through `LANCE_USE_HNSW_SPEEDUP_INDEXING=disabled`.
Paimon follows the same policy boundary and threshold, using Vamana (`R=12`, `L=15`) instead of HNSW (`M=12`, `ef=15`), and provides the finer-grained `ivf.coarse-assignment=exact` opt-out. The low-`nprobe` effect is therefore an intentional, documented build-speed/recall tradeoff of `auto`; callers requiring exact nearest-centroid placement can select `exact`.
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "shyjsarah (via GitHub)" <gi...@apache.org>.
shyjsarah commented on PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85#issuecomment-5507228668
+1
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 commented on PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85#issuecomment-5505837002
Thanks for the detailed review. Addressed in `8c706af`.
1. We are keeping automatic Vamana coarse assignment as an explicit build-speed/recall tradeoff rather than changing search-side list selection. All option-map APIs now accept `ivf.coarse-assignment=auto|exact`. `auto` preserves the thresholded Vamana behavior; `exact` disables the graph and restores exact nearest-centroid assignment. Rust config literals expose the same choice through `use_approximate_coarse_assignment`, and the four direct IVF index types expose `set_approximate_coarse_assignment(...)`. The API and per-index docs now state that automatic graph assignment may select a different list from exact search, can reduce recall at small `nprobe`, and does not guarantee self-recall at `nprobe=1`. A threshold-enabled regression test verifies that `exact` preserves self-recall with `d=256`, `nlist=4096`, and `nprobe=1`.
2. Empty assignments now return before graph preparation, including the separate IVF-RQ preparation path. Small non-empty batches still pay the graph startup cost when automatic assignment is enabled; this is documented, and users can select `exact` to avoid it.
3. `preprocess_vectors` now skips cosine chunking when `d == 0`, with coverage for both the serial and parallel thresholds.
Verification: `cargo test --workspace` passed 496 tests with 2 ignored; `cargo clippy --workspace --all-targets -- -D warnings`, formatting, and `git diff --check` all passed.
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "shyjsarah (via GitHub)" <gi...@apache.org>.
shyjsarah commented on code in PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85#discussion_r3911762636
##########
core/src/index.rs:
##########
@@ -600,6 +625,20 @@ fn parse_nlist_options(
}
}
+fn parse_ivf_coarse_assignment_option(options: &mut ConfigOptions) -> io::Result<bool> {
+ match options
+ .optional("ivf.coarse-assignment")
+ .as_deref()
+ .map(str::trim)
+ {
+ None | Some("auto") => Ok(true),
Review Comment:
**[major] This leaves the original blocker on the default path.** The new `exact` option works, but omitted/`auto` still assigns through Vamana while search selects lists using exact centroid top-k. Re-running the original release probe on this commit still moved 1,807/4,096 centroid vectors and returned `-1 / f32::MAX` for a self-query with `nprobe=1`; explicit exact mode moved 0 and succeeded. Documenting the loss makes it visible, but does not make add and lookup use a consistent default contract. Please default to exact or unify the query-side policy.
##########
core/src/ivfpq.rs:
##########
@@ -114,9 +116,40 @@ impl IVFPQIndex {
codes: vec![Vec::new(); nlist],
precomputed_table: Vec::new(),
fastscan_codes: Vec::new(),
+ coarse_assignment: CoarseAssignment::default(),
}
}
+ pub fn quantizer_centroids(&self) -> &[f32] {
+ &self.quantizer_centroids
+ }
+
+ /// Enables automatic Vamana coarse assignment for large centroid matrices.
+ /// Disable it to keep vector assignment exact.
+ pub fn set_approximate_coarse_assignment(&mut self, enabled: bool) {
+ assert!(
Review Comment:
**[minor] This guard permits changing the policy after `train()` (or on an index created by `from_trained`) as long as no rows were added.** For residual IVF-PQ, training uses the current coarse assignments to build the PQ training residuals, so switching here makes add encode a different assignment distribution than the one used for training. IVF-SQ has the same issue for its residual/list quantizers. Please restrict policy changes to pre-training state, or invalidate/retrain assignment-dependent state; also document the lifecycle requirement.
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "shyjsarah (via GitHub)" <gi...@apache.org>.
shyjsarah commented on code in PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85#discussion_r3910957840
##########
core/src/coarse.rs:
##########
@@ -0,0 +1,154 @@
+// 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 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::diskann::{
+ DiskAnnBuildDistance, DiskAnnBuildParams, DiskAnnRawVectorEncoding, DiskAnnStorageLayout,
+};
+use crate::kmeans;
+use crate::logging::{emit_log, LogLevel};
+use crate::vamana::VamanaGraph;
+use rayon::prelude::*;
+
+const APPROX_ASSIGN_SEARCH_LIST: usize = 15;
+const APPROX_ASSIGN_MIN_CENTROID_VALUES: usize = 1_000_000;
+
+fn use_approximate_assignment(d: usize, nlist: usize) -> bool {
+ d.saturating_mul(nlist) >= APPROX_ASSIGN_MIN_CENTROID_VALUES
+}
+
+#[derive(Default)]
+pub(crate) struct CoarseAssignment {
+ graph: Option<VamanaGraph>,
+ build_attempted: bool,
+}
+
+impl CoarseAssignment {
+ pub(crate) fn reset(&mut self) {
+ *self = Self::default();
+ }
+
+ pub(crate) fn prepare(&mut self, centroids: &[f32], nlist: usize, d: usize) {
+ if self.build_attempted {
+ return;
+ }
+ self.build_attempted = true;
+ if !use_approximate_assignment(d, nlist) {
+ return;
+ }
+
+ let params = DiskAnnBuildParams {
+ max_degree: 12,
+ build_search_list_size: APPROX_ASSIGN_SEARCH_LIST,
+ alpha: 1.2,
+ seed: 42,
+ memory_budget_bytes: 1024 * 1024 * 1024,
+ storage_layout: DiskAnnStorageLayout::Compact,
+ raw_vector_encoding: DiskAnnRawVectorEncoding::F32,
+ build_distance: DiskAnnBuildDistance::FullPrecision,
+ };
+ match VamanaGraph::build(centroids, nlist, d, params) {
+ Ok(graph) => self.graph = Some(graph),
+ Err(error) => emit_log(
+ LogLevel::Warn,
+ &format!("automatic approximate coarse assignment disabled: {error}"),
+ ),
+ }
+ }
+
+ pub(crate) fn assign(
+ &mut self,
+ data: &[f32],
+ n: usize,
+ centroids: &[f32],
+ nlist: usize,
+ d: usize,
+ ) -> Vec<usize> {
+ self.prepare(centroids, nlist, d);
+ let Some(graph) = &self.graph else {
+ return kmeans::find_nearest_batch(data, n, centroids, nlist, d);
+ };
+
+ let mut assignments = vec![0usize; n];
+ let chunk = (n / (rayon::current_num_threads() * 4).max(1)).clamp(16, 1024);
+ assignments.par_chunks_mut(chunk).enumerate().for_each_init(
+ || graph.search_scratch(APPROX_ASSIGN_SEARCH_LIST),
+ |scratch, (chunk_idx, chunk_assignments)| {
+ let row0 = chunk_idx * chunk;
+ for (i, assignment) in chunk_assignments.iter_mut().enumerate() {
+ let row = row0 + i;
+ *assignment = graph
Review Comment:
**[major] The list chosen here is approximate, but all IVF search paths still choose probe lists with exact centroid top-k. The two policies can disagree, so a vector may be stored in a list that a self-query with `nprobe=1` never probes. I reproduced this at `d=256, nlist=4096`: 1,807/4,096 centroid vectors moved away from their exact list, and id 2461 was stored in list 3 while its self-query returned `-1 / f32::MAX`. Please keep one coarse-quantizer contract for both insertion and lookup, or make this approximation explicit and ensure search covers the graph-selected list. A threshold-enabled self-recall regression test would catch this.
--
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] perf: accelerate IVF builds with Vamana coarse assignment [paimon-vector-index]
Posted by "jerry-024 (via GitHub)" <gi...@apache.org>.
jerry-024 merged PR #85:
URL: https://github.com/apache/paimon-vector-index/pull/85
--
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