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-1220] Further extend simplify for reducing expressions
Date Tue, 30 Aug 2016 01:33:29 GMT
Repository: calcite
Updated Branches:
  refs/heads/master 71df67c97 -> e87295979


[CALCITE-1220] Further extend simplify for reducing expressions

Extends work done in [CALCITE-1116].

Close apache/calcite#270


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

Branch: refs/heads/master
Commit: e872959797de16ef856d76526da484e094ef0a10
Parents: 71df67c
Author: Jesus Camacho Rodriguez <jcamacho@apache.org>
Authored: Wed Aug 24 20:25:58 2016 +0100
Committer: Julian Hyde <jhyde@apache.org>
Committed: Mon Aug 29 16:14:10 2016 -0700

----------------------------------------------------------------------
 .../rel/rules/ReduceExpressionsRule.java        |  63 +++--
 .../java/org/apache/calcite/rex/RexUtil.java    | 274 ++++++++++++++++---
 .../calcite/test/MaterializationTest.java       |   8 +-
 .../apache/calcite/test/RelOptRulesTest.java    |  16 +-
 .../org/apache/calcite/test/RexProgramTest.java |  31 +++
 .../org/apache/calcite/test/RelOptRulesTest.xml |  43 ++-
 6 files changed, 358 insertions(+), 77 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/core/src/main/java/org/apache/calcite/rel/rules/ReduceExpressionsRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/ReduceExpressionsRule.java b/core/src/main/java/org/apache/calcite/rel/rules/ReduceExpressionsRule.java
index 44870af..5c50a8e 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/ReduceExpressionsRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/ReduceExpressionsRule.java
@@ -49,6 +49,7 @@ import org.apache.calcite.rex.RexProgramBuilder;
 import org.apache.calcite.rex.RexRangeRef;
 import org.apache.calcite.rex.RexShuttle;
 import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexUtil.ExprSimplifier;
 import org.apache.calcite.rex.RexVisitorImpl;
 import org.apache.calcite.sql.SqlKind;
 import org.apache.calcite.sql.SqlOperator;
@@ -157,6 +158,11 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
         newConditionExp = filter.getCondition();
         reduced = false;
       }
