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/08/30 08:51:38 UTC
[L] Change in asterixdb[master]: [NO ISSUE][COMP] Cost vector index access in the CBO
From Rithwik Koul <ri...@couchbase.com>:
Rithwik Koul has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21644?usp=email )
Change subject: [NO ISSUE][COMP] Cost vector index access in the CBO
......................................................................
[NO ISSUE][COMP] Cost vector index access in the CBO
Move vector index selection from the access-method rule into the CBO,
mirroring the existing BTree contract: JoinNode.addVectorIndexAccessPlans
costs each candidate VTREE against a full scan via the new
costVectorIndexScan/VectorIndexGeometry cost model and vetoes the losers
with a SkipSecondaryIndexSearchExpressionAnnotation, rather than the rule
picking blindly. JoinEnum invokes it once per single-dataset top-k query,
since a similarity search has no join cardinality to price against.
IntroduceTopKAccessMethodRule.matchTopKPattern now takes the transform as
a TopKMatchAction callback so it runs while aboveLimitOps is still fully
populated during the recursion, instead of after it unwinds back to
empty -- fixing a false-positive in isProjectionPkOnly() that could have
let the index-only rewrite drop non-PK projected fields.
Co-Authored-By: Claude Sonnet 5 <no...@anthropic.com>
Change-Id: I75edad1e58408aec9ba6ba9691cf984281220e82
---
M asterixdb/asterix-algebra/pom.xml
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CostMethods.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/ICostMethods.java
A asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/VectorIndexGeometry.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceTopKAccessMethodRule.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
A asterixdb/asterix-algebra/src/test/java/org/apache/asterix/optimizer/cost/VectorIndexGeometryTest.java
8 files changed, 721 insertions(+), 30 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/44/21644/1
diff --git a/asterixdb/asterix-algebra/pom.xml b/asterixdb/asterix-algebra/pom.xml
index b9af6d0..d14535c 100644
--- a/asterixdb/asterix-algebra/pom.xml
+++ b/asterixdb/asterix-algebra/pom.xml
@@ -234,5 +234,10 @@
<groupId>it.unimi.dsi</groupId>
<artifactId>fastutil</artifactId>
</dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <scope>test</scope>
+ </dependency>
</dependencies>
</project>
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CostMethods.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CostMethods.java
index 236bf05..5d3e2c1 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CostMethods.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/CostMethods.java
@@ -144,10 +144,23 @@
indexSel = limit / inputCard;
}
+ return costPrimaryFetch(inputCard * indexSel, jn.getUnnestFactor(), inputSize, outputSize);
+ }
+
+ /**
+ * Fetch of the given number of rows from the primary index, including the sort of their primary
+ * keys that precedes it.
+ *
+ * @param fetchedCard rows reaching the fetch
+ * @param unnestFactor duplicate RIDs the distinct operator removes; 1.0 for regular indexes
+ * @param inputSize original size of the dataset
+ * @param outputSize width of the variables leaving the fetch
+ */
+ private Cost costPrimaryFetch(double fetchedCard, double unnestFactor, double inputSize, double outputSize) {
// Duplicates RIDs will be removed by the distinct operator in case of array indexes.
// We account for that with the unnestFactor, which is 1.0 for regular indexes.
- double docsProcessed = inputCard * indexSel / DOP / jn.getUnnestFactor() * docSizeFactor(outputSize);
- double docsProduced = inputCard * indexSel / DOP * docSizeFactor(outputSize);
+ double docsProcessed = fetchedCard / DOP / unnestFactor * docSizeFactor(outputSize);
+ double docsProduced = fetchedCard / DOP * docSizeFactor(outputSize);
double docsSent = 0;
// Since we do not have exchanges at the logical plan level, docsSent for the exchange above the
@@ -163,6 +176,36 @@
return new Cost(docsProcessed, docsProduced, docsSent, 0, ioSeq, ioRand);
}
+ /**
+ * Cost of answering a similarity search from a vector index: the descent through the centroid
+ * hierarchy, a distance evaluation per entry in every probed cluster, and the fetch and rerank of
+ * the candidates that survive.
+ * <p>
+ * Unlike a b-tree scan this barely moves with what the query's predicate selects. The requested
+ * top-k, the probe fraction and the index geometry set it instead.
+ *
+ * @param geometry how much of the index a search touches
+ * @param fetchedCard candidates reranked; zero when the index answers the query on its own
+ * @param inputSize original size of the dataset
+ * @param outputSize width of the variables leaving the search
+ */
+ public Cost costVectorIndexScan(VectorIndexGeometry geometry, double fetchedCard, double inputSize,
+ double outputSize) {
+ double sizeFactor = docSizeFactor(outputSize);
+
+ // Routing evaluations down the hierarchy, then one distance evaluation per entry in every
+ // probed cluster, plus a second pass over them where replicas have to be deduplicated.
+ double docsProcessed =
+ (geometry.getTreeCentroids() + geometry.getScannedEntries() + geometry.getDeduplicatedEntries())
+ * sizeFactor;
+ double docsProduced = fetchedCard / DOP * sizeFactor;
+
+ // The entries are read out of each probed cluster's page chain.
+ Cost searchCost = new Cost(docsProcessed, docsProduced, 0, 0, geometry.getDataPages(), 0);
+
+ return (Cost) searchCost.costAdd(costPrimaryFetch(fetchedCard, 1.0, inputSize, outputSize));
+ }
+
public Cost costHashJoin(JoinNode jn) {
JoinNode leftJn = jn.getLeftJn();
JoinNode rightJn = jn.getRightJn();
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/ICostMethods.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/ICostMethods.java
index d8dd77f..5028414 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/ICostMethods.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/ICostMethods.java
@@ -33,6 +33,8 @@
Cost costIndexScan(JoinNode jn, double indexSel);
+ Cost costVectorIndexScan(VectorIndexGeometry geometry, double fetchedCard, double inputSize, double outputSize);
+
Cost costHashJoin(JoinNode currentJn);
Cost costBroadcastHashJoin(JoinNode currentJn);
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/VectorIndexGeometry.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/VectorIndexGeometry.java
new file mode 100644
index 0000000..d1f156e
--- /dev/null
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/cost/VectorIndexGeometry.java
@@ -0,0 +1,220 @@
+/*
+ * 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.optimizer.cost;
+
+import java.util.List;
+import java.util.OptionalInt;
+
+import org.apache.asterix.formats.nontagged.TypeTraitProvider;
+import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.om.vector.VectorIndexParameters;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+
+/**
+ * How much of one vector index a similarity search touches: the centroids it descends, the data
+ * entries it scans, and the pages those entries occupy.
+ * <p>
+ * Every quantity here is per storage partition, which is not the compute-node count the cost
+ * components divide by.
+ */
+public final class VectorIndexGeometry {
+
+ // Data-page header: the tree frame's reserved header plus the cluster id, centroid id and
+ // next-data-page pointers.
+ private static final int DATA_PAGE_HEADER_BYTES = 34;
+
+ private static final int TUPLE_SLOT_BYTES = 4;
+ private static final int CENTROID_ID_BYTES = 4;
+ private static final int DISTANCE_BYTES = Double.BYTES;
+
+ // SQ4 and SQ8 both round up to a byte per dimension, so quantization does not separate two
+ // indexes by width.
+ private static final int QUANTIZED_BYTES_PER_DIMENSION = 1;
+
+ // Fixed fields ahead of the primary key in a data entry: distance and centroid id, plus the
+ // quantized distance and quantized embedding when the index is quantized.
+ private static final int UNQUANTIZED_FIXED_FIELDS = 2;
+ private static final int QUANTIZED_FIXED_FIELDS = 4;
+
+ // A data tuple's null flags carry one extra bit marking an antimatter (delete) entry.
+ private static final int ANTIMATTER_BITS = 1;
+
+ private static final int NULL_FLAG_BITS_PER_BYTE = 8;
+ private static final int VAR_LEN_ONE_BYTE_LIMIT = 1 << 7;
+ private static final int VAR_LEN_TWO_BYTE_LIMIT = 1 << 14;
+ private static final int VAR_LEN_MAX_PREFIX_BYTES = 3;
+
+ // Assumed serialized width of a variable-length key or included field, since no per-field
+ // statistic is collected. The quantized embedding dominates a data entry at any realistic
+ // dimension, so the estimate barely moves the result.
+ private static final int VAR_LEN_FIELD_BYTES = 32;
+
+ private static final double MIN_ROWS = 1.0;
+
+ private final boolean replicated;
+ private final double treeCentroids;
+ private final double entriesPerCluster;
+ private final double probes;
+ private final double entryBytes;
+ private final double dataPages;
+
+ /**
+ * @param params the index's WITH parameters
+ * @param includeFieldTypes types of the index's INCLUDE fields
+ * @param primaryKeyTypes the dataset's primary-key field types
+ * @param cardinality dataset rows
+ * @param numPartitions storage partitions
+ * @param pageSize buffer-cache page size in bytes
+ * @param minProbeFraction fraction of clusters the search probes
+ * @param candidateCount candidates the search has to collect before it can stop
+ */
+ public VectorIndexGeometry(VectorIndexParameters params, List<IAType> includeFieldTypes,
+ List<IAType> primaryKeyTypes, double cardinality, int numPartitions, long pageSize, double minProbeFraction,
+ double candidateCount) {
+ double rowsPerPartition = Math.max(cardinality / Math.max(numPartitions, 1), MIN_ROWS);
+ double leafClusters = resolveLeafClusters(params.getNumClusters(), rowsPerPartition);
+ treeCentroids = sumOfLevels(leafClusters);
+ entriesPerCluster = rowsPerPartition * params.getCrossPollinationM() / leafClusters;
+ // The probe fraction is a floor, not a budget: the search keeps opening clusters until it has
+ // collected the candidates it was asked for.
+ probes = Math.min(leafClusters, Math.max(Math.max(1.0, Math.floor(minProbeFraction * leafClusters)),
+ Math.ceil(candidateCount / entriesPerCluster)));
+ replicated = params.getCrossPollinationM() > 1;
+
+ entryBytes = dataEntryBytes(params, includeFieldTypes, primaryKeyTypes);
+ dataPages = probes * Math.ceil(entriesPerCluster * entryBytes / (pageSize - DATA_PAGE_HEADER_BYTES));
+ }
+
+ /** Centroid tuples a search descends, summed over every level of the hierarchy. */
+ public double getTreeCentroids() {
+ return treeCentroids;
+ }
+
+ /** Data entries the probed clusters hold, one distance evaluation each. */
+ public double getScannedEntries() {
+ return probes * entriesPerCluster;
+ }
+
+ /**
+ * Entries a second pass has to deduplicate, because cross-pollination wrote each record to more
+ * than one cluster. Zero otherwise.
+ */
+ public double getDeduplicatedEntries() {
+ return replicated ? getScannedEntries() : 0;
+ }
+
+ /** Clusters the search opens, one seek each. */
+ public double getProbes() {
+ return probes;
+ }
+
+ /** Data pages the probed clusters occupy. */
+ public double getDataPages() {
+ return dataPages;
+ }
+
+ /** Serialized width of one data entry, including its page slot. */
+ public double getEntryBytes() {
+ return entryBytes;
+ }
+
+ /**
+ * Clusters at the widest level, either as the DDL fixed it or as the bulk load derives it from
+ * the rows in one partition.
+ */
+ private static double resolveLeafClusters(OptionalInt declared, double rowsPerPartition) {
+ if (declared.isPresent()) {
+ return Math.max(declared.getAsInt(), 1);
+ }
+ return Math.max(Math.floor(Math.sqrt(rowsPerPartition)), 1);
+ }
+
+ /**
+ * Hierarchical k-means re-derives the cluster count per level as the square root of the level
+ * below, so the descent visits that whole geometric sum and not just the leaf level. A level of one
+ * is never built, so the sum stops above it.
+ * <p>
+ * An over-estimate: the build also stops as soon as a level fits in a frame, which depends on the
+ * dimension and the frame size rather than on the cluster count.
+ */
+ private static double sumOfLevels(double leafClusters) {
+ double total = 0;
+ double level = leafClusters;
+ while (level > 1) {
+ total += level;
+ level = Math.floor(Math.sqrt(level));
+ }
+ return Math.max(total, 1);
+ }
+
+ /**
+ * @param params the index's WITH parameters
+ * @param includeTypes types of the index's INCLUDE fields
+ * @param primaryKeyTypes the dataset's primary-key field types
+ */
+ private static double dataEntryBytes(VectorIndexParameters params, List<IAType> includeTypes,
+ List<IAType> primaryKeyTypes) {
+ boolean quantized = params.isQuantized();
+ double bytes = DISTANCE_BYTES + CENTROID_ID_BYTES;
+ if (quantized) {
+ // A second, quantized distance is kept alongside the raw one. It is written as a bare double
+ // but declared variable length, so it is charged a field slot as well.
+ bytes += DISTANCE_BYTES + varLenPrefixBytes(DISTANCE_BYTES);
+ double quantizedBytes = params.getDimension() * QUANTIZED_BYTES_PER_DIMENSION;
+ double quantizedField = varLenPrefixBytes(quantizedBytes) + quantizedBytes;
+ bytes += quantizedField + varLenPrefixBytes(quantizedField);
+ }
+ bytes += serializedBytes(primaryKeyTypes) + serializedBytes(includeTypes);
+
+ int fixedFields = quantized ? QUANTIZED_FIXED_FIELDS : UNQUANTIZED_FIXED_FIELDS;
+ bytes += nullFlagBytes(fixedFields + primaryKeyTypes.size() + includeTypes.size() + ANTIMATTER_BITS);
+
+ return bytes + TUPLE_SLOT_BYTES;
+ }
+
+ /**
+ * Serialized, type-tagged width of a field list, falling back to an assumed width for the
+ * variable-length ones. Those are charged a field slot on top, since only they need locating.
+ */
+ private static double serializedBytes(List<IAType> types) {
+ double bytes = 0;
+ for (IAType type : types) {
+ ITypeTraits traits = TypeTraitProvider.INSTANCE.getTypeTrait(type);
+ if (traits != null && traits.isFixedLength()) {
+ bytes += traits.getFixedLength();
+ } else {
+ bytes += VAR_LEN_FIELD_BYTES + varLenPrefixBytes(VAR_LEN_FIELD_BYTES);
+ }
+ }
+ return bytes;
+ }
+
+ /** Length prefix and field slot a variable-length field of the given width needs. */
+ private static int varLenPrefixBytes(double width) {
+ if (width < VAR_LEN_ONE_BYTE_LIMIT) {
+ return 1;
+ }
+ return width < VAR_LEN_TWO_BYTE_LIMIT ? 2 : VAR_LEN_MAX_PREFIX_BYTES;
+ }
+
+ private static double nullFlagBytes(int fieldCount) {
+ return Math.ceil((double) fieldCount / NULL_FLAG_BITS_PER_BYTE);
+ }
+}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceTopKAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceTopKAccessMethodRule.java
index 93f8c12..fbb4c43 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceTopKAccessMethodRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceTopKAccessMethodRule.java
@@ -19,6 +19,7 @@
package org.apache.asterix.optimizer.rules.am;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
@@ -28,15 +29,20 @@
import java.util.TreeMap;
import org.apache.asterix.common.annotations.AnnSearchPreferenceAnnotation;
+import org.apache.asterix.common.annotations.SkipSecondaryIndexSearchExpressionAnnotation;
import org.apache.asterix.common.config.DatasetConfig.IndexType;
import org.apache.asterix.metadata.declared.IIndexProvider;
import org.apache.asterix.metadata.declared.MetadataProvider;
import org.apache.asterix.metadata.entities.Index;
import org.apache.asterix.metadata.utils.DatasetUtil;
+import org.apache.asterix.metadata.utils.KeyFieldTypeUtil;
import org.apache.asterix.om.base.AString;
import org.apache.asterix.om.base.IAObject;
import org.apache.asterix.om.constants.AsterixConstantValue;
import org.apache.asterix.om.functions.BuiltinFunctions;
+import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.om.utils.ConstantExpressionUtil;
+import org.apache.asterix.optimizer.cost.VectorIndexGeometry;
import org.apache.commons.lang3.mutable.Mutable;
import org.apache.commons.lang3.mutable.MutableObject;
import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
@@ -92,6 +98,11 @@
protected final OptimizableOperatorSubTree subTree = new OptimizableOperatorSubTree();
protected String queryDistanceMetric = null; // Distance metric from the query (e.g., "euclidean", "cosine")
+ // Search effort the ANN hint asks for, which is what a vector plan costs rather than anything the
+ // optimizer chooses. Unset until the hint is read.
+ protected double queryMinProbeFraction = 0;
+ protected int queryKMultiplier = 0;
+
// SELECT operator info for filter pushdown
protected SelectOperator selectOp = null;
protected Set<List<String>> filterFieldNames = null; // Field names referenced in WHERE clause
@@ -150,12 +161,40 @@
}
/**
+ * What to do once the top-k pattern has been matched. The action runs at the point in the recursion
+ * where {@link #aboveLimitOps} is fully populated, which is what {@link #isProjectionPkOnly} reads.
+ */
+ @FunctionalInterface
+ protected interface TopKMatchAction {
+ boolean apply(IOptimizationContext context) throws AlgebricksException;
+ }
+
+ /**
* Recursively checks the plan for LIMIT → ORDER BY ANN_DISTANCE pattern
* and applies vector index optimization if applicable.
*/
protected boolean checkAndApplyTopKTransformation(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
throws AlgebricksException {
+ return matchTopKPattern(opRef, context, this::analyzeAndTransform);
+ }
+ /**
+ * Recursively looks for the LIMIT → ORDER BY ANN_DISTANCE pattern and runs the action on the first
+ * match.
+ *
+ * @param opRef operator to search from
+ * @param context the optimization context
+ * @param action what to run once the pattern matches
+ */
+ protected boolean matchTopKPattern(Mutable<ILogicalOperator> opRef, IOptimizationContext context,
+ TopKMatchAction action) throws AlgebricksException {
+ // Same example tree as before:
+ // op0 DISTRIBUTE_RESULT (root)
+ // └─ op1 ASSIGN A ($$x := $$pk)
+ // └─ op2 ASSIGN B ($$y := $$name)
+ // └─ op3 LIMIT (k=10, no offset)
+ // └─ op4 ORDER (ann_distance($$emb,$$qvec))
+ // └─ op5 DATASOURCE_SCAN
AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
// Check if current operator is LIMIT
@@ -177,7 +216,7 @@
// truncated/empty results. Fall through to the exact ORDER BY ... LIMIT plan, which honors
// OFFSET correctly. (A future enhancement could size the search to (k + offset).)
if (!limitOp.hasOffset() && matchesAnnDistancePattern()) {
- return analyzeAndTransform(context);
+ return action.apply(context);
}
}
}
@@ -187,8 +226,8 @@
aboveLimitOps.add(op);
try {
for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
- boolean transformed = checkAndApplyTopKTransformation(inputOpRef, context);
- if (transformed) {
+ boolean matched = matchTopKPattern(inputOpRef, context, action);
+ if (matched) {
return true;
}
}
@@ -270,6 +309,40 @@
* Analyzes the pattern and attempts to apply vector index transformation.
*/
protected boolean analyzeAndTransform(IOptimizationContext context) throws AlgebricksException {
+ Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>();
+ List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>();
+ if (!analyzeApplicability(context, analyzedAMs, chosenIndexes)) {
+ return false;
+ }
+
+ if (chosenIndexes.isEmpty()) {
+ // No vector index left: either none exists, none has the required INCLUDE fields, or the
+ // cost-based optimizer priced them all above the scan. Fall back to data scan + sort.
+ context.addToDontApplySet(this, limitOp);
+ return false;
+ }
+
+ Index vectorIndex = chosenIndexes.get(0).second;
+ AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(VectorIndexAccessMethod.INSTANCE);
+
+ boolean transformed = applyTopKPlanTransformation(vectorIndex, analysisCtx, context);
+
+ // Always mark as processed to avoid re-attempting optimization on this operator
+ context.addToDontApplySet(this, limitOp);
+
+ return transformed;
+ }
+
+ /**
+ * Works out which vector indexes can answer the matched pattern, leaving the plan untouched.
+ *
+ * @param context the optimization context
+ * @param analyzedAMs filled with the access-method analysis backing the chosen indexes
+ * @param chosenIndexes filled with the applicable indexes, empty when none apply
+ */
+ protected boolean analyzeApplicability(IOptimizationContext context,
+ Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, List<Pair<IAccessMethod, Index>> chosenIndexes)
+ throws AlgebricksException {
// 1. Initialize subtree from ORDER down to DATASOURCE_SCAN
if (!initializeSubTree()) {
return false;
@@ -292,7 +365,6 @@
findSelectOperatorInSubTree();
// 5. Analyze ANN_DISTANCE function arguments
- Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>();
if (!analyzeAnnDistanceFunction(analyzedAMs, context)) {
return false;
}
@@ -300,27 +372,11 @@
// 6. Find applicable vector indexes on the dataset
fillSubTreeIndexExprs(subTree, analyzedAMs, context, false);
- // 7. Choose best vector index (considering INCLUDE fields if filter exists)
- List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>();
+ // 7. Choose best vector index (considering INCLUDE fields if filter exists), minus the ones the
+ // cost-based optimizer already ruled out.
chooseVectorIndex(analyzedAMs, chosenIndexes);
- if (chosenIndexes.isEmpty()) {
- // No vector index available (either none exists, or none has required INCLUDE fields).
- // Fall back to data scan + sort.
- context.addToDontApplySet(this, limitOp);
- return false;
- }
-
- // 8. Apply plan transformation
- Index vectorIndex = chosenIndexes.get(0).second;
- AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(VectorIndexAccessMethod.INSTANCE);
-
- boolean transformed = applyTopKPlanTransformation(vectorIndex, analysisCtx, context);
-
- // Always mark as processed to avoid re-attempting optimization on this operator
- context.addToDontApplySet(this, limitOp);
-
- return transformed;
+ return true;
}
/**
@@ -592,6 +648,8 @@
AnnSearchPreferenceAnnotation annHint = annDistanceExpr.getAnnotation(AnnSearchPreferenceAnnotation.class);
if (annHint != null) {
queryDistanceMetric = VectorIndexAccessMethod.normalizeDistanceMetric(annHint.getMetric());
+ queryMinProbeFraction = annHint.getMinProbeFraction();
+ queryKMultiplier = annHint.getKMultiplier();
}
// Now analyze the ANN_DISTANCE function arguments
@@ -668,6 +726,22 @@
}
/**
+ * Whether the cost-based optimizer priced this index above the plan it would replace. It records that
+ * verdict on the ordering expression, naming the indexes it rejected, or naming none to reject all.
+ *
+ * @param index the candidate vector index
+ */
+ private boolean isRuledOutByCost(Index index) {
+ SkipSecondaryIndexSearchExpressionAnnotation skipAnnotation =
+ annDistanceExpr.getAnnotation(SkipSecondaryIndexSearchExpressionAnnotation.class);
+ if (skipAnnotation == null) {
+ return false;
+ }
+ Collection<String> rejected = skipAnnotation.getIndexNames();
+ return rejected == null || rejected.contains(index.getIndexName());
+ }
+
+ /**
* Chooses the best vector index from candidates.
* Considers:
* 1. INCLUDE fields: If query has filter (WHERE clause), index must have all filter fields in INCLUDE
@@ -689,7 +763,9 @@
Iterator<Map.Entry<Index, List<Pair<Integer, Integer>>>> indexIt =
analysisCtx.getIteratorForIndexExprsAndVars();
- Pair<IAccessMethod, Index> exactMatch = null; // Index with matching field, metric, AND INCLUDE fields
+ // Every index whose field, metric and INCLUDE fields all match. More than one can qualify, so
+ // they are collected rather than settled here: the cheapest is picked once they are costed.
+ List<Pair<IAccessMethod, Index>> exactMatches = new ArrayList<>();
Pair<IAccessMethod, Index> fieldMatch = null; // Index with matching field only (and INCLUDE if needed)
while (indexIt.hasNext()) {
@@ -697,6 +773,10 @@
Index index = indexEntry.getKey();
if (index.getIndexType() == IndexType.VTREE) {
+ if (isRuledOutByCost(index)) {
+ continue;
+ }
+
// If query has filter, index must have all filter fields in its INCLUDE list.
if (hasFilter && !indexHasIncludeFields(index, filterFieldNames)) {
continue;
@@ -706,8 +786,7 @@
String indexMetric = VectorIndexAccessMethod.getIndexDistanceMetric(index);
if (queryDistanceMetric.equals(indexMetric)) {
// Exact match: field name AND distance metric match.
- exactMatch = new Pair<>(VectorIndexAccessMethod.INSTANCE, index);
- break;
+ exactMatches.add(new Pair<>(VectorIndexAccessMethod.INSTANCE, index));
} else if (fieldMatch == null) {
// Field matches but metric doesn't - store as fallback only if no exact match.
fieldMatch = new Pair<>(VectorIndexAccessMethod.INSTANCE, index);
@@ -726,8 +805,8 @@
}
// Prefer exact match. If only a field match exists (metric mismatch), fall back to full scan (KNN).
- if (exactMatch != null) {
- result.add(exactMatch);
+ if (!exactMatches.isEmpty()) {
+ result.addAll(exactMatches);
} else if (fieldMatch != null) {
Index idx = fieldMatch.second;
String indexMetric = VectorIndexAccessMethod.getIndexDistanceMetric(idx);
@@ -737,6 +816,93 @@
}
/**
+ * One vector index that can answer the matched top-k pattern, together with the shape a cost model
+ * needs to price it. Built here because the index shape is this rule's knowledge; priced by the
+ * caller because the cost model is not.
+ *
+ * @param index the vector index
+ * @param geometry how much of the index a search touches
+ * @param fetchedCard candidates reranked; zero when the index answers the query on its own
+ * @param annDistanceExpr ordering expression a rejection has to be recorded on
+ */
+ public record VectorIndexCandidate(Index index, VectorIndexGeometry geometry, double fetchedCard,
+ AbstractFunctionCallExpression annDistanceExpr) {
+ }
+
+ /**
+ * Collects every vector index that could answer a top-k ANN pattern under the given operator,
+ * leaving the plan untouched. Lets a cost-based caller price the alternatives before this rule runs
+ * for real; the caller records its verdict as a
+ * {@link org.apache.asterix.common.annotations.SkipSecondaryIndexSearchExpressionAnnotation} on each
+ * rejected candidate's ordering expression, which {@link #chooseVectorIndex} then honors.
+ *
+ * @param opRef operator to search from
+ * @param context the optimization context
+ * @param datasetCardinality rows in the dataset; the index holds an entry per row whatever the query filters
+ * @param candidates filled with the applicable indexes, left empty when none apply
+ */
+ public boolean collectVectorIndexCandidates(Mutable<ILogicalOperator> opRef, IOptimizationContext context,
+ double datasetCardinality, List<VectorIndexCandidate> candidates) throws AlgebricksException {
+ clear();
+ setMetadataIndexDeclarations(context, (IIndexProvider) context.getMetadataProvider());
+ return matchTopKPattern(opRef, context, ctx -> describeCandidates(ctx, datasetCardinality, candidates));
+ }
+
+ /**
+ * Analyzes the matched pattern and describes each applicable index in costable terms.
+ *
+ * @param context the optimization context
+ * @param datasetCardinality rows in the dataset; the index holds an entry per row whatever the query filters
+ * @param candidates filled with the applicable indexes
+ */
+ private boolean describeCandidates(IOptimizationContext context, double datasetCardinality,
+ List<VectorIndexCandidate> candidates) throws AlgebricksException {
+ Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>();
+ List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>();
+ if (!analyzeApplicability(context, analyzedAMs, chosenIndexes) || chosenIndexes.isEmpty()) {
+ return false;
+ }
+
+ Long topK = integralConstant(limitOp.getMaxObjects().getValue());
+ if (topK == null || queryKMultiplier <= 0) {
+ return false;
+ }
+
+ MetadataProvider metadataProvider = (MetadataProvider) context.getMetadataProvider();
+ List<IAType> primaryKeyTypes = KeyFieldTypeUtil.getPartitoningKeyTypes(subTree.getDataset(),
+ subTree.getRecordType(), subTree.getMetaRecordType());
+ int numPartitions = metadataProvider.getPartitioningProperties(subTree.getDataset()).getNumberOfPartitions();
+ long pageSize = metadataProvider.getStorageProperties().getBufferCachePageSize();
+
+ // The search collects this many candidates either way; an index-only plan then reads the distance
+ // off the cursor rather than fetching and reranking them.
+ double candidateCard = (double) topK * queryKMultiplier;
+ double fetchedCard = isProjectionPkOnly() ? 0 : candidateCard;
+
+ for (Pair<IAccessMethod, Index> candidate : chosenIndexes) {
+ Index.VectorIndexDetails details = (Index.VectorIndexDetails) candidate.second.getIndexDetails();
+ VectorIndexGeometry geometry = new VectorIndexGeometry(details.getVectorParameters(),
+ details.getIncludeFieldTypes(), primaryKeyTypes, datasetCardinality, numPartitions, pageSize,
+ queryMinProbeFraction, candidateCard);
+ candidates.add(new VectorIndexCandidate(candidate.second, geometry, fetchedCard, annDistanceExpr));
+ }
+ return true;
+ }
+
+ /**
+ * Value of an integral constant, whichever width it was written at, or null if the expression is not
+ * one. A literal limit parses as an integer rather than a bigint, so both have to be accepted.
+ */
+ private static Long integralConstant(ILogicalExpression expr) {
+ Long asLong = ConstantExpressionUtil.getLongConstant(expr);
+ if (asLong != null) {
+ return asLong;
+ }
+ Integer asInt = ConstantExpressionUtil.getIntConstant(expr);
+ return asInt == null ? null : asInt.longValue();
+ }
+
+ /**
* Applies the top-k plan transformation using the chosen vector index.
*
* Transforms:
@@ -1052,6 +1218,8 @@
annDistanceExpr = null;
typeEnvironment = null;
queryDistanceMetric = null;
+ queryMinProbeFraction = 0;
+ queryKMultiplier = 0;
selectOp = null;
filterFieldNames = null;
aboveLimitOps.clear();
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
index dacc614..9889739 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
@@ -1233,6 +1233,12 @@
// We may not add any index plans, so need to check for NO_PLAN
jn.addIndexAccessPlans(EnumerateJoinsRule.removeTrue(leafInput), indexProvider);
}
+
+ // A top-k similarity search is a single-dataset access path, so it is priced once, after the scan
+ // it would replace. Fake cardinalities cannot price one, so test mode leaves the choice alone.
+ if (this.numberOfTerms == 1 && !cboTestMode) {
+ jnArray[1].addVectorIndexAccessPlans(this.op, indexProvider);
+ }
return this.numberOfTerms;
}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
index b157e24..47a1406 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
@@ -52,6 +52,7 @@
import org.apache.asterix.optimizer.rules.am.IOptimizableFuncExpr;
import org.apache.asterix.optimizer.rules.am.IntroduceJoinAccessMethodRule;
import org.apache.asterix.optimizer.rules.am.IntroduceSelectAccessMethodRule;
+import org.apache.asterix.optimizer.rules.am.IntroduceTopKAccessMethodRule;
import org.apache.commons.lang3.mutable.Mutable;
import org.apache.commons.lang3.mutable.MutableObject;
import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
@@ -979,6 +980,76 @@
}
}
+ /**
+ * Prices every vector index that could answer a top-k ANN query over this dataset against the scan
+ * already costed for it, and records a rejection on the ordering expression for each index that does
+ * not come out cheaper. The access method rule that rewrites the plan later honors those rejections,
+ * so the choice is made here rather than there.
+ * <p>
+ * A similarity search only approximates the ordering it replaces, so a tie goes to the scan: the query
+ * can come out more accurate than it is today, never less.
+ *
+ * @param rootOp operator the top-k pattern is searched from
+ * @param indexProvider supplies the dataset's indexes
+ */
+ protected void addVectorIndexAccessPlans(ILogicalOperator rootOp, IIndexProvider indexProvider)
+ throws AlgebricksException {
+ record CostedIndex(IntroduceTopKAccessMethodRule.VectorIndexCandidate candidate, double cost) {
+ }
+
+ if (origCardinality <= 0) {
+ return;
+ }
+
+ List<IntroduceTopKAccessMethodRule.VectorIndexCandidate> candidates = new ArrayList<>();
+ IntroduceTopKAccessMethodRule tmp = new IntroduceTopKAccessMethodRule();
+ tmp.collectVectorIndexCandidates(new MutableObject<>(rootOp), joinEnum.optCtx, origCardinality, candidates);
+ if (candidates.isEmpty()) {
+ return;
+ }
+
+ AbstractFunctionCallExpression annDistanceExpr = candidates.get(0).annDistanceExpr();
+ SkipSecondaryIndexSearchExpressionAnnotation skipHint = joinEnum.findSkipIndexHint(annDistanceExpr);
+ if (skipHint != null && skipHint.getIndexNames() == null) {
+ return; // every secondary index here is already ruled out
+ }
+
+ double scanCost = joinEnum.getCostMethodsHandle().costFullScan(this).computeTotalCost(); //eg 12000
+ List<CostedIndex> affordable = new ArrayList<>();
+ for (IntroduceTopKAccessMethodRule.VectorIndexCandidate candidate : candidates) {
+ double cost = joinEnum.getCostMethodsHandle()
+ .costVectorIndexScan(candidate.geometry(), candidate.fetchedCard(), getInputSize(),
+ getOutputSize())
+ .computeTotalCost();
+ if (cost < scanCost) {
+ affordable.add(new CostedIndex(candidate, cost));
+ } else if (LOGGER.isDebugEnabled()) {
+ LOGGER.debug("Vector index {} priced at {} against {} for the scan; not used.",
+ candidate.index().getIndexName(), cost, scanCost);
+ }
+ }
+
+ // Narrower entries break a cost tie, then the name, so repeated compilations agree.
+ affordable.sort(Comparator.comparingDouble(CostedIndex::cost)
+ .thenComparingDouble(costedIndex -> costedIndex.candidate().geometry().getEntryBytes())
+ .thenComparing(costedIndex -> costedIndex.candidate().index().getIndexName()));
+
+ Collection<String> rejected = new HashSet<>();
+ if (skipHint != null) {
+ rejected.addAll(skipHint.getIndexNames());
+ }
+ for (IntroduceTopKAccessMethodRule.VectorIndexCandidate candidate : candidates) {
+ rejected.add(candidate.index().getIndexName());
+ }
+ if (!affordable.isEmpty()) {
+ rejected.remove(affordable.get(0).candidate().index().getIndexName());
+ }
+ if (!rejected.isEmpty()) {
+ EnumerateJoinsRule.setAnnotation(annDistanceExpr,
+ SkipSecondaryIndexSearchExpressionAnnotation.newInstance(rejected));
+ }
+ }
+
// check if the left side or the right side is the preserving side.
// The preserving side has to be the probe side (which is the left side since our engine builds from the right side)
// R LOJ S -- R is the preserving side; S is the null extending side.
diff --git a/asterixdb/asterix-algebra/src/test/java/org/apache/asterix/optimizer/cost/VectorIndexGeometryTest.java b/asterixdb/asterix-algebra/src/test/java/org/apache/asterix/optimizer/cost/VectorIndexGeometryTest.java
new file mode 100644
index 0000000..511af80
--- /dev/null
+++ b/asterixdb/asterix-algebra/src/test/java/org/apache/asterix/optimizer/cost/VectorIndexGeometryTest.java
@@ -0,0 +1,176 @@
+/*
+ * 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.optimizer.cost;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.List;
+
+import org.apache.asterix.common.exceptions.AsterixException;
+import org.apache.asterix.common.vector.VectorSimilarityMetric;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.om.vector.VectorIndexParameters;
+import org.junit.Test;
+
+public class VectorIndexGeometryTest {
+
+ private static final List<IAType> BIGINT_KEY = List.of(BuiltinType.AINT64);
+ private static final List<IAType> NO_INCLUDES = List.of();
+
+ private static final int DIMENSION = 384;
+ private static final double CARDINALITY = 1_000_000;
+ private static final int PARTITIONS = 4;
+ private static final long PAGE_SIZE = 128 * 1024;
+ private static final double PROBE_FRACTION = 0.1;
+ private static final double CANDIDATES = 50;
+
+ private static VectorIndexParameters params(int dimension) throws AsterixException {
+ return VectorIndexParameters.builder().setDimension(dimension).setSimilarity(VectorSimilarityMetric.EUCLIDEAN)
+ .build();
+ }
+
+ private static VectorIndexGeometry geometry(VectorIndexParameters params, List<IAType> includeTypes,
+ double cardinality, double minProbeFraction, double candidateCount) {
+ return new VectorIndexGeometry(params, includeTypes, BIGINT_KEY, cardinality, PARTITIONS, PAGE_SIZE,
+ minProbeFraction, candidateCount);
+ }
+
+ /**
+ * One million rows over four partitions, 384 dimensions, quantized, a tenth of the clusters probed.
+ * 250,000 rows per partition cluster into floor(sqrt(250,000)) = 500 leaves of 500 entries each, of
+ * which a tenth are probed.
+ */
+ @Test
+ public void oneMillionRows() throws Exception {
+ VectorIndexGeometry geometry =
+ geometry(params(DIMENSION), NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+
+ assertEquals(50, geometry.getProbes(), 0);
+ assertEquals(25_000, geometry.getScannedEntries(), 0);
+
+ // 500 leaves, then floor(sqrt(500)) = 22, then 4, then 2; no level of one is ever built.
+ assertEquals(528, geometry.getTreeCentroids(), 0);
+
+ // 8 distance + 4 centroid id + 8 quantized distance + 1 its slot + 385 quantized embedding
+ // + 1 its slot + 9 bigint key + 1 null flags + 4 page slot.
+ assertEquals(423, geometry.getEntryBytes(), 0);
+
+ // 500 entries of 423 bytes span two 128 KiB pages, counted per probed cluster since entries
+ // chain from the cluster's own first page.
+ assertEquals(100, geometry.getDataPages(), 0);
+ }
+
+ /** Cross-pollination replicates each row, so the probed clusters hold proportionally more entries. */
+ @Test
+ public void crossPollinationWidensClustersAndAddsDeduplication() throws Exception {
+ VectorIndexParameters replicated = VectorIndexParameters.builder().setDimension(DIMENSION)
+ .setSimilarity(VectorSimilarityMetric.EUCLIDEAN).setCrossPollinationM(3).build();
+
+ VectorIndexGeometry plain = geometry(params(DIMENSION), NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+ VectorIndexGeometry withReplicas = geometry(replicated, NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+
+ assertEquals(3 * plain.getScannedEntries(), withReplicas.getScannedEntries(), 0);
+ assertEquals(withReplicas.getScannedEntries(), withReplicas.getDeduplicatedEntries(), 0);
+ assertEquals(0, plain.getDeduplicatedEntries(), 0);
+ }
+
+ /** A declared cluster count replaces the one the bulk load would derive from the row count. */
+ @Test
+ public void declaredClusterCountIsHonoured() throws Exception {
+ VectorIndexParameters declared = VectorIndexParameters.builder().setDimension(DIMENSION)
+ .setSimilarity(VectorSimilarityMetric.EUCLIDEAN).setNumClusters(100).build();
+
+ VectorIndexGeometry geometry = geometry(declared, NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+
+ // 100 leaves, then 10, then 3, then 1 -- which is not built.
+ assertEquals(113, geometry.getTreeCentroids(), 0);
+ assertEquals(10, geometry.getProbes(), 0);
+ // 250,000 rows per partition over 100 clusters, a tenth of them probed.
+ assertEquals(25_000, geometry.getScannedEntries(), 0);
+ }
+
+ /** The probe fraction is a floor: the search keeps opening clusters until it has enough candidates. */
+ @Test
+ public void candidateCountRaisesProbesAboveTheFraction() throws Exception {
+ // 100 rows per partition cluster into 10 leaves of 10 entries; a zero fraction would probe one.
+ VectorIndexGeometry geometry = geometry(params(DIMENSION), NO_INCLUDES, 400, 0, 35);
+
+ assertEquals(4, geometry.getProbes(), 0);
+ assertEquals(40, geometry.getScannedEntries(), 0);
+ }
+
+ /** However many candidates are asked for, no more clusters exist than the index has. */
+ @Test
+ public void probesNeverExceedTheClusterCount() throws Exception {
+ VectorIndexGeometry geometry = geometry(params(DIMENSION), NO_INCLUDES, 400, 1.0, Double.MAX_VALUE);
+
+ assertEquals(10, geometry.getProbes(), 0);
+ }
+
+ /** An empty dataset still describes one cluster rather than dividing by zero. */
+ @Test
+ public void emptyDatasetStaysFinite() throws Exception {
+ VectorIndexGeometry geometry = geometry(params(DIMENSION), NO_INCLUDES, 0, PROBE_FRACTION, CANDIDATES);
+
+ assertEquals(1, geometry.getProbes(), 0);
+ assertEquals(1, geometry.getTreeCentroids(), 0);
+ assertTrue(Double.isFinite(geometry.getScannedEntries()));
+ assertTrue(Double.isFinite(geometry.getDataPages()));
+ }
+
+ /** Included fields widen an entry, which is what separates two otherwise identical indexes. */
+ @Test
+ public void includedFieldsWidenTheEntry() throws Exception {
+ VectorIndexGeometry narrow = geometry(params(DIMENSION), NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+ VectorIndexGeometry wide = geometry(params(DIMENSION), List.of(BuiltinType.AINT64, BuiltinType.ASTRING),
+ CARDINALITY, PROBE_FRACTION, CANDIDATES);
+
+ assertTrue(wide.getEntryBytes() > narrow.getEntryBytes());
+ }
+
+ /** Both quantization widths round to a byte per dimension, so neither separates two indexes. */
+ @Test
+ public void quantizationWidthDoesNotSeparateIndexes() throws Exception {
+ VectorIndexParameters sq4 =
+ VectorIndexParameters.builder().setDimension(DIMENSION).setSimilarity(VectorSimilarityMetric.EUCLIDEAN)
+ .setQuantization(VectorIndexParameters.QUANTIZATION_SQ4).build();
+ VectorIndexParameters sq8 =
+ VectorIndexParameters.builder().setDimension(DIMENSION).setSimilarity(VectorSimilarityMetric.EUCLIDEAN)
+ .setQuantization(VectorIndexParameters.QUANTIZATION_SQ8).build();
+
+ assertEquals(geometry(sq8, NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES).getEntryBytes(),
+ geometry(sq4, NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES).getEntryBytes(), 0);
+ }
+
+ /** Wider vectors mean fewer entries per page, so more pages for the same number of entries. */
+ @Test
+ public void dimensionDrivesEntryWidthAndPageCount() throws Exception {
+ VectorIndexGeometry small = geometry(params(64), NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+ VectorIndexGeometry large = geometry(params(1536), NO_INCLUDES, CARDINALITY, PROBE_FRACTION, CANDIDATES);
+
+ assertTrue(large.getEntryBytes() > small.getEntryBytes());
+ assertTrue(large.getDataPages() > small.getDataPages());
+ // Neither the descent nor the entries scanned depend on the width.
+ assertEquals(small.getScannedEntries(), large.getScannedEntries(), 0);
+ assertEquals(small.getTreeCentroids(), large.getTreeCentroids(), 0);
+ }
+}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21644?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: I75edad1e58408aec9ba6ba9691cf984281220e82
Gerrit-Change-Number: 21644
Gerrit-PatchSet: 1
Gerrit-Owner: Rithwik Koul <ri...@couchbase.com>