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]