calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [1/4] calcite git commit: [CALCITE-1056] In RelBuilder, simplify predicates, and optimize away WHERE FALSE
Date Fri, 22 Jan 2016 07:29:21 GMT
Repository: calcite
Updated Branches:
  refs/heads/master 920a64881 -> 6acb28d84


[CALCITE-1056] In RelBuilder, simplify predicates, and optimize away WHERE FALSE


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

Branch: refs/heads/master
Commit: ee52f691b844d97919a8c0ca211a7c78b86165ef
Parents: 6201013
Author: Julian Hyde <jhyde@apache.org>
Authored: Wed Jan 13 16:07:01 2016 -0800
Committer: Julian Hyde <jhyde@apache.org>
Committed: Thu Jan 21 15:03:41 2016 -0800

----------------------------------------------------------------------
 .../org/apache/calcite/plan/RelOptUtil.java     | 32 +++++++---
 .../java/org/apache/calcite/rex/RexUtil.java    | 61 +++++++++++++-------
 .../org/apache/calcite/tools/RelBuilder.java    | 21 ++++---
 .../calcite/test/MaterializationTest.java       |  2 +-
 .../org/apache/calcite/test/RelBuilderTest.java | 58 +++++++++++++++++--
 .../org/apache/calcite/test/RexProgramTest.java | 20 +++++++
 6 files changed, 150 insertions(+), 44 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/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 eeaea21..610867a 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
