[ASTERIXDB-3195][COMP] Add query properties to enumerate all plans.
- user model changes: yes
- storage format changes: no
- interface changes: no
Details:
Add query properties to enumerate all plans without pruning during
join enumeration. This will help debug issues when good plans may
have been pruned off due to incorrect costing or other reasons.
New properties are:
- "cbofullenumlevel": Num of levels to do full join and plan enumeration.
- "cbocpenum": true/false for cartesian product plan generation.
Change-Id: I7c3e23cc2d24ff16cb026d4fbb317445db1b2574
Reviewed-on: https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/17756
Integration-Tests: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Vijay Sarathy <vijay.sarathy@couchbase.com>
Reviewed-by: Ali Alsuliman <ali.al.solaiman@gmail.com>
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/compiler/provider/SqlppCompilationProvider.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/compiler/provider/SqlppCompilationProvider.java
index 4ad888c..66da5e2 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/compiler/provider/SqlppCompilationProvider.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/compiler/provider/SqlppCompilationProvider.java
@@ -37,6 +37,7 @@
import org.apache.asterix.optimizer.base.FuzzyUtils;
import org.apache.asterix.optimizer.rules.DisjunctivePredicateToJoinRule;
import org.apache.asterix.optimizer.rules.SetAsterixPhysicalOperatorsRule;
+import org.apache.asterix.optimizer.rules.cbo.JoinEnum;
import org.apache.asterix.optimizer.rules.util.EquivalenceClassUtils;
import org.apache.asterix.translator.SqlppExpressionToPlanTranslator;
import org.apache.asterix.translator.SqlppExpressionToPlanTranslatorFactory;
@@ -92,6 +93,7 @@
SqlppExpressionToPlanTranslator.REWRITE_IN_AS_OR_OPTION, "hash_merge", "output-record-type",
DisjunctivePredicateToJoinRule.REWRITE_OR_AS_JOIN_OPTION,
SetAsterixPhysicalOperatorsRule.REWRITE_ATTEMPT_BATCH_ASSIGN,
- EquivalenceClassUtils.REWRITE_INTERNAL_QUERYUID_PK, SqlppQueryRewriter.SQL_COMPAT_OPTION));
+ EquivalenceClassUtils.REWRITE_INTERNAL_QUERYUID_PK, SqlppQueryRewriter.SQL_COMPAT_OPTION,
+ JoinEnum.CBO_FULL_ENUM_LEVEL_KEY, JoinEnum.CBO_CP_ENUM_KEY));
}
}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
index e7a620d..f23af33 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
@@ -29,8 +29,11 @@
import org.apache.asterix.common.annotations.IndexedNLJoinExpressionAnnotation;
import org.apache.asterix.common.annotations.SecondaryIndexSearchPreferenceAnnotation;
+import org.apache.asterix.common.exceptions.AsterixException;
+import org.apache.asterix.common.exceptions.ErrorCode;
import org.apache.asterix.metadata.declared.DataSource;
import org.apache.asterix.metadata.declared.DataSourceId;
+import org.apache.asterix.metadata.declared.MetadataProvider;
import org.apache.asterix.metadata.entities.Index;
import org.apache.asterix.om.base.AOrderedList;
import org.apache.asterix.om.base.IAObject;
@@ -69,6 +72,7 @@
import org.apache.hyracks.algebricks.core.algebra.prettyprint.IPlanPrettyPrinter;
import org.apache.hyracks.algebricks.core.algebra.util.OperatorManipulationUtil;
import org.apache.hyracks.algebricks.core.rewriter.base.PhysicalOptimizationConfig;
+import org.apache.hyracks.control.common.config.OptionTypes;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
@@ -76,6 +80,14 @@
private static final Logger LOGGER = LogManager.getLogger();
+ // Number of levels to do full join and plan enumeration
+ public static final String CBO_FULL_ENUM_LEVEL_KEY = "cbofullenumlevel";
+ private static final int CBO_FULL_ENUM_LEVEL_DEFAULT = 0;
+
+ // Mode for cartesian product plan generation during join and plan enumeration
+ public static final String CBO_CP_ENUM_KEY = "cbocpenum";
+ private static final boolean CBO_CP_ENUM_DEFAULT = true;
+
protected List<JoinCondition> joinConditions; // "global" list of join conditions
protected List<PlanNode> allPlans; // list of all plans
protected JoinNode[] jnArray; // array of all join nodes
@@ -92,6 +104,9 @@
protected PhysicalOptimizationConfig physOptConfig;
protected boolean cboMode;
protected boolean cboTestMode;
+
+ protected int cboFullEnumLevel;
+ protected boolean cboCPEnumMode;
protected int numberOfTerms;
protected AbstractLogicalOperator op;
protected boolean connectedJoinGraph;
@@ -107,7 +122,8 @@
List<Pair<EmptyTupleSourceOperator, DataSourceScanOperator>> emptyTupleAndDataSourceOps,
Map<EmptyTupleSourceOperator, ILogicalOperator> joinLeafInputsHashMap,
Map<DataSourceScanOperator, EmptyTupleSourceOperator> dataSourceEmptyTupleHashMap,
- List<ILogicalOperator> internalEdges, List<ILogicalOperator> joinOps, IOptimizationContext context) {
+ List<ILogicalOperator> internalEdges, List<ILogicalOperator> joinOps, IOptimizationContext context)
+ throws AsterixException {
this.singleDatasetPreds = new ArrayList<>();
this.joinConditions = new ArrayList<>();
this.internalEdges = new ArrayList<>();
@@ -115,6 +131,8 @@
this.numberOfTerms = numberOfFromTerms;
this.cboMode = cboMode;
this.cboTestMode = cboTestMode;
+ this.cboFullEnumLevel = getCBOFullEnumLevel(context);
+ this.cboCPEnumMode = getCBOCPEnumMode(context);
this.connectedJoinGraph = true;
this.optCtx = context;
this.physOptConfig = context.getPhysicalOptimizationConfig();
@@ -141,6 +159,24 @@
}
}
+ private int getCBOFullEnumLevel(IOptimizationContext context) throws AsterixException {
+ MetadataProvider mdp = (MetadataProvider) context.getMetadataProvider();
+
+ String valueInQuery = mdp.getProperty(CBO_FULL_ENUM_LEVEL_KEY);
+ try {
+ return valueInQuery == null ? CBO_FULL_ENUM_LEVEL_DEFAULT
+ : OptionTypes.POSITIVE_INTEGER.parse(valueInQuery);
+ } catch (IllegalArgumentException e) {
+ throw AsterixException.create(ErrorCode.COMPILATION_BAD_QUERY_PARAMETER_VALUE, CBO_FULL_ENUM_LEVEL_KEY, 1,
+ "");
+ }
+ }
+
+ private boolean getCBOCPEnumMode(IOptimizationContext context) {
+ MetadataProvider mdp = (MetadataProvider) context.getMetadataProvider();
+ return mdp.getBooleanProperty(CBO_CP_ENUM_KEY, CBO_CP_ENUM_DEFAULT);
+ }
+
public List<JoinCondition> getJoinConditions() {
return joinConditions;
}
@@ -618,11 +654,11 @@
JoinNode jnIJ = jnArray[addPlansToThisJn];
jnIJ.jnArrayIndex = addPlansToThisJn;
jnIJ.addMultiDatasetPlans(jnI, jnJ);
- if (forceJoinOrderMode) {
+ if (forceJoinOrderMode && level > cboFullEnumLevel) {
break;
}
}
- if (forceJoinOrderMode) {
+ if (forceJoinOrderMode && level > cboFullEnumLevel) {
break;
}
}
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 1f9300d..4418e4b 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
@@ -283,12 +283,13 @@
public int addSingleDatasetPlans() {
List<PlanNode> allPlans = joinEnum.allPlans;
ICost opCost, totalCost;
-
+ PlanNode pn, cheapestPlan;
opCost = joinEnum.getCostMethodsHandle().costFullScan(this);
totalCost = opCost;
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || opCost.costLT(this.cheapestPlanCost)) {
+ boolean forceEnum = level <= joinEnum.cboFullEnumLevel;
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || opCost.costLT(this.cheapestPlanCost) || forceEnum) {
// for now just add one plan
- PlanNode pn = new PlanNode(allPlans.size(), joinEnum);
+ pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.datasetName = this.datasetNames.get(0);
pn.correspondingEmptyTupleSourceOp = this.correspondingEmptyTupleSourceOp;
@@ -301,10 +302,15 @@
pn.totalCost = totalCost;
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
- return this.cheapestPlanIndex;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
+ return pn.allPlansIndex;
}
return PlanNode.NO_PLAN;
}
@@ -312,12 +318,14 @@
protected void buildIndexPlan(boolean forceIndexPlan) {
List<PlanNode> allPlans = joinEnum.allPlans;
ICost opCost, totalCost;
-
+ PlanNode pn, cheapestPlan;
opCost = joinEnum.getCostMethodsHandle().costIndexScan(this);
totalCost = opCost;
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || opCost.costLT(this.cheapestPlanCost) || forceIndexPlan) {
+ boolean forceEnum = level <= joinEnum.cboFullEnumLevel;
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || opCost.costLT(this.cheapestPlanCost) || forceIndexPlan
+ || forceEnum) {
// for now just add one plan
- PlanNode pn = new PlanNode(allPlans.size(), joinEnum);
+ pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.datasetName = this.datasetNames.get(0);
pn.correspondingEmptyTupleSourceOp = this.correspondingEmptyTupleSourceOp;
@@ -327,12 +335,18 @@
pn.planIndexes[1] = PlanNode.NO_PLAN; // There ane no plans below this plan.
pn.opCost = opCost;
pn.scanOp = PlanNode.ScanMethod.INDEX_SCAN;
+ pn.indexHint = forceIndexPlan;
pn.totalCost = totalCost;
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
}
}
@@ -463,50 +477,49 @@
}
}
- protected int buildHashJoinPlan(JoinNode leftJn, JoinNode rightJn, ILogicalExpression hashJoinExpr,
- HashJoinExpressionAnnotation hintHashJoin) {
+ protected int buildHashJoinPlan(JoinNode leftJn, JoinNode rightJn, PlanNode leftPlan, PlanNode rightPlan,
+ ILogicalExpression hashJoinExpr, HashJoinExpressionAnnotation hintHashJoin) {
List<PlanNode> allPlans = joinEnum.allPlans;
- PlanNode pn;
+ PlanNode pn, cheapestPlan;
ICost hjCost, leftExchangeCost, rightExchangeCost, childCosts, totalCost;
this.leftJn = leftJn;
this.rightJn = rightJn;
- int leftPlan = leftJn.cheapestPlanIndex;
- int rightPlan = rightJn.cheapestPlanIndex;
if (hashJoinExpr == null || hashJoinExpr == ConstantExpression.TRUE) {
return PlanNode.NO_PLAN;
}
- if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_LEFTDEEP)
- && !leftJn.IsBaseLevelJoinNode()) {
+ if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_LEFTDEEP) && !leftJn.IsBaseLevelJoinNode()
+ && level > joinEnum.cboFullEnumLevel) {
return PlanNode.NO_PLAN;
}
if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_RIGHTDEEP)
- && !rightJn.IsBaseLevelJoinNode()) {
+ && !rightJn.IsBaseLevelJoinNode() && level > joinEnum.cboFullEnumLevel) {
return PlanNode.NO_PLAN;
}
- if (rightJn.cardinality * rightJn.size <= leftJn.cardinality * leftJn.size || hintHashJoin != null
- || joinEnum.forceJoinOrderMode
- || !joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_ZIGZAG)) {
+ boolean forceEnum = hintHashJoin != null || joinEnum.forceJoinOrderMode
+ || !joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_ZIGZAG)
+ || level <= joinEnum.cboFullEnumLevel;
+
+ if (rightJn.cardinality * rightJn.size <= leftJn.cardinality * leftJn.size || forceEnum) {
// We want to build with the smaller side.
hjCost = joinEnum.getCostMethodsHandle().costHashJoin(this);
leftExchangeCost = joinEnum.getCostMethodsHandle().computeHJProbeExchangeCost(this);
rightExchangeCost = joinEnum.getCostMethodsHandle().computeHJBuildExchangeCost(this);
- childCosts = allPlans.get(leftPlan).totalCost.costAdd(allPlans.get(rightPlan).totalCost);
+ childCosts = allPlans.get(leftPlan.allPlansIndex).totalCost
+ .costAdd(allPlans.get(rightPlan.allPlansIndex).totalCost);
totalCost = hjCost.costAdd(leftExchangeCost).costAdd(rightExchangeCost).costAdd(childCosts);
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost)) {
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost) || forceEnum) {
pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.jnIndexes[0] = leftJn.jnArrayIndex;
pn.jnIndexes[1] = rightJn.jnArrayIndex;
- pn.planIndexes[0] = leftPlan;
- pn.planIndexes[1] = rightPlan;
+ pn.planIndexes[0] = leftPlan.allPlansIndex;
+ pn.planIndexes[1] = rightPlan.allPlansIndex;
pn.joinOp = PlanNode.JoinMethod.HYBRID_HASH_JOIN; // need to check that all the conditions have equality predicates ONLY.
- if (hintHashJoin != null) {
- hintHashJoin.setBuildSide(HashJoinExpressionAnnotation.BuildSide.RIGHT);
- }
+ pn.joinHint = hintHashJoin;
pn.side = HashJoinExpressionAnnotation.BuildSide.RIGHT;
pn.joinExpr = hashJoinExpr;
pn.opCost = hjCost;
@@ -514,61 +527,64 @@
pn.leftExchangeCost = leftExchangeCost;
pn.rightExchangeCost = rightExchangeCost;
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
- return this.cheapestPlanIndex;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
+ return pn.allPlansIndex;
}
}
return PlanNode.NO_PLAN;
}
- protected int buildBroadcastHashJoinPlan(JoinNode leftJn, JoinNode rightJn, ILogicalExpression hashJoinExpr,
- BroadcastExpressionAnnotation hintBroadcastHashJoin) {
+ protected int buildBroadcastHashJoinPlan(JoinNode leftJn, JoinNode rightJn, PlanNode leftPlan, PlanNode rightPlan,
+ ILogicalExpression hashJoinExpr, BroadcastExpressionAnnotation hintBroadcastHashJoin) {
List<PlanNode> allPlans = joinEnum.allPlans;
- PlanNode pn;
+ PlanNode pn, cheapestPlan;
ICost bcastHjCost, leftExchangeCost, rightExchangeCost, childCosts, totalCost;
this.leftJn = leftJn;
this.rightJn = rightJn;
- int leftPlan = leftJn.cheapestPlanIndex;
- int rightPlan = rightJn.cheapestPlanIndex;
if (hashJoinExpr == null || hashJoinExpr == ConstantExpression.TRUE) {
return PlanNode.NO_PLAN;
}
- if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_LEFTDEEP)
- && !leftJn.IsBaseLevelJoinNode()) {
+ if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_LEFTDEEP) && !leftJn.IsBaseLevelJoinNode()
+ && level > joinEnum.cboFullEnumLevel) {
return PlanNode.NO_PLAN;
}
if (joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_RIGHTDEEP)
- && !rightJn.IsBaseLevelJoinNode()) {
+ && !rightJn.IsBaseLevelJoinNode() && level > joinEnum.cboFullEnumLevel) {
return PlanNode.NO_PLAN;
}
- if (rightJn.cardinality * rightJn.size <= leftJn.cardinality * leftJn.size || hintBroadcastHashJoin != null
- || joinEnum.forceJoinOrderMode
- || !joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_ZIGZAG)) {
+ boolean forceEnum = hintBroadcastHashJoin != null || joinEnum.forceJoinOrderMode
+ || !joinEnum.queryPlanShape.equals(AlgebricksConfig.QUERY_PLAN_SHAPE_ZIGZAG)
+ || level <= joinEnum.cboFullEnumLevel;
+ if (rightJn.cardinality * rightJn.size <= leftJn.cardinality * leftJn.size || forceEnum) {
// We want to broadcast and build with the smaller side.
bcastHjCost = joinEnum.getCostMethodsHandle().costBroadcastHashJoin(this);
leftExchangeCost = joinEnum.getCostHandle().zeroCost();
rightExchangeCost = joinEnum.getCostMethodsHandle().computeBHJBuildExchangeCost(this);
- childCosts = allPlans.get(leftPlan).totalCost.costAdd(allPlans.get(rightPlan).totalCost);
+ childCosts = allPlans.get(leftPlan.allPlansIndex).totalCost
+ .costAdd(allPlans.get(rightPlan.allPlansIndex).totalCost);
totalCost = bcastHjCost.costAdd(rightExchangeCost).costAdd(childCosts);
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost)) {
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost) || forceEnum) {
pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.jnIndexes[0] = leftJn.jnArrayIndex;
pn.jnIndexes[1] = rightJn.jnArrayIndex;
- pn.planIndexes[0] = leftPlan;
- pn.planIndexes[1] = rightPlan;
+ pn.planIndexes[0] = leftPlan.allPlansIndex;
+ pn.planIndexes[1] = rightPlan.allPlansIndex;
pn.joinOp = PlanNode.JoinMethod.BROADCAST_HASH_JOIN; // need to check that all the conditions have equality predicates ONLY.
- if (hintBroadcastHashJoin != null) {
- hintBroadcastHashJoin.setBroadcastSide(BroadcastExpressionAnnotation.BroadcastSide.RIGHT);
- }
+ pn.joinHint = hintBroadcastHashJoin;
pn.side = HashJoinExpressionAnnotation.BuildSide.RIGHT;
pn.joinExpr = hashJoinExpr;
pn.opCost = bcastHjCost;
@@ -577,29 +593,34 @@
pn.rightExchangeCost = rightExchangeCost;
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
- return this.cheapestPlanIndex;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
+ return pn.allPlansIndex;
}
}
return PlanNode.NO_PLAN;
}
- protected int buildNLJoinPlan(JoinNode leftJn, JoinNode rightJn, ILogicalExpression nestedLoopJoinExpr)
+ protected int buildNLJoinPlan(JoinNode leftJn, JoinNode rightJn, PlanNode leftPlan, PlanNode rightPlan,
+ ILogicalExpression nestedLoopJoinExpr, IndexedNLJoinExpressionAnnotation hintNLJoin)
throws AlgebricksException {
// Build a nested loops plan, first check if it is possible
// left right order must be preserved and right side should be a single data set
List<PlanNode> allPlans = joinEnum.allPlans;
int numberOfTerms = joinEnum.numberOfTerms;
- PlanNode pn;
+ PlanNode pn, cheapestPlan;
ICost nljCost, leftExchangeCost, rightExchangeCost, childCosts, totalCost;
this.leftJn = leftJn;
this.rightJn = rightJn;
- int leftPlan = leftJn.cheapestPlanIndex;
- int rightPlan = rightJn.cheapestPlanIndex;
+
if (rightJn.jnArrayIndex > numberOfTerms) {
// right side consists of more than one table
return PlanNode.NO_PLAN; // nested loop plan not possible.
@@ -612,42 +633,50 @@
nljCost = joinEnum.getCostMethodsHandle().costIndexNLJoin(this);
leftExchangeCost = joinEnum.getCostMethodsHandle().computeNLJOuterExchangeCost(this);
rightExchangeCost = joinEnum.getCostHandle().zeroCost();
- childCosts = allPlans.get(leftPlan).totalCost;
+ childCosts = allPlans.get(leftPlan.allPlansIndex).totalCost;
totalCost = nljCost.costAdd(leftExchangeCost).costAdd(childCosts);
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost)) {
+ boolean forceEnum = hintNLJoin != null || joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel;
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost) || forceEnum) {
pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.jnIndexes[0] = leftJn.jnArrayIndex;
pn.jnIndexes[1] = rightJn.jnArrayIndex;
- pn.planIndexes[0] = leftPlan;
- pn.planIndexes[1] = rightPlan;
+ pn.planIndexes[0] = leftPlan.allPlansIndex;
+ pn.planIndexes[1] = rightPlan.allPlansIndex;
pn.joinOp = PlanNode.JoinMethod.INDEX_NESTED_LOOP_JOIN;
+ pn.joinHint = hintNLJoin;
pn.joinExpr = nestedLoopJoinExpr; // save it so can be used to add the NESTED annotation in getNewTree.
pn.opCost = nljCost;
pn.totalCost = totalCost;
pn.leftExchangeCost = leftExchangeCost;
pn.rightExchangeCost = rightExchangeCost;
-
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
- return allPlans.size() - 1;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
+ return pn.allPlansIndex;
}
return PlanNode.NO_PLAN;
}
- protected int buildCPJoinPlan(JoinNode leftJn, JoinNode rightJn, ILogicalExpression hashJoinExpr,
- ILogicalExpression nestedLoopJoinExpr) {
+ protected int buildCPJoinPlan(JoinNode leftJn, JoinNode rightJn, PlanNode leftPlan, PlanNode rightPlan,
+ ILogicalExpression hashJoinExpr, ILogicalExpression nestedLoopJoinExpr) {
// Now build a cartesian product nested loops plan
List<PlanNode> allPlans = joinEnum.allPlans;
- PlanNode pn;
+ PlanNode pn, cheapestPlan;
ICost cpCost, leftExchangeCost, rightExchangeCost, childCosts, totalCost;
+ if (!joinEnum.cboCPEnumMode) {
+ return PlanNode.NO_PLAN;
+ }
+
this.leftJn = leftJn;
this.rightJn = rightJn;
- int leftPlan = leftJn.cheapestPlanIndex;
- int rightPlan = rightJn.cheapestPlanIndex;
ILogicalExpression cpJoinExpr = null;
List<Integer> newJoinConditions = this.getNewJoinConditionsOnly();
@@ -670,58 +699,93 @@
cpCost = joinEnum.getCostMethodsHandle().costCartesianProductJoin(this);
leftExchangeCost = joinEnum.getCostHandle().zeroCost();
rightExchangeCost = joinEnum.getCostMethodsHandle().computeCPRightExchangeCost(this);
- childCosts = allPlans.get(leftPlan).totalCost.costAdd(allPlans.get(rightPlan).totalCost);
+ childCosts =
+ allPlans.get(leftPlan.allPlansIndex).totalCost.costAdd(allPlans.get(rightPlan.allPlansIndex).totalCost);
totalCost = cpCost.costAdd(rightExchangeCost).costAdd(childCosts);
- if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost)) {
+ boolean forceEnum = joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel;
+ if (this.cheapestPlanIndex == PlanNode.NO_PLAN || totalCost.costLT(this.cheapestPlanCost) || forceEnum) {
pn = new PlanNode(allPlans.size(), joinEnum);
pn.jn = this;
pn.jnIndexes[0] = leftJn.jnArrayIndex;
pn.jnIndexes[1] = rightJn.jnArrayIndex;
- pn.planIndexes[0] = leftPlan;
- pn.planIndexes[1] = rightPlan;
+ pn.planIndexes[0] = leftPlan.allPlansIndex;
+ pn.planIndexes[1] = rightPlan.allPlansIndex;
pn.joinOp = PlanNode.JoinMethod.CARTESIAN_PRODUCT_JOIN;
pn.joinExpr = Objects.requireNonNullElse(cpJoinExpr, ConstantExpression.TRUE);
pn.opCost = cpCost;
pn.totalCost = totalCost;
pn.leftExchangeCost = leftExchangeCost;
pn.rightExchangeCost = rightExchangeCost;
-
allPlans.add(pn);
- this.planIndexesArray.add(allPlans.size() - 1);
- this.cheapestPlanCost = totalCost;
- this.cheapestPlanIndex = allPlans.size() - 1;
- return allPlans.size() - 1;
+ this.planIndexesArray.add(pn.allPlansIndex);
+ if (!forceEnum) {
+ cheapestPlan = pn;
+ } else {
+ cheapestPlan = findCheapestPlan();
+ }
+ this.cheapestPlanCost = cheapestPlan.totalCost;
+ this.cheapestPlanIndex = cheapestPlan.allPlansIndex;
+ return pn.allPlansIndex;
}
return PlanNode.NO_PLAN;
}
- protected Pair<Integer, ICost> addMultiDatasetPlans(JoinNode leftJn, JoinNode rightJn) throws AlgebricksException {
+ protected void addMultiDatasetPlans(JoinNode leftJn, JoinNode rightJn) throws AlgebricksException {
+ PlanNode leftPlan, rightPlan;
+
+ if (level > joinEnum.cboFullEnumLevel) {
+ // FOR JOIN NODE LEVELS GREATER THAN THE LEVEL SPECIFIED FOR FULL ENUMERATION,
+ // DO NOT DO FULL ENUMERATION => PRUNE
+ if (leftJn.cheapestPlanIndex == PlanNode.NO_PLAN || rightJn.cheapestPlanIndex == PlanNode.NO_PLAN) {
+ return;
+ }
+ leftPlan = joinEnum.allPlans.get(leftJn.cheapestPlanIndex);
+ rightPlan = joinEnum.allPlans.get(rightJn.cheapestPlanIndex);
+ addMultiDatasetPlans(leftJn, rightJn, leftPlan, rightPlan);
+ } else {
+ // FOR JOIN NODE LEVELS LESS THAN OR EQUAL TO THE LEVEL SPECIFIED FOR FULL ENUMERATION,
+ // DO FULL ENUMERATION => DO NOT PRUNE
+ for (int leftPlanIndex : leftJn.planIndexesArray) {
+ leftPlan = joinEnum.allPlans.get(leftPlanIndex);
+ for (int rightPlanIndex : rightJn.planIndexesArray) {
+ rightPlan = joinEnum.allPlans.get(rightPlanIndex);
+ addMultiDatasetPlans(leftJn, rightJn, leftPlan, rightPlan);
+ }
+ }
+ }
+ }
+
+ protected void addMultiDatasetPlans(JoinNode leftJn, JoinNode rightJn, PlanNode leftPlan, PlanNode rightPlan)
+ throws AlgebricksException {
this.leftJn = leftJn;
this.rightJn = rightJn;
ICost noJoinCost = joinEnum.getCostHandle().maxCost();
if (leftJn.planIndexesArray.size() == 0 || rightJn.planIndexesArray.size() == 0) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost);
+ return;
}
if (this.cardinality >= Cost.MAX_CARD) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost); // no card hint available, so do not add this plan
+ return; // no card available, so do not add this plan
+ }
+
+ if (leftJn.cheapestPlanIndex == PlanNode.NO_PLAN || rightJn.cheapestPlanIndex == PlanNode.NO_PLAN) {
+ return;
}
List<Integer> newJoinConditions = this.getNewJoinConditionsOnly(); // these will be a subset of applicable join conditions.
+ if ((newJoinConditions.size() == 0) && joinEnum.connectedJoinGraph) {
+ // at least one plan must be there at each level as the graph is fully connected.
+ if (leftJn.cardinality * rightJn.cardinality > 10000.0 && level > joinEnum.cboFullEnumLevel) {
+ return;
+ }
+ }
ILogicalExpression hashJoinExpr = joinEnum.getHashJoinExpr(newJoinConditions);
ILogicalExpression nestedLoopJoinExpr = joinEnum.getNestedLoopJoinExpr(newJoinConditions);
- if ((newJoinConditions.size() == 0) && joinEnum.connectedJoinGraph) {
- // at least one plan must be there at each level as the graph is fully connected.
- if (leftJn.cardinality * rightJn.cardinality > 10000.0) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost);
- }
- }
-
double current_card = this.cardinality;
if (current_card >= Cost.MAX_CARD) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost); // no card hint available, so do not add this plan
+ return; // no card available, so do not add this plan
}
int hjPlan, commutativeHjPlan, bcastHjPlan, commutativeBcastHjPlan, nljPlan, commutativeNljPlan, cpPlan,
@@ -733,10 +797,6 @@
BroadcastExpressionAnnotation hintBroadcastHashJoin = joinEnum.findBroadcastHashJoinHint(newJoinConditions);
IndexedNLJoinExpressionAnnotation hintNLJoin = joinEnum.findNLJoinHint(newJoinConditions);
- if (leftJn.cheapestPlanIndex == PlanNode.NO_PLAN || rightJn.cheapestPlanIndex == PlanNode.NO_PLAN) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost);
- }
-
if (hintHashJoin != null) {
boolean build = (hintHashJoin.getBuildOrProbe() == HashJoinExpressionAnnotation.BuildOrProbe.BUILD);
boolean probe = (hintHashJoin.getBuildOrProbe() == HashJoinExpressionAnnotation.BuildOrProbe.PROBE);
@@ -752,12 +812,13 @@
|| rightJn.aliases.contains(buildOrProbeObject)))
|| (probe && (leftJn.datasetNames.contains(buildOrProbeObject)
|| leftJn.aliases.contains(buildOrProbeObject)))) {
- hjPlan = buildHashJoinPlan(leftJn, rightJn, hashJoinExpr, hintHashJoin);
+ hjPlan = buildHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, hintHashJoin);
} else if ((build && (leftJn.datasetNames.contains(buildOrProbeObject)
|| leftJn.aliases.contains(buildOrProbeObject)))
|| (probe && (rightJn.datasetNames.contains(buildOrProbeObject)
|| rightJn.aliases.contains(buildOrProbeObject)))) {
- commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, hashJoinExpr, hintHashJoin);
+ commutativeHjPlan =
+ buildHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, hintHashJoin);
}
} else {
// Hints are attached to predicates, so newJoinConditions should not be empty, but adding the check to be safe.
@@ -771,21 +832,24 @@
(build ? "build " : "probe ") + "with " + buildOrProbeObject));
}
}
- hjPlan = buildHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ hjPlan = buildHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeBcastHjPlan =
+ buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- nljPlan = buildNLJoinPlan(leftJn, rightJn, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeNljPlan = buildNLJoinPlan(rightJn, leftJn, nestedLoopJoinExpr);
+ nljPlan = buildNLJoinPlan(leftJn, rightJn, leftPlan, rightPlan, nestedLoopJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeNljPlan =
+ buildNLJoinPlan(rightJn, leftJn, rightPlan, leftPlan, nestedLoopJoinExpr, null);
}
- cpPlan = buildCPJoinPlan(leftJn, rightJn, hashJoinExpr, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeCpPlan = buildCPJoinPlan(rightJn, leftJn, hashJoinExpr, nestedLoopJoinExpr);
+ cpPlan = buildCPJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, nestedLoopJoinExpr);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeCpPlan =
+ buildCPJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, nestedLoopJoinExpr);
}
}
} else if (hintBroadcastHashJoin != null) {
@@ -798,16 +862,18 @@
}
if (validBroadcastObject) {
if (rightJn.datasetNames.contains(broadcastObject) || rightJn.aliases.contains(broadcastObject)) {
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, hintBroadcastHashJoin);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr,
+ hintBroadcastHashJoin);
} else if (leftJn.datasetNames.contains(broadcastObject) || leftJn.aliases.contains(broadcastObject)) {
- commutativeBcastHjPlan =
- buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, hintBroadcastHashJoin);
+ commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan,
+ hashJoinExpr, hintBroadcastHashJoin);
}
} else if (broadcastObject == null) {
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, hintBroadcastHashJoin);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeBcastHjPlan =
- buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, hintBroadcastHashJoin);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr,
+ hintBroadcastHashJoin);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan,
+ hashJoinExpr, hintBroadcastHashJoin);
}
} else {
// Hints are attached to predicates, so newJoinConditions should not be empty, but adding the check to be safe.
@@ -821,27 +887,31 @@
}
}
- hjPlan = buildHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ hjPlan = buildHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeBcastHjPlan =
+ buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- nljPlan = buildNLJoinPlan(leftJn, rightJn, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeNljPlan = buildNLJoinPlan(rightJn, leftJn, nestedLoopJoinExpr);
+ nljPlan = buildNLJoinPlan(leftJn, rightJn, leftPlan, rightPlan, nestedLoopJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeNljPlan =
+ buildNLJoinPlan(rightJn, leftJn, rightPlan, leftPlan, nestedLoopJoinExpr, null);
}
- cpPlan = buildCPJoinPlan(leftJn, rightJn, hashJoinExpr, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeCpPlan = buildCPJoinPlan(rightJn, leftJn, hashJoinExpr, nestedLoopJoinExpr);
+ cpPlan = buildCPJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, nestedLoopJoinExpr);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeCpPlan =
+ buildCPJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, nestedLoopJoinExpr);
}
}
} else if (hintNLJoin != null) {
- nljPlan = buildNLJoinPlan(leftJn, rightJn, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeNljPlan = buildNLJoinPlan(rightJn, leftJn, nestedLoopJoinExpr);
+ nljPlan = buildNLJoinPlan(leftJn, rightJn, leftPlan, rightPlan, nestedLoopJoinExpr, hintNLJoin);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeNljPlan =
+ buildNLJoinPlan(rightJn, leftJn, rightPlan, leftPlan, nestedLoopJoinExpr, hintNLJoin);
}
if (nljPlan == PlanNode.NO_PLAN && commutativeNljPlan == PlanNode.NO_PLAN) {
// Hints are attached to predicates, so newJoinConditions should not be empty, but adding the check to be safe.
@@ -854,50 +924,84 @@
ErrorCode.INAPPLICABLE_HINT, "index nested loop join", "ignored"));
}
}
- hjPlan = buildHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ hjPlan = buildHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeBcastHjPlan =
+ buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- cpPlan = buildCPJoinPlan(leftJn, rightJn, hashJoinExpr, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeCpPlan = buildCPJoinPlan(rightJn, leftJn, hashJoinExpr, nestedLoopJoinExpr);
+ cpPlan = buildCPJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, nestedLoopJoinExpr);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeCpPlan =
+ buildCPJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, nestedLoopJoinExpr);
}
}
} else {
- hjPlan = buildHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ hjPlan = buildHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeHjPlan = buildHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, hashJoinExpr, null);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeBcastHjPlan = buildBroadcastHashJoinPlan(rightJn, leftJn, hashJoinExpr, null);
+ bcastHjPlan = buildBroadcastHashJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeBcastHjPlan =
+ buildBroadcastHashJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, null);
}
- nljPlan = buildNLJoinPlan(leftJn, rightJn, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeNljPlan = buildNLJoinPlan(rightJn, leftJn, nestedLoopJoinExpr);
+ nljPlan = buildNLJoinPlan(leftJn, rightJn, leftPlan, rightPlan, nestedLoopJoinExpr, null);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeNljPlan = buildNLJoinPlan(rightJn, leftJn, rightPlan, leftPlan, nestedLoopJoinExpr, null);
}
- cpPlan = buildCPJoinPlan(leftJn, rightJn, hashJoinExpr, nestedLoopJoinExpr);
- if (!joinEnum.forceJoinOrderMode) {
- commutativeCpPlan = buildCPJoinPlan(rightJn, leftJn, hashJoinExpr, nestedLoopJoinExpr);
+ cpPlan = buildCPJoinPlan(leftJn, rightJn, leftPlan, rightPlan, hashJoinExpr, nestedLoopJoinExpr);
+ if (!joinEnum.forceJoinOrderMode || level <= joinEnum.cboFullEnumLevel) {
+ commutativeCpPlan =
+ buildCPJoinPlan(rightJn, leftJn, rightPlan, leftPlan, hashJoinExpr, nestedLoopJoinExpr);
}
}
- if (hjPlan == PlanNode.NO_PLAN && commutativeHjPlan == PlanNode.NO_PLAN && bcastHjPlan == PlanNode.NO_PLAN
- && commutativeBcastHjPlan == PlanNode.NO_PLAN && nljPlan == PlanNode.NO_PLAN
- && commutativeNljPlan == PlanNode.NO_PLAN && cpPlan == PlanNode.NO_PLAN
- && commutativeCpPlan == PlanNode.NO_PLAN) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost);
- }
-
//Reset as these might have changed when we tried the commutative joins.
this.leftJn = leftJn;
this.rightJn = rightJn;
- return new Pair<>(this.cheapestPlanIndex, this.cheapestPlanCost);
+ if (hjPlan == PlanNode.NO_PLAN && commutativeHjPlan == PlanNode.NO_PLAN && bcastHjPlan == PlanNode.NO_PLAN
+ && commutativeBcastHjPlan == PlanNode.NO_PLAN && nljPlan == PlanNode.NO_PLAN
+ && commutativeNljPlan == PlanNode.NO_PLAN && cpPlan == PlanNode.NO_PLAN
+ && commutativeCpPlan == PlanNode.NO_PLAN) {
+ return;
+ }
+ }
+
+ private PlanNode findCheapestPlan() {
+ List<PlanNode> allPlans = joinEnum.allPlans;
+ ICost cheapestCost = joinEnum.getCostHandle().maxCost();
+ PlanNode cheapestPlanNode = null;
+ boolean isCheapestPlanHinted = false;
+ boolean isPlanHinted;
+
+ for (int planIndex : this.planIndexesArray) {
+ PlanNode plan = allPlans.get(planIndex);
+ isPlanHinted = plan.joinHint != null || plan.indexHint;
+
+ if (isPlanHinted && !isCheapestPlanHinted) {
+ // The hinted plan wins!
+ cheapestPlanNode = plan;
+ cheapestCost = plan.totalCost;
+ isCheapestPlanHinted = true;
+ } else if (isPlanHinted || !isCheapestPlanHinted) {
+ // Either both plans are hinted, or both are non-hinted.
+ // Cost is the decider.
+ if (plan.totalCost.costLT(cheapestCost)) {
+ cheapestPlanNode = plan;
+ cheapestCost = plan.totalCost;
+ isCheapestPlanHinted = isPlanHinted;
+ }
+ } else {
+ // this is the case where isPlanHinted == false AND isCheapestPlanHinted == true
+ // Nothing to do.
+ }
+ }
+ return cheapestPlanNode;
}
@Override
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 7e9c3ee..508e2ec 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
@@ -23,6 +23,7 @@
import org.apache.hyracks.algebricks.common.utils.Pair;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
import org.apache.hyracks.algebricks.core.algebra.expressions.HashJoinExpressionAnnotation;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IExpressionAnnotation;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.EmptyTupleSourceOperator;
@@ -41,6 +42,8 @@
ICost leftExchangeCost;
ICost rightExchangeCost;
JoinMethod joinOp;
+ boolean indexHint;
+ IExpressionAnnotation joinHint;
// Used to indicate which side to build for HJ and which side to broadcast for BHJ.
HashJoinExpressionAnnotation.BuildSide side;
ScanMethod scanOp;
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/joins/nlj_partitioning_property_1.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/joins/nlj_partitioning_property_1.plan
index 91a6aca..5f3c681 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/joins/nlj_partitioning_property_1.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/joins/nlj_partitioning_property_1.plan
@@ -6,26 +6,24 @@
-- RANDOM_MERGE_EXCHANGE |PARTITIONED|
-- AGGREGATE |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- NESTED_LOOP |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$76][$$78] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
+ -- NESTED_LOOP |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$76][$$78] |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Supplier) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Supplier) |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Part) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Partsupp) |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
-- BROADCAST_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Part) |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Partsupp) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- EMPTY_TUPLE_SOURCE |PARTITIONED|
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
index 7609856..c1f2aff 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping.plan
@@ -3,13 +3,13 @@
-- STREAM_PROJECT |PARTITIONED|
-- ASSIGN |PARTITIONED|
-- SORT_MERGE_EXCHANGE [$$l_shipmode(ASC) ] |PARTITIONED|
- -- SORT_GROUP_BY[$$131] |PARTITIONED|
+ -- SORT_GROUP_BY[$$135] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
}
- -- HASH_PARTITION_EXCHANGE [$$131] |PARTITIONED|
- -- SORT_GROUP_BY[$$114] |PARTITIONED|
+ -- HASH_PARTITION_EXCHANGE [$$135] |PARTITIONED|
+ -- SORT_GROUP_BY[$$118] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
@@ -17,20 +17,20 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$118][$$122] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$118][$$124] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
- -- ASSIGN |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$114][$$120] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$122][$$126] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
-- STREAM_SELECT |PARTITIONED|
-- ASSIGN |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
@@ -38,6 +38,6 @@
-- DATASOURCE_SCAN (tpch.LineItem) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- UNNEST |UNPARTITIONED|
- -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
index f21d402..b926894 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results_cbo/tpch/q12_shipping_ps.plan
@@ -9,13 +9,13 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- REPLICATE |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- SORT_GROUP_BY[$$131] |PARTITIONED|
+ -- SORT_GROUP_BY[$$135] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
}
- -- HASH_PARTITION_EXCHANGE [$$131] |PARTITIONED|
- -- SORT_GROUP_BY[$$114] |PARTITIONED|
+ -- HASH_PARTITION_EXCHANGE [$$135] |PARTITIONED|
+ -- SORT_GROUP_BY[$$118] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
@@ -23,20 +23,20 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$118][$$122] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$118][$$124] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
- -- ASSIGN |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$114][$$120] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$122][$$126] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
-- STREAM_SELECT |PARTITIONED|
-- ASSIGN |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
@@ -44,9 +44,9 @@
-- DATASOURCE_SCAN (tpch.LineItem) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- UNNEST |UNPARTITIONED|
- -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
-- BROADCAST_EXCHANGE |PARTITIONED|
-- AGGREGATE |UNPARTITIONED|
-- RANDOM_MERGE_EXCHANGE |PARTITIONED|
@@ -55,13 +55,13 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- REPLICATE |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- SORT_GROUP_BY[$$131] |PARTITIONED|
+ -- SORT_GROUP_BY[$$135] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
}
- -- HASH_PARTITION_EXCHANGE [$$131] |PARTITIONED|
- -- SORT_GROUP_BY[$$114] |PARTITIONED|
+ -- HASH_PARTITION_EXCHANGE [$$135] |PARTITIONED|
+ -- SORT_GROUP_BY[$$118] |PARTITIONED|
{
-- AGGREGATE |LOCAL|
-- NESTED_TUPLE_SOURCE |LOCAL|
@@ -69,20 +69,20 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$118][$$122] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$118][$$124] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
- -- ASSIGN |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- HYBRID_HASH_JOIN [$$114][$$120] |PARTITIONED|
+ -- HYBRID_HASH_JOIN [$$122][$$126] |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN (tpch.Orders) |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
-- STREAM_SELECT |PARTITIONED|
-- ASSIGN |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
@@ -90,6 +90,6 @@
-- DATASOURCE_SCAN (tpch.LineItem) |PARTITIONED|
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- EMPTY_TUPLE_SOURCE |PARTITIONED|
- -- BROADCAST_EXCHANGE |PARTITIONED|
- -- UNNEST |UNPARTITIONED|
- -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|