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


##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -120,6 +129,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_distance(cosine_similarity(self.query, 
self.cosine_norm, stored))

Review Comment:
   **Rounding the similarity before subtracting from one discards a 
representable PK distance.** With query `[3, 4]`, put `[3.0015, 4]` at position 
0 and the exact match at position 1. The base commit gives distances 
`5.9604645e-8` and `0.0` and selects position 1. This code gives both rows 
distance `0.0`, so exact Top-1 returns position 0. The near row's cosine 
distance is approximately `2.8785461e-8`, which fits in `f32`. Please carry the 
`f64` similarity through the PK distance subtraction and narrow the resulting 
distance. This pair with the exact match last would make a regression test.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2775,134 @@ 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,
+}
+
+impl DenseCosineNorm {
+    fn new(vector: &[f64]) -> Self {
+        Self {
+            length: cosine_norm(vector),
+            mixed_signs: has_mixed_signs(vector),
+        }
+    }
+}
+
+fn has_mixed_signs(vector: &[f64]) -> bool {
+    vector.iter().any(|&value| value < 0.0) && vector.iter().any(|&value| 
value > 0.0)
+}
+
+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);
+        for ((stored, stored_norm), &dot) in stored_vectors
+            .chunks_exact(dimension)
+            .zip(stored_norms)
+            .zip(query_dots)
+        {
+            scores.push(cosine_similarity_from_dot(
+                dot,
+                query_norm * stored_norm.length,
+                dimension,
+                || {
+                    // Products of two single-sign vectors cannot cancel.
+                    if query_mixed_signs || stored_norm.mixed_signs {
+                        compensated_dot(query, stored, &mut partials)
                     } else {
-                        *score / denominator
+                        dot

Review Comment:
   **The same query returns a different first row once there are four queries 
in the batch.** I reproduced this with nonnegative coordinates.
   
   ```text
   L = 2^32, a = 2^-12, b = 2^-27
   query   [L, 0, 1, a, b, b, b, b]
   row 10  [0, L, 1, a, 0, 0, 0, 0]
   row 11  [0, L, 1, a, b, b, b, b]
   ```
   
   The scalar scorer puts row 11 first. DGEMM loses the four `b*b` terms, this 
branch accepts the resulting tie, and the matrix scorer puts row 10 first. The 
two cosines round to distinct `f32` values. Please account for same-sign 
summation error near a rounding midpoint and cover both query counts.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2775,134 @@ 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,
+}
+
+impl DenseCosineNorm {
+    fn new(vector: &[f64]) -> Self {
+        Self {
+            length: cosine_norm(vector),
+            mixed_signs: has_mixed_signs(vector),
+        }
+    }
+}
+
+fn has_mixed_signs(vector: &[f64]) -> bool {
+    vector.iter().any(|&value| value < 0.0) && vector.iter().any(|&value| 
value > 0.0)
+}
+
+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);
+        for ((stored, stored_norm), &dot) in stored_vectors
+            .chunks_exact(dimension)
+            .zip(stored_norms)
+            .zip(query_dots)
+        {
+            scores.push(cosine_similarity_from_dot(
+                dot,
+                query_norm * stored_norm.length,
+                dimension,
+                || {
+                    // Products of two single-sign vectors cannot cancel.
+                    if query_mixed_signs || stored_norm.mixed_signs {

Review Comment:
   **A one-hot query triggers a full compensated rescan even though its dot 
product has only one nonzero term.** I used 32 distinct unit-basis queries and 
1,024 rows of dimension 256. Each row has `2^-20` in the 32 queried positions, 
`+1` and `-1` in two other positions, and zeros elsewhere. The stored vectors 
have mixed signs, so all 32,768 pairs enter `compensated_dot`. The optimized 
arm64 matrix scorer took about `13.1 ms` on this head and `0.28 ms` on the base 
commit. Checking once per query for at most one nonzero coordinate brought this 
head to `0.69 ms` with identical scores. Please reuse the DGEMM dot for those 
queries.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -129,21 +157,90 @@ 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>()

Review Comment:
   **Reversing the coordinates changes raw Top-1 through the norm alone.** Use 
a 66-dimensional query `[1, 0, …, 0]`, row 11 equal to the query, and row 10 
`[1, 2^-12, 2^-27, …, 2^-27]` with 64 trailing `2^-27` coordinates. Both dot 
products are exactly `1`. Adding each `2^-54` square after the leading `1` 
loses all 64 contributions. Scalar and matrix scoring then give row 10 score 
`1.0` and put it first. Reversing all three vectors makes both return row 11 
and score row 10 `0.99999994`, its correctly rounded cosine. Please preserve 
the small squares in both this sum and the scalar stored-norm loop, and test 
both orderings.



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