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


##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -129,21 +161,242 @@ 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 norm_product = query_norm * stored_squared_norm.sqrt();
+    let absolute_dot_bound = match output {
+        CosineOutput::Similarity => absolute_dot,
+        CosineOutput::Distance => norm_product,
+    };
+    output.round_from_dot(
+        CosineDot::Approximate {
+            value: dot,
+            absolute_sum_bound: absolute_dot_bound,
+        },
+        norm_product,
+        query,
+        stored,
+        &mut Vec::new(),
+    )
+}
+
+pub(crate) enum CosineDot {
+    Exact(f64),
+    Approximate { value: f64, absolute_sum_bound: f64 },
+}
+
+#[derive(Clone, Copy)]
+pub(crate) enum CosineOutput {
+    Similarity,
+    Distance,
+}
+
+impl CosineOutput {
+    fn value(self, similarity: f64) -> f64 {
+        match self {
+            Self::Similarity => similarity,
+            Self::Distance => 1.0 - similarity,

Review Comment:
   **Near-duplicate PK candidates trigger the arbitrary-precision fallback on 
every row.** I used a 256-dimensional all-ones query and 4,096 rows that each 
change one coordinate by `k * 2^-12`, with `k` ranging from 1 to 13. 
Subtracting the similarity from one makes the error interval span many 
representable distances. In an optimized arm64 run the base scorer took **0.51 
ms** and this scorer took **12.70 ms**.
   
   On the same inputs, half the squared Euclidean distance between the two 
unit-normalized vectors took **1.04 ms** and matched the independently 
calculated `f32` distance for every row. Please use a bounded version of that 
formula for near-parallel pairs and reserve the exact midpoint search for 
distances whose rounding is still ambiguous.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2773,155 @@ 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)
-                    }
-                }
-                RawVectorMetric::Cosine => {
-                    let denominator = stored_l2_squared_norm.sqrt() * 
query_l2_squared_norm.sqrt();
-                    if denominator == 0.0 {
-                        0.0
+            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 mut dots = vec![0.0; raw_score_matrix_size(row_count, query_count)?];
+    if dots.is_empty() {
+        return Ok(Vec::new());
+    }
+
+    // A single double-precision multiply keeps candidates comparable across
+    // coordinate scales. Queries index rows of the output, stored vectors 
columns.
+    // SAFETY: Each dimension is derived from the backing slices, so the input
+    // strides stay within the respective buffers and the output strides are
+    // disjoint within the checked query_count * row_count allocation.
+    unsafe {
+        matrixmultiply::dgemm(
+            query_count,
+            dimension,
+            row_count,
+            1.0,
+            query_vectors.as_ptr(),
+            dimension as isize,
+            1,
+            stored_vectors.as_ptr(),
+            1,
+            dimension as isize,
+            0.0,
+            dots.as_mut_ptr(),
+            row_count as isize,
+            1,
+        );
+    }
+
+    let mut scores = Vec::with_capacity(dots.len());
+    let mut partials = 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 dot = if query_at_most_one_nonzero || 
stored_norm.at_most_one_nonzero {
+                CosineDot::Exact(dot)
+            } else {
+                CosineDot::Approximate {
+                    value: dot,
+                    absolute_sum_bound: if !query_mixed_signs && 
!stored_norm.mixed_signs {
+                        dot.abs()
                     } else {
-                        *score / denominator
-                    }
+                        norm_product

Review Comment:
   **Fully dense inputs can make batched cosine slower than scoring the queries 
individually.** I used 32 queries, 1,024 rows and 256 dimensions. With `e = 
2^-22`, each query has ones in the first half (one entry is `2`) and `e` in the 
second half. Each row has `e` in the first half and equal numbers of `+1` and 
`-1` in the second. The norm product is about `129.5`, but the sum of absolute 
products is only `257 * e`. All 32,768 pairs enter `round_exact`.
   
   On arm64 the optimized matrix scorer took **60.5 ms**, compared with **4.4 
ms** for this PR's scalar scorer. A second DGEMM on absolute coordinates gave a 
tighter bound and produced the same score bits in **0.84 ms** for the whole 
matrix. Please tighten the mixed-sign bound before recomputing all three exact 
sums.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -244,23 +497,114 @@ mod tests {
         assert_eq!(VectorSearchMetric::Cosine.compute_distance(&zero, &s), 
1.0);
     }
 
+    #[test]
+    fn test_cosine_zero_preserves_nonfinite_scores() {
+        assert_eq!(cosine_similarity(&[0.0, 0.0], 0.0, &[1.0, 2.0]), 0.0);
+        assert!(cosine_similarity(&[0.0, 0.0], 0.0, &[f32::INFINITY, 
0.0]).is_nan());
+    }
+
+    #[test]
+    fn test_cosine_exact_distance_is_invariant_to_vector_scale() {
+        for scale in [1.0e20_f32, 1.0e-23_f32] {
+            let query = [scale, 0.0];
+            assert_eq!(
+                VectorSearchMetric::Cosine.compute_distance(&query, &query),
+                0.0
+            );
+            assert_eq!(
+                VectorSearchMetric::Cosine.compute_distance(&query, &[-scale, 
0.0]),
+                2.0
+            );
+        }
+    }
+
+    #[test]
+    fn test_cosine_distance_orders_near_parallel_with_underflowing_squares() {
+        let scale = 2.0_f32.powi(-63);
+        let mut query = [0.0; 257];
+        query[256] = scale;
+        let mut nearly_parallel = [scale * 2.0_f32.powi(-12); 257];
+        nearly_parallel[256] = scale;
+
+        let metric = VectorSearchMetric::Cosine;
+        assert_eq!(metric.compute_distance(&query, &query), 0.0);
+        assert!(metric.compute_distance(&query, &nearly_parallel) > 0.0);
+    }
+
+    #[test]
+    fn test_cosine_distance_orders_near_orthogonal_with_underflowing_dot() {
+        let similarity = 2.0_f32.powi(-24);
+        let metric = VectorSearchMetric::Cosine;
+        for scale in [1.0, 2.0_f32.powi(-63)] {
+            let query = [scale, 0.0];
+            let orthogonal = [0.0, scale];
+            let nearly_orthogonal = [scale * similarity, scale];
+            assert_eq!(metric.compute_distance(&query, &orthogonal), 1.0);
+            assert_eq!(
+                metric.compute_distance(&query, &nearly_orthogonal),
+                1.0 - similarity
+            );
+        }
+    }
+
+    #[test]
+    fn test_cosine_distance_orders_mixed_scale_candidates() {
+        let query = [3.0, 13.0];
+        let exact = [895.0 * query[0], 895.0 * query[1]];
+        let metric = VectorSearchMetric::Cosine;
+        // The squared norm product exceeds the squared dot by one:
+        // (3 * 173 - 13 * 40)^2 == 1.
+        let denominator = (178.0_f64 * 31_529.0).sqrt();
+        let expected_distance = (1.0 / (denominator * (denominator + 2369.0))) 
as f32;
+        for scale in [1.0, 2.0_f32.powi(64)] {
+            let nearby = [40.0 * scale, 173.0 * scale];
+            let nearby_distance = metric.compute_distance(&query, &nearby);
+            assert_eq!(nearby_distance, expected_distance);
+            assert_eq!(metric.compute_distance(&query, &exact), 0.0);
+        }
+    }
+
+    #[test]
+    fn test_cosine_distance_preserves_angle_below_f64_similarity_precision() {
+        let tiny = 2.0_f32.powi(-50);
+        let distance = VectorSearchMetric::Cosine.compute_distance(&[1.0, 
0.0], &[1.0, tiny]);
+        assert_eq!(distance, 2.0_f32.powi(-101));
+    }
+
+    #[test]
+    fn test_cosine_similarity_rounds_signed_subnormal_midpoints_to_even() {
+        let tiny = 2.0_f32.powi(-75);
+        let mut query = vec![tiny];
+        let mut stored = vec![tiny];
+        // Pad each squared norm to exactly one using disjoint coordinates.
+        // The only shared product is 2^-150, the first f32 rounding midpoint.
+        for i in 1..=75 {
+            let value = 2.0_f32.powi(-i);
+            query.extend([value, value, value, 0.0, 0.0, 0.0]);
+            stored.extend([0.0, 0.0, 0.0, value, value, value]);
+        }
+        let norm = cosine_norm(&query);
+        assert_eq!(
+            cosine_similarity(&query, norm, &stored).to_bits(),
+            0.0_f32.to_bits()
+        );
+        stored[0] = -tiny;
+        assert_eq!(
+            cosine_similarity(&query, norm, &stored).to_bits(),
+            (-0.0_f32).to_bits()
+        );
+    }
+
     #[test]
     fn test_cosine_non_perfect_square_norm_uses_f64_sqrt() {
-        // query [0,3] -> norm 9, stored [1,2] -> norm 5; sqrt(5) is irrational
-        // so the f32-sqrt path (each sqrt taken in f32, then widened) and the
-        // f64-sqrt path (widen first, sqrt in f64) produce different f32 bits:
-        // buggy similarity 0.8944271 vs correct 0.8944272. Encode the f64 
contract
-        // in the expected value (dot / (sqrt(9.0f64) * sqrt(5.0f64)) as f32) 
rather
-        // than a magic literal, so this pins the Java-matching f64 
arithmetic. The
-        // cosine distance is `1 - similarity`, so the sqrt path is exercised 
here.
+        // Taking the square roots in f32 can already lose a bit of the score.
         let q = [0.0f32, 3.0];
         let s = [1.0f32, 2.0];
-        let dot = 6.0f32;
-        let denominator = ((9.0f64).sqrt() * (5.0f64).sqrt()) as f32;
-        let expected_similarity = dot / denominator;
+        let denominator = (9.0_f64).sqrt() * (5.0_f64).sqrt();
+        let expected_distance = (1.0 - 6.0 / denominator) as f32;

Review Comment:
   **The new expectation changes Java compatibility for ordinary finite 
vectors, including which row wins PK Top-1.** For the inputs in this test, Java 
returns distance bits `0x3dd83690` and Rust now returns `0x3dd8368f`. With the 
same query `[0, 3]` and candidates `[1, f32::from_bits(0x3ffffffd)]` and `[1, 
f32::from_bits(0x3ffffffe)]`, Java gives the first row the smaller distance and 
Rust gives it to the second. Rust agrees with the mathematical ordering. Please 
document this cross-engine difference in the vector-search reference and 
qualify the module's “Mirrors Java” claim. [Java reference 
implementation](https://github.com/apache/paimon/blob/68dddca6ba335b17bbf8febb6444a121dcd8dcce/paimon-core/src/main/java/org/apache/paimon/globalindex/VectorSearchMetric.java#L87-L115)



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