+
+      // Even if no reduction, let's still test the original
+      // predicate to see if it was already a constant,
+      // in which case we don't need any runtime decision
+      // about filtering.
       if (newConditionExp.isAlwaysTrue()) {
         call.transformTo(
             filter.getInput());
@@ -164,14 +170,16 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
           || RexUtil.isNullLiteral(newConditionExp, true)) {
         call.transformTo(createEmptyRelOrEquivalent(call, filter));
       } else if (reduced) {
+        if (RexUtil.isNullabilityCast(filter.getCluster().getTypeFactory(),
+            newConditionExp)) {
+          newConditionExp = ((RexCall) newConditionExp).getOperands().get(0);
+        }
         call.transformTo(call.builder().
-            push(filter.getInput()).filter(expList.get(0)).build());
+            push(filter.getInput()).filter(newConditionExp).build());
       } else {
         if (newConditionExp instanceof RexCall) {
           RexCall rexCall = (RexCall) newConditionExp;
-          boolean reverse =
-              rexCall.getOperator()
-                  == SqlStdOperatorTable.NOT;
+          boolean reverse = rexCall.getKind() == SqlKind.NOT;
           if (reverse) {
             rexCall = (RexCall) rexCall.getOperands().get(0);
           }
@@ -294,7 +302,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
           mq.getPulledUpPredicates(join.getRight());
       final RelOptPredicateList predicates =
           leftPredicates.union(rightPredicates.shift(fieldCount));
-      if (!reduceExpressions(join, expList, predicates)) {
+      if (!reduceExpressions(join, expList, predicates, true)) {
         return;
       }
       if (join instanceof EquiJoin) {
@@ -455,13 +463,13 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     boolean reduced = reduceExpressionsInternal(rel, expList, predicates);
 
     // Simplify preds in place
+    ExprSimplifier simplifier = new ExprSimplifier(rexBuilder, unknownAsFalse);
     boolean simplified = false;
     for (int i = 0; i < expList.size(); i++) {
-      RexNode newExp = RexUtil.simplify(rexBuilder, expList.get(i),
-          unknownAsFalse);
-      if (!newExp.toString().equals(expList.get(i).toString())) {
+      RexNode expr2 = simplifier.apply(expList.get(i));
+      if (!expr2.toString().equals(expList.get(i).toString())) {
         expList.remove(i);
-        expList.add(i, newExp);
+        expList.add(i, expr2);
         simplified = true;
       }
     }
@@ -480,8 +488,8 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     final List<RexNode> constExps = Lists.newArrayList();
     List<Boolean> addCasts = Lists.newArrayList();
     final List<RexNode> removableCasts = Lists.newArrayList();
-    final ImmutableMap<RexNode, RexLiteral> constants =
-        predicateConstants(RexLiteral.class, rexBuilder, predicates);
+    final ImmutableMap<RexNode, RexNode> constants =
+        predicateConstants(RexNode.class, rexBuilder, predicates);
     findReducibleExps(rel.getCluster().getTypeFactory(), expList, constants,
         constExps, addCasts, removableCasts);
     if (constExps.isEmpty() && removableCasts.isEmpty()) {
@@ -586,7 +594,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
    * @param removableCasts returns the list of cast expressions where the cast
    */
   protected static void findReducibleExps(RelDataTypeFactory typeFactory,
-      List<RexNode> exps, ImmutableMap<RexNode, ? extends RexNode> constants,
+      List<RexNode> exps, ImmutableMap<RexNode, RexNode> constants,
       List<RexNode> constExps, List<Boolean> addCasts,
       List<RexNode> removableCasts) {
     ReducibleExprLocator gardener =
@@ -609,9 +617,8 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
    *           {@link RexUtil#isConstant(RexNode)}
    * @return Map from values to constants
    */
-  protected static <C extends RexNode> ImmutableMap<RexNode, C>
-  predicateConstants(Class<C> clazz,
-      RexBuilder rexBuilder, RelOptPredicateList predicates) {
+  public static <C extends RexNode> ImmutableMap<RexNode, C> predicateConstants(
+          Class<C> clazz, RexBuilder rexBuilder, RelOptPredicateList predicates) {
     // We cannot use an ImmutableMap.Builder here. If there are multiple entries
     // with the same key (e.g. "WHERE deptno = 1 AND deptno = 2"), it doesn't
     // matter which we take, so the latter will replace the former.
@@ -665,18 +672,26 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
   private static <C extends RexNode> void gatherConstraints(Class<C> clazz,
       RexNode predicate, Map<RexNode, C> map, Set<RexNode> excludeSet,
       RexBuilder rexBuilder) {
-    if (predicate.getKind() != SqlKind.EQUALS) {
+    if (predicate.getKind() != SqlKind.EQUALS
+            && predicate.getKind() != SqlKind.IS_NULL) {
       decompose(excludeSet, predicate);
       return;
     }
     final List<RexNode> operands = ((RexCall) predicate).getOperands();
-    if (operands.size() != 2) {
+    if (operands.size() != 2 && predicate.getKind() == SqlKind.EQUALS) {
       decompose(excludeSet, predicate);
       return;
     }
     // if it reaches here, we have rexNode equals rexNode
-    final RexNode left = operands.get(0);
-    final RexNode right = operands.get(1);
+    final RexNode left;
+    final RexNode right;
+    if (predicate.getKind() == SqlKind.EQUALS) {
+      left = operands.get(0);
+      right = operands.get(1);
+    } else {
+      left = operands.get(0);
+      right = rexBuilder.makeNullLiteral(left.getType().getSqlTypeName());
+    }
     // note that literals are immutable too and they can only be compared through
     // values.
     gatherConstraint(clazz, left, right, map, excludeSet, rexBuilder);
@@ -858,7 +873,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
         // If we make 'abc' of type VARCHAR(4), we may later encounter
         // the same expression in a Project's digest where it has
         // type VARCHAR(3), and that's wrong.
-        replacement = rexBuilder.makeCast(call.getType(), replacement, true);
+        replacement = rexBuilder.makeAbstractCast(call.getType(), replacement);
       }
       return replacement;
     }
@@ -877,9 +892,9 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
 
     private final RelDataTypeFactory typeFactory;
 
-    private final List<Constancy> stack;
+    private final List<Constancy> stack = new ArrayList<>();
 
-    private final ImmutableMap<RexNode, ? extends RexNode> constants;
+    private final ImmutableMap<RexNode, RexNode> constants;
 
     private final List<RexNode> constExprs;
 
@@ -890,8 +905,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     private final Deque<SqlOperator> parentCallTypeStack = new ArrayDeque<>();
 
     ReducibleExprLocator(RelDataTypeFactory typeFactory,
-        ImmutableMap<RexNode, ? extends RexNode> constants,
-        List<RexNode> constExprs,
+        ImmutableMap<RexNode, RexNode> constants, List<RexNode> constExprs,
         List<Boolean> addCasts, List<RexNode> removableCasts) {
       // go deep
       super(true);
@@ -900,7 +914,6 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
       this.constExprs = constExprs;
       this.addCasts = addCasts;
       this.removableCasts = removableCasts;
-      this.stack = Lists.newArrayList();
     }
 
     public void analyze(RexNode exp) {

http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/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 8f94860..327b167 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
@@ -44,10 +44,12 @@ import org.apache.calcite.util.mapping.Mappings;
 
 import com.google.common.base.Function;
 import com.google.common.base.Predicate;
+import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
+import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
 
 import java.util.ArrayList;
@@ -264,6 +266,27 @@ public class RexUtil {
     return false;
   }
 
+  /**
+   * Returns whether a node represents an input reference or field access.
+   *
+   * @param node The node, never null.
+   * @param allowCast whether to regard CAST(x) as true
+   * @return Whether the node is a reference or access
+   */
+  public static boolean isReferenceOrAccess(RexNode node, boolean allowCast) {
+    assert node != null;
+    if (node instanceof RexInputRef || node instanceof RexFieldAccess) {
+      return true;
+    }
+    if (allowCast) {
+      if (node.isA(SqlKind.CAST)) {
+        RexCall call = (RexCall) node;
+        return isReferenceOrAccess(call.operands.get(0), false);
+      }
+    }
+    return false;
+  }
+
   /** Returns whether an expression is a cast just for the purposes of
    * nullability, not changing any other aspect of the type. */
   public static boolean isNullabilityCast(RelDataTypeFactory typeFactory,
@@ -1390,11 +1413,13 @@ public class RexUtil {
     case NOT:
       return simplifyNot(rexBuilder, (RexCall) e);
     case CASE:
-      return simplifyCase(rexBuilder, (RexCall) e);
-    }
-    switch (e.getKind()) {
+      return simplifyCase(rexBuilder, (RexCall) e, unknownAsFalse);
     case IS_NULL:
+      return ((RexCall) e).getOperands().get(0).getType().isNullable()
+          ? e : rexBuilder.makeLiteral(false);
     case IS_NOT_NULL:
+      return ((RexCall) e).getOperands().get(0).getType().isNullable()
+          ? e : rexBuilder.makeLiteral(true);
     case IS_TRUE:
     case IS_NOT_TRUE:
     case IS_FALSE:
@@ -1440,6 +1465,33 @@ public class RexUtil {
           rexBuilder.makeCall(op(negateKind),
               ImmutableList.of(((RexCall) a).getOperands().get(0))));
     }
+    final SqlKind negateKind2 = a.getKind().negateNullSafe();
+    if (a.getKind() != negateKind2) {
+      return simplify(rexBuilder,
+          rexBuilder.makeCall(op(negateKind2), ((RexCall) a).getOperands()));
+    }
+    if (a.getKind() == SqlKind.AND) {
+      // NOT distributivity for AND
+      final List<RexNode> newOperands = new ArrayList<>();
+      for (RexNode operand : ((RexCall) a).getOperands()) {
+        newOperands.add(
+            simplify(rexBuilder,
+                rexBuilder.makeCall(SqlStdOperatorTable.NOT, operand)));
+      }
+      return simplify(rexBuilder,
+          rexBuilder.makeCall(SqlStdOperatorTable.OR, newOperands));
+    }
+    if (a.getKind() == SqlKind.OR) {
+      // NOT distributivity for OR
+      final List<RexNode> newOperands = new ArrayList<>();
+      for (RexNode operand : ((RexCall) a).getOperands()) {
+        newOperands.add(
+            simplify(rexBuilder,
+                rexBuilder.makeCall(SqlStdOperatorTable.NOT, operand)));
+      }
+      return simplify(rexBuilder,
+          rexBuilder.makeCall(SqlStdOperatorTable.AND, newOperands));
+    }
     return call;
   }
 
@@ -1529,48 +1581,98 @@ public class RexUtil {
     }
   }
 
-  private static RexNode simplifyCase(RexBuilder rexBuilder, RexCall call) {
+  private static RexNode simplifyCase(RexBuilder rexBuilder, RexCall call,
+      boolean unknownAsFalse) {
     final List<RexNode> operands = call.getOperands();
     final List<RexNode> newOperands = new ArrayList<>();
+    final Set<String> values = new HashSet<>();
     for (int i = 0; i < operands.size(); i++) {
       RexNode operand = operands.get(i);
       if (isCasePredicate(call, i)) {
         if (operand.isAlwaysTrue()) {
           // Predicate is always TRUE. Make value the ELSE and quit.
-          newOperands.add(operands.get(i + 1));
+          newOperands.add(operands.get(++i));
+          if (unknownAsFalse && isNull(operands.get(i))) {
+            values.add(rexBuilder.makeLiteral(false).toString());
+          } else {
+            values.add(operands.get(i).toString());
+          }
           break;
-        }
-        if (operand.isAlwaysFalse()) {
-          // Predicate is always FALSE. Skip predicate and value.
+        } else if (operand.isAlwaysFalse() || isNull(operand)) {
+          // Predicate is always FALSE or NULL. Skip predicate and value.
           ++i;
           continue;
         }
+      } else {
+        if (unknownAsFalse && isNull(operand)) {
+          values.add(rexBuilder.makeLiteral(false).toString());
+        } else {
+          values.add(operand.toString());
+        }
       }
       newOperands.add(operand);
     }
     assert newOperands.size() % 2 == 1;
-    switch (newOperands.size()) {
-    case 1:
-      if (!call.getType().equals(newOperands.get(0).getType())) {
-        return rexBuilder.makeCast(call.getType(), newOperands.get(0));
+    if (newOperands.size() == 1 || values.size() == 1) {
+      if (!call.getType().equals(newOperands.get(newOperands.size() - 1).getType())) {
+        return rexBuilder.makeCast(call.getType(), newOperands.get(newOperands.size() - 1));
       }
-      return newOperands.get(0);
+      return newOperands.get(newOperands.size() - 1);
     }
   trueFalse:
     if (call.getType().getSqlTypeName() == SqlTypeName.BOOLEAN) {
       // Optimize CASE where every branch returns constant true or constant
-      // false:
+      // false.
+      final List<Pair<RexNode, RexNode>> pairs =
+          casePairs(rexBuilder, newOperands);
+      // 1) Possible simplification if unknown is treated as false:
+      //   CASE
+      //   WHEN p1 THEN TRUE
+      //   WHEN p2 THEN TRUE
+      //   ELSE FALSE
+      //   END
+      // can be rewritten to: (p1 or p2)
+      if (unknownAsFalse) {
+        final List<RexNode> terms = new ArrayList<>();
+        int pos = 0;
+        for (; pos < pairs.size(); pos++) {
+          // True block
+          Pair<RexNode, RexNode> pair = pairs.get(pos);
+          if (!pair.getValue().isAlwaysTrue()) {
+            break;
+          }
+          terms.add(pair.getKey());
+        }
+        for (; pos < pairs.size(); pos++) {
+          // False block
+          Pair<RexNode, RexNode> pair = pairs.get(pos);
+          if (!pair.getValue().isAlwaysFalse() && !isNull(pair.getValue())) {
+            break;
+          }
+        }
+        if (pos == pairs.size()) {
+          final RexNode disjunction = composeDisjunction(rexBuilder, terms, false);
+          if (!call.getType().equals(disjunction.getType())) {
+            return rexBuilder.makeCast(call.getType(), disjunction);
+          }
+          return disjunction;
+        }
+      }
+      // 2) Another simplification
       //   CASE
       //   WHEN p1 THEN TRUE
       //   WHEN p2 THEN FALSE
       //   WHEN p3 THEN TRUE
       //   ELSE FALSE
       //   END
-      final List<Pair<RexNode, RexNode>> pairs =
-          casePairs(rexBuilder, newOperands);
+      // if p1...pn cannot be nullable
       for (Ord<Pair<RexNode, RexNode>> pair : Ord.zip(pairs)) {
+        if (pair.e.getKey().getType().isNullable()) {
+          break trueFalse;
+        }
         if (!pair.e.getValue().isAlwaysTrue()
-            && !pair.e.getValue().isAlwaysFalse()) {
+            && !pair.e.getValue().isAlwaysFalse()
+            && (!unknownAsFalse || !isNull(pair.e.getValue()))) {
           break trueFalse;
         }
       }
@@ -1583,15 +1685,11 @@ public class RexUtil {
           notTerms.add(pair.e.getKey());
         }
       }
-      RexNode disjunction = composeDisjunction(rexBuilder, terms, false);
-
-      assert call.getType().getSqlTypeName() == disjunction.getType().getSqlTypeName();
-      if (call.getType().isNullable() == disjunction.getType().isNullable()) {
-        return disjunction;
-      } else if (call.getType().isNullable() && !disjunction.getType().isNullable())
{
-        return rexBuilder.ensureType(call.getType(), disjunction, false);
+      final RexNode disjunction = composeDisjunction(rexBuilder, terms, false);
+      if (!call.getType().equals(disjunction.getType())) {
+        return rexBuilder.makeCast(call.getType(), disjunction);
       }
-      // if call is not nullable, but the disjunction is, we should not use the disjunction.
+      return disjunction;
     }
     if (newOperands.equals(operands)) {
       return call;
@@ -1626,8 +1724,10 @@ public class RexUtil {
 
   public static RexNode simplifyAnd2(RexBuilder rexBuilder,
       List<RexNode> terms, List<RexNode> notTerms) {
-    if (terms.contains(rexBuilder.makeLiteral(false))) {
-      return rexBuilder.makeLiteral(false);
+    for (RexNode term : terms) {
+      if (term.isAlwaysFalse()) {
+        return rexBuilder.makeLiteral(false);
+      }
     }
     if (terms.isEmpty() && notTerms.isEmpty()) {
       return rexBuilder.makeLiteral(true);
@@ -1662,8 +1762,10 @@ public class RexUtil {
    * UNKNOWN it will be interpreted as FALSE. */
   public static RexNode simplifyAnd2ForUnknownAsFalse(RexBuilder rexBuilder,
       List<RexNode> terms, List<RexNode> notTerms) {
-    if (terms.contains(rexBuilder.makeLiteral(false))) {
-      return rexBuilder.makeLiteral(false);
+    for (RexNode term : terms) {
+      if (term.isAlwaysFalse()) {
+        return rexBuilder.makeLiteral(false);
+      }
     }
     if (terms.isEmpty() && notTerms.isEmpty()) {
       return rexBuilder.makeLiteral(true);
@@ -1673,15 +1775,33 @@ public class RexUtil {
       return simplify(rexBuilder, terms.get(0), true);
     }
     // Try to simplify the expression
+    final Multimap<String, Pair<String, RexNode>> equalityTerms = ArrayListMultimap.create();
+    final Map<String, String> equalityConstantTerms = new HashMap<>();
     final Set<String> negatedTerms = new HashSet<>();
     final Set<String> nullOperands = new HashSet<>();
     final Set<RexNode> notNullOperands = new LinkedHashSet<>();
     final Set<String> comparedOperands = new HashSet<>();
     for (int i = 0; i < terms.size(); i++) {
-      final RexNode term = terms.get(i);
+      RexNode term = terms.get(i);
       if (!isDeterministic(term)) {
         continue;
       }
+      // Simplify BOOLEAN expressions if possible
+      while (term.getKind() == SqlKind.EQUALS) {
+        RexCall call = (RexCall) term;
+        if (call.getOperands().get(0).isAlwaysTrue()) {
+          term = call.getOperands().get(1);
+          terms.remove(i);
+          terms.add(i, term);
+          continue;
+        } else if (call.getOperands().get(1).isAlwaysTrue()) {
+          term = call.getOperands().get(0);
+          terms.remove(i);
+          terms.add(i, term);
+          continue;
+        }
+        break;
+      }
       switch (term.getKind()) {
       case EQUALS:
       case NOT_EQUALS:
@@ -1704,6 +1824,28 @@ public class RexUtil {
           RexCall rightCast = (RexCall) right;
           comparedOperands.add(rightCast.getOperands().get(0).toString());
         }
+        // Check for equality on different constants. If the same ref or CAST(ref)
+        // is equal to different constants, this condition cannot be satisfied,
+        // and hence it can be evaluated to FALSE
+        if (term.getKind() == SqlKind.EQUALS) {
+          final boolean leftRef = isReferenceOrAccess(left, true);
+          final boolean rightRef = isReferenceOrAccess(right, true);
+          if (right instanceof RexLiteral && leftRef) {
+            final String literal = right.toString();
+            final String prevLiteral = equalityConstantTerms.put(left.toString(), literal);
+            if (prevLiteral != null && !literal.equals(prevLiteral)) {
+              return rexBuilder.makeLiteral(false);
+            }
+          } else if (left instanceof RexLiteral && rightRef) {
+            final String literal = left.toString();
+            final String prevLiteral = equalityConstantTerms.put(right.toString(), literal);
+            if (prevLiteral != null && !literal.equals(prevLiteral)) {
+              return rexBuilder.makeLiteral(false);
+            }
+          } else if (leftRef && rightRef) {
+            equalityTerms.put(left.toString(), Pair.of(right.toString(), term));
+          }
+        }
         // Assume the expression a > 5 is part of a Filter condition.
         // Then we can derive the negated term: a <= 5.
         // But as the comparison is string based and thus operands order dependent,
@@ -1739,6 +1881,30 @@ public class RexUtil {
     if (!Collections.disjoint(nullOperands, comparedOperands)) {
       return rexBuilder.makeLiteral(false);
     }
+    // Check for equality of two refs wrt equality with constants
+    // Example #1. x=5 AND y=5 AND x=y : x=5 AND y=5
+    // Example #2. x=5 AND y=6 AND x=y - not satisfiable
+    for (String ref1 : equalityTerms.keySet()) {
+      final String literal1 = equalityConstantTerms.get(ref1);
+      if (literal1 == null) {
+        continue;
+      }
+      Collection<Pair<String, RexNode>> references = equalityTerms.get(ref1);
+      for (Pair<String, RexNode> ref2 : references) {
+        final String literal2 = equalityConstantTerms.get(ref2.left);
+        if (literal2 == null) {
+          continue;
+        }
+        if (!literal1.equals(literal2)) {
+          // If an expression is equal to two different constants,
+          // it is not satisfiable
+          return rexBuilder.makeLiteral(false);
+        }
+        // Otherwise we can remove the term, as we already know that
+        // the expression is equal to two constants
+        terms.remove(ref2.right);
+      }
+    }
     // Remove not necessary IS NOT NULL expressions.
     //
     // Example. IS NOT NULL(x) AND x < 5  : x < 5
@@ -1755,13 +1921,12 @@ public class RexUtil {
     // Example #1. x AND y AND z AND NOT (x AND y)  - not satisfiable
     // Example #2. x AND y AND NOT (x AND y)        - not satisfiable
     // Example #3. x AND y AND NOT (x AND y AND z)  - may be satisfiable
-    final Set<String> termsSet = Sets.newHashSet(RexUtil.strings(terms));
+    final Set<String> termsSet = new HashSet<String>(strings(terms));
     for (RexNode notDisjunction : notTerms) {
       if (!isDeterministic(notDisjunction)) {
         continue;
       }
-      final List<String> terms2Set = RexUtil.strings(
-              RelOptUtil.conjunctions(notDisjunction));
+      final List<String> terms2Set = strings(RelOptUtil.conjunctions(notDisjunction));
       if (termsSet.containsAll(terms2Set)) {
         return rexBuilder.makeLiteral(false);
       }
@@ -2450,6 +2615,49 @@ public class RexUtil {
       }
     }
   }
+
+  /** Deep expressions simplifier. */
+  public static class ExprSimplifier extends RexShuttle {
+    private final RexBuilder rexBuilder;
+    private final boolean unknownAsFalse;
+    private final Map<RexNode, Boolean> unknownAsFalseMap;
+
+    public ExprSimplifier(RexBuilder rexBuilder, boolean unknownAsFalse) {
+      this.rexBuilder = rexBuilder;
+      this.unknownAsFalse = unknownAsFalse;
+      this.unknownAsFalseMap = new HashMap<>();
+    }
+
+    @Override public RexNode visitCall(RexCall call) {
+      Boolean unknownAsFalseCall = unknownAsFalse;
+      if (unknownAsFalseCall) {
+        switch (call.getKind()) {
+        case AND:
+        case CASE:
+          unknownAsFalseCall = this.unknownAsFalseMap.get(call);
+          if (unknownAsFalseCall == null) {
+            // Top operator
+            unknownAsFalseCall = true;
+          }
+          break;
+        default:
+          unknownAsFalseCall = false;
+        }
+        for (RexNode operand : call.operands) {
+          this.unknownAsFalseMap.put(operand, unknownAsFalseCall);
+        }
+      }
+      RexNode node = super.visitCall(call);
+      RexNode simplifiedNode = simplify(rexBuilder, node, unknownAsFalseCall);
+      if (node == simplifiedNode) {
+        return node;
+      }
+      if (simplifiedNode.getType().equals(call.getType())) {
+        return simplifiedNode;
+      }
+      return rexBuilder.makeCast(call.getType(), simplifiedNode, true);
+    }
+  }
 }
 
 // End RexUtil.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/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 ba9a05e..117f7fa 100644
--- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
+++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
@@ -586,7 +586,7 @@ public class MaterializationTest {
             rexBuilder.makeCall(
                 SqlStdOperatorTable.NOT,
                 i0_eq_0));
-    checkSatisfiable(e3, "NOT(=($0, 0))");
+    checkSatisfiable(e3, "<>($0, 0)");
 
     // The expression "$1 = 1".
     final RexNode i1_eq_1 =
@@ -616,7 +616,7 @@ public class MaterializationTest {
             rexBuilder.makeCall(
                 SqlStdOperatorTable.NOT,
                 i1_eq_1));
-    checkSatisfiable(e5, "AND(=($0, 0), NOT(=($1, 1)))");
+    checkSatisfiable(e5, "AND(=($0, 0), <>($1, 1))");
 
     // "$0 = 0 AND NOT ($0 = 0 AND $1 = 1)" may be satisfiable. Can simplify.
     final RexNode e6 =
@@ -629,7 +629,7 @@ public class MaterializationTest {
                     SqlStdOperatorTable.AND,
                     i0_eq_0,
                     i1_eq_1)));
-    checkSatisfiable(e6, "AND(=($0, 0), NOT(AND(=($0, 0), =($1, 1))))");
+    checkSatisfiable(e6, "AND(=($0, 0), OR(<>($0, 0), <>($1, 1)))");
 
     // "$0 = 0 AND ($1 = 1 AND NOT ($0 = 0))" is not satisfiable.
     final RexNode e7 =
@@ -682,7 +682,7 @@ public class MaterializationTest {
                         SqlStdOperatorTable.NOT,
                         i4))));
     checkSatisfiable(e8,
-        "AND(=($0, 0), $2, $3, NOT(AND($2, $3, $4)), NOT($4))");
+        "AND(=($0, 0), $2, $3, OR(NOT($2), NOT($3), NOT($4)), NOT($4))");
   }
 
   private void checkNotSatisfiable(RexNode e) {

http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/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 b8de6ca..9aa6239 100644
--- a/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
@@ -867,7 +867,7 @@ public class RelOptRulesTest extends RelOptTestBase {
     final String sql = "select d.deptno"
         + " from dept d"
         + " where d.deptno=7 and d.deptno=8";
-    checkPlanUnchanged(new HepPlanner(program), sql);
+    checkPlanning(new HepPlanner(program), sql);
   }
 
   /** Test case for
@@ -887,6 +887,20 @@ public class RelOptRulesTest extends RelOptTestBase {
     checkPlanning(program, sql);
   }
 
+  @Test public void testPullNull() throws Exception {
+    HepProgram program = new HepProgramBuilder()
+        .addRuleInstance(ReduceExpressionsRule.PROJECT_INSTANCE)
+        .addRuleInstance(ReduceExpressionsRule.FILTER_INSTANCE)
+        .addRuleInstance(ReduceExpressionsRule.JOIN_INSTANCE)
+        .build();
+
+    final String sql = "select *\n"
+        + "from emp\n"
+        + "where deptno=7\n"
+        + "and empno = 10 and mgr is null and empno = 10";
+    checkPlanning(program, sql);
+  }
+
   @Test public void testReduceConstants2() throws Exception {
     HepProgram program = new HepProgramBuilder()
         .addRuleInstance(ReduceExpressionsRule.PROJECT_INSTANCE)

http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/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 0079b49..75fc8fd 100644
--- a/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RexProgramTest.java
@@ -863,6 +863,15 @@ public class RexProgramTest {
     // case: singleton
     checkSimplify(case_(trueLiteral, aRef, eq(cRef, dRef), eRef, cRef), "?0.a");
 
+    // case: always same value
+    checkSimplify(
+        case_(aRef, literal1, bRef, literal1, cRef, literal1, dRef, literal1, literal1),
"1");
+
+    // case: trailing false and null, no simplification
+    checkSimplify(
+        case_(aRef, trueLiteral, bRef, trueLiteral, cRef, falseLiteral, unknownLiteral),
+            "CASE(?0.a, true, ?0.b, true, ?0.c, false, null)");
+
     // case: form an AND of branches that return true
     checkSimplify(
         case_(aRef, trueLiteral, bRef,
@@ -914,7 +923,12 @@ public class RexProgramTest {
 
     final RexDynamicParam range = rexBuilder.makeDynamicParam(rowType, 0);
     final RexNode aRef = rexBuilder.makeFieldAccess(range, 0);
+    final RexNode bRef = rexBuilder.makeFieldAccess(range, 1);
+    final RexNode cRef = rexBuilder.makeFieldAccess(range, 2);
+    final RexNode dRef = rexBuilder.makeFieldAccess(range, 3);
     final RexLiteral literal1 = rexBuilder.makeExactLiteral(BigDecimal.ONE);
+    final RexLiteral literal10 = rexBuilder.makeExactLiteral(BigDecimal.TEN);
+
 
     // condition, and the inverse
     checkSimplifyFilter(and(le(aRef, literal1), gt(aRef, literal1)),
@@ -925,6 +939,23 @@ public class RexProgramTest {
 
     checkSimplifyFilter(and(lt(aRef, literal1), eq(aRef, literal1), ge(aRef, literal1)),
         "false");
+
+    // simplify equals boolean
+    checkSimplifyFilter(and(eq(eq(aRef, literal1), trueLiteral), eq(bRef, literal1)),
+        "AND(=(?0.a, 1), =(?0.b, 1))");
+
+    // equality on constants, can remove the equality on the variables
+    checkSimplifyFilter(and(eq(aRef, literal1), eq(bRef, literal1), eq(aRef, bRef)),
+        "AND(=(?0.a, 1), =(?0.b, 1))");
+
+    // condition not satisfiable
+    checkSimplifyFilter(and(eq(aRef, literal1), eq(bRef, literal10), eq(aRef, bRef)),
+        "false");
+
+    // case: trailing false and null, remove
+    checkSimplifyFilter(
+        case_(aRef, trueLiteral, bRef, trueLiteral, cRef, falseLiteral, dRef, falseLiteral,
+            unknownLiteral), "CAST(OR(?0.a, ?0.b)):BOOLEAN");
   }
 
   /** Unit test for

http://git-wip-us.apache.org/repos/asf/calcite/blob/e8729597/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 10cf15c..07e8c91 100644
--- a/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
+++ b/core/src/test/resources/org/apache/calcite/test/RelOptRulesTest.xml
@@ -658,13 +658,8 @@ LogicalProject(EXPR$0=[+(1, 2)], EXPR$1=[+($0, +(3, 4))], EXPR$2=[+(+(5,
6), $0)
         </Resource>
         <Resource name="planAfter">
             <![CDATA[
-LogicalProject(EXPR$0=[3], EXPR$1=[+($0, 7)], EXPR$2=[+(11, $0)], EXPR$3=[null], EXPR$4=[CAST(2):INTEGER],
EXPR$5=[ROW(15)])
-  LogicalFilter(condition=[AND(=($0, 15), =($0, 2))])
-    LogicalProject(DEPTNO=[$0], NAME=[$1], EMPNO=[$2], ENAME=[$3], JOB=[$4], MGR=[$5], HIREDATE=[$6],
SAL=[$7], COMM=[$8], DEPTNO0=[$9], SLACKER=[$10])
-      LogicalJoin(condition=[=($0, $11)], joinType=[inner])
-        LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
-        LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5],
COMM=[$6], DEPTNO=[$7], SLACKER=[$8], $f9=[+($7, 0)])
-          LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+LogicalProject(EXPR$0=[3], EXPR$1=[22], EXPR$2=[26], EXPR$3=[null], EXPR$4=[CAST(2):INTEGER],
EXPR$5=[ROW(15)])
+  LogicalValues(tuples=[[]])
 ]]>
         </Resource>
     </TestCase>
@@ -681,9 +676,8 @@ LogicalProject(DEPTNO=[$0])
         </Resource>
         <Resource name="planAfter">
             <![CDATA[
-LogicalProject(DEPTNO=[8])
-  LogicalFilter(condition=[AND(=($0, 7), =($0, 8))])
-    LogicalTableScan(table=[[CATALOG, SALES, DEPT]])
+LogicalProject(DEPTNO=[$0])
+  LogicalValues(tuples=[[]])
 ]]>
         </Resource>
     </TestCase>
@@ -948,7 +942,7 @@ LogicalProject(EXPR$0=[CAST(CASE(IS NULL($1), IS NULL($0), IS NULL($0),
IS NULL(
         </Resource>
         <Resource name="planAfter">
             <![CDATA[
-LogicalProject(EXPR$0=[CASE(IS NULL($1), false, CAST(=($1, 2)):BOOLEAN NOT NULL)])
+LogicalProject(EXPR$0=[false])
   LogicalProject(EXPR$0=[2], EXPR$1=[null])
     LogicalValues(tuples=[[{ 0 }]])
 ]]>
@@ -4164,7 +4158,7 @@ LogicalAggregate(group=[{}], EXPR$0=[COUNT()])
             <![CDATA[
 LogicalAggregate(group=[{}], EXPR$0=[COUNT()])
   LogicalProject($f0=[1])
-    LogicalFilter(condition=[CASE(=($7, 20), CAST(false):BOOLEAN, =($7, 10), CAST(true):BOOLEAN,
null)])
+    LogicalFilter(condition=[=($7, 10)])
       LogicalTableScan(table=[[CATALOG, SALES, EMP]])
 ]]>
         </Resource>
@@ -4863,8 +4857,29 @@ LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4],
SAL=[$
         </Resource>
         <Resource name="planAfter">
             <![CDATA[
-LogicalProject(EMPNO=[10], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6],
DEPTNO=[$7], SLACKER=[$8])
-  LogicalFilter(condition=[AND(=($7, 7), =($7, 8), =($0, 10), IS NULL($3))])
+LogicalProject(EMPNO=[10], ENAME=[$1], JOB=[$2], MGR=[null], HIREDATE=[$4], SAL=[$5], COMM=[$6],
DEPTNO=[$7], SLACKER=[$8])
+  LogicalValues(tuples=[[]])
+]]>
+        </Resource>
+    </TestCase>
+    <TestCase name="testPullNull">
+        <Resource name="sql">
+            <![CDATA[select *
+from emp
+where deptno=7
+and empno = 10 and mgr is null and empno = 10]]>
+        </Resource>
+        <Resource name="planBefore">
+            <![CDATA[
+LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6],
DEPTNO=[$7], SLACKER=[$8])
+  LogicalFilter(condition=[AND(=($7, 7), =($0, 10), IS NULL($3), =($0, 10))])
+    LogicalTableScan(table=[[CATALOG, SALES, EMP]])
+]]>
+        </Resource>
+        <Resource name="planAfter">
+            <![CDATA[
+LogicalProject(EMPNO=[10], ENAME=[$1], JOB=[$2], MGR=[null], HIREDATE=[$4], SAL=[$5], COMM=[$6],
DEPTNO=[7], SLACKER=[$8])
+  LogicalFilter(condition=[AND(=($7, 7), =($0, 10), IS NULL($3))])
     LogicalTableScan(table=[[CATALOG, SALES, EMP]])
 ]]>
         </Resource>


Mime
View raw message