calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject calcite git commit: [CALCITE-1365] Add UnionPullUpConstantsRule
Date Wed, 31 Aug 2016 23:22:03 GMT
Repository: calcite
Updated Branches:
  refs/heads/master e87295979 -> 9b1624a88


[CALCITE-1365] Add UnionPullUpConstantsRule

Close apache/calcite#275

Forgot to close the PR for [CALCITE-1290]:
Close apache/calcite#273


Project: http://git-wip-us.apache.org/repos/asf/calcite/repo
Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/9b1624a8
Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/9b1624a8
Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/9b1624a8

Branch: refs/heads/master
Commit: 9b1624a88a506a3ceb1c5ccada1522d2a665aec6
Parents: e872959
Author: Jesus Camacho Rodriguez <jcamacho@apache.org>
Authored: Tue Aug 30 16:15:56 2016 +0100
Committer: Julian Hyde <jhyde@apache.org>
Committed: Wed Aug 31 12:10:26 2016 -0700

----------------------------------------------------------------------
 .../org/apache/calcite/plan/RelOptUtil.java     |   2 +
 .../calcite/rel/metadata/RelMdPredicates.java   |  52 +++++--
 .../rel/rules/UnionPullUpConstantsRule.java     | 146 +++++++++++++++++++
 .../apache/calcite/test/RelOptRulesTest.java    |  41 ++++++
 .../org/apache/calcite/tools/PlannerTest.java   |   8 +-
 .../org/apache/calcite/test/RelOptRulesTest.xml |  72 +++++++++
 6 files changed, 306 insertions(+), 15 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
index a6636a8..7cc5212 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
@@ -45,6 +45,7 @@ import org.apache.calcite.rel.rules.FilterMergeRule;
 import org.apache.calcite.rel.rules.MultiJoin;
 import org.apache.calcite.rel.rules.ProjectToWindowRule;
 import org.apache.calcite.rel.rules.PruneEmptyRules;
+import org.apache.calcite.rel.rules.UnionPullUpConstantsRule;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeFactory;
 import org.apache.calcite.rel.type.RelDataTypeField;
