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


##########
crates/paimon/src/table/hybrid_search_builder.rs:
##########
@@ -892,10 +892,22 @@ impl<'a> HybridSearchBuilder<'a> {
     ) -> crate::Result<PkRoute> {
         let builder = self.vector_route_builder(table, route);
         let result = builder.execute().await?;
+        let cosine_distances = match self.ranker {
+            HybridSearchRanker::Rrf | HybridSearchRanker::Mrr => {
+                result.primary_key_cosine_distances()
+            }
+            HybridSearchRanker::WeightedScore => None,

Review Comment:
   **`weighted_score` can return a near match ahead of the exact match.** I ran 
the new `[3, 4, 0, 0]` fixture with one cosine route, final limit `1`, and 
refine factor `2`. `execute_read()` returns the exact match (ID `1`) at route 
limit `1` and the near match (ID `0`) at route limit `2`. The reranked 
distances are `0.0` and `2.8785461e-8`. Both become `1.0f32` in 
`position.score`, so min–max normalization gives both rows full weight and the 
physical tie-break picks ID `0`. The base scorer gave the near row `0.99999994`.
   
   For cosine, min–max normalization gives the same result after adding a 
constant to every route score. Please normalize `-distance` directly and extend 
the route-limit regression to `WeightedScore`.



##########
crates/paimon/src/vindex/pkvector/metric.rs:
##########
@@ -129,21 +163,294 @@ 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 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 bounds.0 == 0.0 && (query == stored || 
positively_proportional(query, stored)) {
+            return 0.0;
+        }
+        let (lower, upper) = normalized_distance_bounds(query, stored, 
query_norm, stored_norm);
+        bounds = (bounds.0.max(lower), bounds.1.min(upper));
+        if bounds.0 == bounds.1 {
+            return bounds.0;
+        }
     }
-    let denominator = ((query_norm as f64).sqrt() * (stored_norm as 
f64).sqrt()) as f32;
-    if denominator == 0.0 {
-        0.0
-    } else {
-        dot / denominator
+    output.round_exact(dot, query, stored, bounds, &mut Vec::new())
+}
+
+fn positively_proportional(query: &[f32], stored: &[f32]) -> bool {
+    let Some((&query_pivot, &stored_pivot)) = 
query.iter().zip(stored).find(|(q, _)| **q != 0.0)
+    else {
+        return false;
+    };
+    let query_pivot = f64::from(query_pivot);
+    let stored_pivot = f64::from(stored_pivot);
+    // Both cross products are exact because the coordinates are finite f32.
+    query_pivot * stored_pivot > 0.0
+        && query
+            .iter()
+            .zip(stored)
+            .all(|(&q, &s)| f64::from(q) * stored_pivot == f64::from(s) * 
query_pivot)
+}
+
+/// Bound the cosine distance as half the squared difference of unit vectors.
+/// The distance interval narrows as the difference approaches zero.
+fn normalized_distance_bounds(
+    query: &[f32],
+    stored: &[f32],
+    query_norm: f64,
+    stored_norm: f64,
+) -> (f32, f32) {
+    let roundoff = (query.len() as f64 + 8.0) * f64::EPSILON;
+    if roundoff >= 0.5 {
+        return (0.0, 2.0);
+    }
+    let inverse_query_norm = query_norm.recip();
+    let inverse_stored_norm = stored_norm.recip();
+    let mut squared_length = 0.0_f64;
+    for (&q, &s) in query.iter().zip(stored) {
+        let difference = f64::from(q) * inverse_query_norm - f64::from(s) * 
inverse_stored_norm;
+        squared_length += difference * difference;
     }
+    let length = squared_length.sqrt();
+    // Each input has unit length. Bound the normalization errors in both
+    // inputs and the relative error in the length of their difference.
+    let error = (1.0 + length) * roundoff / (1.0 - roundoff);
+    let lower = (length - error).max(0.0);
+    let upper = (length + error).min(2.0);
+    ((0.5 * lower * lower) as f32, (0.5 * upper * upper) as f32)
+}
+
+#[derive(Clone, Copy)]
+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,
+        }
+    }
+
+    #[inline]
+    pub(crate) fn round_from_dot<T: Copy + Into<f64>>(
+        self,
+        dot_product: CosineDot,
+        norm_product: f64,
+        query: &[T],
+        stored: &[T],
+        partials: &mut Vec<f64>,
+    ) -> f32 {
+        self.try_round_from_dot(dot_product, norm_product, query.len())
+            .unwrap_or_else(|bounds| self.round_exact(dot_product, query, 
stored, bounds, partials))
+    }
+
+    #[inline]
+    pub(crate) fn try_round_from_dot(
+        self,
+        dot_product: CosineDot,
+        norm_product: f64,
+        dimension: usize,
+    ) -> Result<f32, (f32, f32)> {
+        let (dot, absolute_dot_bound) = match dot_product {
+            CosineDot::Exact(value) => (value, 0.0),
+            CosineDot::Approximate {
+                value,
+                absolute_sum_bound,
+            } => (value, absolute_sum_bound),
+        };
+        if norm_product == 0.0 {
+            return Ok(self.value(0.0) as f32);
+        }
+        if !norm_product.is_finite() {
+            return Ok(self.value(dot / norm_product) as f32);
+        }
+        let inverse_norm = norm_product.recip();
+        let estimate = self.value(dot * inverse_norm);
+        // The products of two f32 coordinates are exact in f64. Bound the
+        // accumulation error in the dot and both squared norms, then allow
+        // for the square roots, normalization, and distance subtraction.
+        let error = 8.0
+            * f64::EPSILON
+            * (dimension as f64 + 2.0)
+            * (absolute_dot_bound + dot.abs())
+            * inverse_norm
+            + f64::EPSILON * estimate.abs();
+        let lower = (estimate - error) as f32;
+        let upper = (estimate + error) as f32;
+        if lower.to_bits() == upper.to_bits() {
+            return Ok(lower);
+        }
+        let lower = self.clamp(lower);
+        let upper = self.clamp(upper);
+        if lower.to_bits() == upper.to_bits() {
+            return Ok(lower);
+        }
+        Err((lower, upper))
+    }
+
+    fn clamp(self, value: f32) -> f32 {
+        match self {
+            Self::Similarity => value.clamp(-1.0, 1.0),
+            Self::Distance => value.clamp(0.0, 2.0),
+        }
+    }
+
+    #[cold]
+    pub(crate) fn round_exact<T: Copy + Into<f64>>(
+        self,
+        dot_product: CosineDot,
+        query: &[T],
+        stored: &[T],
+        bounds: (f32, f32),
+        partials: &mut Vec<f64>,
+    ) -> f32 {
+        let dot = match dot_product {
+            CosineDot::Exact(dot) => scale_f32_product(dot),
+            CosineDot::Approximate { .. } => exact_dot(query, stored, 
partials),
+        };
+        if dot.sign() == Sign::NoSign {
+            return self.value(0.0) as f32;
+        }
+        let negative = dot.sign() == Sign::Minus;
+        let norms_squared = exact_dot(query, query, partials).into_parts().1

Review Comment:
   **Once the exact dot is known, its value can already determine the rounded 
similarity.** I tested 16 queries `[a, t, a]` against 256 rows `[b, t, -b]`, 
concatenating 128-element blocks around `t = 2^-40`. The blocks contain varying 
multiples of `1/16` and `1/32`, respectively. The exact dot is `2^-80` for 
every pair. Retrying `try_round_from_dot` with that value and the ordinary norm 
estimates resolved all 4,096 scores. The optimized arm64 scorer took **26 ms** 
through this branch and **4.1 ms** with the extra check, with identical score 
bits.
   
   Please retry the rounding bound when the recovered dot is exactly 
representable in `f64`. That lets the similarity path reuse the norm estimates 
and reserve both exact norm sums and the midpoint search for results whose 
rounding is still ambiguous.



##########
crates/paimon/src/table/de_vector_read.rs:
##########
@@ -2713,52 +2775,273 @@ 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,
+    max_abs_integer: Option<f64>,
+}
+
+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),
+            max_abs_integer: max_abs_integer(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 max_abs_integer(vector: &[f64]) -> Option<f64> {
+    let mut maximum = 0.0_f64;
+    for &value in vector {
+        if value.fract() != 0.0 {

Review Comment:
   **Unit-normalizing orthogonal sign vectors sends every pair through exact 
summation.** In the 256-dimensional Walsh–Hadamard example, normalization 
changes each coordinate from `±1` to `±1/16`. This guard rejects every vector, 
although DGEMM still computes every cross-dot exactly. With 32 query vectors 
and 1,024 stored vectors drawn from other Walsh rows, all 32,768 scores are 
zero. On arm64 the optimized scorer took about **11 ms** for the normalized 
inputs. The base scorer took **0.28 ms**, and accounting for the common binary 
scale in this check gave identical score bits in **0.7 ms**.
   
   Please allow a common power-of-two scale per vector in the integer exactness 
check and include the unit-normalized case in 
`test_raw_cosine_matrix_certifies_orthogonal_integer_dots`.



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