You are viewing a plain text version of this content. The canonical link for it is here.

Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2021/06/08 19:39:37 UTC

Change in asterixdb[mad-hatter]: [ASTERIXDB-2886][COMP] Fix RemoveRedundantVariablesRule

From Dmitry Lychagin <dm...@couchbase.com>:

Dmitry Lychagin has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11863 )


Change subject: [ASTERIXDB-2886][COMP] Fix RemoveRedundantVariablesRule
......................................................................

[ASTERIXDB-2886][COMP] Fix RemoveRedundantVariablesRule

- user model changes: no
- storage format changes: no
- interface changes: no

Details:
- Change RemoveRedundantVariablesRule to
  operate on the whole plan at once instead
  of working incrementally on each operator

Change-Id: Ie948372c53bf42687ffd0ac37eff39bddf7395bc
---
A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.1.ddl.sqlpp
A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.2.ddl.sqlpp
A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.query.sqlpp
A asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.adm
M asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
M hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/RemoveRedundantVariablesRule.java
6 files changed, 178 insertions(+), 41 deletions(-)



  git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/63/11863/1

diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.1.ddl.sqlpp
new file mode 100644
index 0000000..ab6b723
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.1.ddl.sqlpp
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+
+drop dataverse test1 if exists;
+create dataverse test1;
+use test1;
+
+create dataset a(
+  c_a1 bigint not unknown,
+  c_a2 bigint,
+  c_a3 string
+) primary key c_a1;
+
+create index ia2 on a(c_a2);
+
+create index ia3 on a(c_a3);
+
+create dataset b(
+  c_b1 bigint not unknown,
+  c_b2 bigint,
+  c_b3 string
+) primary key c_b1;
+
+create index ib2 on b(c_b2);
+
+create index ib3 on b(c_b3);
+
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.2.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.2.ddl.sqlpp
new file mode 100644
index 0000000..621d057
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.2.ddl.sqlpp
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+
+drop dataverse test2 if exists;
+create dataverse test2;
+use test2;
+
+create dataset a(
+  c_a1 bigint not unknown,
+  c_a2 bigint,
+  c_a3 string
+) primary key c_a1;
+
+create index ia2 on a(c_a2);
+
+create index ia3 on a(c_a3);
+
+create dataset b(
+  c_b1 bigint not unknown,
+  c_b2 bigint,
+  c_b3 string
+) primary key c_b1;
+
+create index ib2 on b(c_b2);
+
+create index ib3 on b(c_b3);
+
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.query.sqlpp
new file mode 100644
index 0000000..e48a1e1
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.query.sqlpp
@@ -0,0 +1,30 @@
+/*
+ * 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.
+ */
+
+select ds.DataverseName, ds.DatasetName, dt.Derived.IsAnonymous, indexes
+from Metadata.`Dataset` as ds left join Metadata.`Datatype` dt
+on ds.DataverseName = dt.DataverseName and ds.DatatypeName = dt.DatatypeName
+let indexes = (
+  select idx.IndexName
+  from Metadata.`Index` as idx
+  where idx.DataverseName = ds.DataverseName and idx.DatasetName = ds.DatasetName
+  order by idx.IndexName
+)
+where ds.DataverseName like "test%"
+order by ds.DataverseName, ds.DatasetName;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.adm
new file mode 100644
index 0000000..7065d25
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-2886/query-ASTERIXDB-2886.3.adm
@@ -0,0 +1,4 @@
+{ "DataverseName": "test1", "DatasetName": "a", "IsAnonymous": true, "indexes": [ { "IndexName": "a" }, { "IndexName": "ia2" }, { "IndexName": "ia3" } ] }
+{ "DataverseName": "test1", "DatasetName": "b", "IsAnonymous": true, "indexes": [ { "IndexName": "b" }, { "IndexName": "ib2" }, { "IndexName": "ib3" } ] }
+{ "DataverseName": "test2", "DatasetName": "a", "IsAnonymous": true, "indexes": [ { "IndexName": "a" }, { "IndexName": "ia2" }, { "IndexName": "ia3" } ] }
+{ "DataverseName": "test2", "DatasetName": "b", "IsAnonymous": true, "indexes": [ { "IndexName": "b" }, { "IndexName": "ib2" }, { "IndexName": "ib3" } ] }
\ 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 af6ca78..327a58d 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
@@ -6399,6 +6399,11 @@
       </compilation-unit>
     </test-case>
     <test-case FilePath="misc">
