>From Preetham Poluparthi <[email protected]>: Preetham Poluparthi has submitted this change. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/20475?usp=email )
Change subject: [ASTERIXDB-3635][COMP] Change costing to account for index-only plans ...................................................................... [ASTERIXDB-3635][COMP] Change costing to account for index-only plans - user model changes: no - storage format changes: no - interface changes: no Ext-ref: MB-68371 Change-Id: Ifc835f8c4f8386e7b290c68891b4274f1ae87cd5 Reviewed-on: https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/20475 Tested-by: Jenkins <[email protected]> Reviewed-by: Ali Alsuliman <[email protected]> Integration-Tests: Jenkins <[email protected]> --- M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorConditionParser.java M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorScanPlanNode.java 7 files changed, 185 insertions(+), 85 deletions(-) Approvals: Ali Alsuliman: Looks good to me, approved Jenkins: Verified; Verified Anon. E. Moose #1000171: diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java index 2d97258..ce6a0d4 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java @@ -105,6 +105,33 @@ } } + public static class IndexAccessInfo { + public final IAccessMethod accessMethod; + public final Index index; + public boolean isIndexOnlyPlan = false; + + public IndexAccessInfo(IAccessMethod accessMethod, Index index) { + this.accessMethod = accessMethod; + this.index = index; + } + + public boolean isIndexOnlyPlan() { + return isIndexOnlyPlan; + } + + public void setIsIndexOnlyPlan(boolean isIndexOnlyPlan) { + this.isIndexOnlyPlan = isIndexOnlyPlan; + } + + public IAccessMethod getAccessMethod() { + return accessMethod; + } + + public Index getIndex() { + return index; + } + } + @Override public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException { @@ -202,9 +229,9 @@ * Simply picks the first index that it finds. TODO: Improve this decision * process by making it more systematic. */ - protected Pair<IAccessMethod, Index> chooseBestIndex(Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, - List<Pair<IAccessMethod, Index>> chosenIndexes) { - List<Pair<IAccessMethod, Index>> list = new ArrayList<>(); + protected IntroduceSelectAccessMethodRule.IndexAccessInfo chooseBestIndex( + Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, List<IndexAccessInfo> chosenIndexes) { + List<IntroduceSelectAccessMethodRule.IndexAccessInfo> list = new ArrayList<>(); chooseAllIndexes(analyzedAMs, list); chosenIndexes.addAll(list); return list.isEmpty() ? null : list.get(0); @@ -219,7 +246,7 @@ * LENGTH_PARTITIONED_WORD_INVIX || LENGTH_PARTITIONED_NGRAM_INVIX] */ protected void chooseAllIndexes(Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, - List<Pair<IAccessMethod, Index>> result) { + List<IntroduceSelectAccessMethodRule.IndexAccessInfo> result) { // Use variables (fields) to the index types map to check which type of indexes are applied for the vars. Map<List<Pair<Integer, Integer>>, List<IndexType>> resultVarsToIndexTypesMap = new HashMap<>(); Iterator<Map.Entry<IAccessMethod, AccessMethodAnalysisContext>> amIt = analyzedAMs.entrySet().iterator(); @@ -265,13 +292,15 @@ List<IndexType> appliedIndexTypes = resultVarsToIndexTypesMap.get(indexEntry.getValue()); if (!appliedIndexTypes.contains(indexType)) { appliedIndexTypes.add(indexType); - result.add(new Pair<>(chosenAccessMethod, chosenIndex)); + result.add(new IntroduceSelectAccessMethodRule.IndexAccessInfo(chosenAccessMethod, + chosenIndex)); } } else { List<IndexType> addedIndexTypes = new ArrayList<>(); addedIndexTypes.add(indexType); resultVarsToIndexTypesMap.put(indexEntry.getValue(), addedIndexTypes); - result.add(new Pair<>(chosenAccessMethod, chosenIndex)); + result.add( + new IntroduceSelectAccessMethodRule.IndexAccessInfo(chosenAccessMethod, chosenIndex)); } } } diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java index 09cf843..88468dd 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java @@ -147,7 +147,7 @@ afterJoinRefs = new ArrayList<>(); // Recursively checks the given plan whether the desired pattern exists in it. // If so, try to optimize the plan. - List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>(); + List<IndexAccessInfo> chosenIndexes = new ArrayList<>(); Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>(); boolean planTransformed = checkAndApplyJoinTransformation(opRef, context, false, chosenIndexes, analyzedAMs); @@ -166,7 +166,7 @@ } public boolean checkApplicable(Mutable<ILogicalOperator> opRef, IOptimizationContext context, - List<Pair<IAccessMethod, Index>> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, + List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, IIndexProvider indexProvider) throws AlgebricksException { clear(); setMetadataIndexDeclarations(context, indexProvider); @@ -266,7 +266,7 @@ * if it is not already optimized. */ protected boolean checkAndApplyJoinTransformation(Mutable<ILogicalOperator> opRef, IOptimizationContext context, - boolean checkApplicableOnly, List<Pair<IAccessMethod, Index>> chosenIndexes, + boolean checkApplicableOnly, List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) throws AlgebricksException { AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue(); boolean joinFoundAndOptimizationApplied; @@ -405,7 +405,7 @@ // We are going to use indexes from the inner branch. // If no index is available, then we stop here. - Pair<IAccessMethod, Index> chosenIndex = chooseBestIndex(analyzedAMs, chosenIndexes); + IndexAccessInfo chosenIndex = chooseBestIndex(analyzedAMs, chosenIndexes); if (chosenIndex == null) { context.addToDontApplySet(this, joinOp); continueCheck = false; @@ -422,7 +422,7 @@ } // Applies the plan transformation using chosen index. - AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenIndex.first); + AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenIndex.getAccessMethod()); IAlgebricksConstantValue leftOuterMissingValue = isLeftOuterJoin ? ((LeftOuterJoinOperator) joinOp).getMissingValue() : null; @@ -449,7 +449,7 @@ isLeftOuterJoinWithSpecialGroupBy = false; } - Dataset indexDataset = analysisCtx.getDatasetFromIndexDatasetMap(chosenIndex.second); + Dataset indexDataset = analysisCtx.getDatasetFromIndexDatasetMap(chosenIndex.getIndex()); // We assume that the left subtree is the outer branch and the right subtree // is the inner branch. This assumption holds true since we only use an index @@ -464,8 +464,8 @@ } // Finally, tries to apply plan transformation using the chosen index. - boolean res = chosenIndex.first.applyJoinPlanTransformation(afterJoinRefs, joinRef, leftSubTree, - rightSubTree, chosenIndex.second, analysisCtx, context, isLeftOuterJoin, + boolean res = chosenIndex.getAccessMethod().applyJoinPlanTransformation(afterJoinRefs, joinRef, + leftSubTree, rightSubTree, chosenIndex.getIndex(), analysisCtx, context, isLeftOuterJoin, isLeftOuterJoinWithSpecialGroupBy, leftOuterMissingValue); // If the plan transformation is successful, we don't need to traverse the plan @@ -525,7 +525,7 @@ private boolean rewriteLocallyAndTransform(Mutable<ILogicalOperator> opRef, IOptimizationContext context, IIntroduceAccessMethodRuleLocalRewrite<AbstractBinaryJoinOperator> rewriter, boolean checkApplicableOnly, - List<Pair<IAccessMethod, Index>> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) + List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) throws AlgebricksException { AbstractBinaryJoinOperator joinRewrite = rewriter.createOperator(joinOp, context); boolean transformationResult = false; diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java index d3efcac..b246ff2 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java @@ -40,6 +40,7 @@ import org.apache.commons.lang3.mutable.MutableObject; import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException; import org.apache.hyracks.algebricks.common.utils.Pair; +import org.apache.hyracks.algebricks.common.utils.Quadruple; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator; import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext; @@ -167,7 +168,7 @@ afterSelectRefs = new ArrayList<>(); // Recursively check the given plan whether the desired pattern exists in it. // If so, try to optimize the plan. - List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>(); + List<IndexAccessInfo> chosenIndexes = new ArrayList<>(); Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = null; boolean planTransformed = checkAndApplyTheSelectTransformation(opRef, context, false, chosenIndexes, analyzedAMs); @@ -187,7 +188,7 @@ } public boolean checkApplicable(Mutable<ILogicalOperator> opRef, IOptimizationContext context, - List<Pair<IAccessMethod, Index>> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, + List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, IIndexProvider indexProvider) throws AlgebricksException { clear(); setMetadataIndexDeclarations(context, indexProvider); @@ -247,7 +248,7 @@ * intersects them using INTERSECT operator to guide to the common primary-index search. * This method assumes that there are two or more secondary indexes in the given path. */ - private boolean intersectAllSecondaryIndexes(List<Pair<IAccessMethod, Index>> chosenIndexes, + private boolean intersectAllSecondaryIndexes(List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, IOptimizationContext context) throws AlgebricksException { if (chosenIndexes.size() == 1) { @@ -258,22 +259,22 @@ Mutable<ILogicalExpression> conditionRef = selectOp.getCondition(); List<ILogicalOperator> subRoots = new ArrayList<>(); - for (Pair<IAccessMethod, Index> pair : chosenIndexes) { - AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(pair.first); + for (IndexAccessInfo pair : chosenIndexes) { + AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(pair.getAccessMethod()); boolean retainInput = AccessMethodUtils.retainInputs(subTree.getDataSourceVariables(), subTree.getDataSourceRef().getValue(), afterSelectRefs); boolean requiresBroadcast = subTree.getDataSourceRef().getValue().getInputs().get(0).getValue() .getExecutionMode() == ExecutionMode.UNPARTITIONED; - ILogicalOperator subRoot = pair.first.createIndexSearchPlan(afterSelectRefs, selectRef, conditionRef, - subTree.getAssignsAndUnnestsRefs(), subTree, null, pair.second, analysisCtx, retainInput, false, - requiresBroadcast, context, null, null); + ILogicalOperator subRoot = pair.getAccessMethod().createIndexSearchPlan(afterSelectRefs, selectRef, + conditionRef, subTree.getAssignsAndUnnestsRefs(), subTree, null, pair.getIndex(), analysisCtx, + retainInput, false, requiresBroadcast, context, null, null); if (subRoot == null) { return false; } subRoots.add(subRoot); } // Connect each secondary index utilization plan to a common intersect operator. - Index idx = chosenIndexes.get(0).getSecond(); + Index idx = chosenIndexes.get(0).getIndex(); ILogicalOperator primaryUnnestOp = connectAll2ndarySearchPlanWithIntersect(subRoots, context, idx); subTree.getDataSourceRef().setValue(primaryUnnestOp); @@ -288,10 +289,10 @@ * null otherwise * @throws AlgebricksException */ - private Pair<IAccessMethod, Index> fetchPrimaryIndexAmongChosenIndexes( - List<Pair<IAccessMethod, Index>> chosenIndexes) throws AlgebricksException { - Optional<Pair<IAccessMethod, Index>> primaryIndex = - chosenIndexes.stream().filter(pair -> pair.second.isPrimaryIndex()).findFirst(); + private IndexAccessInfo fetchPrimaryIndexAmongChosenIndexes(List<IndexAccessInfo> chosenIndexes) + throws AlgebricksException { + Optional<IndexAccessInfo> primaryIndex = + chosenIndexes.stream().filter(pair -> pair.getIndex().isPrimaryIndex()).findFirst(); if (primaryIndex.isPresent()) { return primaryIndex.get(); } @@ -382,7 +383,7 @@ return true; } - protected void removeSmallerPrefixIndexes(List<Pair<IAccessMethod, Index>> indexes) throws CompilationException { + protected void removeSmallerPrefixIndexes(List<IndexAccessInfo> indexes) throws CompilationException { int len = indexes.size(); int i, j; Index indexI, indexJ; @@ -396,16 +397,16 @@ for (i = 0; i < len - 1; i++) { if (include[i]) { - IAccessMethod ami = indexes.get(i).first; - indexI = indexes.get(i).second; + IAccessMethod ami = indexes.get(i).getAccessMethod(); + indexI = indexes.get(i).getIndex(); DatasetConfig.IndexType typeI = indexI.getIndexType(); fieldNamesI = findKeyFieldNames(indexI); for (j = i + 1; j < len; j++) { if (include[j]) { - IAccessMethod amj = indexes.get(j).first; + IAccessMethod amj = indexes.get(j).getAccessMethod(); if (ami == amj) { // should be the same accessMethods - indexJ = indexes.get(j).second; + indexJ = indexes.get(j).getIndex(); DatasetConfig.IndexType typeJ = indexJ.getIndexType(); if (typeI == typeJ) { fieldNamesJ = findKeyFieldNames(indexJ); @@ -438,7 +439,7 @@ * if it is not already optimized. */ protected boolean checkAndApplyTheSelectTransformation(Mutable<ILogicalOperator> opRef, - IOptimizationContext context, boolean checkApplicableOnly, List<Pair<IAccessMethod, Index>> chosenIndexes, + IOptimizationContext context, boolean checkApplicableOnly, List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) throws AlgebricksException { AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue(); boolean selectFoundAndOptimizationApplied; @@ -554,6 +555,18 @@ context.addToDontApplySet(this, selectRef.getValue()); return false; } + + for (IndexAccessInfo indexAccessInfo : chosenIndexes) { + AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(indexAccessInfo.getAccessMethod()); + boolean isIndexOnlyPlan = false; + boolean requireVerificationAfterSIdxSearch = false; + Quadruple<Boolean, Boolean, Boolean, Boolean> indexOnlyPlanInfo = + new Quadruple<>(isIndexOnlyPlan, false, requireVerificationAfterSIdxSearch, false); + AccessMethodUtils.indexOnlyPlanCheck(afterSelectRefs, selectRef, subTree, null, + indexAccessInfo.getIndex(), analysisCtx, context, indexOnlyPlanInfo, false); + indexAccessInfo.setIsIndexOnlyPlan(indexOnlyPlanInfo.getFirst()); + } + if (checkApplicableOnly) { return true; } @@ -561,23 +574,23 @@ // Apply plan transformation using chosen index. boolean res; // Primary index applicable? - Pair<IAccessMethod, Index> chosenPrimaryIndex = fetchPrimaryIndexAmongChosenIndexes(chosenIndexes); + IndexAccessInfo chosenPrimaryIndex = fetchPrimaryIndexAmongChosenIndexes(chosenIndexes); if (chosenPrimaryIndex != null) { - AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenPrimaryIndex.first); - res = chosenPrimaryIndex.first.applySelectPlanTransformation(afterSelectRefs, selectRef, subTree, - chosenPrimaryIndex.second, analysisCtx, context); + AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenPrimaryIndex.getAccessMethod()); + res = chosenPrimaryIndex.getAccessMethod().applySelectPlanTransformation(afterSelectRefs, selectRef, + subTree, chosenPrimaryIndex.getIndex(), analysisCtx, context); context.addToDontApplySet(this, selectRef.getValue()); } else if (chosenIndexes.size() == 1) { // Index-only plan possible? // Gets the analysis context for the given index. - AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenIndexes.get(0).first); + AccessMethodAnalysisContext analysisCtx = analyzedAMs.get(chosenIndexes.get(0).getAccessMethod()); // Finds the field name of each variable in the sub-tree. fillFieldNamesInTheSubTree(subTree, context); // Finally, try to apply plan transformation using chosen index. - res = chosenIndexes.get(0).first.applySelectPlanTransformation(afterSelectRefs, selectRef, subTree, - chosenIndexes.get(0).second, analysisCtx, context); + res = chosenIndexes.get(0).getAccessMethod().applySelectPlanTransformation(afterSelectRefs, + selectRef, subTree, chosenIndexes.get(0).getIndex(), analysisCtx, context); context.addToDontApplySet(this, selectRef.getValue()); } else { // Multiple secondary indexes applicable? @@ -613,7 +626,7 @@ private boolean rewriteLocallyAndTransform(Mutable<ILogicalOperator> opRef, IOptimizationContext context, IIntroduceAccessMethodRuleLocalRewrite<SelectOperator> rewriter, boolean checkApplicableOnly, - List<Pair<IAccessMethod, Index>> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) + List<IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) throws AlgebricksException { SelectOperator selectRewrite = rewriter.createOperator(selectOp, context); @@ -624,7 +637,7 @@ transformationResult = checkAndApplyTheSelectTransformation(selectRuleInput, context, checkApplicableOnly, chosenIndexes, analyzedAMs); } else { - List<Pair<IAccessMethod, Index>> chosenIndexes2 = new ArrayList<>(); + List<IndexAccessInfo> chosenIndexes2 = new ArrayList<>(); Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs2 = null; transformationResult = checkAndApplyTheSelectTransformation(selectRuleInput, context, checkApplicableOnly, chosenIndexes2, analyzedAMs2); 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 76c091f..36377db 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 @@ -44,6 +44,7 @@ import org.apache.asterix.om.functions.BuiltinFunctions; import org.apache.asterix.optimizer.cost.Cost; import org.apache.asterix.optimizer.cost.ICost; +import org.apache.asterix.optimizer.rules.am.AbstractIntroduceAccessMethodRule; import org.apache.asterix.optimizer.rules.am.AccessMethodAnalysisContext; import org.apache.asterix.optimizer.rules.am.IAccessMethod; import org.apache.asterix.optimizer.rules.am.IOptimizableFuncExpr; @@ -54,7 +55,6 @@ import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException; import org.apache.hyracks.algebricks.common.utils.Pair; import org.apache.hyracks.algebricks.common.utils.Quadruple; -import org.apache.hyracks.algebricks.common.utils.Triple; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator; import org.apache.hyracks.algebricks.core.algebra.base.LogicalExpressionTag; @@ -110,7 +110,7 @@ private List<Integer> applicableJoinConditions; protected ILogicalOperator leafInput; protected Index.SampleIndexDetails idxDetails; - private List<Triple<Index, Double, AbstractFunctionCallExpression>> IndexCostInfo; + private List<IndexCostInfo> indexCostInfoList; // The triple above is : Index, selectivity, and the index expression protected static int NO_JN = -1; private static int NO_CARDS = -2; @@ -657,10 +657,46 @@ return andExpr; } + static class IndexCostInfo { + private final Index index; + private double selectivity; + private final AbstractFunctionCallExpression afce; + private final boolean isIndexOnly; + + public IndexCostInfo(Index index, double selectivity, AbstractFunctionCallExpression afce, + boolean isIndexOnly) { + this.index = index; + this.selectivity = selectivity; + this.afce = afce; + this.isIndexOnly = isIndexOnly; + } + + public AbstractFunctionCallExpression getAfce() { + return afce; + } + + public Index getIndex() { + return index; + } + + public double getSelectivity() { + return selectivity; + } + + public void setSelectivity(double selectivity) { + this.selectivity = selectivity; + } + + public boolean isIndexOnly() { + return isIndexOnly; + } + } + private void setSkipIndexAnnotationsForUnusedIndexes() { - for (int i = 0; i < IndexCostInfo.size(); i++) { - if (IndexCostInfo.get(i).second == -1.0) { - AbstractFunctionCallExpression afce = IndexCostInfo.get(i).third; + + for (IndexCostInfo indexCostInfo : indexCostInfoList) { + if (indexCostInfo.getSelectivity() == -1.0) { + AbstractFunctionCallExpression afce = indexCostInfo.getAfce(); SkipSecondaryIndexSearchExpressionAnnotation skipAnno = joinEnum.findSkipIndexHint(afce); Collection<String> indexNames = new HashSet<>(); if (skipAnno != null && skipAnno.getIndexNames() != null) { @@ -669,9 +705,9 @@ if (indexNames.isEmpty()) { // this index has to be skipped, so find the corresponding expression EnumerateJoinsRule.setAnnotation(afce, SkipSecondaryIndexSearchExpressionAnnotation - .newInstance(Collections.singleton(IndexCostInfo.get(i).first.getIndexName()))); + .newInstance(Collections.singleton(indexCostInfo.getIndex().getIndexName()))); } else { - indexNames.add(IndexCostInfo.get(i).first.getIndexName()); + indexNames.add(indexCostInfo.getIndex().getIndexName()); EnumerateJoinsRule.setAnnotation(afce, SkipSecondaryIndexSearchExpressionAnnotation.newInstance(indexNames)); } @@ -680,11 +716,12 @@ } private void costAndChooseIndexPlans(ILogicalOperator leafInput, - Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) throws AlgebricksException { + Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, + List<IntroduceSelectAccessMethodRule.IndexAccessInfo> chosenIndexes) throws AlgebricksException { SelectOperator selOp; double sel; - List<Triple<Index, Double, AbstractFunctionCallExpression>> IndexCostInfo = new ArrayList<>(); + List<IndexCostInfo> indexCostInfoList = new ArrayList<>(); for (Map.Entry<IAccessMethod, AccessMethodAnalysisContext> amEntry : analyzedAMs.entrySet()) { AccessMethodAnalysisContext analysisCtx = amEntry.getValue(); Iterator<Map.Entry<Index, List<Pair<Integer, Integer>>>> indexIt = @@ -718,11 +755,15 @@ chosenIndex.getIndexType().equals(DatasetConfig.IndexType.ARRAY) || joinEnum.findUnnestOp(selOp)); } - IndexCostInfo.add(new Triple<>(chosenIndex, sel, afce)); + + boolean isIndexOnlyApplicable = chosenIndexes.stream() + .filter(indexAccessInfo -> indexAccessInfo.getIndex().equals(chosenIndex)).findFirst() + .map(AbstractIntroduceAccessMethodRule.IndexAccessInfo::isIndexOnlyPlan).orElse(false); + indexCostInfoList.add(new IndexCostInfo(chosenIndex, sel, afce, isIndexOnlyApplicable)); } } - this.IndexCostInfo = IndexCostInfo; - if (IndexCostInfo.size() > 0) { + this.indexCostInfoList = indexCostInfoList; + if (!indexCostInfoList.isEmpty()) { buildIndexPlans(); } setSkipIndexAnnotationsForUnusedIndexes(); @@ -733,30 +774,40 @@ PlanNode pn; double ic, dc, tc, oc; // for debugging - List<Triple<Index, Double, AbstractFunctionCallExpression>> mandatoryIndexesInfo = new ArrayList<>(); - List<Triple<Index, Double, AbstractFunctionCallExpression>> optionalIndexesInfo = new ArrayList<>(); + List<IndexCostInfo> mandatoryIndexesInfo = new ArrayList<>(); + List<IndexCostInfo> optionalIndexesInfo = new ArrayList<>(); double sel = 1.0; - for (int i = 0; i < IndexCostInfo.size(); i++) { - if (joinEnum.findUseIndexHint(IndexCostInfo.get(i).third)) { - mandatoryIndexesInfo.add(IndexCostInfo.get(i)); + for (IndexCostInfo indexCostInfo : indexCostInfoList) { + + if (joinEnum.findUseIndexHint(indexCostInfo.getAfce())) { + mandatoryIndexesInfo.add(indexCostInfo); } else { - optionalIndexesInfo.add(IndexCostInfo.get(i)); + optionalIndexesInfo.add(indexCostInfo); } + } ICost indexCosts = this.joinEnum.getCostHandle().zeroCost(); ICost totalCost = this.joinEnum.getCostHandle().zeroCost(); ICost dataScanCost; + boolean isIndexOnlyApplicable = true; + int numSecondaryIndexesUsed = 0; + if (mandatoryIndexesInfo.size() > 0) { for (int i = 0; i < mandatoryIndexesInfo.size(); i++) { - ICost cost = joinEnum.getCostMethodsHandle().costIndexScan(this, mandatoryIndexesInfo.get(i).second); - if ((mandatoryIndexesInfo.get(i).first.getIndexType() == DatasetConfig.IndexType.ARRAY)) { + ICost cost = joinEnum.getCostMethodsHandle().costIndexScan(this, + mandatoryIndexesInfo.get(i).getSelectivity()); + if ((mandatoryIndexesInfo.get(i).getIndex().getIndexType() == DatasetConfig.IndexType.ARRAY)) { cost = cost.costAdd(cost); // double the cost for arrays. } + + isIndexOnlyApplicable = isIndexOnlyApplicable && mandatoryIndexesInfo.get(i).isIndexOnly(); + numSecondaryIndexesUsed += mandatoryIndexesInfo.get(i).getIndex().isPrimaryIndex() ? 0 : 1; + indexCosts = indexCosts.costAdd(cost); // a running tally - sel *= mandatoryIndexesInfo.get(i).second; + sel *= mandatoryIndexesInfo.get(i).getSelectivity(); } dataScanCost = joinEnum.getCostMethodsHandle().costIndexDataScan(this, sel); totalCost = indexCosts.costAdd(dataScanCost); // this is the total cost of using the mandatory costs. This cost cannot be skipped. @@ -764,28 +815,35 @@ ICost opCost = totalCost; if (optionalIndexesInfo.size() > 0) { - optionalIndexesInfo.sort(Comparator.comparingDouble(o -> o.second)); + optionalIndexesInfo.sort(Comparator.comparingDouble(o -> o.getSelectivity())); for (int i = 0; i < optionalIndexesInfo.size(); i++) { - ICost cost = joinEnum.getCostMethodsHandle().costIndexScan(this, optionalIndexesInfo.get(i).second); - if ((optionalIndexesInfo.get(i).first.getIndexType() == DatasetConfig.IndexType.ARRAY)) { + ICost cost = joinEnum.getCostMethodsHandle().costIndexScan(this, + optionalIndexesInfo.get(i).getSelectivity()); + if ((optionalIndexesInfo.get(i).getIndex().getIndexType() == DatasetConfig.IndexType.ARRAY)) { cost = cost.costAdd(cost); // double the cost for arrays. } indexCosts = indexCosts.costAdd(cost); - sel *= optionalIndexesInfo.get(i).second; + sel *= optionalIndexesInfo.get(i).getSelectivity(); dataScanCost = joinEnum.getCostMethodsHandle().costIndexDataScan(this, sel); opCost = indexCosts.costAdd(dataScanCost); tc = totalCost.computeTotalCost(); + + isIndexOnlyApplicable = isIndexOnlyApplicable && optionalIndexesInfo.get(i).isIndexOnly(); + numSecondaryIndexesUsed += optionalIndexesInfo.get(i).getIndex().isPrimaryIndex() ? 0 : 1; + if (tc > 0.0) { if (opCost.costGT(totalCost)) { // we can stop here since additional indexes are not useful for (int j = i; j < optionalIndexesInfo.size(); j++) { - optionalIndexesInfo.get(j).second = -1.0; + optionalIndexesInfo.get(j).setSelectivity(-1.0); } opCost = totalCost; break; } } else { - totalCost = indexCosts.costAdd(dataScanCost); + if (!isIndexOnlyApplicable || numSecondaryIndexesUsed > 1) { + totalCost = indexCosts.costAdd(dataScanCost); + } } } } @@ -793,7 +851,7 @@ // opCost is now the total cost of the indexes chosen along with the associated data scan cost. if (opCost.costGT(this.cheapestPlanCost) && level > joinEnum.cboFullEnumLevel) { // cheapest plan cost is the data scan cost. for (int j = 0; j < optionalIndexesInfo.size(); j++) { - optionalIndexesInfo.get(j).second = -1.0; // remove all indexes from consideration. + optionalIndexesInfo.get(j).setSelectivity(-1.0); // remove all indexes from consideration. } } @@ -881,7 +939,7 @@ protected void addIndexAccessPlans(ILogicalOperator leafInput, IIndexProvider indexProvider) throws AlgebricksException { IntroduceSelectAccessMethodRule tmp = new IntroduceSelectAccessMethodRule(); - List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>(); + List<IntroduceSelectAccessMethodRule.IndexAccessInfo> chosenIndexes = new ArrayList<>(); Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>(); while (combineDoubleSelectsBeforeSubPlans(leafInput)); @@ -894,7 +952,7 @@ chosenIndexes, analyzedAMs, indexProvider); restoreSelExprs(selExprs, selOpers); if (index_access_possible) { - costAndChooseIndexPlans(leafInput, analyzedAMs); + costAndChooseIndexPlans(leafInput, analyzedAMs, chosenIndexes); } } else { restoreSelExprs(selExprs, selOpers); @@ -943,8 +1001,9 @@ } private boolean nestedLoopsApplicable(ILogicalExpression joinExpr, boolean outerJoin, - List<Pair<IAccessMethod, Index>> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, - IIndexProvider indexProvider) throws AlgebricksException { + List<AbstractIntroduceAccessMethodRule.IndexAccessInfo> chosenIndexes, + Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, IIndexProvider indexProvider) + throws AlgebricksException { if (joinExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) { return false; @@ -1006,7 +1065,8 @@ } private boolean NLJoinApplicable(JoinNode leftJn, JoinNode rightJn, boolean outerJoin, - ILogicalExpression nestedLoopJoinExpr, List<Pair<IAccessMethod, Index>> chosenIndexes, + ILogicalExpression nestedLoopJoinExpr, + List<AbstractIntroduceAccessMethodRule.IndexAccessInfo> chosenIndexes, Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs, IIndexProvider indexProvider) throws AlgebricksException { @@ -1149,7 +1209,7 @@ return PlanNode.NO_PLAN; } - List<Pair<IAccessMethod, Index>> chosenIndexes = new ArrayList<>(); + List<AbstractIntroduceAccessMethodRule.IndexAccessInfo> chosenIndexes = new ArrayList<>(); Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new TreeMap<>(); if (!NLJoinApplicable(leftJn, rightJn, outerJoin, nestedLoopJoinExpr, chosenIndexes, analyzedAMs, indexProvider)) { diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java index 2cf9130..109e006 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/PlanNode.java @@ -25,7 +25,6 @@ import org.apache.asterix.metadata.entities.Index; import org.apache.asterix.optimizer.cost.ICost; import org.apache.hyracks.algebricks.common.utils.Pair; -import org.apache.hyracks.algebricks.common.utils.Triple; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression; import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator; import org.apache.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression; @@ -286,9 +285,8 @@ numHintsUsed = 0; } - protected void setScanAndHintInfo(ScanMethod scanMethod, - List<Triple<Index, Double, AbstractFunctionCallExpression>> mandatoryIndexesInfo, - List<Triple<Index, Double, AbstractFunctionCallExpression>> optionalIndexesInfo) { + protected void setScanAndHintInfo(ScanMethod scanMethod, List<JoinNode.IndexCostInfo> mandatoryIndexesInfo, + List<JoinNode.IndexCostInfo> optionalIndexesInfo) { setScanMethod(scanMethod); if (mandatoryIndexesInfo.size() > 0) { indexHint = true; @@ -298,9 +296,9 @@ // So seeing if only index is used. if (optionalIndexesInfo.size() + mandatoryIndexesInfo.size() == 1) { if (optionalIndexesInfo.size() == 1) { - indexUsed = optionalIndexesInfo.get(0).first; + indexUsed = optionalIndexesInfo.get(0).getIndex(); } else { - indexUsed = mandatoryIndexesInfo.get(0).first; + indexUsed = mandatoryIndexesInfo.get(0).getIndex(); } } } diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorConditionParser.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorConditionParser.java index 3e0e5c4..d7404e0 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorConditionParser.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorConditionParser.java @@ -191,7 +191,7 @@ return unnestFilterConditions; } - private static List<ScanFilterCondition> extractPrimitiveConditions(ILogicalOperator op, + public static List<ScanFilterCondition> extractPrimitiveConditions(ILogicalOperator op, IOptimizationContext context) throws AlgebricksException { List<ExprRef> filterExprRefs = new ArrayList<>(); ILogicalOperator tempOp = op; diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorScanPlanNode.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorScanPlanNode.java index f4a15d8..964a80b 100644 --- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorScanPlanNode.java +++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/indexadvisor/AdvisorScanPlanNode.java @@ -39,7 +39,7 @@ filter = AdvisorConditionParser.parseScanNode(op, context); } - private DataSourceScanOperator findDatascanOperator(ILogicalOperator op) { + public static DataSourceScanOperator findDatascanOperator(ILogicalOperator op) { while (op.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN) { op = op.getInputs().get(0).getValue(); } -- To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/20475?usp=email To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email Gerrit-MessageType: merged Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Change-Id: Ifc835f8c4f8386e7b290c68891b4274f1ae87cd5 Gerrit-Change-Number: 20475 Gerrit-PatchSet: 7 Gerrit-Owner: Preetham Poluparthi <[email protected]> Gerrit-Reviewer: Ali Alsuliman <[email protected]> Gerrit-Reviewer: Anon. E. Moose #1000171 Gerrit-Reviewer: Jenkins <[email protected]> Gerrit-Reviewer: Preetham Poluparthi <[email protected]> Gerrit-Reviewer: [email protected]
