This is an automated email from the ASF dual-hosted git repository.
mblow pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/asterixdb.git
The following commit(s) were added to refs/heads/master by this push:
new 4e5aa99155 [ASTERIXDB-3195][COMP] Add query properties to enumerate
all plans.
new f93eb449de Null merge commit '4e5aa99155' into 'master'
4e5aa99155 is described below
commit 4e5aa99155eed03ba2b91a16a0b3ce8debc8fe82
Author: Vijay Sarathy <[email protected]>
AuthorDate: Mon Sep 4 17:41:34 2023 -0700
[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 <[email protected]>
Tested-by: Jenkins <[email protected]>
Reviewed-by: Vijay Sarathy <[email protected]>
Reviewed-by: Ali Alsuliman <[email protected]>
---
.../provider/SqlppCompilationProvider.java | 4 +-
.../asterix/optimizer/rules/cbo/JoinEnum.java | 42 +-
.../asterix/optimizer/rules/cbo/JoinNode.java | 424 +++++++++++++--------
.../asterix/optimizer/rules/cbo/PlanNode.java | 3 +
.../joins/nlj_partitioning_property_1.plan | 24 +-
.../optimizerts/results_cbo/tpch/q12_shipping.plan | 30 +-
.../results_cbo/tpch/q12_shipping_ps.plan | 60 +--
7 files changed, 365 insertions(+), 222 deletions(-)
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 4ad888c442..66da5e2566 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.lang.sqlpp.visitor.SqlppAstPrintVisitorFactory;
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 @@ public class SqlppCompilationProvider implements
ILangCompilationProvider {
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 e7a620d137..f23af33513 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 java.util.Set;
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.operators.logical.visitors.Var
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 @@ public class JoinEnum {
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 @@ public class JoinEnum {
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 @@ public class JoinEnum {
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 @@ public class JoinEnum {
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 @@ public class JoinEnum {
}
}
+ 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 @@ public class JoinEnum {
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 1f9300d00a..4418e4b1fc 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 class JoinNode {
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 @@ public class JoinNode {
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 @@ public class JoinNode {
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 @@ public class JoinNode {
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 @@ public class JoinNode {
}
}
- 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 @@ public class JoinNode {
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 @@ public class JoinNode {
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 @@ public class JoinNode {
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 @@ public class JoinNode {
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
}
- List<Integer> newJoinConditions = this.getNewJoinConditionsOnly(); //
these will be a subset of applicable join conditions.
- ILogicalExpression hashJoinExpr =
joinEnum.getHashJoinExpr(newJoinConditions);
- ILogicalExpression nestedLoopJoinExpr =
joinEnum.getNestedLoopJoinExpr(newJoinConditions);
+ 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) {
- return new Pair<>(PlanNode.NO_PLAN, noJoinCost);
+ if (leftJn.cardinality * rightJn.cardinality > 10000.0 && level >
joinEnum.cboFullEnumLevel) {
+ return;
}
}
+ ILogicalExpression hashJoinExpr =
joinEnum.getHashJoinExpr(newJoinConditions);
+ ILogicalExpression nestedLoopJoinExpr =
joinEnum.getNestedLoopJoinExpr(newJoinConditions);
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 @@ public class JoinNode {
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 @@ public class JoinNode {
|| 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 @@ public class JoinNode {
(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 @@ public class JoinNode {
}
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 @@ public class JoinNode {
}
}
- 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 @@ public class JoinNode {
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);
}
}
+ //Reset as these might have changed when we tried the commutative
joins.
+ this.leftJn = leftJn;
+ this.rightJn = rightJn;
+
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);
+ return;
}
+ }
- //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);
+ 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 7e9c3eecf2..508e2ec67f 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.asterix.optimizer.cost.ICost;
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 @@ public class PlanNode {
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 91a6acab57..5f3c6816c0 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 7609856f43..c1f2aff418 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,19 +17,19 @@
-- 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|
@@ -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 f21d40277f..b92689446b 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,19 +23,19 @@
-- 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|
@@ -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,19 +69,19 @@
-- 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|
@@ -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|
