[ASTERIXDB-2521][COMP] Add rule to eliminate isomorphic subplans
- user model changes: no
- storage format changes: no
- interface changes: no
Details:
- Add optimizer rule that finds two isomorphic subplans
and eliminates one of them
Change-Id: I1142ea4805e7508a5d0a778081093504cf4f526a
Reviewed-on: https://asterix-gerrit.ics.uci.edu/3238
Sonar-Qube: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Integration-Tests: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Contrib: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Ali Alsuliman <ali.al.solaiman@gmail.com>
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
index 31be802..1dd5e9c 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
@@ -135,6 +135,7 @@
import org.apache.hyracks.algebricks.rewriter.rules.SetExecutionModeRule;
import org.apache.hyracks.algebricks.rewriter.rules.SimpleUnnestToProductRule;
import org.apache.hyracks.algebricks.rewriter.rules.SwitchInnerJoinBranchRule;
+import org.apache.hyracks.algebricks.rewriter.rules.subplan.EliminateIsomorphicSubplanRule;
import org.apache.hyracks.algebricks.rewriter.rules.subplan.EliminateSubplanRule;
import org.apache.hyracks.algebricks.rewriter.rules.subplan.EliminateSubplanWithInputCardinalityOneRule;
import org.apache.hyracks.algebricks.rewriter.rules.subplan.NestedSubplanToJoinRule;
@@ -224,6 +225,10 @@
condPushDownAndJoinInference.add(new PushMapOperatorDownThroughProductRule());
condPushDownAndJoinInference.add(new PushSubplanWithAggregateDownThroughProductRule());
condPushDownAndJoinInference.add(new SubplanOutOfGroupRule());
+ // The following rule must run before PushAggregateIntoNestedSubplanRule
+ // (before common subplans diverge due to aggregate pushdown)
+ condPushDownAndJoinInference.add(new EliminateIsomorphicSubplanRule());
+
condPushDownAndJoinInference.add(new AsterixExtractFunctionsFromJoinConditionRule());
condPushDownAndJoinInference.add(new RemoveRedundantVariablesRule());
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/queries/group-by/listify-3.1.sqlpp b/asterixdb/asterix-app/src/test/resources/optimizerts/queries/group-by/listify-3.1.sqlpp
new file mode 100644
index 0000000..b15c3b3
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/queries/group-by/listify-3.1.sqlpp
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+WITH info AS (
+ SELECT avg(t) AS mean, min(t) AS min
+ FROM range(1, 10) t
+)[0]
+
+SELECT round_half_to_even(sqrt(avg(square)), 2) std
+FROM (
+ SELECT VALUE power(info.mean - t + info.min - 1, 2)
+ FROM range(1, 10) t
+) square;
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results/group-by/listify-3.1.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results/group-by/listify-3.1.plan
new file mode 100644
index 0000000..85fa62d
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results/group-by/listify-3.1.plan
@@ -0,0 +1,43 @@
+-- DISTRIBUTE_RESULT |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- NESTED_LOOP |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- NESTED_LOOP |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |UNPARTITIONED|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- REPLICATE |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- REPLICATE |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- STREAM_PROJECT |LOCAL|
+ -- ASSIGN |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- AGGREGATE |LOCAL|
+ -- UNNEST |UNPARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |UNPARTITIONED|
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/group-by/listify-3/listify-3.1.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/group-by/listify-3/listify-3.1.query.sqlpp
new file mode 100644
index 0000000..b15c3b3
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/group-by/listify-3/listify-3.1.query.sqlpp
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+WITH info AS (
+ SELECT avg(t) AS mean, min(t) AS min
+ FROM range(1, 10) t
+)[0]
+
+SELECT round_half_to_even(sqrt(avg(square)), 2) std
+FROM (
+ SELECT VALUE power(info.mean - t + info.min - 1, 2)
+ FROM range(1, 10) t
+) square;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/group-by/listify-3/listify-3.1.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/group-by/listify-3/listify-3.1.adm
new file mode 100644
index 0000000..5be6793
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/group-by/listify-3/listify-3.1.adm
@@ -0,0 +1 @@
+{ "std": 2.87 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
index b39c2f8..6f530ac 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
@@ -4172,6 +4172,11 @@
</compilation-unit>
</test-case>
<test-case FilePath="group-by">
+ <compilation-unit name="listify-3">
+ <output-dir compare="Text">listify-3</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="group-by">
<compilation-unit name="redundant-var-in-groupby">
<output-dir compare="Text">redundant-var-in-groupby</output-dir>
</compilation-unit>
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/IsomorphismOperatorVisitor.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/IsomorphismOperatorVisitor.java
index a39af41..c33c647 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/IsomorphismOperatorVisitor.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/IsomorphismOperatorVisitor.java
@@ -136,8 +136,9 @@
AbstractLogicalOperator aop = (AbstractLogicalOperator) arg;
// require the same physical operator, otherwise delivers different data
// properties
- if (aop.getOperatorTag() != LogicalOperatorTag.GROUP
- || aop.getPhysicalOperator().getOperatorTag() != op.getPhysicalOperator().getOperatorTag()) {
+ if (aop.getOperatorTag() != LogicalOperatorTag.GROUP || op.getPhysicalOperator() == null
+ || aop.getPhysicalOperator() == null
+ || op.getPhysicalOperator().getOperatorTag() != aop.getPhysicalOperator().getOperatorTag()) {
return Boolean.FALSE;
}
@@ -471,7 +472,8 @@
return Boolean.FALSE;
}
// require the same partition property
- if (!(op.getPhysicalOperator().getOperatorTag() == aop.getPhysicalOperator().getOperatorTag())) {
+ if (op.getPhysicalOperator() == null || aop.getPhysicalOperator() == null
+ || op.getPhysicalOperator().getOperatorTag() != aop.getPhysicalOperator().getOperatorTag()) {
return Boolean.FALSE;
}
variableMapping.clear();
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/subplan/EliminateIsomorphicSubplanRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/subplan/EliminateIsomorphicSubplanRule.java
new file mode 100644
index 0000000..1410a3a
--- /dev/null
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/subplan/EliminateIsomorphicSubplanRule.java
@@ -0,0 +1,165 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.algebricks.rewriter.rules.subplan;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import org.apache.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.visitors.IsomorphismUtilities;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import org.apache.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * <pre>
+ * This rules searches for
+ * SUBPLAN_1 { v1 = ... } (directly followed by)
+ * SUBPLAN_2 { v2 = ... }
+ * and eliminates nested plans from subplan_1 that are isomorphic to nested plans defined by subplan_2.
+ * The variables produced by eliminated nested plans are then ASSIGN-ed to variables produced by
+ * matching nested plans in subplan_2:
+ * ASSIGN { v1 = v2 }
+ * SUBPLAN_2 { v2 = ...}
+ *
+ * Note: SUBPLAN_1 will remain in the plan (below ASSIGN) if some of its nested plans could not be eliminated.
+ * </pre>
+ */
+public class EliminateIsomorphicSubplanRule implements IAlgebraicRewriteRule {
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) opRef.getValue();
+ if (op1.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+ return false;
+ }
+ SubplanOperator subplan1 = (SubplanOperator) op1;
+
+ Mutable<ILogicalOperator> op2Ref = subplan1.getInputs().get(0);
+ ILogicalOperator op2 = op2Ref.getValue();
+ if (op2.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+ return false;
+ }
+ SubplanOperator subplan2 = (SubplanOperator) op2;
+
+ Map<LogicalVariable, LogicalVariable> assignVarMap = new LinkedHashMap<>();
+ Map<LogicalVariable, LogicalVariable> tmpVarMap = new LinkedHashMap<>();
+ List<LogicalVariable> tmpVarList = new ArrayList<>();
+
+ for (Iterator<ILogicalPlan> nestedPlanIter = subplan1.getNestedPlans().iterator(); nestedPlanIter.hasNext();) {
+ ILogicalPlan nestedPlan = nestedPlanIter.next();
+ for (Iterator<Mutable<ILogicalOperator>> rootOpIter = nestedPlan.getRoots().iterator(); rootOpIter
+ .hasNext();) {
+ ILogicalOperator rootOp = rootOpIter.next().getValue();
+ if (findIsomorphicPlanRoot(rootOp, subplan2, assignVarMap, tmpVarList, tmpVarMap)) {
+ rootOpIter.remove();
+ }
+ }
+ if (nestedPlan.getRoots().isEmpty()) {
+ nestedPlanIter.remove();
+ }
+ }
+
+ int assignVarCount = assignVarMap.size();
+ if (assignVarCount == 0) {
+ return false;
+ }
+
+ List<LogicalVariable> assignVars = new ArrayList<>(assignVarCount);
+ List<Mutable<ILogicalExpression>> assignExprs = new ArrayList<>(assignVarCount);
+
+ for (Map.Entry<LogicalVariable, LogicalVariable> me : assignVarMap.entrySet()) {
+ LogicalVariable subplan1Var = me.getKey();
+
+ LogicalVariable subplan2Var = me.getValue();
+ VariableReferenceExpression subplan2VarRef = new VariableReferenceExpression(subplan2Var);
+ subplan2VarRef.setSourceLocation(subplan2.getSourceLocation());
+
+ assignVars.add(subplan1Var);
+ assignExprs.add(new MutableObject<>(subplan2VarRef));
+ }
+
+ Mutable<ILogicalOperator> assignInputOp;
+ if (subplan1.getNestedPlans().isEmpty()) {
+ assignInputOp = op2Ref;
+ } else {
+ // some nested plans were removed from subplan1 -> recompute its type environment
+ context.computeAndSetTypeEnvironmentForOperator(subplan1);
+ assignInputOp = new MutableObject<>(subplan1);
+ }
+
+ AssignOperator assignOp = new AssignOperator(assignVars, assignExprs);
+ assignOp.setSourceLocation(subplan1.getSourceLocation());
+ assignOp.getInputs().add(assignInputOp);
+
+ context.computeAndSetTypeEnvironmentForOperator(assignOp);
+ opRef.setValue(assignOp);
+
+ return true;
+ }
+
+ /**
+ * Finds nested plan root in given subplan that is isomorphic to given operator
+ * and returns their variable mappings
+ */
+ private boolean findIsomorphicPlanRoot(ILogicalOperator op, SubplanOperator subplanOp,
+ Map<LogicalVariable, LogicalVariable> outVarMap, List<LogicalVariable> tmpVarList,
+ Map<LogicalVariable, LogicalVariable> tmpVarMap) throws AlgebricksException {
+ for (ILogicalPlan nestedPlan : subplanOp.getNestedPlans()) {
+ for (Mutable<ILogicalOperator> rootOpRef : nestedPlan.getRoots()) {
+ ILogicalOperator rootOp = rootOpRef.getValue();
+ if (IsomorphismUtilities.isOperatorIsomorphicPlanSegment(op, rootOp)) {
+ tmpVarList.clear();
+ VariableUtilities.getProducedVariables(op, tmpVarList);
+ tmpVarMap.clear();
+ IsomorphismUtilities.mapVariablesTopDown(rootOp, op, tmpVarMap);
+ tmpVarMap.keySet().retainAll(tmpVarList);
+ if (tmpVarMap.size() == tmpVarList.size()) {
+ outVarMap.putAll(tmpVarMap);
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ return false;
+ }
+}