You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2026/09/24 04:35:30 UTC
[M] Change in asterixdb[master]: [ASTERIXDB-3876][STO] Convert DOT VTree behaviour and formula to cosine
From Calvin Thomas Dani <ca...@gmail.com>:
Calvin Thomas Dani has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21878?usp=email )
Change subject: [ASTERIXDB-3876][STO] Convert DOT VTree behaviour and formula to cosine
......................................................................
[ASTERIXDB-3876][STO] Convert DOT VTree behaviour and formula to cosine
Assisted-by: Grok 4.7 <no...@x.ai>
Assisted-by: Cursor <cu...@cursor.com>
Change-Id: I628a38c1a8ffc0f626f17037763aecdaa6838111
---
M asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NearestCentroidScalarEvaluator.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NormalizedDotProductDescriptor.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceFunctionFactory.java
M hyracks-fullstack/hyracks/hyracks-storage-am-lsm-vtree/src/main/java/org/apache/hyracks/storage/am/lsm/vector/impls/LSMVTreeTopKSearchCursor.java
8 files changed, 133 insertions(+), 43 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/78/21878/1
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
index c87d1a3..a67e374 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
@@ -1223,6 +1223,8 @@
FunctionConstants.newAsterix("euclidean-squared-distance", 2);
public static final FunctionIdentifier COSINE_SIMILARITY = FunctionConstants.newAsterix("cosine-similarity", 2);
public static final FunctionIdentifier DOT_PRODUCT = FunctionConstants.newAsterix("dot-product", 2);
+ public static final FunctionIdentifier NORMALIZED_DOT_PRODUCT =
+ FunctionConstants.newAsterix("normalized-dot-product", 2);
public static final FunctionIdentifier COSINE_DISTANCE = FunctionConstants.newAsterix("cosine-distance", 2);
public static final FunctionIdentifier DOT_DISTANCE = FunctionConstants.newAsterix("dot-distance", 2);
public static final FunctionIdentifier VECTOR_DISTANCE = FunctionConstants.newAsterix("vector-distance", 3);
@@ -1978,6 +1980,7 @@
addFunction(EUCLIDEAN_SQUARED_DISTANCE, ADoubleTypeComputer.INSTANCE, true);
addFunction(COSINE_SIMILARITY, ADoubleTypeComputer.INSTANCE, true);
addFunction(DOT_PRODUCT, ADoubleTypeComputer.INSTANCE, true);
+ addPrivateFunction(NORMALIZED_DOT_PRODUCT, ADoubleTypeComputer.INSTANCE, true);
addPrivateFunction(COSINE_DISTANCE, ADoubleTypeComputer.INSTANCE, true);
addPrivateFunction(DOT_DISTANCE, ADoubleTypeComputer.INSTANCE, true);
addFunction(VECTOR_DISTANCE, ADoubleTypeComputer.INSTANCE, true);
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NearestCentroidScalarEvaluator.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NearestCentroidScalarEvaluator.java
index f1c610f..3474565 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NearestCentroidScalarEvaluator.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NearestCentroidScalarEvaluator.java
@@ -102,7 +102,7 @@
/**
* Resolves the metric argument to a distance function, caching by name. Returns false and warns if the
- * name is not a known metric or names one k-means cannot use.
+ * name is not a known metric. DOT uses the same distance as cosine.
*/
private boolean resolveMetric(IFrameTupleReference tuple) throws HyracksDataException {
if (metricEval == null) {
@@ -126,11 +126,6 @@
warn("nearest_centroid: unknown metric '" + name + "'");
return false;
}
- if (metric == VectorSimilarityMetric.DOT) {
- // dotDistance is a negated inner product, unbounded below, so no centroid minimizes it.
- warn("nearest_centroid: metric 'dot' is not usable for clustering");
- return false;
- }
distanceFn = new VectorDistanceFunctionFactory(metric).createDistanceFunction();
resolvedMetricName = name;
return true;
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NormalizedDotProductDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NormalizedDotProductDescriptor.java
new file mode 100644
index 0000000..2ee2131
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/vector/NormalizedDotProductDescriptor.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.asterix.runtime.evaluators.functions.vector;
+
+import org.apache.asterix.common.annotations.MissingNullInOutFunction;
+import org.apache.asterix.om.functions.BuiltinFunctions;
+import org.apache.asterix.om.functions.IFunctionDescriptorFactory;
+import org.apache.asterix.runtime.evaluators.base.AbstractScalarFunctionDynamicDescriptor;
+import org.apache.asterix.runtime.utils.VectorDistanceCalculation;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluator;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluatorFactory;
+import org.apache.hyracks.api.context.IEvaluatorContext;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+
+/**
+ * Private builtin for {@code dot(a, b) / (|a| |b|)}, the same value as {@code cosine_similarity}.
+ * Not resolvable from SQL++. It does not normalize its arguments.
+ */
+@MissingNullInOutFunction
+public class NormalizedDotProductDescriptor extends AbstractScalarFunctionDynamicDescriptor {
+ private static final long serialVersionUID = 1L;
+
+ public final static IFunctionDescriptorFactory FACTORY = NormalizedDotProductDescriptor::new;
+
+ @Override
+ public FunctionIdentifier getIdentifier() {
+ return BuiltinFunctions.NORMALIZED_DOT_PRODUCT;
+ }
+
+ @Override
+ public IScalarEvaluatorFactory createEvaluatorFactory(final IScalarEvaluatorFactory[] args) {
+ return new IScalarEvaluatorFactory() {
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ public IScalarEvaluator createScalarEvaluator(final IEvaluatorContext ctx) throws HyracksDataException {
+ return new VectorDistanceScalarEvaluator(ctx, args, getIdentifier(),
+ VectorDistanceCalculation::normalizedDotProduct, sourceLoc);
+ }
+ };
+
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
index 6ee56f2..1328177 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
@@ -662,6 +662,7 @@
import org.apache.asterix.runtime.evaluators.functions.vector.EuclideanSquaredDistanceDescriptor;
import org.apache.asterix.runtime.evaluators.functions.vector.NearestCentroidDescriptor;
import org.apache.asterix.runtime.evaluators.functions.vector.NormalizeVectorDescriptor;
+import org.apache.asterix.runtime.evaluators.functions.vector.NormalizedDotProductDescriptor;
import org.apache.asterix.runtime.runningaggregates.std.DenseRankRunningAggregateDescriptor;
import org.apache.asterix.runtime.runningaggregates.std.NtileRunningAggregateDescriptor;
import org.apache.asterix.runtime.runningaggregates.std.PercentRankRunningAggregateDescriptor;
@@ -1360,6 +1361,7 @@
fc.add(EuclideanSquaredDistanceDescriptor.FACTORY);
fc.add(CosineSimilarityDescriptor.FACTORY);
fc.add(DotProductDescriptor.FACTORY);
+ fc.add(NormalizedDotProductDescriptor.FACTORY);
fc.add(CosineDistanceDescriptor.FACTORY);
fc.add(DotDistanceDescriptor.FACTORY);
fc.add(NormalizeVectorDescriptor.FACTORY);
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
index d46dbf4..73f6eca 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
@@ -148,7 +148,7 @@
private final int maxScalableKmeansIter; // Maximum iterations for scalable K-means++ candidate selection
- private final VectorSimilarityMetric similarityMetric; // resolved from distanceMetric; drives cosine normalization
+ private final VectorSimilarityMetric similarityMetric; // resolved from distanceMetric; drives spherical normalization
private final RecordDescriptor secondaryRecDesc; // Input record descriptor (2-field format)
@@ -177,6 +177,13 @@
}
/**
+ * Cosine and DOT share spherical k-means: each Lloyd update L2-normalizes the centroid.
+ */
+ private static boolean requiresSphericalCentroids(VectorSimilarityMetric metric) {
+ return metric == VectorSimilarityMetric.COSINE || metric == VectorSimilarityMetric.DOT;
+ }
+
+ /**
* Whether the index can hold this vector. The bulk load applies the same rule, so one that fails here is
* never indexed, and must not shape the centroids either: not as a seed, candidate, padding or mean.
*/
@@ -1374,9 +1381,7 @@
}
/**
- * Normalizes centroid in place to unit L2 norm when using cosine similarity (spherical
- * k-means), so that centroid semantics match FAISS/Spark. Dot product is not normalized.
- * No-op for other metrics.
+ * L2-normalizes {@code centroid} after a Lloyd update when the metric uses spherical k-means.
*/
private void maybeNormalizeCentroid(double[] centroid) {
if (centroid != null && requiresNormalizedCentroids()) {
@@ -1384,14 +1389,8 @@
}
}
- /**
- * Whether the current distance function requires centroids to be L2-normalized after each
- * Lloyd update. Normalization is required only for cosine (spherical k-means); aligns with
- * FAISS spherical k-means and Spark's CosineDistanceMeasure. Dot product (MIPS) uses raw
- * centroids and does not require normalization.
- */
private boolean requiresNormalizedCentroids() {
- return similarityMetric == VectorSimilarityMetric.COSINE;
+ return requiresSphericalCentroids(similarityMetric);
}
private static IVTreeDistanceFunction distanceFunctionFor(VectorSimilarityMetric metric) {
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
index 39b09b3..07da309 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
@@ -49,7 +49,7 @@
/** Cosine distance (1 - cosine similarity) as an {@link IVTreeDistanceFunction}. */
public static final IVTreeDistanceFunction COSINE_DISTANCE_FN = new CosineDistanceFunction();
- /** Negated dot product as an {@link IVTreeDistanceFunction}, so that smaller still means nearer. */
+ /** VTree DOT hops use {@link #normalizedDotDistance}. SQL++ {@link #dotDistance} stays {@code -dot}. */
public static final IVTreeDistanceFunction DOT_DISTANCE_FN = new DotDistanceFunction();
private static final class EuclideanSquaredFunction implements IVTreeDistanceFunction {
@@ -110,18 +110,18 @@
private static final class DotDistanceFunction implements IVTreeDistanceFunction {
@Override
public double apply(double[] a, double[] b) {
- return dotDistance(a, b);
+ return normalizedDotDistance(a, b);
}
@Override
public double decodeAndApply(double[] query, byte[] bytes, int offset, int length, double[] dst)
throws HyracksDataException {
- return fusedDotDistance(query, bytes, offset, length, dst);
+ return fusedNormalizedDotDistance(query, bytes, offset, length, dst);
}
@Override
public double decodeAndApply(double[] query, byte[] bytes, int offset, int length) throws HyracksDataException {
- return fusedDotDistance(query, bytes, offset, length, null);
+ return fusedNormalizedDotDistance(query, bytes, offset, length, null);
}
}
@@ -166,6 +166,20 @@
return sum;
}
+ /**
+ * {@code dot(a, b) / (|a| |b|)}. Same expression as {@link #cosineSimilarity}, including the norm
+ * division that corrects a vector whose length is only approximately 1 after {@link #normalizeInPlace}.
+ */
+ public static double normalizedDotProduct(double[] a, double[] b) {
+ return cosineSimilarity(a, b);
+ }
+
+ /** {@code 1 - dot(a, b) / (|a| |b|)}. DOT page hops call this instead of {@link #cosineDistance}. */
+ public static double normalizedDotDistance(double[] a, double[] b) {
+ double similarity = normalizedDotProduct(a, b);
+ return Double.isNaN(similarity) ? Double.NaN : 1.0 - similarity;
+ }
+
public static double cosineSimilarity(double[] a, double[] b) {
double dot = 0.0, normA = 0.0, normB = 0.0;
for (int i = 0; i < a.length; i++) {
@@ -196,7 +210,7 @@
return sum;
}
- // USED BY VECTOR INDEX WILL BE USED FOR DOT DISTANCE
+ // SQL++ dot_distance / vector_distance(DOT). Index DOT hops use normalizedDotDistance.
public static double dotDistance(double[] a, double[] b) {
double dot = dotProduct(a, b);
return Double.isNaN(dot) ? Double.NaN : -dot;
@@ -224,6 +238,7 @@
return sum;
}
+ // Not called by the index page hop. That hop uses fusedNormalizedDotDistance.
private static double fusedDotDistance(double[] query, byte[] bytes, int offset, int length, double[] dst)
throws HyracksDataException {
int len = checkedLength(bytes, offset, length, dst);
@@ -239,6 +254,29 @@
return Double.isNaN(sum) ? Double.NaN : -sum;
}
+ private static double fusedNormalizedDotDistance(double[] query, byte[] bytes, int offset, int length, double[] dst)
+ throws HyracksDataException {
+ int len = checkedLength(bytes, offset, length, dst);
+ double dot = 0.0;
+ double normQuery = 0.0;
+ double normCentroid = 0.0;
+ int pos = offset + Integer.BYTES;
+ for (int i = 0; i < len; i++, pos += Double.BYTES) {
+ double x = DoublePointable.getDouble(bytes, pos);
+ if (dst != null) {
+ dst[i] = x;
+ }
+ dot += query[i] * x;
+ normQuery += query[i] * query[i];
+ normCentroid += x * x;
+ }
+ if (normQuery == 0.0 || normCentroid == 0.0 || Double.isNaN(normQuery) || Double.isNaN(normCentroid)
+ || Double.isNaN(dot)) {
+ return Double.NaN;
+ }
+ return 1.0 - dot / (Math.sqrt(normQuery) * Math.sqrt(normCentroid));
+ }
+
private static double fusedCosineDistance(double[] query, byte[] bytes, int offset, int length, double[] dst)
throws HyracksDataException {
int len = checkedLength(bytes, offset, length, dst);
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceFunctionFactory.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceFunctionFactory.java
index 0b14162..c031160 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceFunctionFactory.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceFunctionFactory.java
@@ -57,7 +57,7 @@
case EUCLIDEAN_SQUARED -> VectorDistanceCalculation.EUCLIDEAN_SQUARED_FN;
case COSINE -> VectorDistanceCalculation.COSINE_DISTANCE_FN;
case DOT ->
- // dotDistance returns -dot(a,b) so that minimizing "distance" equals maximizing dot product (MIPS).
+ // Same page calculation as cosine: 1 - dot / (|a| |b|).
VectorDistanceCalculation.DOT_DISTANCE_FN;
};
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-vtree/src/main/java/org/apache/hyracks/storage/am/lsm/vector/impls/LSMVTreeTopKSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-vtree/src/main/java/org/apache/hyracks/storage/am/lsm/vector/impls/LSMVTreeTopKSearchCursor.java
index 49282fb..f8a5d48 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-vtree/src/main/java/org/apache/hyracks/storage/am/lsm/vector/impls/LSMVTreeTopKSearchCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-vtree/src/main/java/org/apache/hyracks/storage/am/lsm/vector/impls/LSMVTreeTopKSearchCursor.java
@@ -131,8 +131,8 @@
// Vector accessor for extracting vectors from tuples
private IVTreeBinaryAccessor vectorAccessor;
- // Quantization state (propagated from first search cursor)
- private double[] quantizedQueryVector;
+ // Decodes stored SQ codes. The heap scores those against the original query, so the
+ // quantized query is not kept here.
private IVTreeQuantizer quantizer;
// Data-tuple layout authority. This cursor is quantized-only (see class javadoc), so the layout
@@ -275,8 +275,8 @@
this.queryVector = firstSearchCursor.getQueryVector();
this.distanceFunction = firstSearchCursor.getDistanceFunction();
- // Extract quantized state from first cursor (null = non-quantized path)
- this.quantizedQueryVector = firstSearchCursor.getQuantizedQueryVector();
+ // Stored codes still have to be decoded. The heap does not use the quantized query:
+ // quantizing it again was a second rounding on top of the stored codes.
this.quantizer = firstSearchCursor.getQuantizer();
if (this.queryVector == null) {
@@ -284,13 +284,10 @@
"A query vector is required for the vector index blocked search");
}
- // computeApproximateDistance() dequantizes every candidate with these two, and they arrive
- // independently of the USE_TOPK_SEARCH flag that selected this cursor (from a quantizer factory
- // or instance in the index access parameters). Fail here rather than NPE per candidate.
- if (this.quantizer == null || this.quantizedQueryVector == null) {
+ if (this.quantizer == null) {
throw HyracksDataException.create(ErrorCode.ILLEGAL_STATE,
- "LSMVTreeTopKSearchCursor requires a quantizer and a quantized query vector; none was supplied "
- + "through the index access parameters");
+ "LSMVTreeTopKSearchCursor requires a quantizer; none was supplied through the index access "
+ + "parameters");
}
// Initialize strategy with first component's tree (candidateLimit so we collect 2*K for reranking)
@@ -666,21 +663,15 @@
}
/**
- * Compute approximate distance D(q, x) using quantized embedding.
+ * Approximate distance from the original query to a stored code.
*
- * This cursor is dedicated for quantized vector indexes.
- * Quantized data tuple format:
- * Field 0: distance_to_centroid, Field 1: centroidId,
- * Field 2: quantized_distance, Field 3: quantized_embedding, Field 4+: key and value fields
- *
- * Dequantizes the stored embedding bytes (field 3) and computes distance
- * against the quantized query vector.
+ * Quantizing the query as well as the stored vector rounded it a second time, and that
+ * second rounding reordered neighbors. The stored code is still decoded; the query is not.
*/
private double computeApproximateDistance(ITupleReference tuple) throws HyracksDataException {
- // Quantized embedding content bytes (field 3, ByteArrayPointable prefix stripped) → dequantize.
byte[] qBytes = dataAccessor.getQuantizedEmbedding(tuple);
double[] dequantized = quantizer.dequantize(qBytes);
- return distanceFunction.apply(quantizedQueryVector, dequantized);
+ return distanceFunction.apply(queryVector, dequantized);
}
// ==================== IIndexCursor Interface (EnforcedIndexCursor template methods) ====================
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21878?usp=email
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I628a38c1a8ffc0f626f17037763aecdaa6838111
Gerrit-Change-Number: 21878
Gerrit-PatchSet: 1
Gerrit-Owner: Calvin Thomas Dani <ca...@gmail.com>