shyjsarah commented on code in PR #82:
URL:
https://github.com/apache/paimon-vector-index/pull/82#discussion_r3910562076
##########
core/src/pq.rs:
##########
@@ -22,6 +22,34 @@ use crate::distance::{
use crate::kmeans::{self, KMeansConfig};
use rayon::prelude::*;
+pub(crate) fn l2_argmin_is_stable(
+ values: &[f32],
+ common_offset: f64,
+ mut error_bound: impl FnMut(usize) -> f64,
+) -> bool {
+ let Some((best_index, &best_value)) = values
Review Comment:
**[Major correctness]** This proves only that the global centroid argmin is
stable, then treats the entire sub-table as safe. IVF-PQ scanning consumes
arbitrary persisted code entries, not necessarily the global table minimum.
On `9e6cb1b`, adding an unused code 2 that is a clearly separated global
argmin suppresses fallback while stored codes 0/1 remain reversed. Add emits
codes `[0,1]`; canonical direct/FMA distances rank id 1 first, but ordinary,
reopened-reader, ephemeral, resident-reader, and in-memory precomputed searches
all return id 0.
Please certify the ordering of entries that scanning can consume, or use the
canonical direct/FMA table. Add an unused-global-minimum variant to the
five-path regression test; the current test has one disputed stored code as the
global argmin and therefore misses this case.
##########
core/src/pq.rs:
##########
@@ -436,7 +600,22 @@ impl ProductQuantizer {
let c_off = c_base + j * chunk_dim;
fvec_norm_l2sqr(&self.centroids[c_off..c_off +
chunk_dim])
};
- table[t_base + j] = (q_norm + c_norm - 2.0 *
table[t_base + j]).max(0.0);
+ table[t_base + j] = q_norm + c_norm - 2.0 *
table[t_base + j];
+ }
+ let table = &mut table[t_base..t_base + self.ksub];
+ let stable = l2_argmin_is_stable(table, 0.0, |j| {
Review Comment:
**[Major search regression]** The table has already been populated, but this
call performs a `min_by` pass and another `all()` pass over all 256 entries,
including repeated per-code bound computation. The same policy is present in
resident and ephemeral table construction.
Against `7296eaa`, a standard-scale short-list benchmark measured ordinary
search about +36%, resident precomputed about +56%, and ephemeral reuse about
+217% on the latest head.
Please track the best/runner-up values and error metadata while producing or
combining the table, rather than rescanning the completed table twice.
##########
core/src/ivfpq.rs:
##########
@@ -1086,6 +1162,25 @@ fn combine_stable_ephemeral_tables(
sim_table[offset] =
(residual_norm + list_table[offset] - 2.0 *
query_table[offset]).max(0.0) as f32;
}
+ if !l2_argmin_is_stable(&sim_table[table_base..table_base + pq.ksub],
0.0, |code| {
+ let offset = table_base + code;
+ 16.0 * range.len() as f64
+ * f64::from(f32::EPSILON)
+ * (residual_norm + list_table[offset].abs() + 2.0 *
query_table[offset].abs())
+ }) {
+ let residual_query = residual_query.get_or_insert_with(|| {
Review Comment:
**[Major fallback regression]** When this table is unstable, the fallback
allocates a fresh full-dimensional residual vector for every query/list pair
and recomputes the full exact PQ table after the ephemeral list/query tables
have already been built.
For `nq=64,nprobe=8,d=64`, large-offset Auto ephemeral search is about `6.6
ms` here versus `0.46 ms` at `7296eaa` (~14x), with exactly 512 extra
allocations and 131,072 extra bytes—matching `nq*nprobe` residual vectors.
Please reuse a per-worker scratch buffer and avoid the ephemeral route when
scale/fallback history indicates that exact recomputation will be required, so
the search does not pay both algorithms.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
