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


##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -131,18 +131,89 @@ fn squared_l2(query: &[f32], stored: &[f32]) -> f32 {
 
 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;
+    let mut query_norm = CosineNorm::default();
+    let mut stored_norm = CosineNorm::default();
     for i in 0..query.len() {
         dot += query[i] * stored[i];
-        query_norm += query[i] * query[i];
-        stored_norm += stored[i] * stored[i];
+        query_norm.add(query[i]);
+        stored_norm.add(stored[i]);
     }
-    let denominator = ((query_norm as f64).sqrt() * (stored_norm as 
f64).sqrt()) as f32;
+    query_norm
+        .try_score(stored_norm, dot, |query, stored| {
+            ((query as f64).sqrt() * (stored as f64).sqrt()) as f32
+        })
+        .unwrap_or_else(|| cosine_similarity_wide(query, stored))
+}
+
+#[derive(Clone, Copy, Default)]
+pub(crate) struct CosineNorm {
+    squared: f32,
+    has_small_square: bool,
+    has_non_finite: bool,
+}
+
+impl CosineNorm {
+    pub(crate) fn from_vector(vector: &[f32]) -> Self {
+        let mut norm = Self::default();
+        for &value in vector {
+            norm.add(value);
+        }
+        norm
+    }
+
+    pub(crate) fn add(&mut self, value: f32) {
+        let square = value * value;
+        self.squared += square;
+        self.has_non_finite |= !value.is_finite();
+        // A normal total can hide underflow in a coordinate square or its dot 
product term.
+        self.has_small_square |= value != 0.0 && square < f32::MIN_POSITIVE;
+    }
+
+    fn is_zero(self) -> bool {
+        self.squared == 0.0 && !self.has_small_square
+    }
+
+    pub(crate) fn try_score(
+        self,
+        stored: Self,
+        dot: f32,
+        denominator: impl FnOnce(f32, f32) -> f32,
+    ) -> Option<f32> {
+        if (self.is_zero() && !stored.has_non_finite) || (stored.is_zero() && 
!self.has_non_finite)
+        {
+            return Some(0.0);
+        }
+        if self.has_small_square
+            || stored.has_small_square
+            || !self.squared.is_normal()
+            || !stored.squared.is_normal()
+            || !dot.is_finite()
+            || dot.is_subnormal()
+        {
+            return None;
+        }
+        let denominator = denominator(self.squared, stored.squared);
+        denominator.is_normal().then(|| dot / denominator)

Review Comment:
   **Rescaling one candidate makes it outrank an exactly parallel vector.** Let 
`q = [3, 13]`, row 10 be `895 * q`, and row 11 be `[40, 173]`. Multiplying only 
row 11 by `2^64` moves it onto the wide path. Row 10 scores `0.99999988` here 
and row 11 scores `0.99999994`. Their true cosines rounded to `f32` are `1.0` 
and `0.99999994`. I get row 10 before scaling and row 11 afterward with both 
one and four raw queries. PK distance also puts row 11 first. Please make close 
contenders comparable across the two precision paths and cover this mixed-scale 
case in all three scorers.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -131,18 +131,89 @@ fn squared_l2(query: &[f32], stored: &[f32]) -> f32 {
 
 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;
+    let mut query_norm = CosineNorm::default();
+    let mut stored_norm = CosineNorm::default();
     for i in 0..query.len() {
         dot += query[i] * stored[i];
-        query_norm += query[i] * query[i];
-        stored_norm += stored[i] * stored[i];
+        query_norm.add(query[i]);
+        stored_norm.add(stored[i]);
     }
-    let denominator = ((query_norm as f64).sqrt() * (stored_norm as 
f64).sqrt()) as f32;
+    query_norm
+        .try_score(stored_norm, dot, |query, stored| {
+            ((query as f64).sqrt() * (stored as f64).sqrt()) as f32
+        })
+        .unwrap_or_else(|| cosine_similarity_wide(query, stored))
+}
+
+#[derive(Clone, Copy, Default)]
+pub(crate) struct CosineNorm {
+    squared: f32,
+    has_small_square: bool,
+    has_non_finite: bool,
+}
+
+impl CosineNorm {
+    pub(crate) fn from_vector(vector: &[f32]) -> Self {
+        let mut norm = Self::default();
+        for &value in vector {
+            norm.add(value);
+        }
+        norm
+    }
+
+    pub(crate) fn add(&mut self, value: f32) {
+        let square = value * value;
+        self.squared += square;
+        self.has_non_finite |= !value.is_finite();
+        // A normal total can hide underflow in a coordinate square or its dot 
product term.
+        self.has_small_square |= value != 0.0 && square < f32::MIN_POSITIVE;
+    }
+
+    fn is_zero(self) -> bool {
+        self.squared == 0.0 && !self.has_small_square
+    }
+
+    pub(crate) fn try_score(
+        self,
+        stored: Self,
+        dot: f32,
+        denominator: impl FnOnce(f32, f32) -> f32,
+    ) -> Option<f32> {
+        if (self.is_zero() && !stored.has_non_finite) || (stored.is_zero() && 
!self.has_non_finite)
+        {
+            return Some(0.0);
+        }
+        if self.has_small_square
+            || stored.has_small_square
+            || !self.squared.is_normal()
+            || !stored.squared.is_normal()
+            || !dot.is_finite()
+            || dot.is_subnormal()
+        {
+            return None;
+        }
+        let denominator = denominator(self.squared, stored.squared);
+        denominator.is_normal().then(|| dot / denominator)
+    }
+}
+
+/// Computes cosine when f32 arithmetic overflows or underflows.
+pub(crate) fn cosine_similarity_wide(query: &[f32], stored: &[f32]) -> f32 {
+    let mut dot = 0.0_f64;
+    let mut query_norm = 0.0_f64;
+    let mut stored_norm = 0.0_f64;
+    for (&query, &stored) in query.iter().zip(stored) {
+        let q = f64::from(query);
+        let s = f64::from(stored);
+        dot += q * s;

Review Comment:
   **Permuting coordinates changes raw Top-1 even on the wide path.** Take `s = 
2^64`, `t = 2^37`, query `[s, t, s]`, row 10 `[s, 0, -s]`, and row 11 `[s, t, 
-s]`. Row 11 has cosine `2.7755576e-17`, but adding `t*t` to `s*s` loses the 
term in `f64`. Subtracting `s*s` then leaves zero. Both raw scorers tie the 
rows and return row 10. Swapping the last two coordinates in all three vectors 
makes both return row 11. Please preserve the small term in the wide dot 
product, for example with Neumaier compensated summation, and add this 
permutation as a regression.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2744,14 +2762,17 @@ fn compute_raw_vector_score_matrix(
                         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
-                    } else {
-                        *score / denominator
-                    }
-                }
+                RawVectorMetric::Cosine => query_norms.cosine[query_index]
+                    .try_score(stored_norms.cosine[row_index], *score, |query, 
stored| {
+                        query.sqrt() * stored.sqrt()
+                    })
+                    .unwrap_or_else(|| {

Review Comment:
   **One tiny coordinate per query sends the whole score matrix through a 
second scalar pass.** I used 32 queries, 1,024 rows and 256 dimensions, with 
ordinary finite values except for `2^-70` in the first coordinate of every 
query and zero in that coordinate of every row. `has_small_square` sends all 
32,768 pairs through this closure. It recomputes the dot product and both norms 
after SGEMM. An optimized arm64 run of this function took `0.28 ms` on the base 
commit and `5.10 ms` here. Please reuse wide norms per vector and batch the dot 
products for affected queries so the same matrix does not need two full scoring 
passes.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -131,18 +131,89 @@ fn squared_l2(query: &[f32], stored: &[f32]) -> f32 {
 
 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;
+    let mut query_norm = CosineNorm::default();
+    let mut stored_norm = CosineNorm::default();
     for i in 0..query.len() {
         dot += query[i] * stored[i];
-        query_norm += query[i] * query[i];
-        stored_norm += stored[i] * stored[i];
+        query_norm.add(query[i]);

Review Comment:
   **The PK exact scan repeats the new coordinate checks on the same query for 
every row.** The streaming reader calls `compute_distance` with that query for 
each candidate. In an optimized arm64 run with one query and 16,384 ordinary 
finite 256-dimensional rows, median scorer time rose from `2.24 ms` on the base 
commit to `2.65 ms` here. With the query's `CosineNorm` prepared once, the same 
scan took `2.11 ms` and produced identical distances for every row. Please 
reuse the prepared query norm in PK exact scans and reranking.



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