This is an automated email from the ASF dual-hosted git repository. asf-gitbox-commits pushed a commit to branch PHOENIX-7998 in repository https://gitbox.apache.org/repos/asf/phoenix.git
commit 373e6eaac8b23a3073f5e2a8f10c6f44f249d3b0 Author: Andrew Purtell <[email protected]> AuthorDate: Mon Oct 5 23:43:48 2026 -0700 PHOENIX-7998 Phase 9: Cost-based plan selection and explain enhancements Co-Authored-By: Claude Opus 5.5 (1M context) <[email protected]> --- .../phoenix/compile/ExplainPlanAttributes.java | 52 ++- .../phoenix/execute/VectorIndexScanPlan.java | 60 +++- .../org/apache/phoenix/iterate/ExplainTable.java | 3 +- .../apache/phoenix/optimize/OptimizerReasons.java | 1 + .../apache/phoenix/optimize/QueryOptimizer.java | 44 ++- .../apache/phoenix/optimize/VectorSearchUtil.java | 78 +++++ .../java/org/apache/phoenix/util/CostUtil.java | 14 + .../apache/phoenix/end2end/VectorIvfCostIT.java | 353 +++++++++++++++++++++ .../apache/phoenix/end2end/VectorIvfQueryIT.java | 234 ++++++++++++++ .../phoenix/optimize/VectorPlanOrderingTest.java | 101 ++++++ .../phoenix/optimize/VectorSearchUtilTest.java | 22 ++ .../phoenix/query/explain/ExplainPlanTest.java | 3 + 12 files changed, 945 insertions(+), 20 deletions(-) diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/compile/ExplainPlanAttributes.java b/phoenix-core-client/src/main/java/org/apache/phoenix/compile/ExplainPlanAttributes.java index ef785bed11..3548133227 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/compile/ExplainPlanAttributes.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/compile/ExplainPlanAttributes.java @@ -49,12 +49,13 @@ import org.apache.phoenix.schema.PColumn; "serverDistinctFilter", "serverMergeColumns", "serverParsedProjections", "serverProject", "serverFilters", "ignoredHints", "serverFirstKeyOnlyProjection", "serverEmptyColumnOnlyProjection", "serverAggregate", "serverGroupByLimit", "serverSortedBy", - "vectorSearch", "serverOffset", "serverRowLimit", "clientFilterBy", "clientFilters", - "clientAggregate", "clientDistinctFilter", "clientAfterAggregate", "clientSortAlgo", - "clientSortedBy", "clientOffset", "clientRowLimit", "clientSequenceCount", "clientCursorName", - "clientSteps", "lhsJoinQueryExplainPlan", "rhsJoinQueryExplainPlan", "subPlans", - "dynamicServerFilter", "afterJoinFilter", "joinScannerLimit", "sortMergeSkipMerge", - "regionLocations", "regionLocationsTotalSize", "numRegionLocationLookups" }) + "vectorSearch", "vectorProbeCount", "vectorCentroidCount", "vectorDistanceMetric", "serverOffset", + "serverRowLimit", "clientFilterBy", "clientFilters", "clientAggregate", "clientDistinctFilter", + "clientAfterAggregate", "clientSortAlgo", "clientSortedBy", "clientOffset", "clientRowLimit", + "clientSequenceCount", "clientCursorName", "clientSteps", "lhsJoinQueryExplainPlan", + "rhsJoinQueryExplainPlan", "subPlans", "dynamicServerFilter", "afterJoinFilter", + "joinScannerLimit", "sortMergeSkipMerge", "regionLocations", "regionLocationsTotalSize", + "numRegionLocationLookups" }) public class ExplainPlanAttributes { // Top-of-plan disclosures (populated only on the root plan) @@ -113,6 +114,9 @@ public class ExplainPlanAttributes { private final String serverSortedBy; // True if the plan is a top-K vector similarity search. private final boolean isVectorSearch; + private final Integer vectorProbeCount; + private final Integer vectorCentroidCount; + private final String vectorDistanceMetric; private final Integer serverOffset; private final Long serverRowLimit; @@ -211,6 +215,9 @@ public class ExplainPlanAttributes { this.serverGroupByLimit = b.serverGroupByLimit; this.serverSortedBy = b.serverSortedBy; this.isVectorSearch = b.isVectorSearch; + this.vectorProbeCount = b.vectorProbeCount; + this.vectorCentroidCount = b.vectorCentroidCount; + this.vectorDistanceMetric = b.vectorDistanceMetric; this.serverOffset = b.serverOffset; this.serverRowLimit = b.serverRowLimit; this.clientFilterBy = b.clientFilterBy; @@ -448,6 +455,18 @@ public class ExplainPlanAttributes { return isVectorSearch; } + public Integer getVectorProbeCount() { + return vectorProbeCount; + } + + public Integer getVectorCentroidCount() { + return vectorCentroidCount; + } + + public String getVectorDistanceMetric() { + return vectorDistanceMetric; + } + public Integer getServerOffset() { return serverOffset; } @@ -650,6 +669,9 @@ public class ExplainPlanAttributes { private Integer serverGroupByLimit; private String serverSortedBy; private boolean isVectorSearch; + private Integer vectorProbeCount; + private Integer vectorCentroidCount; + private String vectorDistanceMetric; private Integer serverOffset; private Long serverRowLimit; private String clientFilterBy; @@ -738,6 +760,9 @@ public class ExplainPlanAttributes { this.serverGroupByLimit = explainPlanAttributes.getServerGroupByLimit(); this.serverSortedBy = explainPlanAttributes.getServerSortedBy(); this.isVectorSearch = explainPlanAttributes.isVectorSearch(); + this.vectorProbeCount = explainPlanAttributes.getVectorProbeCount(); + this.vectorCentroidCount = explainPlanAttributes.getVectorCentroidCount(); + this.vectorDistanceMetric = explainPlanAttributes.getVectorDistanceMetric(); this.serverOffset = explainPlanAttributes.getServerOffset(); this.serverRowLimit = explainPlanAttributes.getServerRowLimit(); this.clientFilterBy = explainPlanAttributes.getClientFilterBy(); @@ -1040,6 +1065,21 @@ public class ExplainPlanAttributes { return this; } + public ExplainPlanAttributesBuilder setVectorProbeCount(Integer vectorProbeCount) { + this.vectorProbeCount = vectorProbeCount; + return this; + } + + public ExplainPlanAttributesBuilder setVectorCentroidCount(Integer vectorCentroidCount) { + this.vectorCentroidCount = vectorCentroidCount; + return this; + } + + public ExplainPlanAttributesBuilder setVectorDistanceMetric(String vectorDistanceMetric) { + this.vectorDistanceMetric = vectorDistanceMetric; + return this; + } + public ExplainPlanAttributesBuilder setServerOffset(Integer serverOffset) { this.serverOffset = serverOffset; return this; diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/execute/VectorIndexScanPlan.java b/phoenix-core-client/src/main/java/org/apache/phoenix/execute/VectorIndexScanPlan.java index 8b160c89cd..578957f87c 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/execute/VectorIndexScanPlan.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/execute/VectorIndexScanPlan.java @@ -25,6 +25,8 @@ import org.apache.hadoop.hbase.io.ImmutableBytesWritable; import org.apache.phoenix.cache.VectorCentroidCache; import org.apache.phoenix.cache.VectorCentroidCache.CachedCentroids; import org.apache.phoenix.compile.ExplainPlan; +import org.apache.phoenix.compile.ExplainPlanAttributes; +import org.apache.phoenix.compile.ExplainPlanAttributes.ExplainPlanAttributesBuilder; import org.apache.phoenix.compile.OrderByCompiler.OrderBy; import org.apache.phoenix.compile.QueryPlan; import org.apache.phoenix.compile.RowProjector; @@ -35,6 +37,7 @@ import org.apache.phoenix.expression.function.DistanceFunction; import org.apache.phoenix.index.vector.CentroidManager; import org.apache.phoenix.iterate.ParallelIteratorFactory; import org.apache.phoenix.jdbc.PhoenixConnection; +import org.apache.phoenix.optimize.Cost; import org.apache.phoenix.optimize.DistanceMetric; import org.apache.phoenix.parse.FilterableStatement; import org.apache.phoenix.parse.HintNode; @@ -46,8 +49,10 @@ import org.apache.phoenix.schema.PTable; import org.apache.phoenix.schema.SaltingUtil; import org.apache.phoenix.schema.TableRef; import org.apache.phoenix.schema.types.PInteger; +import org.apache.phoenix.util.CostUtil; import org.apache.phoenix.util.ReadOnlyProps; import org.apache.phoenix.util.ScanUtil; +import org.apache.phoenix.util.SchemaUtil; import org.apache.phoenix.thirdparty.com.google.common.base.Optional; @@ -193,15 +198,66 @@ public class VectorIndexScanPlan extends ScanPlan { return defaultValue; } + /** + * Estimates the cost of the vector index scan. If the index has guideposts, the cost comes from + * the scan ranges of the probed posting lists. Without index statistics, the estimate scales the + * data table statistics by the probed centroid fraction and by the ratio of the row sizes. If the + * query has a limit, this estimate also adds the cost of the server top-N sort. For an uncovered + * index, the cost also includes a data table lookup for each candidate row. Returns + * {@link Cost#UNKNOWN} if the statistics cannot supply an estimate. + */ + @Override + public Cost getCost() { + Cost cost = super.getCost(); + Long candidates = null; + try { + candidates = getEstimatedRowsToScan(); + if (cost.isUnknown()) { + Long dataBytes = dataPlan == null ? null : dataPlan.getEstimatedBytesToScan(); + if (dataBytes == null) { + return Cost.UNKNOWN; + } + double fraction = probeCount == 0 ? 1.0 : (double) probeCount / centroidCount; + double bytes = dataBytes * fraction * SchemaUtil.estimateRowSize(getTableRef().getTable()) + / SchemaUtil.estimateRowSize(dataPlan.getTableRef().getTable()); + cost = new Cost(0, 0, bytes); + Long dataRows = dataPlan.getEstimatedRowsToScan(); + candidates = dataRows == null ? null : (long) Math.ceil(dataRows * fraction); + if (limit != null && candidates != null) { + double outputBytes = Math.min(candidates, limit + (offset == null ? 0 : offset)) + * (double) SchemaUtil.estimateRowSize(getTableRef().getTable()); + cost = cost.plus(CostUtil.estimateOrderByCost(bytes, outputBytes, + CostUtil.estimateParallelLevel(true, context.getConnection().getQueryServices()))); + } + } + } catch (SQLException e) { + return Cost.UNKNOWN; + } + if (context.isUncoveredIndex()) { + if (candidates == null) { + return Cost.UNKNOWN; + } + cost = cost.plus(CostUtil.estimateLookupCost(candidates, dataPlan.getTableRef().getTable())); + } + return cost; + } + @Override public ExplainPlan getExplainPlan() throws SQLException { ExplainPlan explainPlan = super.getExplainPlan(); if (probeCount == 0) { return explainPlan; } + String metric = getTableRef().getTable().getVectorDistanceMetric(); List<String> steps = new ArrayList<>(explainPlan.getPlanSteps()); - steps.add(0, "CLIENT PROBING " + probeCount + " OF " + centroidCount + " CENTROIDS"); - return new ExplainPlan(steps, explainPlan.getPlanStepsAsAttributes()); + steps.add(0, + "CLIENT PROBING " + probeCount + " OF " + centroidCount + " CENTROIDS (" + metric + ")"); + ExplainPlanAttributes attributes = explainPlan.getPlanStepsAsAttributes(); + return new ExplainPlan(steps, + (attributes == null + ? new ExplainPlanAttributesBuilder() + : new ExplainPlanAttributesBuilder(attributes)).setVectorProbeCount(probeCount) + .setVectorCentroidCount(centroidCount).setVectorDistanceMetric(metric).build()); } /** Number of probed centroid posting lists, or 0 for full index scans. */ diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/iterate/ExplainTable.java b/phoenix-core-client/src/main/java/org/apache/phoenix/iterate/ExplainTable.java index b2c9cb2a44..6135dce8b4 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/iterate/ExplainTable.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/iterate/ExplainTable.java @@ -516,7 +516,8 @@ public abstract class ExplainTable { String orderByExpressions; if (isVectorSearch) { Expression distanceExpr = orderBy.getOrderByExpressions().get(0).getExpression(); - orderByExpressions = "SERVER TOP-" + limit + " BY " + distanceExpr; + orderByExpressions = + "SERVER TOP-" + limit + " BY " + VectorSearchUtil.toExplainString(distanceExpr); } else { orderByExpressions = "SERVER" + (limit == null ? "" : " TOP " + limit + " ROW" + (limit == 1 ? "" : "S")) diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/OptimizerReasons.java b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/OptimizerReasons.java index dbdb9c9dbb..cc84f798ac 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/OptimizerReasons.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/OptimizerReasons.java @@ -35,6 +35,7 @@ public final class OptimizerReasons { public static final String RULE_ORDER_PRESERVING = "order-preserving"; public static final String RULE_NON_LOCAL_PREFERRED = "non-local preferred"; public static final String RULE_PARTIAL_INDEX_APPLICABLE = "partial index applicable"; + public static final String RULE_NEAREST_NEIGHBOR_INDEX = "nearest-neighbor index"; // REASON_* — rejected-index reason labels. public static final String REASON_NO_PK_PREFIX_BOUND = "no PK prefix bound"; diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/QueryOptimizer.java b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/QueryOptimizer.java index 611449189d..13c76dad0f 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/QueryOptimizer.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/QueryOptimizer.java @@ -921,16 +921,20 @@ public class QueryOptimizer { return plans; } + final boolean useDataOverIndexHint = select.getHint().hasHint(Hint.USE_DATA_OVER_INDEX_TABLE); + final int comparisonOfDataVersusIndexTable = useDataOverIndexHint ? -1 : 1; if (this.costBased) { Collections.sort(plans, new Comparator<QueryPlan>() { @Override public int compare(QueryPlan plan1, QueryPlan plan2) { - return plan1.getCost().compareTo(plan2.getCost()); + int c = VectorSearchUtil.getCost(plan1).compareTo(VectorSearchUtil.getCost(plan2)); + // If the costs are equal, the static precedence rules for vector plans set the order. + return c != 0 ? c : compareVectorPlans(plan1, plan2, comparisonOfDataVersusIndexTable); } }); // Return ordered list based on cost if stats are available; otherwise fall // back to static ordering. - if (!plans.get(0).getCost().isUnknown()) { + if (!VectorSearchUtil.getCost(plans.get(0)).isUnknown()) { QueryPlan costWinner = plans.get(0); for (int i = 1; i < plans.size(); i++) { PTable losingTable = plans.get(i).getTableRef().getTable(); @@ -991,20 +995,14 @@ public class QueryOptimizer { } } final int boundRanges = nViewConstants; - final boolean useDataOverIndexHint = select.getHint().hasHint(Hint.USE_DATA_OVER_INDEX_TABLE); - final int comparisonOfDataVersusIndexTable = useDataOverIndexHint ? -1 : 1; Collections.sort(bestCandidates, new Comparator<QueryPlan>() { @Override public int compare(QueryPlan plan1, QueryPlan plan2) { PTable table1 = plan1.getTableRef().getTable(); PTable table2 = plan2.getTableRef().getTable(); - // Prioritize vector index plans for nearest-neighbor queries over data table scans unless - // hinted otherwise. - boolean vector1 = VectorSearchUtil.usesVectorIndex(plan1); - if (vector1 != VectorSearchUtil.usesVectorIndex(plan2)) { - return vector1 ? -comparisonOfDataVersusIndexTable : comparisonOfDataVersusIndexTable; - } + int c = compareVectorPlans(plan1, plan2, comparisonOfDataVersusIndexTable); + if (c != 0) return c; int boundCount1 = plan1.getContext().getScanRanges().getBoundPkColumnCount(); int boundCount2 = plan2.getContext().getScanRanges().getBoundPkColumnCount(); // For shared indexes (i.e. indexes on views and local indexes), @@ -1016,7 +1014,7 @@ public class QueryOptimizer { // (but the sum of buckets cover the entire table) boundCount1 -= plan1.getContext().getScanRanges().isSalted() ? 1 : 0; boundCount2 -= plan2.getContext().getScanRanges().isSalted() ? 1 : 0; - int c = boundCount2 - boundCount1; + c = boundCount2 - boundCount1; if (c != 0) return c; if (plan1.getGroupBy() != null && plan2.getGroupBy() != null) { if (plan1.getGroupBy().isOrderPreserving() != plan2.getGroupBy().isOrderPreserving()) { @@ -1078,6 +1076,27 @@ public class QueryOptimizer { return stopAtBestPlan ? bestCandidates.subList(0, 1) : bestCandidates; } + /** + * Compares plans based on vector index precedence. + * <p> + * Prioritizes vector index plans over non-vector plans for nearest neighbor queries unless base + * table execution is hinted. Among competing vector index plans, preference is given to plans + * requiring fewer base table lookups (covering index, then deferred projection, then filter-time + * joins). Returns 0 when neither plan uses a vector index to preserve external ordering. + */ + static int compareVectorPlans(QueryPlan plan1, QueryPlan plan2, + int comparisonOfDataVersusIndexTable) { + boolean vector1 = VectorSearchUtil.usesVectorIndex(plan1); + boolean vector2 = VectorSearchUtil.usesVectorIndex(plan2); + if (vector1 != vector2) { + return vector1 ? -comparisonOfDataVersusIndexTable : comparisonOfDataVersusIndexTable; + } + return vector1 + ? Integer.compare(VectorSearchUtil.getLookupRank(plan1), + VectorSearchUtil.getLookupRank(plan2)) + : 0; + } + /** * Outcome of attempting to build an index candidate plan in {@link #addPlan}. Carries either the * successfully built {@code plan} or a {@code rejection} explaining why the candidate index was @@ -1267,6 +1286,9 @@ public class QueryOptimizer { if (runnerUp == null) { return OptimizerReasons.RULE_ONLY_CANDIDATE; } + if (VectorSearchUtil.usesVectorIndex(winner) && compareVectorPlans(winner, runnerUp, 1) != 0) { + return OptimizerReasons.RULE_NEAREST_NEIGHBOR_INDEX; + } PTable winnerTable = winner.getTableRef().getTable(); PTable runnerUpTable = runnerUp.getTableRef().getTable(); if (adjustedBoundCount(winner, boundRanges) != adjustedBoundCount(runnerUp, boundRanges)) { diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/VectorSearchUtil.java b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/VectorSearchUtil.java index 3d9914ed68..62405217c2 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/VectorSearchUtil.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/optimize/VectorSearchUtil.java @@ -17,7 +17,9 @@ */ package org.apache.phoenix.optimize; +import java.lang.reflect.Array; import java.util.List; +import org.apache.hadoop.hbase.io.ImmutableBytesWritable; import org.apache.phoenix.compile.OrderByCompiler.OrderBy; import org.apache.phoenix.compile.QueryPlan; import org.apache.phoenix.execute.DelegateQueryPlan; @@ -36,6 +38,9 @@ import org.apache.phoenix.parse.LiteralParseNode; import org.apache.phoenix.parse.OrderByNode; import org.apache.phoenix.parse.ParseNode; import org.apache.phoenix.parse.SelectStatement; +import org.apache.phoenix.schema.types.PDataType; +import org.apache.phoenix.schema.types.PVectorDataType; +import org.apache.phoenix.util.CostUtil; /** * Finds vector similarity search queries and extracts their parameters. @@ -47,6 +52,9 @@ import org.apache.phoenix.parse.SelectStatement; */ public final class VectorSearchUtil { + /** The maximum number of elements that EXPLAIN shows for a literal query vector. */ + private static final int EXPLAIN_VECTOR_ELEMENTS = 8; + private VectorSearchUtil() { } @@ -256,4 +264,74 @@ public final class VectorSearchUtil { public static boolean usesVectorIndex(QueryPlan plan) { return getVectorIndexScan(plan) != null; } + + /** + * Returns the rank of a plan by its data table lookups, where a lower rank does fewer lookups. A + * covering vector index plan gets 0 because it does no lookups. A deferred projection gets 1 + * because it looks up only the top-k rows. An uncovered vector index plan gets 2 because it looks + * up every candidate row at filter time. A plan that does not read a vector index gets 0. + */ + public static int getLookupRank(QueryPlan plan) { + VectorIndexScanPlan scan = getVectorIndexScan(plan); + if (scan == null || scan == plan) { + return scan != null && scan.getContext().isUncoveredIndex() ? 2 : 0; + } + return 1; + } + + /** + * Returns the cost of a query plan for comparison with the other candidate plans. For a deferred + * projection, the cost is the vector index scan cost plus point lookups for LIMIT + OFFSET rows. + * This cost does not include a full data table scan. For other plans, the cost is + * {@link QueryPlan#getCost()}. A deferred projection gets {@link Cost#UNKNOWN} if the scan cost + * is unknown or the scan has no limit. + */ + public static Cost getCost(QueryPlan plan) { + VectorIndexScanPlan scan = getVectorIndexScan(plan); + if (scan == null || scan == plan) { + return plan.getCost(); + } + Cost scanCost = scan.getCost(); + if (scanCost.isUnknown() || scan.getLimit() == null) { + return Cost.UNKNOWN; + } + long rows = scan.getLimit() + (scan.getOffset() == null ? 0 : scan.getOffset()); + return scanCost.plus(CostUtil.estimateLookupCost(rows, plan.getTableRef().getTable())); + } + + /** + * Formats a distance expression for EXPLAIN output. A literal query vector shows only its type, + * its dimension, and its first elements, so that a large vector does not make the plan too long. + */ + public static String toExplainString(Expression distance) { + if (!(distance instanceof DistanceFunction)) { + return distance.toString(); + } + StringBuilder buf = new StringBuilder(((DistanceFunction) distance).getName()).append('('); + List<Expression> children = distance.getChildren(); + for (int i = 0; i < children.size(); i++) { + if (i > 0) { + buf.append(", "); + } + Expression child = children.get(i); + PDataType type = child.getDataType(); + ImmutableBytesWritable ptr = new ImmutableBytesWritable(); + if ( + child.isStateless() && type instanceof PVectorDataType && child.evaluate(null, ptr) + && ptr.getLength() > 0 + ) { + Object elements = type.toObject(ptr); + int dim = Array.getLength(elements); + buf.append("VECTOR(").append(((PVectorDataType<?>) type).getElementType().getSqlTypeName()) + .append(", ").append(dim).append(")["); + for (int j = 0; j < Math.min(dim, EXPLAIN_VECTOR_ELEMENTS); j++) { + buf.append(j > 0 ? ", " : "").append(Array.get(elements, j)); + } + buf.append(dim > EXPLAIN_VECTOR_ELEMENTS ? ", ...]" : "]"); + } else { + buf.append(child); + } + } + return buf.append(')').toString(); + } } diff --git a/phoenix-core-client/src/main/java/org/apache/phoenix/util/CostUtil.java b/phoenix-core-client/src/main/java/org/apache/phoenix/util/CostUtil.java index 8a9a7f5b57..33928bec4d 100644 --- a/phoenix-core-client/src/main/java/org/apache/phoenix/util/CostUtil.java +++ b/phoenix-core-client/src/main/java/org/apache/phoenix/util/CostUtil.java @@ -20,6 +20,7 @@ package org.apache.phoenix.util; import org.apache.phoenix.compile.GroupByCompiler.GroupBy; import org.apache.phoenix.optimize.Cost; import org.apache.phoenix.query.QueryServices; +import org.apache.phoenix.schema.PTable; /** * Utilities for computing costs. Some of the methods here should eventually be replaced by a @@ -77,6 +78,19 @@ public class CostUtil { + outputBytes); } + /** + * Estimates the I/O cost of primary key point lookups in a data table, for example to read the + * columns that an index does not cover. The cost is the row count times the estimated row size. + * @param rows the estimated number of rows to look up + * @param dataTable the data table that the lookups read + * @return the estimated I/O cost, or {@link Cost#ZERO} if {@code rows} is zero or less + */ + public static Cost estimateLookupCost(long rows, PTable dataTable) { + return rows <= 0 + ? Cost.ZERO + : new Cost(0, 0, (double) rows * SchemaUtil.estimateRowSize(dataTable)); + } + /** * Estimate the parallel level of an operation * @param runningOnServer if the operation will be running on server side diff --git a/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfCostIT.java b/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfCostIT.java new file mode 100644 index 0000000000..46894fc972 --- /dev/null +++ b/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfCostIT.java @@ -0,0 +1,353 @@ +/* + * 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.phoenix.end2end; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.sql.Connection; +import java.sql.DriverManager; +import java.sql.PreparedStatement; +import java.sql.SQLException; +import java.sql.Statement; +import java.util.Arrays; +import java.util.List; +import java.util.Properties; +import java.util.Random; +import org.apache.phoenix.compile.QueryPlan; +import org.apache.phoenix.execute.VectorIndexScanPlan; +import org.apache.phoenix.jdbc.PhoenixPreparedStatement; +import org.apache.phoenix.optimize.Cost; +import org.apache.phoenix.optimize.VectorSearchUtil; +import org.apache.phoenix.query.QueryServices; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.experimental.categories.Category; + +/** Integration tests for the vector index cost model and for cost-based plan selection. */ +@Category(ParallelStatsEnabledTest.class) +public class VectorIvfCostIT extends ParallelStatsEnabledIT { + + private static String tableName; + private static String indexCoveringCategory; + private static List<float[]> l2Centroids; + private static final Float[] queryVectorBoxed = new Float[] { 0.0f, 0.0f, 0.0f, 0.0f }; + + private static Connection getCostBasedConnection() throws SQLException { + Properties props = new Properties(); + props.setProperty(QueryServices.COST_BASED_OPTIMIZER_ENABLED, "true"); + return DriverManager.getConnection(getUrl(), props); + } + + @BeforeClass + public static synchronized void doTableSetup() throws Exception { + tableName = generateUniqueName(); + indexCoveringCategory = generateUniqueName(); + + try (Connection conn = getCostBasedConnection()) { + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE TABLE " + tableName + + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 4), CATEGORY VARCHAR, DESCRIPTION VARCHAR)"); + stmt.execute("CREATE VECTOR INDEX " + indexCoveringCategory + " ON " + tableName + " (V) " + + "INCLUDE (CATEGORY) WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + + l2Centroids = Arrays.asList(new float[] { 0.0f, 0.0f, 0.0f, 0.0f }, + new float[] { 100.0f, 0.0f, 0.0f, 0.0f }, new float[] { 200.0f, 0.0f, 0.0f, 0.0f }, + new float[] { 300.0f, 0.0f, 0.0f, 0.0f }); + + VectorIndexTestUtil.activateWithKnownCentroids(conn, tableName, indexCoveringCategory, + l2Centroids); + + Random rng = new Random(42); + String upsert = + "UPSERT INTO " + tableName + " (ID, V, CATEGORY, DESCRIPTION) VALUES (?, ?, ?, ?)"; + try (PreparedStatement ps = conn.prepareStatement(upsert)) { + for (int k = 0; k < 4; k++) { + float[] center = l2Centroids.get(k); + for (int i = 0; i < 1000; i++) { + String id = String.format("k%d_r%04d", k, i); + float[] v = new float[] { center[0] + (float) (rng.nextGaussian() * 0.1), + center[1] + (float) (rng.nextGaussian() * 0.1), + center[2] + (float) (rng.nextGaussian() * 0.1), + center[3] + (float) (rng.nextGaussian() * 0.1) }; + String cat = (i % 2 == 0) ? "catA" : "catB"; + String desc = "desc_" + id; + ps.setString(1, id); + ps.setArray(2, conn.createArrayOf("FLOAT", new Float[] { v[0], v[1], v[2], v[3] })); + ps.setString(3, cat); + ps.setString(4, desc); + ps.addBatch(); + if (i % 250 == 0) { + ps.executeBatch(); + } + } + ps.executeBatch(); + } + conn.commit(); + } + + try (Statement stmt = conn.createStatement()) { + stmt.execute("UPDATE STATISTICS " + tableName); + stmt.execute("UPDATE STATISTICS " + indexCoveringCategory); + } + } + } + + @Test + public void testProbeFractionAppliedOnce() throws Exception { + try (Connection conn = getCostBasedConnection()) { + String query1 = "SELECT /*+ VECTOR_PROBE_COUNT(1) */ ID FROM " + tableName + + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + String query4 = "SELECT /*+ VECTOR_PROBE_COUNT(4) */ ID FROM " + tableName + + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + String queryExact = + "SELECT /*+ NO_INDEX */ ID FROM " + tableName + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + + Cost cost1; + try (PreparedStatement ps1 = conn.prepareStatement(query1)) { + ps1.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps1 = ps1.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan1 = pps1.optimizeQuery(); + assertTrue("plan1 should be VectorIndexScanPlan", plan1 instanceof VectorIndexScanPlan); + cost1 = plan1.getCost(); + } + + Cost cost4; + try (PreparedStatement ps4 = conn.prepareStatement(query4)) { + ps4.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps4 = ps4.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan4 = pps4.optimizeQuery(); + assertTrue("plan4 should be VectorIndexScanPlan", plan4 instanceof VectorIndexScanPlan); + cost4 = plan4.getCost(); + } + + Cost exactCost; + try (PreparedStatement psExact = conn.prepareStatement(queryExact)) { + psExact.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement ppsExact = psExact.unwrap(PhoenixPreparedStatement.class); + QueryPlan planExact = ppsExact.optimizeQuery(); + assertFalse("planExact should not be VectorIndexScanPlan", + planExact instanceof VectorIndexScanPlan); + exactCost = planExact.getCost(); + } + + assertFalse("cost1 should be known", cost1.isUnknown()); + assertFalse("cost4 should be known", cost4.isUnknown()); + assertFalse("exactCost should be known", exactCost.isUnknown()); + + double ratioProbe = cost1.getIo() / cost4.getIo(); + assertTrue("cost(probe=1)/cost(probe=4) (" + ratioProbe + ") should be within [0.18, 0.35]", + ratioProbe >= 0.18 && ratioProbe <= 0.35); + + double ratioExact = cost4.getIo() / exactCost.getIo(); + assertTrue("cost(probe=4)/exactCost (" + ratioExact + ") should be within [0.75, 1.25]", + ratioExact >= 0.75 && ratioExact <= 1.25); + } + } + + @Test + public void testLookupsAreCosted() throws Exception { + try (Connection conn = getCostBasedConnection()) { + // A covered query reads only the index and does no data table lookups. + String queryCovered = "SELECT /*+ VECTOR_PROBE_COUNT(1) */ ID, CATEGORY FROM " + tableName + + " WHERE CATEGORY = 'catA' ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + // A deferred projection reads DESCRIPTION from the data table only for the top-k rows. + String queryProjLookup = "SELECT /*+ VECTOR_PROBE_COUNT(1) */ ID, DESCRIPTION FROM " + + tableName + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + // A filter on an uncovered column looks up every candidate row before the top-k step. + String queryFilterLookup = "SELECT /*+ VECTOR_PROBE_COUNT(1) */ ID, CATEGORY FROM " + + tableName + " WHERE DESCRIPTION = 'desc_k0_r0001' ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + + Cost costCovered; + try (PreparedStatement ps = conn.prepareStatement(queryCovered)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("plan should be VectorIndexScanPlan", plan instanceof VectorIndexScanPlan); + assertFalse("Covered query should not have filter lookup", + VectorIndexTestUtil.isFilterTimeLookup(plan)); + costCovered = VectorSearchUtil.getCost(plan); + } + + Cost costProj; + try (PreparedStatement ps = conn.prepareStatement(queryProjLookup)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("Projection-time query should read the projection for the final rows", + VectorIndexTestUtil.isDeferredProjection(plan)); + costProj = VectorSearchUtil.getCost(plan); + } + + Cost costFilter; + try (PreparedStatement ps = conn.prepareStatement(queryFilterLookup)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("Filter-time query should join every candidate", + VectorIndexTestUtil.isFilterTimeLookup(plan)); + costFilter = VectorSearchUtil.getCost(plan); + } + + assertFalse("costCovered should be known", costCovered.isUnknown()); + assertFalse("costProj should be known", costProj.isUnknown()); + assertFalse("costFilter should be known", costFilter.isUnknown()); + + assertTrue( + "cost(covered) [" + costCovered.getIo() + + "] should be strictly less than cost(projectionLookup) [" + costProj.getIo() + "]", + costCovered.getIo() < costProj.getIo()); + assertTrue( + "cost(projectionLookup) [" + costProj.getIo() + + "] should be strictly less than cost(filterLookup) [" + costFilter.getIo() + "]", + costProj.getIo() < costFilter.getIo()); + } + } + + @Test + public void testVectorIndexWithoutStatsNotDiscarded() throws Exception { + try (Connection conn = getCostBasedConnection()) { + String dataTable = generateUniqueName(); + String vecIndex = generateUniqueName(); + + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE TABLE " + dataTable + + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 4), CATEGORY VARCHAR)"); + } + + // Load the data table with vectors in four clusters. + Random rng = new Random(42); + String upsert = "UPSERT INTO " + dataTable + " (ID, V, CATEGORY) VALUES (?, ?, ?)"; + try (PreparedStatement ps = conn.prepareStatement(upsert)) { + for (int k = 0; k < 4; k++) { + float[] center = l2Centroids.get(k); + for (int i = 0; i < 200; i++) { + String id = String.format("t3_k%d_r%04d", k, i); + float[] v = new float[] { center[0] + (float) (rng.nextGaussian() * 0.1), + center[1] + (float) (rng.nextGaussian() * 0.1), + center[2] + (float) (rng.nextGaussian() * 0.1), + center[3] + (float) (rng.nextGaussian() * 0.1) }; + ps.setString(1, id); + ps.setArray(2, conn.createArrayOf("FLOAT", new Float[] { v[0], v[1], v[2], v[3] })); + ps.setString(3, "catA"); + ps.addBatch(); + } + ps.executeBatch(); + } + conn.commit(); + } + + // Collect statistics on the data table only, so that the index has no guideposts. + try (Statement stmt = conn.createStatement()) { + stmt.execute("UPDATE STATISTICS " + dataTable); + } + + // Create and activate the vector index, but do not collect statistics for it. + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE VECTOR INDEX " + vecIndex + " ON " + dataTable + " (V) " + + "INCLUDE (CATEGORY) WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + VectorIndexTestUtil.activateWithKnownCentroids(conn, dataTable, vecIndex, l2Centroids); + + // The cost-based optimizer must estimate the index cost from the data table statistics. + String query = + "SELECT ID, CATEGORY FROM " + dataTable + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(query)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("Optimized plan should be VectorIndexScanPlan despite index having no stats", + plan instanceof VectorIndexScanPlan); + assertFalse("Plan cost should not be unknown", plan.getCost().isUnknown()); + } + } + } + + @Test + public void testCostBasedChoiceBetweenTwoEligibleVectorIndexes() throws Exception { + try (Connection conn = getCostBasedConnection()) { + String dataTable = generateUniqueName(); + String idxCovering = generateUniqueName(); + String idxNonCovering = generateUniqueName(); + + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE TABLE " + dataTable + + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 4), DESCRIPTION VARCHAR)"); + stmt.execute("CREATE VECTOR INDEX " + idxCovering + " ON " + dataTable + " (V) " + + "INCLUDE (DESCRIPTION) WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + stmt.execute("CREATE VECTOR INDEX " + idxNonCovering + " ON " + dataTable + " (V) " + + "WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + + VectorIndexTestUtil.activateWithKnownCentroids(conn, dataTable, idxCovering, l2Centroids); + VectorIndexTestUtil.activateWithKnownCentroids(conn, dataTable, idxNonCovering, l2Centroids); + + Random rng = new Random(42); + String upsert = "UPSERT INTO " + dataTable + " (ID, V, DESCRIPTION) VALUES (?, ?, ?)"; + try (PreparedStatement ps = conn.prepareStatement(upsert)) { + for (int k = 0; k < 4; k++) { + float[] center = l2Centroids.get(k); + for (int i = 0; i < 3; i++) { + String id = String.format("t4_k%d_r%04d", k, i); + float[] v = new float[] { center[0] + (float) (rng.nextGaussian() * 0.1), + center[1] + (float) (rng.nextGaussian() * 0.1), + center[2] + (float) (rng.nextGaussian() * 0.1), + center[3] + (float) (rng.nextGaussian() * 0.1) }; + ps.setString(1, id); + ps.setArray(2, conn.createArrayOf("FLOAT", new Float[] { v[0], v[1], v[2], v[3] })); + ps.setString(3, "desc_" + id); + ps.addBatch(); + } + ps.executeBatch(); + } + conn.commit(); + } + + try (Statement stmt = conn.createStatement()) { + stmt.execute("UPDATE STATISTICS " + dataTable); + stmt.execute("UPDATE STATISTICS " + idxCovering); + stmt.execute("UPDATE STATISTICS " + idxNonCovering); + } + + String defaultQuery = + "SELECT ID, DESCRIPTION FROM " + dataTable + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(defaultQuery)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("Optimized plan should be VectorIndexScanPlan", + plan instanceof VectorIndexScanPlan); + assertEquals(idxCovering, plan.getTableRef().getTable().getTableName().getString()); + } + + String hintedQuery = "SELECT /*+ INDEX(" + dataTable + " " + idxNonCovering + + ") */ ID, DESCRIPTION FROM " + dataTable + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(hintedQuery)) { + ps.setArray(1, conn.createArrayOf("FLOAT", queryVectorBoxed)); + PhoenixPreparedStatement pps = ps.unwrap(PhoenixPreparedStatement.class); + QueryPlan plan = pps.optimizeQuery(); + assertTrue("Non-covering index should read the projection for the final rows", + VectorIndexTestUtil.isDeferredProjection(plan)); + assertEquals(idxNonCovering, + VectorIndexTestUtil.vectorPlan(plan).getTableRef().getTable().getTableName().getString()); + } + } + } +} diff --git a/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfQueryIT.java b/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfQueryIT.java index 7f46dbbfa9..2225bf850f 100644 --- a/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfQueryIT.java +++ b/phoenix-core/src/it/java/org/apache/phoenix/end2end/VectorIvfQueryIT.java @@ -43,13 +43,20 @@ import java.util.Set; import org.apache.hadoop.hbase.client.Delete; import org.apache.hadoop.hbase.client.Table; import org.apache.hadoop.hbase.util.Bytes; +import org.apache.phoenix.compile.ExplainPlanAttributes; import org.apache.phoenix.compile.QueryPlan; +import org.apache.phoenix.execute.VectorIndexScanPlan; +import org.apache.phoenix.expression.LiteralExpression; import org.apache.phoenix.hbase.index.IndexRegionObserver; import org.apache.phoenix.jdbc.PhoenixConnection; import org.apache.phoenix.jdbc.PhoenixPreparedStatement; import org.apache.phoenix.jdbc.PhoenixStatement; +import org.apache.phoenix.optimize.OptimizerReasons; +import org.apache.phoenix.optimize.VectorSearchUtil; +import org.apache.phoenix.query.explain.ExplainPlanTestUtil; import org.apache.phoenix.schema.PTable; import org.apache.phoenix.schema.types.PVarchar; +import org.apache.phoenix.schema.types.PVectorFloat; import org.apache.phoenix.util.PhoenixRuntime; import org.apache.phoenix.util.QueryUtil; import org.apache.phoenix.util.ReadOnlyProps; @@ -1846,6 +1853,233 @@ public class VectorIvfQueryIT extends ParallelStatsDisabledIT { } } + private static final List<float[]> STEP_50_CENTROIDS = + Arrays.asList(new float[] { 0.0f, 0.0f, 0.0f, 0.0f }, new float[] { 50.0f, 0.0f, 0.0f, 0.0f }, + new float[] { 100.0f, 0.0f, 0.0f, 0.0f }, new float[] { 150.0f, 0.0f, 0.0f, 0.0f }); + + @Test + public void testStaticOrderingPrefersCoveringVectorIndex() throws Exception { + try (Connection conn = DriverManager.getConnection(getUrl())) { + String t = generateUniqueName(); + String idxCovering = generateUniqueName(); + String idxNonCovering = generateUniqueName(); + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE TABLE " + t + + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 4), CATEGORY VARCHAR, DESCRIPTION VARCHAR)"); + // Create the non-covering index first. Then the result shows the static plan order, not + // the order of index creation. + stmt.execute("CREATE VECTOR INDEX " + idxNonCovering + " ON " + t + " (V) " + + "WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + stmt.execute("CREATE VECTOR INDEX " + idxCovering + " ON " + t + " (V) " + + "INCLUDE (DESCRIPTION) WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + VectorIndexTestUtil.activateWithKnownCentroids(conn, t, idxCovering, STEP_50_CENTROIDS); + VectorIndexTestUtil.activateWithKnownCentroids(conn, t, idxNonCovering, STEP_50_CENTROIDS); + + String query = "SELECT ID, DESCRIPTION FROM " + t + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(query)) { + ps.setArray(1, conn.createArrayOf("FLOAT", new Float[] { 1.0f, 0.0f, 0.0f, 0.0f })); + QueryPlan plan = ps.unwrap(PhoenixPreparedStatement.class).optimizeQuery(); + assertTrue("Expected the covering index to answer the query alone", + plan instanceof VectorIndexScanPlan); + assertEquals(idxCovering, plan.getTableRef().getTable().getTableName().getString()); + } + assertEquals(OptimizerReasons.RULE_NEAREST_NEIGHBOR_INDEX, + ExplainPlanTestUtil.getExplainAttributes(conn, "SELECT ID, DESCRIPTION FROM " + t + + " ORDER BY L2_DISTANCE(V, ARRAY[1.0, 0.0, 0.0, 0.0]) LIMIT 5").getIndexRule()); + } + } + + @Test + public void testStaticOrderingPrefersVectorIndexOverRegularIndex() throws Exception { + try (Connection conn = DriverManager.getConnection(getUrl())) { + String t = generateUniqueName(); + String regularIdx = generateUniqueName(); + String vectorIdx = generateUniqueName(); + try (Statement stmt = conn.createStatement()) { + stmt.execute("CREATE TABLE " + t + + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 4), CATEGORY VARCHAR, DESCRIPTION VARCHAR)"); + stmt.execute( + "CREATE INDEX " + regularIdx + " ON " + t + " (CATEGORY) INCLUDE (V, DESCRIPTION)"); + stmt.execute("CREATE VECTOR INDEX " + vectorIdx + " ON " + t + " (V) " + + "INCLUDE (CATEGORY, DESCRIPTION) WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + VectorIndexTestUtil.activateWithKnownCentroids(conn, t, vectorIdx, STEP_50_CENTROIDS); + + Map<String, float[]> scienceVectors = new LinkedHashMap<>(); + String upsert = "UPSERT INTO " + t + " (ID, V, CATEGORY, DESCRIPTION) VALUES (?, ?, ?, ?)"; + try (PreparedStatement ps = conn.prepareStatement(upsert)) { + for (int i = 0; i < 20; i++) { + String id = "r" + i; + float[] v = new float[] { (float) i, 0.0f, 0.0f, 0.0f }; + String cat = (i % 2 == 0) ? "science" : "art"; + if ("science".equals(cat)) { + scienceVectors.put(id, v); + } + ps.setString(1, id); + ps.setArray(2, conn.createArrayOf("FLOAT", new Float[] { v[0], v[1], v[2], v[3] })); + ps.setString(3, cat); + ps.setString(4, "desc_" + id); + ps.executeUpdate(); + } + conn.commit(); + } + + // Without statistics, the static order puts the vector index plan before a regular index + // plan that binds the leading key column. + String defaultQuery = + "SELECT ID FROM " + t + " WHERE CATEGORY = 'science' ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(defaultQuery)) { + ps.setArray(1, conn.createArrayOf("FLOAT", new Float[] { 0.0f, 0.0f, 0.0f, 0.0f })); + QueryPlan plan = ps.unwrap(PhoenixPreparedStatement.class).optimizeQuery(); + assertTrue("Default plan should be VectorIndexScanPlan", + plan instanceof VectorIndexScanPlan); + assertEquals(vectorIdx, plan.getTableRef().getTable().getTableName().getString()); + } + + // An explicit INDEX hint selects the regular index, which gives an exact search. + String hintedQuery = "SELECT /*+ INDEX(" + t + " " + regularIdx + ") */ ID FROM " + t + + " WHERE CATEGORY = 'science' ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + List<String> expected = VectorIndexTestUtil.bruteForceTopK(scienceVectors, + new float[] { 0.0f, 0.0f, 0.0f, 0.0f }, "L2", 5); + try (PreparedStatement ps = conn.prepareStatement(hintedQuery)) { + ps.setArray(1, conn.createArrayOf("FLOAT", new Float[] { 0.0f, 0.0f, 0.0f, 0.0f })); + QueryPlan plan = ps.unwrap(PhoenixPreparedStatement.class).optimizeQuery(); + assertFalse(VectorSearchUtil.usesVectorIndex(plan)); + assertEquals(regularIdx, plan.getTableRef().getTable().getTableName().getString()); + List<String> results = new ArrayList<>(); + try (ResultSet rs = ps.executeQuery()) { + while (rs.next()) { + results.add(rs.getString(1)); + } + } + assertEquals(expected, results); + } + + // The USE_DATA_OVER_INDEX_TABLE hint puts vector index plans after all other candidates. + String dataHinted = "SELECT /*+ USE_DATA_OVER_INDEX_TABLE */ ID FROM " + t + + " WHERE CATEGORY = 'science' ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PreparedStatement ps = conn.prepareStatement(dataHinted)) { + ps.setArray(1, conn.createArrayOf("FLOAT", new Float[] { 0.0f, 0.0f, 0.0f, 0.0f })); + QueryPlan plan = ps.unwrap(PhoenixPreparedStatement.class).optimizeQuery(); + assertFalse(VectorSearchUtil.usesVectorIndex(plan)); + } + } + } + + @Test + public void testExplainDistinguishesLookupStrategies() throws Exception { + try (Connection conn = DriverManager.getConnection(getUrl())) { + Float[] q = new Float[] { 50.2f, 0.1f, -0.1f, 0.05f }; + + // Covered: the index answers the query without data table access. + String covered = explain(conn, "SELECT ID, CATEGORY FROM " + fixL2Covered.tableName + + " WHERE CATEGORY = 'science' ORDER BY L2_DISTANCE(V, ?) LIMIT 5", q); + assertTrue(covered, covered.contains("CLIENT PROBING 2 OF 4 CENTROIDS (L2)")); + assertFalse(covered, covered.contains("SERVER MERGE")); + assertFalse(covered, covered.contains("SKIP-SCAN-JOIN")); + + // Deferred projection: the index ranks rows, then the top-k rows come from the data table. + String projection = explain(conn, "SELECT ID, DESCRIPTION FROM " + fixL2Covered.tableName + + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5", q); + assertTrue(projection, projection.contains("CLIENT PROBING 2 OF 4 CENTROIDS (L2)")); + assertTrue(projection, projection.contains("SKIP-SCAN-JOIN")); + assertFalse(projection, projection.contains("SERVER MERGE")); + + // Filter-time join: every candidate row joins to the data table before the top-k step. + String filter = explain(conn, "SELECT ID, DESCRIPTION FROM " + fixL2Uncovered.tableName + + " WHERE CATEGORY = 'science' ORDER BY L2_DISTANCE(V, ?) LIMIT 5", q); + assertTrue(filter, filter.contains("CLIENT PROBING 2 OF 4 CENTROIDS (L2)")); + assertTrue(filter, filter.contains("SERVER MERGE")); + assertFalse(filter, filter.contains("SKIP-SCAN-JOIN")); + } + } + + private static String explain(Connection conn, String query, Float[] q) throws Exception { + try (PreparedStatement ps = conn.prepareStatement("EXPLAIN " + query)) { + ps.setArray(1, conn.createArrayOf("FLOAT", q)); + try (ResultSet rs = ps.executeQuery()) { + return QueryUtil.getExplainPlan(rs); + } + } + } + + @Test + public void testStructuredExplainAttributes() throws Exception { + try (Connection conn = DriverManager.getConnection(getUrl())) { + Float[] q = new Float[] { 50.2f, 0.1f, -0.1f, 0.05f }; + String query = "SELECT /*+ VECTOR_PROBE_COUNT(3) */ ID, CATEGORY FROM " + + fixL2Covered.tableName + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PhoenixPreparedStatement pps = + conn.prepareStatement(query).unwrap(PhoenixPreparedStatement.class)) { + pps.setArray(1, conn.createArrayOf("FLOAT", q)); + ExplainPlanAttributes attrs = + pps.optimizeQuery().getExplainPlan().getPlanStepsAsAttributes(); + assertEquals(Integer.valueOf(3), attrs.getVectorProbeCount()); + assertEquals(Integer.valueOf(4), attrs.getVectorCentroidCount()); + assertEquals("L2", attrs.getVectorDistanceMetric()); + assertTrue(attrs.isVectorSearch()); + } + + // A full scan plan does not set the vector probe attributes. + String exact = "SELECT /*+ NO_INDEX */ ID FROM " + fixL2Covered.tableName + + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5"; + try (PhoenixPreparedStatement pps = + conn.prepareStatement(exact).unwrap(PhoenixPreparedStatement.class)) { + pps.setArray(1, conn.createArrayOf("FLOAT", q)); + ExplainPlanAttributes attrs = + pps.optimizeQuery().getExplainPlan().getPlanStepsAsAttributes(); + assertEquals(null, attrs.getVectorProbeCount()); + assertEquals(null, attrs.getVectorDistanceMetric()); + } + } + } + + @Test + public void testVectorLiteralAbbreviationInExplain() throws Exception { + try (Connection conn = DriverManager.getConnection(getUrl())) { + String tableName = generateUniqueName(); + String indexName = generateUniqueName(); + try (Statement stmt = conn.createStatement()) { + stmt.execute( + "CREATE TABLE " + tableName + " (ID VARCHAR NOT NULL PRIMARY KEY, V VECTOR(FLOAT, 128))"); + stmt.execute("CREATE VECTOR INDEX " + indexName + " ON " + tableName + " (V) " + + "WITH (algorithm = 'IVF', metric = 'L2', lists = 4, sample_size = 100)"); + } + List<float[]> centroids = new ArrayList<>(); + for (int k = 0; k < 4; k++) { + float[] c = new float[128]; + c[0] = k * 10.0f; + centroids.add(c); + } + VectorIndexTestUtil.activateWithKnownCentroids(conn, tableName, indexName, centroids); + + float[] queryVector = new float[128]; + queryVector[0] = 1.0f; + queryVector[99] = 77.125f; + Float[] boxedQ = new Float[128]; + for (int i = 0; i < 128; i++) { + boxedQ[i] = queryVector[i]; + } + String plan = explain(conn, + "SELECT ID FROM " + tableName + " ORDER BY L2_DISTANCE(V, ?) LIMIT 5", boxedQ); + String serverTopLine = null; + for (String line : plan.split("\\r?\\n")) { + if (line.contains("SERVER TOP-")) { + serverTopLine = line.trim(); + } + } + assertNotNull(plan, serverTopLine); + assertTrue(serverTopLine, serverTopLine.length() < 256); + assertTrue(serverTopLine, serverTopLine.contains("VECTOR(FLOAT, 128)[1.0, 0.0")); + assertFalse(serverTopLine, serverTopLine.contains("77.125")); + + // The expression string must stay exact, because persistence and DDL use it. + assertTrue(LiteralExpression.newConstant(queryVector, PVectorFloat.INSTANCE).toString() + .contains("77.125")); + } + } + /** * Tests writes and a vector top-K query through a view with a WHERE clause. The view inherits the * vector index of the table under a view-specific name. That inherited index must assign and diff --git a/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorPlanOrderingTest.java b/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorPlanOrderingTest.java new file mode 100644 index 0000000000..e3897a35b8 --- /dev/null +++ b/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorPlanOrderingTest.java @@ -0,0 +1,101 @@ +/* + * 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.phoenix.optimize; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.when; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import org.apache.phoenix.compile.QueryPlan; +import org.apache.phoenix.compile.StatementContext; +import org.apache.phoenix.execute.HashJoinPlan; +import org.apache.phoenix.execute.HashJoinPlan.SubPlan; +import org.apache.phoenix.execute.VectorIndexScanPlan; +import org.junit.Test; + +/** Unit tests for the precedence rules that order vector index plans in the query optimizer. */ +public class VectorPlanOrderingTest { + + private static final int NO_HINT = 1; + private static final int DATA_HINTED = -1; + + private static VectorIndexScanPlan vectorScan(boolean joinsEveryCandidate) { + VectorIndexScanPlan plan = mock(VectorIndexScanPlan.class); + StatementContext context = mock(StatementContext.class); + when(context.isUncoveredIndex()).thenReturn(joinsEveryCandidate); + when(plan.getContext()).thenReturn(context); + return plan; + } + + private static QueryPlan deferredProjection() { + HashJoinPlan plan = mock(HashJoinPlan.class); + SubPlan subPlan = mock(SubPlan.class); + QueryPlan scan = vectorScan(false); + when(subPlan.getInnerPlan()).thenReturn(scan); + when(plan.getSubPlans()).thenReturn(new SubPlan[] { subPlan }); + return plan; + } + + @Test + public void testPlansWithoutVectorIndexAreTied() { + // Plans that do not read a vector index compare as equal, so the default order stays. + assertEquals(0, + QueryOptimizer.compareVectorPlans(mock(QueryPlan.class), mock(QueryPlan.class), NO_HINT)); + assertEquals(0, + QueryOptimizer.compareVectorPlans(mock(QueryPlan.class), mock(QueryPlan.class), DATA_HINTED)); + } + + @Test + public void testVectorIndexPlanPrecedesOtherPlansUnlessDataHinted() { + QueryPlan vector = vectorScan(false); + QueryPlan other = mock(QueryPlan.class); + assertTrue(QueryOptimizer.compareVectorPlans(vector, other, NO_HINT) < 0); + assertTrue(QueryOptimizer.compareVectorPlans(other, vector, NO_HINT) > 0); + assertTrue(QueryOptimizer.compareVectorPlans(vector, other, DATA_HINTED) > 0); + assertTrue(QueryOptimizer.compareVectorPlans(other, vector, DATA_HINTED) < 0); + } + + @Test + public void testVectorPlansOrderedByDataTableReads() { + QueryPlan covered = vectorScan(false); + QueryPlan deferred = deferredProjection(); + QueryPlan joined = vectorScan(true); + assertEquals(0, VectorSearchUtil.getLookupRank(covered)); + assertEquals(1, VectorSearchUtil.getLookupRank(deferred)); + assertEquals(2, VectorSearchUtil.getLookupRank(joined)); + List<QueryPlan> plans = new ArrayList<>(Arrays.asList(joined, deferred, covered)); + plans.sort((p1, p2) -> QueryOptimizer.compareVectorPlans(p1, p2, NO_HINT)); + assertEquals(Arrays.asList(covered, deferred, joined), plans); + } + + @Test + public void testOrderingIsTransitiveUnderDataHint() { + // Under the data table hint, vector index plans sort after all other candidates. The order + // must stay transitive, without cycles. + QueryPlan vector = vectorScan(false); + QueryPlan index = mock(QueryPlan.class); + QueryPlan data = mock(QueryPlan.class); + assertTrue(QueryOptimizer.compareVectorPlans(index, vector, DATA_HINTED) < 0); + assertTrue(QueryOptimizer.compareVectorPlans(data, vector, DATA_HINTED) < 0); + assertEquals(0, QueryOptimizer.compareVectorPlans(index, data, DATA_HINTED)); + } +} diff --git a/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorSearchUtilTest.java b/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorSearchUtilTest.java index bfd5025117..55ce4e80e6 100644 --- a/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorSearchUtilTest.java +++ b/phoenix-core/src/test/java/org/apache/phoenix/optimize/VectorSearchUtilTest.java @@ -25,6 +25,7 @@ import static org.junit.Assert.assertSame; import static org.junit.Assert.assertTrue; import java.sql.DriverManager; +import java.util.Arrays; import org.apache.phoenix.compile.ColumnResolver; import org.apache.phoenix.compile.FromCompiler; import org.apache.phoenix.compile.GroupByCompiler.GroupBy; @@ -32,6 +33,8 @@ import org.apache.phoenix.compile.OrderByCompiler; import org.apache.phoenix.compile.OrderByCompiler.OrderBy; import org.apache.phoenix.compile.RowProjector; import org.apache.phoenix.compile.StatementContext; +import org.apache.phoenix.expression.Expression; +import org.apache.phoenix.expression.LiteralExpression; import org.apache.phoenix.expression.function.CosineDistanceFunction; import org.apache.phoenix.expression.function.InnerProductDistanceFunction; import org.apache.phoenix.expression.function.L2DistanceFunction; @@ -46,6 +49,8 @@ import org.apache.phoenix.parse.ParseNode; import org.apache.phoenix.parse.SQLParser; import org.apache.phoenix.parse.SelectStatement; import org.apache.phoenix.query.BaseConnectionlessQueryTest; +import org.apache.phoenix.schema.types.PVectorDouble; +import org.apache.phoenix.schema.types.PVectorFloat; import org.junit.Test; /** Unit tests that find vector search queries and extract their descriptors. */ @@ -651,4 +656,21 @@ public class VectorSearchUtilTest extends BaseConnectionlessQueryTest { } } + @Test + public void testExplainAbbreviatesQueryVector() throws Exception { + float[] longVector = new float[10]; + for (int i = 0; i < longVector.length; i++) { + longVector[i] = i + 0.5f; + } + Expression column = LiteralExpression.newConstant(null, PVectorFloat.INSTANCE); + String rendered = VectorSearchUtil.toExplainString(new L2DistanceFunction( + Arrays.asList(column, LiteralExpression.newConstant(longVector, PVectorFloat.INSTANCE)))); + assertEquals( + "L2_DISTANCE(null, VECTOR(FLOAT, 10)[0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, ...])", + rendered); + String shortVector = + VectorSearchUtil.toExplainString(new CosineDistanceFunction(Arrays.asList(column, + LiteralExpression.newConstant(new double[] { 1.0, 2.0 }, PVectorDouble.INSTANCE)))); + assertEquals("COSINE_DISTANCE(null, VECTOR(DOUBLE, 2)[1.0, 2.0])", shortVector); + } } diff --git a/phoenix-core/src/test/java/org/apache/phoenix/query/explain/ExplainPlanTest.java b/phoenix-core/src/test/java/org/apache/phoenix/query/explain/ExplainPlanTest.java index 700d26c354..c915020174 100644 --- a/phoenix-core/src/test/java/org/apache/phoenix/query/explain/ExplainPlanTest.java +++ b/phoenix-core/src/test/java/org/apache/phoenix/query/explain/ExplainPlanTest.java @@ -1837,6 +1837,9 @@ public class ExplainPlanTest extends BaseConnectionlessQueryTest { n.putNull("hint"); n.putNull("serverSortedBy"); n.put("vectorSearch", false); + n.putNull("vectorProbeCount"); + n.putNull("vectorCentroidCount"); + n.putNull("vectorDistanceMetric"); n.putNull("explainScanType"); n.putNull("tableName"); n.putNull("keyRanges");
