shyjsarah commented on code in PR #82:
URL:
https://github.com/apache/paimon-vector-index/pull/82#discussion_r3903222561
##########
core/src/pq.rs:
##########
@@ -436,7 +535,29 @@ 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);
+ let approximate = q_norm + c_norm - 2.0 * table[t_base
+ j];
+ // Cover the three reductions and final subtraction
before trusting SGEMM.
+ let error_bound =
+ 16.0 * chunk_dim as f32 * f32::EPSILON * (q_norm +
c_norm);
+ table[t_base + j] =
+ if !approximate.is_finite() || approximate <=
error_bound {
Review Comment:
**[Major correctness]** This fallback only asks whether each individual
expanded distance is near its own cancellation bound. It does not protect the
ordering when two large, nonzero candidate distances differ by less than their
numerical error.
I reproduced this on `7296eaa`: the direct/FMA add path selects code 1
(`88314130 < 88314136`), but ordinary in-memory search, unoptimized reader
search, ephemeral reuse, resident precomputation, and optimized
serialized-reader search all rank code 0 first. The new per-sub exact fallback
is not triggered for this subspace.
Please make the direct-encoded 8-bit table contract canonical across all
search paths, or use a pairwise error/margin rule that recomputes candidates
whose ordering is not provably stable. The ephemeral f64-to-f32 path also needs
to preserve the same f32/FMA ordering used for persisted code assignment.
##########
core/src/pq.rs:
##########
@@ -370,6 +386,87 @@ impl ProductQuantizer {
);
}
+ /// Blocked batch encode for the IVF-PQ add path.
+ ///
+ /// The nbits=8 path uses a transposed-codebook kernel: per sub-quantizer
+ /// the centroids are transposed once to `[dsub][ksub]` so the inner
+ /// distance loop is stride-1 over `ksub` and runs on SIMD (NEON/AVX2,
+ /// scalar fallback). This removes the per-vector-per-sub GEMM calls and
+ /// their distance-table memory traffic. Distances are accumulated directly
+ /// from coordinate differences, avoiding the cancellation possible in the
+ /// norm/dot identity used by [`Self::encode_batch`]. The different
arithmetic
+ /// can produce different valid codes, so use this only where codes are
freshly
+ /// produced (index build), not where byte-stable output is pinned. Trained
+ /// codebooks are expected to contain only finite values.
+ pub(crate) fn encode_batch_blocked(&self, data: &[f32], n: usize, codes:
&mut [u8]) {
+ // The 4-bit packed path keeps the original per-vector implementation.
+ if self.nbits == 8 && (0..self.m).all(|sub| self.chunk_dim(sub) >= 4) {
+ self.encode_batch_8bit_transposed(data, n, codes);
Review Comment:
**[Major x86_64 fallback regression]** This now transposes the full codebook
for every eligible add, even when runtime dispatch selects the scalar scorer.
For `d=768,m=192`, that is about 0.75 MiB of allocation/writes before
processing a single row.
On a supported x86_64 runtime without AVX2/FMA, versus `314c6bf`, I measured
approximately +39%/+46%/+37%/+45% for rows 1/7/8/31; rows=32 was effectively
unchanged, isolating the fixed transpose cost.
Please restore a small-batch direct path when `score_argmin_kernel` resolves
to scalar, use a backend-specific threshold, or cache the transposed codebook
after training.
##########
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]