@@ -1673,6 +1674,7 @@ public abstract class RelOptUtil {
 
   public static void registerAbstractRels(RelOptPlanner planner) {
     planner.addRule(AggregateProjectPullUpConstantsRule.INSTANCE2);
+    planner.addRule(UnionPullUpConstantsRule.INSTANCE);
     planner.addRule(PruneEmptyRules.UNION_INSTANCE);
     planner.addRule(PruneEmptyRules.PROJECT_INSTANCE);
     planner.addRule(PruneEmptyRules.FILTER_INSTANCE);

http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
index 0e7183a..d256e9b 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdPredicates.java
@@ -63,10 +63,12 @@ import com.google.common.collect.Maps;
 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.SortedMap;
 
@@ -305,27 +307,55 @@ public class RelMdPredicates
 
   /**
    * Infers predicates for a Union.
-   *
-   * <p>The pulled up expression is a disjunction of its children's predicates.
    */
   public RelOptPredicateList getPredicates(Union union, RelMetadataQuery mq) {
     RexBuilder rB = union.getCluster().getRexBuilder();
-    List<RexNode> orList = Lists.newArrayList();
-    for (RelNode input : union.getInputs()) {
+
+    Map<String, RexNode> finalPreds = new HashMap<>();
+    List<RexNode> finalResidualPreds = new ArrayList<>();
+    for (int i = 0; i < union.getInputs().size(); i++) {
+      RelNode input = union.getInputs().get(i);
       RelOptPredicateList info = mq.getPulledUpPredicates(input);
       if (info.pulledUpPredicates.isEmpty()) {
         return RelOptPredicateList.EMPTY;
       }
-      RelOptUtil.decomposeDisjunction(
-          RexUtil.composeConjunction(rB, info.pulledUpPredicates, false),
-          orList);
+      Map<String, RexNode> preds = new HashMap<>();
+      List<RexNode> residualPreds = new ArrayList<>();
+      for (RexNode pred : info.pulledUpPredicates) {
+        final String predDigest = pred.toString();
+        if (i == 0) {
+          preds.put(predDigest, pred);
+          continue;
+        }
+        if (finalPreds.containsKey(predDigest)) {
+          preds.put(predDigest, pred);
+        } else {
+          residualPreds.add(pred);
+        }
+      }
+      // Add new residual preds
+      finalResidualPreds.add(RexUtil.composeConjunction(rB, residualPreds, false));
+      // Add those that are not part of the final set to residual
+      for (Entry<String, RexNode> e : finalPreds.entrySet()) {
+        if (!preds.containsKey(e.getKey())) {
+          // This node was in previous union inputs, but it is not in this one
+          for (int j = 0; j < i; j++) {
+            finalResidualPreds.set(j,
+                RexUtil.composeConjunction(rB,
+                    Lists.newArrayList(finalResidualPreds.get(j), e.getValue()), false));
+          }
+        }
+      }
+      // Final preds
+      finalPreds = preds;
     }
 
-    if (orList.isEmpty()) {
-      return RelOptPredicateList.EMPTY;
+    List<RexNode> preds = new ArrayList<>(finalPreds.values());
+    RexNode disjPred = RexUtil.composeDisjunction(rB, finalResidualPreds, false);
+    if (!disjPred.isAlwaysFalse()) {
+      preds.add(disjPred);
     }
-    return RelOptPredicateList.of(
-        RelOptUtil.conjunctions(RexUtil.composeDisjunction(rB, orList, false)));
+    return RelOptPredicateList.of(preds);
   }
 
   /**

http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/main/java/org/apache/calcite/rel/rules/UnionPullUpConstantsRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/UnionPullUpConstantsRule.java
b/core/src/main/java/org/apache/calcite/rel/rules/UnionPullUpConstantsRule.java
new file mode 100644
index 0000000..b59b08d
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/rules/UnionPullUpConstantsRule.java
@@ -0,0 +1,146 @@
+/*
+ * 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.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.RelOptRule;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.RelFactories;
+import org.apache.calcite.rel.core.Union;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.tools.RelBuilder;
+import org.apache.calcite.tools.RelBuilderFactory;
+import org.apache.calcite.util.ImmutableBitSet;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.mapping.Mappings;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Planner rule that pulls up constants through a Union operator.
+ */
+public class UnionPullUpConstantsRule extends RelOptRule {
+
+  public static final UnionPullUpConstantsRule INSTANCE =
+      new UnionPullUpConstantsRule(Union.class, RelFactories.LOGICAL_BUILDER);
+
+  /** Creates a UnionPullUpConstantsRule. */
+  protected UnionPullUpConstantsRule(Class<? extends Union> unionClass,
+      RelBuilderFactory relBuilderFactory) {
+    super(operand(unionClass, any()), relBuilderFactory, null);
+  }
+
+  @Override public void onMatch(RelOptRuleCall call) {
+    final Union union = call.rel(0);
+
+    final int count = union.getRowType().getFieldCount();
+    if (count == 1) {
+      // No room for optimization since we cannot create an empty Project
+      // operator. If we created a Project with one column, this rule would
+      // cycle.
+      return;
+    }
+
+    final RexBuilder rexBuilder = union.getCluster().getRexBuilder();
+    final RelMetadataQuery mq = RelMetadataQuery.instance();
+    final RelOptPredicateList predicates = mq.getPulledUpPredicates(union);
+    if (predicates == null) {
+      return;
+    }
+
+    Map<RexNode, RexNode> conditionsExtracted =
+        ReduceExpressionsRule.predicateConstants(RexNode.class, rexBuilder,
+            predicates);
+    Map<RexNode, RexNode> constants = new HashMap<>();
+    for (int i = 0; i < count; i++) {
+      RexNode expr = rexBuilder.makeInputRef(union, i);
+      if (conditionsExtracted.containsKey(expr)) {
+        constants.put(expr, conditionsExtracted.get(expr));
+      }
+    }
+
+    // None of the expressions are constant. Nothing to do.
+    if (constants.isEmpty()) {
+      return;
+    }
+
+    // Create expressions for Project operators before and after the Union
+    List<RelDataTypeField> fields = union.getRowType().getFieldList();
+    List<RexNode> topChildExprs = new ArrayList<>();
+    List<String> topChildExprsFields = new ArrayList<>();
+    List<RexNode> refs = new ArrayList<>();
+    ImmutableBitSet.Builder refsIndexBuilder = ImmutableBitSet.builder();
+    for (int i = 0; i < count; i++) {
+      RexNode expr = rexBuilder.makeInputRef(union, i);
+      RelDataTypeField field = fields.get(i);
+      if (constants.containsKey(expr)) {
+        topChildExprs.add(constants.get(expr));
+        topChildExprsFields.add(field.getName());
+      } else {
+        topChildExprs.add(expr);
+        topChildExprsFields.add(field.getName());
+        refs.add(expr);
+        refsIndexBuilder.set(i);
+      }
+    }
+    ImmutableBitSet refsIndex = refsIndexBuilder.build();
+
+    // Update top Project positions
+    final Mappings.TargetMapping mapping =
+        RelOptUtil.permutation(refs, union.getInput(0).getRowType()).inverse();
+    topChildExprs = ImmutableList.copyOf(RexUtil.apply(mapping, topChildExprs));
+
+    // Create new Project-Union-Project sequences
+    final RelBuilder relBuilder = call.builder();
+    for (RelNode input : union.getInputs()) {
+      List<Pair<RexNode, String>> newChildExprs = new ArrayList<>();
+      for (int j : refsIndex) {
+        newChildExprs.add(
+            Pair.<RexNode, String>of(rexBuilder.makeInputRef(input, j),
+                input.getRowType().getFieldList().get(j).getName()));
+      }
+      if (newChildExprs.isEmpty()) {
+        // At least a single item in project is required.
+        newChildExprs.add(
+            Pair.of(topChildExprs.get(0), topChildExprsFields.get(0)));
+      }
+      // Add the input with project on top
+      relBuilder.push(input);
+      relBuilder.project(Pair.left(newChildExprs), Pair.right(newChildExprs));
+    }
+    relBuilder.union(union.all, union.getInputs().size());
+    // Create top Project fixing nullability of fields
+    relBuilder.project(topChildExprs, topChildExprsFields);
+    relBuilder.convert(union.getRowType(), false);
+
+    call.transformTo(relBuilder.build());
+  }
+
+}
+
+// End UnionPullUpConstantsRule.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java b/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
index 9aa6239..6ad6747 100644
--- a/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
@@ -80,6 +80,7 @@ import org.apache.calcite.rel.rules.SortProjectTransposeRule;
 import org.apache.calcite.rel.rules.SortUnionTransposeRule;
 import org.apache.calcite.rel.rules.SubQueryRemoveRule;
 import org.apache.calcite.rel.rules.TableScanRule;
+import org.apache.calcite.rel.rules.UnionPullUpConstantsRule;
 import org.apache.calcite.rel.rules.UnionToDistinctRule;
 import org.apache.calcite.rel.rules.ValuesReduceRule;
 import org.apache.calcite.rel.type.RelDataType;
@@ -1655,6 +1656,46 @@ public class RelOptRulesTest extends RelOptTestBase {
     basePullConstantTroughAggregate();
   }
 
+  @Test public void testPullConstantThroughUnion()
+      throws Exception {
+    HepProgram preProgram = HepProgram.builder().build();
+    HepProgram program = HepProgram.builder()
+        .addRuleInstance(UnionPullUpConstantsRule.INSTANCE)
+        .addRuleInstance(ProjectMergeRule.INSTANCE)
+        .build();
+    final String sql = "select 2, deptno, job from emp as e1\n"
+        + "union all\n"
+        + "select 2, deptno, job from emp as e2";
+    checkPlanning(tester.withTrim(true), preProgram, new HepPlanner(program), sql);
+  }
+
+  @Test public void testPullConstantThroughUnion2()
+      throws Exception {
+    // Negative test: constants should not be pulled up
+    HepProgram program = HepProgram.builder()
+        .addRuleInstance(UnionPullUpConstantsRule.INSTANCE)
+        .addRuleInstance(ProjectMergeRule.INSTANCE)
+        .build();
+    final String sql = "select 2, deptno, job from emp as e1\n"
+        + "union all\n"
+        + "select 1, deptno, job from emp as e2";
+    checkPlanUnchanged(new HepPlanner(program), sql);
+  }
+
+  @Test public void testPullConstantThroughUnion3()
+      throws Exception {
+    // We should leave at least a single column in each Union input
+    HepProgram preProgram = HepProgram.builder().build();
+    HepProgram program = HepProgram.builder()
+        .addRuleInstance(UnionPullUpConstantsRule.INSTANCE)
+        .addRuleInstance(ProjectMergeRule.INSTANCE)
+        .build();
+    final String sql = "select 2, 3 from emp as e1\n"
+        + "union all\n"
+        + "select 2, 3 from emp as e2";
+    checkPlanning(tester.withTrim(true), preProgram, new HepPlanner(program), sql);
+  }
+
   @Test public void testAggregateProjectMerge() throws Exception {
     HepProgram program = new HepProgramBuilder()
         .addRuleInstance(AggregateProjectMergeRule.INSTANCE)

http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/tools/PlannerTest.java b/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
index 4aa2795..826e775 100644
--- a/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
+++ b/core/src/test/java/org/apache/calcite/tools/PlannerTest.java
@@ -300,13 +300,13 @@ public class PlannerTest {
   }
 
   @Test public void testMetadataUnionPredicates3() throws Exception {
-    // The result [OR(<($1, 10), AND(<($1, 10), >($0, 1)))]
-    // could be simplified to [<($1, 10)] but is nevertheless correct.
+    // The result is [OR(<($1, 10), AND(<($1, 10), >($0, 1)))]
+    // which can be simplified to [<($1, 10)].
     checkMetadataUnionPredicates(
         "select * from \"emps\" where \"deptno\" < 10\n"
             + "union all\n"
             + "select * from \"emps\" where \"deptno\" < 10 and \"empid\" > 1",
-        "[OR(<($1, 10), AND(<($1, 10), >($0, 1)))]");
+        "[<($1, 10), OR(true, >($0, 1))]");
   }
 
   @Test public void testMetadataUnionPredicates4() throws Exception {
@@ -314,7 +314,7 @@ public class PlannerTest {
         "select * from \"emps\" where \"deptno\" < 10\n"
             + "union all\n"
             + "select * from \"emps\" where \"deptno\" < 10 or \"empid\" > 1",
-        "[OR(<($1, 10), >($0, 1))]");
+        "[OR(<($1, 10), <($1, 10), >($0, 1))]");
   }
 
   /** Unit test that parses, validates, converts and plans. */

http://git-wip-us.apache.org/repos/asf/calcite/blob/9b1624a8/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
----------------------------------------------------------------------
diff --git a/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml b/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
index 07e8c91..27816d4 100644
--- a/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
+++ b/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
@@ -2034,6 +2034,78 @@ LogicalProject(EXPR$0=[$0], EXPR$1=[+(2, 3)], EXPR$2=[$1])
 ]]>
         </Resource>
     </TestCase>
+    <TestCase name="testPullConstantThroughUnion">
+        <Resource name="sql">
+            <![CDATA[select 2, deptno, job from emp as e1
+union all
+select 2, deptno, job from emp as e2]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+LogicalUnion(all=[true])
+  LogicalProject(EXPR$0=[2], DEPTNO=[$1], JOB=[$0])
+    LogicalProject(JOB=[$2], DEPTNO=[$7])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+  LogicalProject(EXPR$0=[2], DEPTNO=[$1], JOB=[$0])
+    LogicalProject(JOB=[$2], DEPTNO=[$7])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+LogicalProject(EXPR$0=[2], DEPTNO=[$0], JOB=[$1])
+  LogicalUnion(all=[true])
+    LogicalProject(DEPTNO=[$7], JOB=[$2])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+    LogicalProject(DEPTNO=[$7], JOB=[$2])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+    </TestCase>
+    <TestCase name="testPullConstantThroughUnion2">
+        <Resource name="sql">
+            <![CDATA[select 2, deptno, job from emp as e1
+union all
+select 1, deptno, job from emp as e2]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+LogicalUnion(all=[true])
+  LogicalProject(EXPR$0=[2], DEPTNO=[$7], JOB=[$2])
+    LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+  LogicalProject(EXPR$0=[1], DEPTNO=[$7], JOB=[$2])
+    LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+    </TestCase>
+    <TestCase name="testPullConstantThroughUnion3">
+        <Resource name="sql">
+            <![CDATA[select 2, 3 from emp as e1
+union all
+select 2, 3 from emp as e2]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+LogicalUnion(all=[true])
+  LogicalProject(EXPR$0=[2], EXPR$1=[3])
+    LogicalProject(DUMMY=[0])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+  LogicalProject(EXPR$0=[2], EXPR$1=[3])
+    LogicalProject(DUMMY=[0])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+LogicalProject(EXPR$0=[2], EXPR$1=[3])
+  LogicalUnion(all=[true])
+    LogicalProject(EXPR$0=[2])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+    LogicalProject(EXPR$0=[2])
+      LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+    </TestCase>
     <TestCase name="testConvertMultiJoinRule">
         <Resource name="sql">
             <![CDATA[select e1.ename from emp e1, dept d, emp e2 where e1.deptno = d.deptno
and d.deptno = e2.deptno]]>


Mime
View raw message