+      <compilation-unit name="query-ASTERIXDB-2886">
+        <output-dir compare="Text">query-ASTERIXDB-2886</output-dir>
+      </compilation-unit>
+    </test-case>
+    <test-case FilePath="misc">
       <compilation-unit name="unsupported_parameter">
         <output-dir compare="Text">none</output-dir>
         <expected-error>Query parameter compiler.joinmem is not supported</expected-error>
diff --git a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/RemoveRedundantVariablesRule.java b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/RemoveRedundantVariablesRule.java
index 5386193..3760be5 100644
--- a/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/RemoveRedundantVariablesRule.java
+++ b/hyracks-fullstack/algebricks/algebricks-rewriter/src/main/java/org/apache/hyracks/algebricks/rewriter/rules/RemoveRedundantVariablesRule.java
@@ -36,7 +36,6 @@
 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.AbstractFunctionCallExpression;
-import org.apache.hyracks.algebricks.core.algebra.expressions.AbstractLogicalExpression;
 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.AbstractOperatorWithNestedPlans;
@@ -69,26 +68,33 @@
 public class RemoveRedundantVariablesRule implements IAlgebraicRewriteRule {
 
     private final VariableSubstitutionVisitor substVisitor = new VariableSubstitutionVisitor();
-    private final Map<LogicalVariable, List<LogicalVariable>> equivalentVarsMap =
-            new HashMap<LogicalVariable, List<LogicalVariable>>();
+
+    private final Map<LogicalVariable, List<LogicalVariable>> equivalentVarsMap = new HashMap<>();
 
     @Override
     public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
             throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
         if (context.checkIfInDontApplySet(this, opRef.getValue())) {
             return false;
         }
-        boolean modified = removeRedundantVariables(opRef, context);
-        if (modified) {
-            context.computeAndSetTypeEnvironmentForOperator(opRef.getValue());
-        }
-        return modified;
+        clear();
+        return removeRedundantVariables(opRef, true, context);
+    }
+
+    private void clear() {
+        equivalentVarsMap.clear();
     }
 
     private void updateEquivalenceClassMap(LogicalVariable lhs, LogicalVariable rhs) {
         List<LogicalVariable> equivalentVars = equivalentVarsMap.get(rhs);
         if (equivalentVars == null) {
-            equivalentVars = new ArrayList<LogicalVariable>();
+            equivalentVars = new ArrayList<>();
             // The first element in the list is the bottom-most representative which will replace all equivalent vars.
             equivalentVars.add(rhs);
             equivalentVars.add(lhs);
@@ -97,12 +103,32 @@
         equivalentVarsMap.put(lhs, equivalentVars);
     }
 
-    private boolean removeRedundantVariables(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
-            throws AlgebricksException {
+    private LogicalVariable findEquivalentRepresentativeVar(LogicalVariable var) {
+        List<LogicalVariable> equivalentVars = equivalentVarsMap.get(var);
+        if (equivalentVars == null) {
+            return null;
+        }
+        LogicalVariable representativeVar = equivalentVars.get(0);
+        return var.equals(representativeVar) ? null : representativeVar;
+    }
+
+    private boolean removeRedundantVariables(Mutable<ILogicalOperator> opRef, boolean first,
+            IOptimizationContext context) throws AlgebricksException {
         AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (!first) {
+            context.addToDontApplySet(this, op);
+        }
+
         LogicalOperatorTag opTag = op.getOperatorTag();
         boolean modified = false;
 
+        // Recurse into children.
+        for (Mutable<ILogicalOperator> inputOpRef : op.getInputs()) {
+            if (removeRedundantVariables(inputOpRef, false, context)) {
+                modified = true;
+            }
+        }
+
         // Update equivalence class map.
         if (opTag == LogicalOperatorTag.ASSIGN) {
             AssignOperator assignOp = (AssignOperator) op;
@@ -142,7 +168,7 @@
             AbstractOperatorWithNestedPlans opWithNestedPlan = (AbstractOperatorWithNestedPlans) op;
             for (ILogicalPlan nestedPlan : opWithNestedPlan.getNestedPlans()) {
                 for (Mutable<ILogicalOperator> rootRef : nestedPlan.getRoots()) {
-                    if (removeRedundantVariables(rootRef, context)) {
+                    if (removeRedundantVariables(rootRef, false, context)) {
                         modified = true;
                     }
                 }
@@ -158,14 +184,8 @@
 
         if (modified) {
             context.computeAndSetTypeEnvironmentForOperator(op);
-            context.addToDontApplySet(this, op);
         }
 
-        // Clears the equivalent variable map if the current operator is the root operator
-        // in the query plan.
-        if (opTag == LogicalOperatorTag.DISTRIBUTE_RESULT || opTag == LogicalOperatorTag.SINK) {
-            equivalentVarsMap.clear();
-        }
         return modified;
     }
 
@@ -227,38 +247,34 @@
      * We cannot use the VariableSubstitutionVisitor here because the project ops
      * maintain their variables as a list and not as expressions.
      */
-    private boolean replaceProjectVars(ProjectOperator op) throws AlgebricksException {
+    private boolean replaceProjectVars(ProjectOperator op) {
         List<LogicalVariable> vars = op.getVariables();
         int size = vars.size();
         boolean modified = false;
         for (int i = 0; i < size; i++) {
             LogicalVariable var = vars.get(i);
-            List<LogicalVariable> equivalentVars = equivalentVarsMap.get(var);
-            if (equivalentVars == null) {
-                continue;
-            }
-            // Replace with equivalence class representative.
-            LogicalVariable representative = equivalentVars.get(0);
-            if (representative != var) {
-                vars.set(i, equivalentVars.get(0));
+            LogicalVariable representativeVar = findEquivalentRepresentativeVar(var);
+            if (representativeVar != null) {
+                // Replace with equivalence class representative.
+                vars.set(i, representativeVar);
                 modified = true;
             }
         }
         return modified;
     }
 
-    private boolean replaceUnionAllVars(UnionAllOperator op) throws AlgebricksException {
+    private boolean replaceUnionAllVars(UnionAllOperator op) {
         boolean modified = false;
         for (Triple<LogicalVariable, LogicalVariable, LogicalVariable> varMapping : op.getVariableMappings()) {
-            List<LogicalVariable> firstEquivalentVars = equivalentVarsMap.get(varMapping.first);
-            List<LogicalVariable> secondEquivalentVars = equivalentVarsMap.get(varMapping.second);
             // Replace variables with their representative.
-            if (firstEquivalentVars != null) {
-                varMapping.first = firstEquivalentVars.get(0);
+            LogicalVariable firstRepresentativeVar = findEquivalentRepresentativeVar(varMapping.first);
+            if (firstRepresentativeVar != null) {
+                varMapping.first = firstRepresentativeVar;
                 modified = true;
             }
-            if (secondEquivalentVars != null) {
-                varMapping.second = secondEquivalentVars.get(0);
+            LogicalVariable secondRepresentativeVar = findEquivalentRepresentativeVar(varMapping.second);
+            if (secondRepresentativeVar != null) {
+                varMapping.second = secondRepresentativeVar;
                 modified = true;
             }
         }
@@ -269,17 +285,13 @@
         @Override
         public boolean transform(Mutable<ILogicalExpression> exprRef) {
             ILogicalExpression e = exprRef.getValue();
-            switch (((AbstractLogicalExpression) e).getExpressionTag()) {
+            switch (e.getExpressionTag()) {
                 case VARIABLE: {
                     // Replace variable references with their equivalent representative in the equivalence class map.
                     VariableReferenceExpression varRefExpr = (VariableReferenceExpression) e;
                     LogicalVariable var = varRefExpr.getVariableReference();
-                    List<LogicalVariable> equivalentVars = equivalentVarsMap.get(var);
-                    if (equivalentVars == null) {
-                        return false;
-                    }
-                    LogicalVariable representative = equivalentVars.get(0);
-                    if (representative != var) {
+                    LogicalVariable representative = findEquivalentRepresentativeVar(var);
+                    if (representative != null) {
                         varRefExpr.setVariable(representative);
                         return true;
                     }

-- 
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11863
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings

Gerrit-Project: asterixdb
Gerrit-Branch: mad-hatter
Gerrit-Change-Id: Ie948372c53bf42687ffd0ac37eff39bddf7395bc
Gerrit-Change-Number: 11863
Gerrit-PatchSet: 1
Gerrit-Owner: Dmitry Lychagin <dm...@couchbase.com>
Gerrit-MessageType: newchange