SteNicholas commented on code in PR #1486:
URL: https://github.com/apache/paimon-rust/pull/1486#discussion_r4657247610


##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -120,6 +135,25 @@ impl VectorSearchMetric {
     }
 }
 
+pub(crate) struct PreparedVectorQuery<'a> {
+    metric: VectorSearchMetric,
+    query: &'a [f32],
+    cosine_norm: f64,
+}
+
+impl PreparedVectorQuery<'_> {
+    /// Lower-is-better distance for exact vector search.
+    pub(crate) fn compute_distance(&self, stored: &[f32]) -> f32 {
+        match self.metric {
+            VectorSearchMetric::L2 => squared_l2(self.query, stored),
+            VectorSearchMetric::Cosine => {
+                cosine_score(self.query, self.cosine_norm, stored, 
CosineOutput::Distance)

Review Comment:
   **Increasing a PK hybrid vector route's candidate limit changes Top-1 from 
the exact match to a worse row.** I reproduced this with a single RRF route, 
final limit `1`, refine factor `2`, and query `[3, 4, 0, 0]`. Position 0 holds 
`[3.0015, 4, 0, 0]` and position 1 holds the query itself. With a route limit 
of `1`, the exact match wins. At `2`, the vector route still returns positions 
`[1, 0]`, but `distance_to_score` maps both distances to `1.0f32`. RRF gives 
them the same rank and returns position 0 by its physical tie-break. On the 
base commit, position 1 wins at both route limits.
   
   Please carry the canonical distance or its rank and tie information into 
rank-based fusion. An end-to-end check with both route limits would cover the 
loss after the exact scorer returns.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -129,21 +163,279 @@ fn squared_l2(query: &[f32], stored: &[f32]) -> f32 {
     squared
 }
 
-fn cosine_similarity(query: &[f32], stored: &[f32]) -> f32 {
-    let mut dot = 0.0f32;
-    let mut query_norm = 0.0f32;
-    let mut stored_norm = 0.0f32;
-    for i in 0..query.len() {
-        dot += query[i] * stored[i];
-        query_norm += query[i] * query[i];
-        stored_norm += stored[i] * stored[i];
+pub(crate) fn cosine_norm<T: Copy + Into<f64>>(vector: &[T]) -> f64 {
+    vector
+        .iter()
+        .map(|&value| {
+            let value = value.into();
+            value * value
+        })
+        .sum::<f64>()
+        .sqrt()
+}
+
+pub(crate) fn cosine_similarity(query: &[f32], query_norm: f64, stored: 
&[f32]) -> f32 {
+    cosine_score(query, query_norm, stored, CosineOutput::Similarity)
+}
+
+#[inline]
+fn cosine_score(query: &[f32], query_norm: f64, stored: &[f32], output: 
CosineOutput) -> f32 {
+    let mut dot = 0.0_f64;
+    let mut absolute_dot = 0.0_f64;
+    let mut stored_squared_norm = 0.0_f64;
+    for (&query, &stored) in query.iter().zip(stored) {
+        let q = f64::from(query);
+        let s = f64::from(stored);
+        let product = q * s;
+        dot += product;
+        if matches!(output, CosineOutput::Similarity) {
+            absolute_dot += product.abs();
+        }
+        stored_squared_norm += s * s;
     }
-    let denominator = ((query_norm as f64).sqrt() * (stored_norm as 
f64).sqrt()) as f32;
-    if denominator == 0.0 {
-        0.0
-    } else {
-        dot / denominator
+    let stored_norm = stored_squared_norm.sqrt();
+    let norm_product = query_norm * stored_norm;
+    let absolute_dot_bound = match output {
+        CosineOutput::Similarity => absolute_dot,
+        CosineOutput::Distance => norm_product,
+    };
+    let dot = CosineDot::Approximate {
+        value: dot,
+        absolute_sum_bound: absolute_dot_bound,
+    };
+    let mut bounds = match output.try_round_from_dot(dot, norm_product, 
query.len()) {
+        Ok(rounded) => return rounded,
+        Err(bounds) => bounds,
+    };
+    if matches!(output, CosineOutput::Distance) && bounds.1 <= 0.5 {
+        if query == stored {

Review Comment:
   **Positive rescalings of the query still take the arbitrary-precision path 
for every PK candidate.** For a 256-coordinate query with `q[i] = (31 * i % 27) 
- 13`, I scored 4,096 rows cycling through `2*q` to `17*q`. Every distance is 
exactly zero. The optimized arm64 scorer took about 7.0 ms on this commit and 
0.61 ms on the base.
   
   A proportionality check inside this fallback brought the same scan to 1.09 
ms with identical distance bits. A nonzero pivot lets the scorer check `q[i] * 
s[pivot] == s[i] * q[pivot]` exactly in `f64` for `f32` coordinates and return 
zero when the scale is positive.



##########
docs/src/sql.md:
##########
@@ -3067,6 +3067,14 @@ Larger refine factors may improve recall and ordering 
quality, but they also
 increase index result merging, raw-vector reads, and exact scoring work. Use 
the
 smallest factor that provides the desired recall.
 
+### Exact Cosine Distance on Primary-Key Tables
+
+Rust's exact scans and reranking on primary-key tables round the cosine 
distance

Review Comment:
   **Data Evolution exact Top-K can also differ between Java and Rust, before 
any distance subtraction.** For query `[4096, 1, 4096, 0]`, the Java scorer 
returns `0` for `[4096, 1, -4096, 0]` and `1.0536712e-8` for `[0, 0.25, 0, 
4096]`. Both Rust paths score the first row `2.9802322e-8` and the second 
`1.0536712e-8`, so the two engines select different winners. Please extend this 
compatibility note to raw scans and reranking on Data Evolution tables and 
mention the difference in dot-product accumulation.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2773,205 @@ fn compute_raw_vector_score_matrix(
         return Ok(scores);
     }
 
-    let stored_l2_squared_norms = stored_vectors
-        .chunks_exact(dimension)
-        .map(|vector| vector.iter().map(|value| value * value).sum::<f32>())
-        .collect::<Vec<_>>();
+    debug_assert_eq!(metric, RawVectorMetric::L2);
+    let stored_norms = 
RawVectorNorms::new(stored_vectors.chunks_exact(dimension), metric);
     for (matrix_query_index, &query_index) in query_indices.iter().enumerate() 
{
-        for (row_index, &stored_l2_squared_norm) in 
stored_l2_squared_norms.iter().enumerate() {
+        let query_l2_squared_norm = query_norms.l2_squared[query_index];
+        for (row_index, &stored_l2_squared_norm) in 
stored_norms.l2_squared.iter().enumerate() {
             let score = &mut scores[matrix_query_index * row_count + 
row_index];
-            let query_l2_squared_norm = query_l2_squared_norms[query_index];
-            *score = match metric {
-                RawVectorMetric::L2 => {
-                    let squared_distance =
-                        stored_l2_squared_norm + query_l2_squared_norm - 2.0 * 
*score;
-                    // The norm/dot reconstruction loses the low-order 
difference when two
-                    // large vectors are close. Estimate a conservative 
accumulation-error
-                    // bound and preserve the former scalar semantics inside 
that region.
-                    let roundoff_bound = (stored_l2_squared_norm.abs()
-                        + query_l2_squared_norm.abs()
-                        + 2.0 * score.abs())
-                        * f32::EPSILON
-                        * (dimension as f32 + 2.0)
-                        * 4.0;
-                    if !squared_distance.is_finite() || squared_distance <= 
roundoff_bound {
-                        let stored =
-                            &stored_vectors[row_index * dimension..(row_index 
+ 1) * dimension];
-                        let query = &query_vectors
-                            [matrix_query_index * 
dimension..(matrix_query_index + 1) * dimension];
-                        compute_raw_vector_l2_score(query, stored)
-                    } else {
-                        1.0 / (1.0 + squared_distance)
-                    }
+            let squared_distance = stored_l2_squared_norm + 
query_l2_squared_norm - 2.0 * *score;
+            // The norm/dot reconstruction loses the low-order difference when 
two
+            // large vectors are close. Estimate a conservative 
accumulation-error
+            // bound and preserve the former scalar semantics inside that 
region.
+            let roundoff_bound =
+                (stored_l2_squared_norm.abs() + query_l2_squared_norm.abs() + 
2.0 * score.abs())
+                    * f32::EPSILON
+                    * (dimension as f32 + 2.0)
+                    * 4.0;
+            *score = if !squared_distance.is_finite() || squared_distance <= 
roundoff_bound {
+                let stored = &stored_vectors[row_index * dimension..(row_index 
+ 1) * dimension];
+                let query = &query_vectors
+                    [matrix_query_index * dimension..(matrix_query_index + 1) 
* dimension];
+                compute_raw_vector_l2_score(query, stored)
+            } else {
+                1.0 / (1.0 + squared_distance)
+            };
+        }
+    }
+    Ok(scores)
+}
+
+struct DenseCosineNorm {
+    length: f64,
+    mixed_signs: bool,
+    at_most_one_nonzero: bool,
+}
+
+impl DenseCosineNorm {
+    fn new(vector: &[f64]) -> Self {
+        Self {
+            length: cosine_norm(vector),
+            mixed_signs: has_mixed_signs(vector),
+            at_most_one_nonzero: has_at_most_one_nonzero(vector),
+        }
+    }
+}
+
+fn has_mixed_signs(vector: &[f64]) -> bool {
+    vector.iter().any(|&value| value < 0.0) && vector.iter().any(|&value| 
value > 0.0)
+}
+
+fn has_at_most_one_nonzero(vector: &[f64]) -> bool {
+    vector
+        .iter()
+        .filter(|&&value| value != 0.0)
+        .nth(1)
+        .is_none()
+}
+
+fn compute_raw_cosine_score_matrix(
+    stored_vectors: &[f64],
+    stored_norms: &[DenseCosineNorm],
+    query_vectors: &[f64],
+    query_norms: &[f64],
+    query_indices: &[usize],
+    dimension: usize,
+) -> crate::Result<Vec<f32>> {
+    let row_count = stored_vectors.len() / dimension;
+    let query_count = query_vectors.len() / dimension;
+    debug_assert_eq!(stored_norms.len(), row_count);
+    debug_assert_eq!(query_indices.len(), query_count);
+    let dots = compute_raw_cosine_dot_matrix(query_vectors, stored_vectors, 
dimension)?;
+    if dots.is_empty() {
+        return Ok(Vec::new());
+    }
+
+    let similarity = CosineOutput::Similarity;
+    let mut scores = Vec::with_capacity(dots.len());
+    let mut partials = Vec::new();
+    let mut needs_tighter_bound = Vec::new();
+    for ((query, &query_index), query_dots) in query_vectors
+        .chunks_exact(dimension)
+        .zip(query_indices)
+        .zip(dots.chunks_exact(row_count))
+    {
+        let query_norm = query_norms[query_index];
+        let query_mixed_signs = has_mixed_signs(query);
+        let query_at_most_one_nonzero = has_at_most_one_nonzero(query);
+        for ((stored, stored_norm), &dot) in stored_vectors
+            .chunks_exact(dimension)
+            .zip(stored_norms)
+            .zip(query_dots)
+        {
+            let norm_product = query_norm * stored_norm.length;
+            // A single product is exact. For multiple products with uniform
+            // signs, estimate their absolute sum from the dot. Otherwise use
+            // the norm product (Cauchy-Schwarz).
+            let exact = query_at_most_one_nonzero || 
stored_norm.at_most_one_nonzero;

Review Comment:
   **Dense orthogonal sign vectors trigger a coordinate rescan for every 
query/row pair.** I used 32 query rows of a 256-dimensional Walsh–Hadamard 
matrix and 1,024 stored rows drawn from its other rows. Every coordinate is 
`+1` or `-1`, so DGEMM computes all 32,768 zero dots exactly. The 
absolute-product pass returns `256` for each pair and every pair still reaches 
`exact_dot`.
   
   The optimized arm64 matrix scorer took 11.7 ms here and 0.28 ms on the base. 
Certifying integer dots once per vector pair from precomputed maxima and 
`dimension * max_abs_q * max_abs_s < 2^53` reduced this to 0.73 ms with 
identical score bits. Please reuse the DGEMM result when the inputs satisfy an 
exactness bound like this.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2773,205 @@ fn compute_raw_vector_score_matrix(
         return Ok(scores);
     }
 
-    let stored_l2_squared_norms = stored_vectors
-        .chunks_exact(dimension)
-        .map(|vector| vector.iter().map(|value| value * value).sum::<f32>())
-        .collect::<Vec<_>>();
+    debug_assert_eq!(metric, RawVectorMetric::L2);
+    let stored_norms = 
RawVectorNorms::new(stored_vectors.chunks_exact(dimension), metric);
     for (matrix_query_index, &query_index) in query_indices.iter().enumerate() 
{
-        for (row_index, &stored_l2_squared_norm) in 
stored_l2_squared_norms.iter().enumerate() {
+        let query_l2_squared_norm = query_norms.l2_squared[query_index];
+        for (row_index, &stored_l2_squared_norm) in 
stored_norms.l2_squared.iter().enumerate() {
             let score = &mut scores[matrix_query_index * row_count + 
row_index];
-            let query_l2_squared_norm = query_l2_squared_norms[query_index];
-            *score = match metric {
-                RawVectorMetric::L2 => {
-                    let squared_distance =
-                        stored_l2_squared_norm + query_l2_squared_norm - 2.0 * 
*score;
-                    // The norm/dot reconstruction loses the low-order 
difference when two
-                    // large vectors are close. Estimate a conservative 
accumulation-error
-                    // bound and preserve the former scalar semantics inside 
that region.
-                    let roundoff_bound = (stored_l2_squared_norm.abs()
-                        + query_l2_squared_norm.abs()
-                        + 2.0 * score.abs())
-                        * f32::EPSILON
-                        * (dimension as f32 + 2.0)
-                        * 4.0;
-                    if !squared_distance.is_finite() || squared_distance <= 
roundoff_bound {
-                        let stored =
-                            &stored_vectors[row_index * dimension..(row_index 
+ 1) * dimension];
-                        let query = &query_vectors
-                            [matrix_query_index * 
dimension..(matrix_query_index + 1) * dimension];
-                        compute_raw_vector_l2_score(query, stored)
-                    } else {
-                        1.0 / (1.0 + squared_distance)
-                    }
+            let squared_distance = stored_l2_squared_norm + 
query_l2_squared_norm - 2.0 * *score;
+            // The norm/dot reconstruction loses the low-order difference when 
two
+            // large vectors are close. Estimate a conservative 
accumulation-error
+            // bound and preserve the former scalar semantics inside that 
region.
+            let roundoff_bound =
+                (stored_l2_squared_norm.abs() + query_l2_squared_norm.abs() + 
2.0 * score.abs())
+                    * f32::EPSILON
+                    * (dimension as f32 + 2.0)
+                    * 4.0;
+            *score = if !squared_distance.is_finite() || squared_distance <= 
roundoff_bound {
+                let stored = &stored_vectors[row_index * dimension..(row_index 
+ 1) * dimension];
+                let query = &query_vectors
+                    [matrix_query_index * dimension..(matrix_query_index + 1) 
* dimension];
+                compute_raw_vector_l2_score(query, stored)
+            } else {
+                1.0 / (1.0 + squared_distance)
+            };
+        }
+    }
+    Ok(scores)
+}
+
+struct DenseCosineNorm {
+    length: f64,
+    mixed_signs: bool,
+    at_most_one_nonzero: bool,
+}
+
+impl DenseCosineNorm {
+    fn new(vector: &[f64]) -> Self {
+        Self {
+            length: cosine_norm(vector),
+            mixed_signs: has_mixed_signs(vector),
+            at_most_one_nonzero: has_at_most_one_nonzero(vector),
+        }
+    }
+}
+
+fn has_mixed_signs(vector: &[f64]) -> bool {
+    vector.iter().any(|&value| value < 0.0) && vector.iter().any(|&value| 
value > 0.0)
+}
+
+fn has_at_most_one_nonzero(vector: &[f64]) -> bool {
+    vector
+        .iter()
+        .filter(|&&value| value != 0.0)
+        .nth(1)
+        .is_none()
+}
+
+fn compute_raw_cosine_score_matrix(
+    stored_vectors: &[f64],
+    stored_norms: &[DenseCosineNorm],
+    query_vectors: &[f64],
+    query_norms: &[f64],
+    query_indices: &[usize],
+    dimension: usize,
+) -> crate::Result<Vec<f32>> {
+    let row_count = stored_vectors.len() / dimension;
+    let query_count = query_vectors.len() / dimension;
+    debug_assert_eq!(stored_norms.len(), row_count);
+    debug_assert_eq!(query_indices.len(), query_count);
+    let dots = compute_raw_cosine_dot_matrix(query_vectors, stored_vectors, 
dimension)?;
+    if dots.is_empty() {
+        return Ok(Vec::new());
+    }
+
+    let similarity = CosineOutput::Similarity;
+    let mut scores = Vec::with_capacity(dots.len());
+    let mut partials = Vec::new();
+    let mut needs_tighter_bound = Vec::new();
+    for ((query, &query_index), query_dots) in query_vectors
+        .chunks_exact(dimension)
+        .zip(query_indices)
+        .zip(dots.chunks_exact(row_count))
+    {
+        let query_norm = query_norms[query_index];
+        let query_mixed_signs = has_mixed_signs(query);
+        let query_at_most_one_nonzero = has_at_most_one_nonzero(query);
+        for ((stored, stored_norm), &dot) in stored_vectors
+            .chunks_exact(dimension)
+            .zip(stored_norms)
+            .zip(query_dots)
+        {
+            let norm_product = query_norm * stored_norm.length;
+            // A single product is exact. For multiple products with uniform
+            // signs, estimate their absolute sum from the dot. Otherwise use
+            // the norm product (Cauchy-Schwarz).
+            let exact = query_at_most_one_nonzero || 
stored_norm.at_most_one_nonzero;
+            let may_cancel = !exact && (query_mixed_signs || 
stored_norm.mixed_signs);
+            let dot = if exact {
+                CosineDot::Exact(dot)
+            } else {
+                CosineDot::Approximate {
+                    value: dot,
+                    absolute_sum_bound: if may_cancel { norm_product } else { 
dot.abs() },
                 }
-                RawVectorMetric::Cosine => {
-                    let denominator = stored_l2_squared_norm.sqrt() * 
query_l2_squared_norm.sqrt();
-                    if denominator == 0.0 {
-                        0.0
-                    } else {
-                        *score / denominator
-                    }
+            };
+            let score = match similarity.try_round_from_dot(dot, norm_product, 
dimension) {
+                Ok(score) => score,
+                Err(_) if may_cancel => {
+                    needs_tighter_bound.push(scores.len());
+                    0.0
                 }
-                RawVectorMetric::InnerProduct => unreachable!(),
+                Err(bounds) => similarity.round_exact(dot, query, stored, 
bounds, &mut partials),
             };
+            scores.push(score);
         }
     }
+
+    // Refine a few uncertain pairs directly. A second multiply amortizes the
+    // coordinate scans when many mixed-sign pairs need the absolute-product 
sum.
+    let absolute_dots = if needs_tighter_bound.len() >= 
dots.len().div_ceil(8).max(32) {
+        let absolute_queries: Vec<_> = query_vectors.iter().map(|value| 
value.abs()).collect();
+        let absolute_rows: Vec<_> = stored_vectors.iter().map(|value| 
value.abs()).collect();

Review Comment:
   **The refinement pass duplicates the entire stored-vector matrix regardless 
of the score chunk size.** Four queries against 8,192 rows of dimension 1,536 
produce a 256 KiB dot matrix, but `absolute_rows` alone allocates another 96 
MiB. With mixed-sign vectors on disjoint coordinate ranges, peak RSS for the 
isolated scorer was 197 MiB. Running the same scorer in blocks of 256 stored 
rows returned identical scores and peaked at 103 MiB.
   
   Please bound the stored-row block used for absolute-product refinement so 
concurrent raw scans do not each need a second full-size copy.



-- 
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]

Reply via email to