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]