@@ -678,15 +678,11 @@ public abstract class RelOptUtil {
         RexUtil.generateCastExpressions(rexBuilder, castRowType, rowType);
     if (rename) {
       // Use names and types from castRowType.
-      return projectFactory.createProject(
-          rel,
-          castExps,
+      return projectFactory.createProject(rel, castExps,
           castRowType.getFieldNames());
     } else {
       // Use names from rowType, types from castRowType.
-      return projectFactory.createProject(
-          rel,
-          castExps,
+      return projectFactory.createProject(rel, castExps,
           rowType.getFieldNames());
     }
   }
@@ -1928,8 +1924,30 @@ public abstract class RelOptUtil {
       if (e.isAlwaysFalse()) {
         return;
       }
-      notList.add(e);
+      switch (e.getKind()) {
+      case OR:
+        final List<RexNode> ors = new ArrayList<>();
+        decomposeDisjunction(e, ors);
+        for (RexNode or : ors) {
+          switch (or.getKind()) {
+          case NOT:
+            rexList.add(((RexCall) or).operands.get(0));
+            break;
+          default:
+            notList.add(or);
+          }
+        }
+        break;
+      default:
+        notList.add(e);
+      }
       break;
+    case LITERAL:
+      if (!RexLiteral.isNullLiteral(rexPredicate)
+          && RexLiteral.booleanValue(rexPredicate)) {
+        return; // ignore TRUE
+      }
+      // fall through
     default:
       rexList.add(rexPredicate);
       break;

http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/main/java/org/apache/calcite/rex/RexUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rex/RexUtil.java b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
index b766590..ce3e936 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
@@ -1308,6 +1308,19 @@ public class RexUtil {
     }
   }
 
+  /**
+   * Simplifies a conjunction of boolean expressions.
+   */
+  public static RexNode simplifyAnds(RexBuilder rexBuilder,
+      Iterable<? extends RexNode> nodes) {
+    final List<RexNode> terms = new ArrayList<>();
+    final List<RexNode> notTerms = new ArrayList<>();
+    for (RexNode e : nodes) {
+      RelOptUtil.decomposeConjunction(e, terms, notTerms);
+    }
+    return simplifyAnd2(rexBuilder, terms, notTerms);
+  }
+
   private static RexNode simplifyNot(RexBuilder rexBuilder, RexCall call) {
     final RexNode a = call.getOperands().get(0);
     switch (a.getKind()) {
@@ -1324,6 +1337,17 @@ public class RexUtil {
     return call;
   }
 
+  /** Negates a logical expression by adding or removing a NOT. */
+  public static RexNode not(RexNode e) {
+    switch (e.getKind()) {
+    case NOT:
+      return ((RexCall) e).getOperands().get(0);
+    default:
+      return new RexCall(e.getType(), SqlStdOperatorTable.NOT,
+          ImmutableList.of(e));
+    }
+  }
+
   private static RexNode simplifyIs(RexBuilder rexBuilder, RexCall call) {
     final SqlKind kind = call.getKind();
     final RexNode a = call.getOperands().get(0);
@@ -1461,31 +1485,24 @@ public class RexUtil {
   }
 
   public static RexNode simplifyAnd(RexBuilder rexBuilder, RexCall e) {
-    final List<RexNode> terms = RelOptUtil.conjunctions(e);
+    final List<RexNode> terms = new ArrayList<>();
     final List<RexNode> notTerms = new ArrayList<>();
-    for (int i = 0; i < terms.size(); i++) {
-      final RexNode term = terms.get(i);
-      switch (term.getKind()) {
-      case NOT:
-        notTerms.add(
-            ((RexCall) term).getOperands().get(0));
-        terms.remove(i);
-        --i;
-        break;
-      case LITERAL:
-        if (!RexLiteral.isNullLiteral(term)) {
-          if (!RexLiteral.booleanValue(term)) {
-            return term; // false
-          } else {
-            terms.remove(i);
-            --i;
-          }
-        }
-      }
+    RelOptUtil.decomposeConjunction(e, terms, notTerms);
+    return simplifyAnd2(rexBuilder, terms, notTerms);
+  }
+
+  public static RexNode simplifyAnd2(RexBuilder rexBuilder,
+      List<RexNode> terms, List<RexNode> notTerms) {
+    if (terms.contains(rexBuilder.makeLiteral(false))) {
+      return rexBuilder.makeLiteral(false);
     }
     if (terms.isEmpty() && notTerms.isEmpty()) {
       return rexBuilder.makeLiteral(true);
     }
+    if (terms.size() == 1 && notTerms.isEmpty()) {
+      // Make sure "x OR y OR x" (a single-term conjunction) gets simplified.
+      return simplify(rexBuilder, terms.get(0));
+    }
     // If one of the not-disjunctions is a disjunction that is wholly
     // contained in the disjunctions list, the expression is not
     // satisfiable.
@@ -1502,8 +1519,8 @@ public class RexUtil {
     // Add the NOT disjunctions back in.
     for (RexNode notDisjunction : notTerms) {
       terms.add(
-          rexBuilder.makeCall(
-              SqlStdOperatorTable.NOT, notDisjunction));
+          simplify(rexBuilder,
+              rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction)));
     }
     return composeConjunction(rexBuilder, terms, false);
   }

http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/main/java/org/apache/calcite/tools/RelBuilder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java
index cf9fcb6..32d3b6b 100644
--- a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java
+++ b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java
@@ -452,9 +452,13 @@ public class RelBuilder {
     return and(ImmutableList.copyOf(operands));
   }
 
-  /** Creates an AND. */
+  /** Creates an AND.
+   *
+   * <p>Simplifies the expression a little:
+   * {@code e AND TRUE} becomes {@code e};
+   * {@code e AND e2 AND NOT e} becomes {@code e2}. */
   public RexNode and(Iterable<? extends RexNode> operands) {
-    return RexUtil.composeConjunction(cluster.getRexBuilder(), operands, false);
+    return RexUtil.simplifyAnds(cluster.getRexBuilder(), operands);
   }
 
   /** Creates an OR. */
@@ -692,8 +696,10 @@ public class RelBuilder {
    * and optimized in a similar way to the {@link #and} method.
    * If the result is TRUE no filter is created. */
   public RelBuilder filter(Iterable<? extends RexNode> predicates) {
-    final RexNode x = RexUtil.simplify(cluster.getRexBuilder(),
-            RexUtil.composeConjunction(cluster.getRexBuilder(), predicates, false));
+    final RexNode x = RexUtil.simplifyAnds(cluster.getRexBuilder(), predicates);
+    if (x.isAlwaysFalse()) {
+      return empty();
+    }
     if (!x.isAlwaysTrue()) {
       final Frame frame = Stacks.pop(stack);
       final RelNode filter = filterFactory.createFilter(frame.rel, x);
@@ -991,8 +997,7 @@ public class RelBuilder {
    * conditions. */
   public RelBuilder join(JoinRelType joinType,
       Iterable<? extends RexNode> conditions) {
-    return join(joinType,
-        RexUtil.composeConjunction(cluster.getRexBuilder(), conditions, false),
+    return join(joinType, and(conditions),
         ImmutableSet.<CorrelationId>of());
   }
 
@@ -1057,9 +1062,7 @@ public class RelBuilder {
     final Frame right = Stacks.pop(stack);
     final Frame left = Stacks.pop(stack);
     final RelNode semiJoin =
-        semiJoinFactory.createSemiJoin(left.rel, right.rel,
-            RexUtil.composeConjunction(cluster.getRexBuilder(), conditions,
-                false));
+        semiJoinFactory.createSemiJoin(left.rel, right.rel, and(conditions));
     Stacks.push(stack, new Frame(semiJoin, left.right));
     return this;
   }

http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
index 05726b3..389d3ec 100644
--- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
+++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
@@ -259,7 +259,7 @@ public class MaterializationTest {
       MaterializationService.setThreadLocal();
       final String m = "select \"salary\", \"commission\",\n"
           + "\"deptno\", \"empid\", \"name\" from \"emps\"";
-      final String v = "select * from \"emps\" where \"salary\" is null";
+      final String v = "select * from \"emps\" where \"name\" is null";
       final String q = "select * from V where \"commission\" is null";
       final JsonBuilder builder = new JsonBuilder();
       final String model = "{\n"

http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
index db13a02..8a164c5 100644
--- a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
@@ -207,6 +207,10 @@ public class RelBuilderTest {
     //   SELECT *
     //   FROM emp
     //   WHERE deptno = 20 OR deptno = 20
+    // simplifies to
+    //   SELECT *
+    //   FROM emp
+    //   WHERE deptno = 20
     final RelBuilder builder = RelBuilder.create(config().build());
     RelNode root =
         builder.scan("EMP")
@@ -224,6 +228,45 @@ public class RelBuilderTest {
             + "  LogicalTableScan(table=[[scott, EMP]])\n"));
   }
 
+  @Test public void testScanFilterAndFalse() {
+    // Equivalent SQL:
+    //   SELECT *
+    //   FROM emp
+    //   WHERE deptno = 20 AND FALSE
+    // simplifies to
+    //   VALUES
+    final RelBuilder builder = RelBuilder.create(config().build());
+    RelNode root =
+        builder.scan("EMP")
+            .filter(
+                builder.call(SqlStdOperatorTable.GREATER_THAN,
+                    builder.field("DEPTNO"),
+                    builder.literal(20)),
+                builder.literal(false))
+            .build();
+    final String plan = "LogicalValues(tuples=[[]])\n";
+    assertThat(str(root), is(plan));
+  }
+
+  @Test public void testScanFilterAndTrue() {
+    // Equivalent SQL:
+    //   SELECT *
+    //   FROM emp
+    //   WHERE deptno = 20 AND TRUE
+    final RelBuilder builder = RelBuilder.create(config().build());
+    RelNode root =
+        builder.scan("EMP")
+            .filter(
+                builder.call(SqlStdOperatorTable.GREATER_THAN,
+                    builder.field("DEPTNO"),
+                    builder.literal(20)),
+                builder.literal(true))
+            .build();
+    final String plan = "LogicalFilter(condition=[>($7, 20)])\n"
+        + "  LogicalTableScan(table=[[scott, EMP]])\n";
+    assertThat(str(root), is(plan));
+  }
+
   @Test public void testBadFieldName() {
     final RelBuilder builder = RelBuilder.create(config().build());
     try {
@@ -295,7 +338,7 @@ public class RelBuilderTest {
                 builder.or(
                     builder.equals(builder.field("DEPTNO"),
                         builder.literal(20)),
-                    builder.and(builder.literal(false),
+                    builder.and(builder.literal(null),
                         builder.equals(builder.field("DEPTNO"),
                             builder.literal(10)),
                         builder.and(builder.isNull(builder.field(6)),
@@ -312,8 +355,8 @@ public class RelBuilderTest {
             .build();
     assertThat(str(root),
         is("LogicalProject(DEPTNO=[$7], COMM=[CAST($6):SMALLINT NOT NULL],"
-                + " $f2=[OR(=($7, 20), AND(false, =($7, 10), IS NULL($6),"
-                + " NOT(IS NOT NULL($7))), =($7, 30))], n2=[IS NULL($2)],"
+                + " $f2=[OR(=($7, 20), AND(null, =($7, 10), IS NULL($6),"
+                + " IS NULL($7)), =($7, 30))], n2=[IS NULL($2)],"
                 + " nn2=[IS NOT NULL($3)], $f5=[20], COMM6=[$6], C=[$6])\n"
                 + "  LogicalTableScan(table=[[scott, EMP]])\n"));
   }
@@ -760,7 +803,9 @@ public class RelBuilderTest {
     // Equivalent SQL:
     //   SELECT *
     //   FROM emp
-    //   LEFT JOIN dept ON emp.deptno = dept.deptno AND emp.empno = 123
+    //   LEFT JOIN dept ON emp.deptno = dept.deptno
+    //     AND emp.empno = 123
+    //     AND dept.deptno IS NOT NULL
     final RelBuilder builder = RelBuilder.create(config().build());
     RelNode root =
         builder.scan("EMP")
@@ -771,8 +816,11 @@ public class RelBuilderTest {
                     builder.field(2, 1, "DEPTNO")),
                 builder.call(SqlStdOperatorTable.EQUALS,
                     builder.field(2, 0, "EMPNO"),
-                    builder.literal(123)))
+                    builder.literal(123)),
+                builder.call(SqlStdOperatorTable.IS_NOT_NULL,
+                    builder.field(2, 1, "DEPTNO")))
             .build();
+    // Note that "dept.deptno IS NOT NULL" has been simplified away.
     final String expected = ""
         + "LogicalJoin(condition=[AND(=($7, $0), =($0, 123))], joinType=[left])\n"
         + "  LogicalTableScan(table=[[scott, EMP]])\n"

http://git-wip-us.apache.org/repos/asf/calcite/blob/ee52f691/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
index 7b50427..1efb8cc 100644
--- a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
@@ -771,6 +771,26 @@ public class RexProgramTest {
     checkSimplify(and(aRef, bRef, false_),
         "false");
 
+    // and: remove duplicate "not"s
+    checkSimplify(and(not(aRef), bRef, not(cRef), not(aRef)),
+        "AND(?0.b, NOT(?0.a), NOT(?0.c))");
+
+    // and: "not true" falsifies
+    checkSimplify(and(not(aRef), bRef, not(true_)),
+        "false");
+
+    // and: flatten and remove duplicates
+    checkSimplify(
+        and(aRef, and(and(bRef, not(cRef), dRef, not(eRef)), not(eRef))),
+        "AND(?0.a, ?0.b, ?0.d, NOT(?0.c), NOT(?0.e))");
+
+    // and: expand "... and not(or(x, y))" to "... and not(x) and not(y)"
+    checkSimplify(and(aRef, bRef, not(or(cRef, or(dRef, eRef)))),
+        "AND(?0.a, ?0.b, NOT(?0.c), NOT(?0.d), NOT(?0.e))");
+
+    checkSimplify(and(aRef, bRef, not(or(not(cRef), dRef, not(eRef)))),
+        "AND(?0.a, ?0.b, ?0.c, ?0.e, NOT(?0.d))");
+
     // or: remove duplicates
     checkSimplify(or(aRef, bRef, aRef), "OR(?0.a, ?0.b)");
 


Mime
View raw message