>From Vijay Sarathy <[email protected]>:
Vijay Sarathy has uploaded this change for review. (
https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/17945 )
Change subject: [ASTERIXDB-3308][COMP]: Internal erorr for CH2 Q7 with CBO
......................................................................
[ASTERIXDB-3308][COMP]: Internal erorr for CH2 Q7 with CBO
Change-Id: I745fc5bcb62d7740373d4dff19eae95b7bc7479e
---
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinEnum.java
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/JoinNode.java
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/EnumerateJoinsRule.java
3 files changed, 81 insertions(+), 84 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb
refs/changes/45/17945/1
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/EnumerateJoinsRule.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/EnumerateJoinsRule.java
index 82e7b32..190a598 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/EnumerateJoinsRule.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/cbo/EnumerateJoinsRule.java
@@ -163,7 +163,7 @@
return false;
}
- convertOuterJoinstoJoinsIfPossible(outerJoinsDependencyList);
+ convertOuterJoinstoJoinsIfPossible();
printPlan(pp, (AbstractLogicalOperator) op, "Original Whole plan2");
int numberOfFromTerms = leafInputs.size();
@@ -183,18 +183,18 @@
rootGroupByDistinctOp, rootOrderByOp, context);
if (cboMode) {
- if (!doAllDataSourcesHaveSamples(leafInputs, context)) {
+ if (!doAllDataSourcesHaveSamples(context)) {
return false;
}
}
- printLeafPlans(pp, leafInputs, "Inputs1");
+ printLeafPlans(pp, "Inputs1");
if (assignOps.size() > 0) {
- pushAssignsIntoLeafInputs(pp, leafInputs, assignOps,
assignJoinExprs);
+ pushAssignsIntoLeafInputs(pp);
}
- printLeafPlans(pp, leafInputs, "Inputs2");
+ printLeafPlans(pp, "Inputs2");
int cheapestPlan = joinEnum.enumerateJoins(); // MAIN CALL INTO CBO
if (cheapestPlan == PlanNode.NO_PLAN) {
@@ -206,12 +206,12 @@
generateHintWarnings();
if (numberOfFromTerms > 1) {
- getNewJoinOps(cheapestPlanNode, allJoinOps);
+ getNewJoinOps(cheapestPlanNode);
if (allJoinOps.size() != newJoinOps.size()) {
return false; // there are some cases such as R OJ S on true.
Here there is an OJ predicate but the code in findJoinConditions
// in JoinEnum does not capture this. Will fix later. Just
bail for now.
}
- buildNewTree(cheapestPlanNode, newJoinOps, new MutableInt(0));
+ buildNewTree(cheapestPlanNode, new MutableInt(0));
opRef.setValue(newJoinOps.get(0));
if (assignOps.size() > 0) {
@@ -226,7 +226,7 @@
}
printPlan(pp, (AbstractLogicalOperator) newJoinOps.get(0), "New
Whole Plan after buildNewTree 1");
- ILogicalOperator root =
addRemainingAssignsAtTheTop(newJoinOps.get(0), assignOps);
+ ILogicalOperator root =
addRemainingAssignsAtTheTop(newJoinOps.get(0));
printPlan(pp, (AbstractLogicalOperator) newJoinOps.get(0), "New
Whole Plan after buildNewTree 2");
printPlan(pp, (AbstractLogicalOperator) root, "New Whole Plan
after buildNewTree");
@@ -244,7 +244,7 @@
if (LOGGER.isTraceEnabled()) {
LOGGER.trace("---------------------------- Printing Leaf
Inputs");
- printLeafPlans(pp, leafInputs, "Inputs");
+ printLeafPlans(pp, "Inputs");
// print joins starting from the bottom
for (int i = newJoinOps.size() - 1; i >= 0; i--) {
printPlan(pp, (AbstractLogicalOperator) newJoinOps.get(i),
"join " + i);
@@ -344,7 +344,7 @@
* Check to see if there is only one assign here and nothing below that
other than a join.
* have not seen cases where there is more than one assign in a leafinput.
*/
- private boolean onlyOneAssign(ILogicalOperator op, List<AssignOperator>
assignOps) {
+ private boolean onlyOneAssign(ILogicalOperator op) {
if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
AssignOperator aOp = (AssignOperator) op;
assignOps.add(aOp);
@@ -371,7 +371,7 @@
return count;
}
- private boolean onlyAssigns(ILogicalOperator op, List<AssignOperator>
assignOps) {
+ private boolean onlyAssigns(ILogicalOperator op) {
while (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
AssignOperator aOp = (AssignOperator) op;
int count = numVarRefExprs(aOp);
@@ -501,8 +501,7 @@
// If we have a case of (first, second, LOJ_operator) = (R_leaf_input_id,
S_leaf_input_id, LOJop),
// and another (S_leaf_input_id, ..., joinOp),
// OR (..., S_leaf_input_id, joinOp) then the LOJ can be converted to a
join!!
- private void convertOuterJoinstoJoinsIfPossible(
- List<Quadruple<Integer, Integer, JoinOperator, Integer>>
outerJoinsDependencyList) {
+ private void convertOuterJoinstoJoinsIfPossible() {
int i, j;
boolean changes = true;
while (changes) {
@@ -538,8 +537,7 @@
}
// Each outer join will create one set of dependencies. The right side
depends on the left side.
- private boolean buildDependencyList(ILogicalOperator op, JoinOperator jO,
- List<Quadruple<Integer, Integer, JoinOperator, Integer>>
outerJoinsDependencyList, int rightSideBits)
+ private boolean buildDependencyList(ILogicalOperator op, JoinOperator jO,
int rightSideBits)
throws AlgebricksException {
AbstractBinaryJoinOperator outerJoinOp = (AbstractBinaryJoinOperator)
op;
ILogicalOperator leftOp = op.getInputs().get(0).getValue();
@@ -640,7 +638,7 @@
&& (firstLeafInputNumber < lastLeafInputNumber)) {
// if more is than one leafInput, only then buildSets make sense.
buildSets.add(new Triple<>(k, lastLeafInputNumber -
firstLeafInputNumber + 1, true)); // convert the second to boolean later
}
- boolean ret = buildDependencyList(op, jO,
outerJoinsDependencyList, k);
+ boolean ret = buildDependencyList(op, jO, k);
if (!ret) {
return false;
}
@@ -669,7 +667,7 @@
}
}
} else { // This must be an internal edge
- if (onlyAssigns(op, assignOps)) {
+ if (onlyAssigns(op)) {
ILogicalOperator skipAssisgnsOp = skipPastAssigns(op);
boolean canTransform =
getJoinOpsAndLeafInputs(skipAssisgnsOp);
if (!canTransform) {
@@ -744,32 +742,6 @@
}
}
- private int findAssignOp(ILogicalOperator leafInput, List<AssignOperator>
assignOps,
- List<ILogicalExpression> assignJoinExprs) throws
AlgebricksException {
- int i = -1;
- for (AssignOperator aOp : assignOps) {
- i++;
- if (assignJoinExprs.get(i) != null)
- continue; // this is an assign associated with a join
expression
- // this will be an Assign, so no need to check
- List<LogicalVariable> vars = new ArrayList<>();
- aOp.getExpressions().get(0).getValue().getUsedVariables(vars);
- HashSet<LogicalVariable> vars2 = new HashSet<>();
- VariableUtilities.getLiveVariables(leafInput, vars2);
- if (vars2.containsAll(vars)) { // note that this will fail if
there variables from different leafInputs
- return i;
- }
- }
-
- return -1;
- }
-
- private ILogicalOperator addAssignToLeafInput(ILogicalOperator leafInput,
AssignOperator aOp) {
- // this will be an Assign, so no need to check
- aOp.getInputs().get(0).setValue(leafInput);
- return aOp;
- }
-
private void skipAllIndexes(PlanNode plan, ILogicalOperator leafInput) {
if (plan.scanOp == PlanNode.ScanMethod.TABLE_SCAN &&
leafInput.getOperatorTag() == LogicalOperatorTag.SELECT) {
SelectOperator selOper = (SelectOperator) leafInput;
@@ -807,7 +779,7 @@
addCardCostAnnotations(findDataSourceScanOperator(leftInput), plan);
}
- private void getJoinNode(PlanNode plan, List<JoinOperator> allJoinOps)
throws AlgebricksException {
+ private void getJoinNode(PlanNode plan) throws AlgebricksException {
AbstractBinaryJoinOperator abjOp;
int i;
@@ -830,11 +802,11 @@
}
}
- private void getNewJoinOps(PlanNode plan, List<JoinOperator> allJoinOps)
throws AlgebricksException {
+ private void getNewJoinOps(PlanNode plan) throws AlgebricksException {
if (plan.IsJoinNode()) {
- getJoinNode(plan, allJoinOps);
- getNewJoinOps(plan.getLeftPlanNode(), allJoinOps);
- getNewJoinOps(plan.getRightPlanNode(), allJoinOps);
+ getJoinNode(plan);
+ getNewJoinOps(plan.getLeftPlanNode());
+ getNewJoinOps(plan.getRightPlanNode());
}
}
@@ -885,8 +857,7 @@
}
// This one is for join queries
- private void buildNewTree(PlanNode plan, List<ILogicalOperator> joinOps,
MutableInt totalNumberOfJoins)
- throws AlgebricksException {
+ private void buildNewTree(PlanNode plan, MutableInt totalNumberOfJoins)
throws AlgebricksException {
// we have to move the inputs in op around so that they match the tree
structure in pn
// we use the existing joinOps and switch the leafInputs appropriately.
List<PlanNode> allPlans = joinEnum.getAllPlans();
@@ -897,7 +868,7 @@
PlanNode leftPlan = allPlans.get(leftIndex);
PlanNode rightPlan = allPlans.get(rightIndex);
- ILogicalOperator joinOp = joinOps.get(totalNumberOfJoins.intValue());
// intValue set to 0 initially
+ ILogicalOperator joinOp =
newJoinOps.get(totalNumberOfJoins.intValue()); // intValue set to 0 initially
if (plan.IsJoinNode()) {
fillJoinAnnotations(plan, joinOp);
@@ -916,9 +887,9 @@
} else {
// join
totalNumberOfJoins.increment();
- ILogicalOperator leftInput =
joinOps.get(totalNumberOfJoins.intValue());
+ ILogicalOperator leftInput =
newJoinOps.get(totalNumberOfJoins.intValue());
joinOp.getInputs().get(0).setValue(leftInput);
- buildNewTree(leftPlan, joinOps, totalNumberOfJoins);
+ buildNewTree(leftPlan, totalNumberOfJoins);
}
if (rightPlan.IsScanNode()) {
@@ -934,9 +905,9 @@
} else {
// join
totalNumberOfJoins.increment();
- ILogicalOperator rightInput =
joinOps.get(totalNumberOfJoins.intValue());
+ ILogicalOperator rightInput =
newJoinOps.get(totalNumberOfJoins.intValue());
joinOp.getInputs().get(1).setValue(rightInput);
- buildNewTree(rightPlan, joinOps, totalNumberOfJoins);
+ buildNewTree(rightPlan, totalNumberOfJoins);
}
}
@@ -944,7 +915,7 @@
// is not used anywhere in the current join graph but is used outside the
current join graph. So we add this assign to the top of
// our plan, so the rest of the code will be happy. Strange that this
assign appears in the join graph.
- private ILogicalOperator addRemainingAssignsAtTheTop(ILogicalOperator op,
List<AssignOperator> assignOps) {
+ private ILogicalOperator addRemainingAssignsAtTheTop(ILogicalOperator op) {
ILogicalOperator root = op;
for (AssignOperator aOp : assignOps) {
aOp.getInputs().get(0).setValue(root);
@@ -962,8 +933,7 @@
}
}
- private void printLeafPlans(IPlanPrettyPrinter pp, List<ILogicalOperator>
leafInputs, String msg)
- throws AlgebricksException {
+ private void printLeafPlans(IPlanPrettyPrinter pp, String msg) throws
AlgebricksException {
if (LOGGER.isTraceEnabled()) {
LOGGER.trace(msg);
int i = 0;
@@ -974,28 +944,49 @@
}
}
+ private int findLeafInputToPushThisAssignOp(AssignOperator aOp) throws
AlgebricksException {
+ int i = -1;
+ List<LogicalVariable> vars = new ArrayList<>();
+ aOp.getExpressions().get(0).getValue().getUsedVariables(vars);
+ for (ILogicalOperator leafInput : leafInputs) {
+ i++;
+ HashSet<LogicalVariable> vars2 = new HashSet<>();
+ VariableUtilities.getLiveVariables(leafInput, vars2);
+ if (vars2.containsAll(vars)) { // note that this will fail if
there variables from different leafInputs
+ return i;
+ }
+ }
+ return -1;
+ }
+
// for every internal edge assign (again assuming only 1 for now), find
the corresponding leafInput and place the assign
// on top of that LeafInput. Modify the joinLeafInputsHashMap as well.
- private void pushAssignsIntoLeafInputs(IPlanPrettyPrinter pp,
List<ILogicalOperator> leafInputs,
- List<AssignOperator> assignOps, List<ILogicalExpression>
assignJoinExprs) throws AlgebricksException {
- int pos = 0;
- for (ILogicalOperator lo : leafInputs) {
- ILogicalOperator joinLeafInput = lo;
- printPlan(pp, (AbstractLogicalOperator) joinLeafInput, "Incoming
leaf Input");
- int assignNumber = findAssignOp(joinLeafInput, assignOps,
assignJoinExprs);
- if (assignNumber != -1) {
- joinLeafInput = addAssignToLeafInput(joinLeafInput,
assignOps.get(assignNumber));
- printPlan(pp, (AbstractLogicalOperator) joinLeafInput,
"Modified leaf Input");
- leafInputs.add(pos, joinLeafInput);
- assignOps.remove(assignNumber);
- }
+ private void pushAssignsIntoLeafInputs(IPlanPrettyPrinter pp) throws
AlgebricksException {
+ int pos = -1;
+ List<Integer> movedAssignOps = new ArrayList<>();
+ for (AssignOperator aOp : assignOps) {
pos++;
+ int leafInputNum = findLeafInputToPushThisAssignOp(aOp);
+ if (leafInputNum != -1) {
+ aOp.getInputs().get(0).setValue(leafInputs.get(leafInputNum));
+ leafInputs.set(leafInputNum, aOp);
+ printPlan(pp, (AbstractLogicalOperator) aOp, "Modified leaf
Input");
+ movedAssignOps.add(pos);
+ // For the purposes of join enumeration, leafInput numbers
start at 1.
+ for (LogicalVariable var : aOp.getVariables()) {
+ varLeafInputIds.put(var, leafInputNum + 1);
+ }
+ }
}
+ // now remove the moved assign ops from the assignOps list
+ for (int i : movedAssignOps) {
+ assignOps.remove(i);
+ }
+
}
// check to see if every dataset has a sample. If not, CBO code cannot
run. A warning message must be issued as well.
- private boolean doAllDataSourcesHaveSamples(List<ILogicalOperator>
leafInputs, IOptimizationContext context)
- throws AlgebricksException {
+ private boolean doAllDataSourcesHaveSamples(IOptimizationContext context)
throws AlgebricksException {
for (ILogicalOperator li : leafInputs) {
DataSourceScanOperator scanOp = (DataSourceScanOperator)
findDataSourceScanOperator(li);
if (scanOp == null)
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 d33f8ce..198481e 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
@@ -498,7 +498,6 @@
}
private void markComponents(int startingJoinCondition) {
- List<JoinCondition> joinConditions = this.getJoinConditions();
// see if all the joinCondition can be reached starting with the first.
JoinCondition jc1 = joinConditions.get(startingJoinCondition);
for (int i = 0; i < joinConditions.size(); i++) {
@@ -847,8 +846,6 @@
}
int dataScanPlan;
- JoinNode[] jnArray = this.getJnArray();
- int limit = -1;
if (this.numberOfTerms == 1) {
jnArray[1].setLimitVal(findLimitValue(this.op));
}
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 48d88a9..6eb37ea 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
@@ -303,7 +303,7 @@
// Now see if any redundant edges are present; R.a = S.a and S.a = T.a
==> R.a = T.a.
// One of them must be removed to estimate cardinality correctly.
if (this.applicableJoinConditions.size() >= 3) {
- redundantSel = removeRedundantPred(this.applicableJoinConditions);
+ redundantSel = removeRedundantPred();
}
// By dividing by redundantSel, we are undoing the earlier
multiplication of all the selectivities.
@@ -336,28 +336,28 @@
// Each edge has two vertices. So we can only handle predicate with
exactly two tables such as R.a = S.a
// We will not handle cases such as R.a + S.a = T.a
// It should be easy to identify two vertex edges as only two bits will be
set for such conditions.
- private double removeRedundantPred(List<Integer>
applicablePredicatesInCurrentJn) {
+ private double removeRedundantPred() {
double redundantSel = 1.0;
List<JoinCondition> joinConditions = joinEnum.getJoinConditions();
JoinCondition jc1, jc2, jc3;
int[] vertices = new int[6];
int[] verticesCopy = new int[6];
- for (int i = 0; i <= applicablePredicatesInCurrentJn.size() - 3; i++) {
- jc1 = joinConditions.get(applicablePredicatesInCurrentJn.get(i));
+ for (int i = 0; i <= applicableJoinConditions.size() - 3; i++) {
+ jc1 = joinConditions.get(applicableJoinConditions.get(i));
if (jc1.partOfComposite) {
continue; // must ignore these or the same triangles will be
found more than once.
}
vertices[0] = jc1.leftSideBits;
vertices[1] = jc1.rightSideBits;
- for (int j = i + 1; j <= applicablePredicatesInCurrentJn.size() -
2; j++) {
- jc2 =
joinConditions.get(applicablePredicatesInCurrentJn.get(j));
+ for (int j = i + 1; j <= applicableJoinConditions.size() - 2; j++)
{
+ jc2 = joinConditions.get(applicableJoinConditions.get(j));
if (jc2.partOfComposite) {
continue;
}
vertices[2] = jc2.leftSideBits;
vertices[3] = jc2.rightSideBits;
- for (int k = j + 1; k <=
applicablePredicatesInCurrentJn.size() - 1; k++) {
- jc3 =
joinConditions.get(applicablePredicatesInCurrentJn.get(k));
+ for (int k = j + 1; k <= applicableJoinConditions.size() - 1;
k++) {
+ jc3 = joinConditions.get(applicableJoinConditions.get(k));
if (jc3.partOfComposite) {
continue;
}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/17945
To unsubscribe, or for help writing mail filters, visit
https://asterix-gerrit.ics.uci.edu/settings
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I745fc5bcb62d7740373d4dff19eae95b7bc7479e
Gerrit-Change-Number: 17945
Gerrit-PatchSet: 1
Gerrit-Owner: Vijay Sarathy <[email protected]>
Gerrit-MessageType: newchange
