calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [7/7] calcite git commit: [CALCITE-1695] Add class RexSimplify, providing an explicit RexExecutor for methods to simplify RexNodes
Date Wed, 15 Mar 2017 15:58:34 GMT
[CALCITE-1695] Add class RexSimplify, providing an explicit RexExecutor for methods to simplify RexNodes

The static simplifyXxx methods in RexUtil still exist, but are
deprecated. Most do not have a RexExecutor argument so will give
unexpected behavior if the statement is being prepared with a
non-default executor.

Remove some methods that were added to RexUtil but have never
appeared in a release.


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

Branch: refs/heads/master
Commit: ca48431ee7872f294de7a10a6da0892185e8e4a7
Parents: 256b1b9
Author: Julian Hyde <jhyde@apache.org>
Authored: Tue Mar 14 20:56:19 2017 -0700
Committer: Julian Hyde <jhyde@apache.org>
Committed: Wed Mar 15 01:44:46 2017 -0700

----------------------------------------------------------------------
 .../adapter/enumerable/EnumerableCalc.java      |   9 +-
 .../calcite/plan/SubstitutionVisitor.java       |  33 +-
 .../calcite/rel/metadata/RelMdPredicates.java   |  11 +-
 .../calcite/rel/rules/DateRangeRules.java       |   4 +-
 .../calcite/rel/rules/ProjectToWindowRule.java  |   2 +-
 .../rel/rules/ReduceExpressionsRule.java        |  55 +-
 .../java/org/apache/calcite/rex/RexProgram.java |  13 +-
 .../apache/calcite/rex/RexProgramBuilder.java   |  57 +-
 .../org/apache/calcite/rex/RexSimplify.java     | 805 +++++++++++++++++++
 .../java/org/apache/calcite/rex/RexUtil.java    | 780 ++----------------
 .../sql2rel/StandardConvertletTable.java        |   2 +-
 .../org/apache/calcite/tools/RelBuilder.java    |  17 +-
 .../calcite/rel/rules/DateRangeRulesTest.java   |   3 +-
 .../calcite/test/MaterializationTest.java       |  19 +-
 .../calcite/test/RexImplicationCheckerTest.java |   3 +
 .../org/apache/calcite/test/RexProgramTest.java |  25 +-
 .../calcite/adapter/druid/DruidRules.java       |  12 +-
 .../calcite/test/DruidDateRangeRulesTest.java   |   3 +-
 18 files changed, 1039 insertions(+), 814 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableCalc.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableCalc.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableCalc.java
index 205bd05..a23dcfe 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableCalc.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableCalc.java
@@ -38,7 +38,10 @@ import org.apache.calcite.rel.core.Calc;
 import org.apache.calcite.rel.metadata.RelMdCollation;
 import org.apache.calcite.rel.metadata.RelMdDistribution;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexProgram;
+import org.apache.calcite.rex.RexSimplify;
+import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.util.BuiltInMethod;
 import org.apache.calcite.util.Pair;
 import org.apache.calcite.util.Util;
@@ -146,8 +149,10 @@ public class EnumerableCalc extends Calc implements EnumerableRel {
                 BuiltInMethod.ENUMERATOR_CURRENT.method),
             inputJavaType);
 
-    final RexProgram program =
-        this.program.normalize(getCluster().getRexBuilder(), true);
+    final RexBuilder rexBuilder = getCluster().getRexBuilder();
+    final RexSimplify simplify =
+        new RexSimplify(rexBuilder, false, RexUtil.EXECUTOR);
+    final RexProgram program = this.program.normalize(rexBuilder, simplify);
 
     BlockStatement moveNextBody;
     if (program.getCondition() == null) {

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
index 02c63b0..bd6dddf 100644
--- a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
+++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
@@ -35,11 +35,13 @@ import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeField;
 import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexExecutor;
 import org.apache.calcite.rex.RexExecutorImpl;
 import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexSimplify;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.runtime.PredicateImpl;
 import org.apache.calcite.sql.SqlAggFunction;
@@ -76,7 +78,6 @@ import java.util.Set;
 
 import static org.apache.calcite.rex.RexUtil.andNot;
 import static org.apache.calcite.rex.RexUtil.removeAll;
-import static org.apache.calcite.rex.RexUtil.simplify;
 
 /**
  * Substitutes part of a tree of relational expressions with another tree.
@@ -129,6 +130,7 @@ public class SubstitutionVisitor {
   private final Map<Pair<Class, Class>, List<UnifyRule>> ruleMap =
       new HashMap<>();
   private final RelOptCluster cluster;
+  private final RexSimplify simplify;
   private final Holder query;
   private final MutableRel target;
 
@@ -161,6 +163,9 @@ public class SubstitutionVisitor {
   public SubstitutionVisitor(RelNode target_, RelNode query_,
       ImmutableList<UnifyRule> rules) {
     this.cluster = target_.getCluster();
+    final RexExecutor executor =
+        Util.first(cluster.getPlanner().getExecutor(), RexUtil.EXECUTOR);
+    this.simplify = new RexSimplify(cluster.getRexBuilder(), false, executor);
     this.rules = rules;
     this.query = Holder.of(MutableRels.toMutable(query_));
     this.target = MutableRels.toMutable(target_);
@@ -248,22 +253,22 @@ public class SubstitutionVisitor {
    * problem.</p>
    */
   @VisibleForTesting
-  public static RexNode splitFilter(
-      final RexBuilder rexBuilder, RexNode condition, RexNode target) {
+  public static RexNode splitFilter(final RexSimplify simplify,
+      RexNode condition, RexNode target) {
     // First, try splitting into ORs.
     // Given target    c1 OR c2 OR c3 OR c4
     // and condition   c2 OR c4
     // residue is      NOT c1 AND NOT c3
     // Also deals with case target [x] condition [x] yields residue [true].
-    RexNode z = splitOr(rexBuilder, condition, target);
+    RexNode z = splitOr(simplify.rexBuilder, condition, target);
     if (z != null) {
       return z;
     }
 
-    RexNode x = andNot(rexBuilder, target, condition);
+    RexNode x = andNot(simplify.rexBuilder, target, condition);
     if (mayBeSatisfiable(x)) {
-      RexNode x2 = andNot(rexBuilder, condition, target);
-      return simplify(rexBuilder, x2);
+      RexNode x2 = andNot(simplify.rexBuilder, condition, target);
+      return simplify.simplify(x2);
     }
     return null;
   }
@@ -795,6 +800,10 @@ public class SubstitutionVisitor {
     public RelOptCluster getCluster() {
       return cluster;
     }
+
+    public RexSimplify getSimplify() {
+      return simplify;
+    }
   }
 
   /**
@@ -1055,16 +1064,17 @@ public class SubstitutionVisitor {
       final MutableFilter query = (MutableFilter) call.query;
       final MutableFilter target = (MutableFilter) call.target;
       final MutableFilter newFilter =
-          createFilter(query, target);
+          createFilter(call, query, target);
       if (newFilter == null) {
         return null;
       }
       return call.result(newFilter);
     }
 
-    MutableFilter createFilter(MutableFilter query, MutableFilter target) {
+    MutableFilter createFilter(UnifyRuleCall call, MutableFilter query,
+        MutableFilter target) {
       final RexNode newCondition =
-          splitFilter(query.cluster.getRexBuilder(), query.condition,
+          splitFilter(call.getSimplify(), query.condition,
               target.condition);
       if (newCondition == null) {
         // Could not map query onto target.
@@ -1094,8 +1104,7 @@ public class SubstitutionVisitor {
         final MutableFilter query = (MutableFilter) in2.query;
         final MutableFilter target = (MutableFilter) in2.target;
         final MutableFilter newFilter =
-            FilterToFilterUnifyRule.INSTANCE.createFilter(
-                query, target);
+            FilterToFilterUnifyRule.INSTANCE.createFilter(call, query, target);
         if (newFilter == null) {
           return null;
         }

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/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 bfad3e7..65071fe 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
@@ -19,6 +19,7 @@ package org.apache.calcite.rel.metadata;
 import org.apache.calcite.linq4j.Linq4j;
 import org.apache.calcite.linq4j.Ord;
 import org.apache.calcite.linq4j.function.Predicate1;
+import org.apache.calcite.plan.RelOptCluster;
 import org.apache.calcite.plan.RelOptPredicateList;
 import org.apache.calcite.plan.RelOptUtil;
 import org.apache.calcite.plan.Strong;
@@ -37,10 +38,12 @@ import org.apache.calcite.rel.core.TableScan;
 import org.apache.calcite.rel.core.Union;
 import org.apache.calcite.rex.RexBuilder;
 import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexExecutor;
 import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
 import org.apache.calcite.rex.RexPermuteInputsShuttle;
+import org.apache.calcite.rex.RexSimplify;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.rex.RexVisitorImpl;
 import org.apache.calcite.sql.SqlKind;
@@ -265,7 +268,7 @@ public class RelMdPredicates
         }
       }
       if (!list.isEmpty()) {
-        return RexUtil.composeDisjunction(rexBuilder, list, false);
+        return RexUtil.composeDisjunction(rexBuilder, list);
       }
     }
     // Cannot weaken to anything non-trivial
@@ -412,7 +415,11 @@ public class RelMdPredicates
     }
 
     List<RexNode> preds = new ArrayList<>(finalPreds.values());
-    RexNode disjPred = RexUtil.simplifyOrs(rB, finalResidualPreds);
+    final RelOptCluster cluster = union.getCluster();
+    final RexExecutor executor =
+        Util.first(cluster.getPlanner().getExecutor(), RexUtil.EXECUTOR);
+    final RexSimplify simplify = new RexSimplify(rB, true, executor);
+    RexNode disjPred = simplify.simplifyOrs(finalResidualPreds);
     if (!disjPred.isAlwaysTrue()) {
       preds.add(disjPred);
     }

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/rel/rules/DateRangeRules.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/DateRangeRules.java b/core/src/main/java/org/apache/calcite/rel/rules/DateRangeRules.java
index 3102f42..7b30571 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/DateRangeRules.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/DateRangeRules.java
@@ -155,7 +155,7 @@ public abstract class DateRangeRules {
       final RelBuilder relBuilder =
           relBuilderFactory.create(filter.getCluster(), null);
       relBuilder.push(filter.getInput())
-          .filter(RexUtil.simplify(rexBuilder, condition, true));
+          .filter(condition);
       call.transformTo(relBuilder.build());
     }
   }
@@ -316,7 +316,7 @@ public abstract class DateRangeRules {
       for (Range<Calendar> r : s2.asRanges()) {
         nodes.add(toRex(operand, r));
       }
-      return RexUtil.composeDisjunction(rexBuilder, nodes, false);
+      return RexUtil.composeDisjunction(rexBuilder, nodes);
     }
 
     private boolean next(Calendar c, TimeUnitRange timeUnit, int v,

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/rel/rules/ProjectToWindowRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/ProjectToWindowRule.java b/core/src/main/java/org/apache/calcite/rel/rules/ProjectToWindowRule.java
index 054f4c6..416a473 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/ProjectToWindowRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/ProjectToWindowRule.java
@@ -199,7 +199,7 @@ public abstract class ProjectToWindowRule extends RelOptRule {
         protected RelNode makeRel(RelOptCluster cluster, RelTraitSet traitSet,
             RelBuilder relBuilder, RelNode input, RexProgram program) {
           assert !program.containsAggs();
-          program = program.normalize(cluster.getRexBuilder(), false);
+          program = program.normalize(cluster.getRexBuilder(), null);
           return super.makeRel(cluster, traitSet, relBuilder, input, program);
         }
       },

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/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 11db392..d5530c9 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
@@ -16,6 +16,7 @@
  */
 package org.apache.calcite.rel.rules;
 
+import org.apache.calcite.plan.RelOptCluster;
 import org.apache.calcite.plan.RelOptPredicateList;
 import org.apache.calcite.plan.RelOptRule;
 import org.apache.calcite.plan.RelOptRuleCall;
@@ -48,6 +49,7 @@ import org.apache.calcite.rex.RexProgram;
 import org.apache.calcite.rex.RexProgramBuilder;
 import org.apache.calcite.rex.RexRangeRef;
 import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexSimplify;
 import org.apache.calcite.rex.RexSubQuery;
 import org.apache.calcite.rex.RexUtil;
 import org.apache.calcite.rex.RexUtil.ExprSimplifier;
@@ -457,17 +459,18 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
    */
   protected static boolean reduceExpressions(RelNode rel, List<RexNode> expList,
       RelOptPredicateList predicates, boolean unknownAsFalse) {
-    RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
-
-    boolean reduced = reduceExpressionsInternal(rel, expList, predicates);
+    final RelOptCluster cluster = rel.getCluster();
+    final RexBuilder rexBuilder = cluster.getRexBuilder();
+    final RexExecutor executor =
+        Util.first(cluster.getPlanner().getExecutor(), RexUtil.EXECUTOR);
+    final RexSimplify simplify =
+        new RexSimplify(rexBuilder, unknownAsFalse, executor);
 
     // Simplify predicates in place
-    RexExecutor executor = rel.getCluster().getPlanner().getExecutor();
-    if (executor == null) {
-      executor = RexUtil.EXECUTOR;
-    }
-    ExprSimplifier simplifier =
-        new ExprSimplifier(rexBuilder, unknownAsFalse, executor);
+    boolean reduced = reduceExpressionsInternal(rel, simplify, expList,
+        predicates);
+
+    final ExprSimplifier simplifier = new ExprSimplifier(simplify);
     boolean simplified = false;
     for (int i = 0; i < expList.size(); i++) {
       RexNode expr2 = simplifier.apply(expList.get(i));
@@ -481,10 +484,9 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     return reduced || simplified;
   }
 
-  protected static boolean reduceExpressionsInternal(RelNode rel, List<RexNode> expList,
+  protected static boolean reduceExpressionsInternal(RelNode rel,
+      RexSimplify simplify, List<RexNode> expList,
       RelOptPredicateList predicates) {
-    RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
-
     // Replace predicates on CASE to CASE on predicates.
     new CaseShuttle().mutate(expList);
 
@@ -509,10 +511,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
         reducedExprs.add(call.getOperands().get(0));
       }
       RexReplacer replacer =
-          new RexReplacer(
-              rexBuilder,
-              removableCasts,
-              reducedExprs,
+          new RexReplacer(simplify, removableCasts, reducedExprs,
               Collections.nCopies(removableCasts.size(), false));
       replacer.mutate(expList);
     }
@@ -528,10 +527,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
           (List<Map.Entry<RexNode, RexNode>>) (List)
               Lists.newArrayList(predicates.constantMap.entrySet());
       RexReplacer replacer =
-          new RexReplacer(
-              rexBuilder,
-              Pair.left(pairs),
-              Pair.right(pairs),
+          new RexReplacer(simplify, Pair.left(pairs), Pair.right(pairs),
               Collections.nCopies(pairs.size(), false));
       replacer.mutate(constExps2);
     }
@@ -550,7 +546,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     }
 
     final List<RexNode> reducedValues = Lists.newArrayList();
-    executor.reduce(rexBuilder, constExps2, reducedValues);
+    executor.reduce(simplify.rexBuilder, constExps2, reducedValues);
 
     // Use RexNode.digest to judge whether each newly generated RexNode
     // is equivalent to the original one.
@@ -570,11 +566,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
     }
 
     RexReplacer replacer =
-        new RexReplacer(
-            rexBuilder,
-            constExps,
-            reducedValues,
-            addCasts);
+        new RexReplacer(simplify, constExps, reducedValues, addCasts);
     replacer.mutate(expList);
     return true;
   }
@@ -684,17 +676,17 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
    * look for RexCall, since nothing else is reducible in the first place.
    */
   protected static class RexReplacer extends RexShuttle {
-    private final RexBuilder rexBuilder;
+    private final RexSimplify simplify;
     private final List<RexNode> reducibleExps;
     private final List<RexNode> reducedValues;
     private final List<Boolean> addCasts;
 
     RexReplacer(
-        RexBuilder rexBuilder,
+        RexSimplify simplify,
         List<RexNode> reducibleExps,
         List<RexNode> reducedValues,
         List<Boolean> addCasts) {
-      this.rexBuilder = rexBuilder;
+      this.simplify = simplify;
       this.reducibleExps = reducibleExps;
       this.reducedValues = reducedValues;
       this.addCasts = addCasts;
@@ -715,7 +707,7 @@ public abstract class ReduceExpressionsRule extends RelOptRule {
       }
       node = super.visitCall(call);
       if (node != call) {
-        node = RexUtil.simplify(rexBuilder, node);
+        node = simplify.withUnknownAsFalse(false).simplify(node);
       }
       return node;
     }
@@ -736,7 +728,8 @@ 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.makeAbstractCast(call.getType(), replacement);
+        replacement =
+            simplify.rexBuilder.makeAbstractCast(call.getType(), replacement);
       }
       return replacement;
     }

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/rex/RexProgram.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rex/RexProgram.java b/core/src/main/java/org/apache/calcite/rex/RexProgram.java
index 1aeb0ae..b40b02f 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexProgram.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexProgram.java
@@ -753,7 +753,7 @@ public class RexProgram {
    * @return whether in canonical form
    */
   public boolean isNormalized(Litmus litmus, RexBuilder rexBuilder) {
-    final RexProgram normalizedProgram = normalize(rexBuilder, false);
+    final RexProgram normalizedProgram = normalize(rexBuilder, null);
     String normalized = normalizedProgram.toString();
     String string = toString();
     if (!normalized.equals(string)) {
@@ -769,10 +769,11 @@ public class RexProgram {
    * Creates a simplified/normalized copy of this program.
    *
    * @param rexBuilder Rex builder
-   * @param simplify Whether to simplify (in addition to normalizing)
+   * @param simplify Simplifier to simplify (in addition to normalizing),
+   *     or null to not simplify
    * @return Normalized program
    */
-  public RexProgram normalize(RexBuilder rexBuilder, boolean simplify) {
+  public RexProgram normalize(RexBuilder rexBuilder, RexSimplify simplify) {
     // Normalize program by creating program builder from the program, then
     // converting to a program. getProgram does not need to normalize
     // because the builder was normalized on creation.
@@ -783,6 +784,12 @@ public class RexProgram {
     return builder.getProgram(false);
   }
 
+  @Deprecated // to be removed before 2.0
+  public RexProgram normalize(RexBuilder rexBuilder, boolean simplify) {
+    return normalize(rexBuilder,
+        simplify ? new RexSimplify(rexBuilder, false, RexUtil.EXECUTOR) : null);
+  }
+
   //~ Inner Classes ----------------------------------------------------------
 
   /**

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/rex/RexProgramBuilder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rex/RexProgramBuilder.java b/core/src/main/java/org/apache/calcite/rex/RexProgramBuilder.java
index 2fadc90..8371d77 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexProgramBuilder.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexProgramBuilder.java
@@ -23,6 +23,8 @@ import org.apache.calcite.sql.fun.SqlStdOperatorTable;
 import org.apache.calcite.util.Litmus;
 import org.apache.calcite.util.Pair;
 
+import com.google.common.base.Preconditions;
+
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
@@ -46,19 +48,27 @@ public class RexProgramBuilder {
   private final List<RexLocalRef> localRefList = new ArrayList<>();
   private final List<RexLocalRef> projectRefList = new ArrayList<>();
   private final List<String> projectNameList = new ArrayList<>();
+  private final RexSimplify simplify;
   private RexLocalRef conditionRef = null;
   private boolean validating;
 
   //~ Constructors -----------------------------------------------------------
 
   /**
-   * Creates a program-builder.
+   * Creates a program-builder that will not simplify.
    */
   public RexProgramBuilder(RelDataType inputRowType, RexBuilder rexBuilder) {
-    assert inputRowType != null;
-    assert rexBuilder != null;
-    this.inputRowType = inputRowType;
-    this.rexBuilder = rexBuilder;
+    this(inputRowType, rexBuilder, null);
+  }
+
+  /**
+   * Creates a program-builder.
+   */
+  private RexProgramBuilder(RelDataType inputRowType, RexBuilder rexBuilder,
+      RexSimplify simplify) {
+    this.inputRowType = Preconditions.checkNotNull(inputRowType);
+    this.rexBuilder = Preconditions.checkNotNull(rexBuilder);
+    this.simplify = simplify; // may be null
     this.validating = assertionsAreEnabled();
 
     // Pre-create an expression for each input field.
@@ -80,7 +90,7 @@ public class RexProgramBuilder {
    * @param condition      Condition, or null
    * @param outputRowType  Output row type
    * @param normalize      Whether to normalize
-   * @param simplify       Whether to simplify
+   * @param simplify       Simplifier, or null to not simplify
    */
   private RexProgramBuilder(
       RexBuilder rexBuilder,
@@ -90,8 +100,8 @@ public class RexProgramBuilder {
       RexNode condition,
       final RelDataType outputRowType,
       boolean normalize,
-      boolean simplify) {
-    this(inputRowType, rexBuilder);
+      RexSimplify simplify) {
+    this(inputRowType, rexBuilder, simplify);
 
     // Create a shuttle for registering input expressions.
     final RexShuttle shuttle =
@@ -114,8 +124,8 @@ public class RexProgramBuilder {
     for (Pair<? extends RexNode, RelDataTypeField> pair
         : Pair.zip(projectList, fieldList)) {
       final RexNode project;
-      if (simplify) {
-        project = RexUtil.simplify(rexBuilder, pair.left.accept(expander));
+      if (simplify != null) {
+        project = simplify.simplify(pair.left.accept(expander));
       } else {
         project = pair.left;
       }
@@ -126,8 +136,8 @@ public class RexProgramBuilder {
 
     // Register the condition, if there is one.
     if (condition != null) {
-      if (simplify) {
-        condition = RexUtil.simplify(rexBuilder,
+      if (simplify != null) {
+        condition = simplify.simplify(
             rexBuilder.makeCall(SqlStdOperatorTable.IS_TRUE,
                 condition.accept(expander)));
         if (condition.isAlwaysTrue()) {
@@ -313,7 +323,7 @@ public class RexProgramBuilder {
    *              sub-expression exists.
    */
   private RexLocalRef registerInternal(RexNode expr, boolean force) {
-    expr = RexUtil.simplify(rexBuilder, expr);
+    expr = new RexSimplify(rexBuilder, false, RexUtil.EXECUTOR).simplify(expr);
 
     RexLocalRef ref;
     final Pair<String, String> key;
@@ -519,7 +529,7 @@ public class RexProgramBuilder {
       final RexNode condition,
       final RelDataType outputRowType,
       boolean normalize,
-      boolean simplify) {
+      RexSimplify simplify) {
     return new RexProgramBuilder(rexBuilder, inputRowType, exprList,
         projectList, condition, outputRowType, normalize, simplify);
   }
@@ -532,9 +542,24 @@ public class RexProgramBuilder {
       final List<? extends RexNode> projectList,
       final RexNode condition,
       final RelDataType outputRowType,
+      boolean normalize,
+      boolean simplify) {
+    return new RexProgramBuilder(rexBuilder, inputRowType, exprList,
+        projectList, condition, outputRowType, normalize,
+        simplify ? new RexSimplify(rexBuilder, false, RexUtil.EXECUTOR) : null);
+  }
+
+  @Deprecated // to be removed before 2.0
+  public static RexProgramBuilder create(
+      RexBuilder rexBuilder,
+      final RelDataType inputRowType,
+      final List<RexNode> exprList,
+      final List<? extends RexNode> projectList,
+      final RexNode condition,
+      final RelDataType outputRowType,
       boolean normalize) {
     return create(rexBuilder, inputRowType, exprList, projectList, condition,
-        outputRowType, normalize, false);
+        outputRowType, normalize, null);
   }
 
   /**
@@ -580,7 +605,7 @@ public class RexProgramBuilder {
   public static RexProgram normalize(
       RexBuilder rexBuilder,
       RexProgram program) {
-    return program.normalize(rexBuilder, false);
+    return program.normalize(rexBuilder, null);
   }
 
   /**

http://git-wip-us.apache.org/repos/asf/calcite/blob/ca48431e/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rex/RexSimplify.java b/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
new file mode 100644
index 0000000..a910778
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
@@ -0,0 +1,805 @@
+/*
+ * 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.rex;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.plan.Strong;
+import org.apache.calcite.rel.core.Project;
+import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.sql.SqlOperator;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.Util;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Multimap;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Context required to simplify a row-expression.
+ */
+public class RexSimplify {
+  public final RexBuilder rexBuilder;
+  final boolean unknownAsFalse;
+  private final RexExecutor executor;
+
+  /**
+   * Creates a RexSimplify.
+   *
+   * @param rexBuilder Rex builder
+   * @param unknownAsFalse Whether to convert UNKNOWN values to FALSE
+   * @param executor Executor for constant reduction, not null
+   */
+  public RexSimplify(RexBuilder rexBuilder, boolean unknownAsFalse,
+      RexExecutor executor) {
+    this.rexBuilder = Preconditions.checkNotNull(rexBuilder);
+    this.unknownAsFalse = unknownAsFalse;
+    this.executor = Preconditions.checkNotNull(executor);
+  }
+
+  //~ Methods ----------------------------------------------------------------
+
+  /** Returns a RexSimplify the same as this but with a specified
+   * {@link #unknownAsFalse} value. */
+  public RexSimplify withUnknownAsFalse(boolean unknownAsFalse) {
+    return unknownAsFalse == this.unknownAsFalse
+        ? this
+        : new RexSimplify(rexBuilder, unknownAsFalse, executor);
+  }
+
+  /** Simplifies a boolean expression, always preserving its type and its
+   * nullability.
+   *
+   * <p>This is useful if you are simplifying expressions in a
+   * {@link Project}. */
+  public RexNode simplifyPreservingType(RexNode e) {
+    final RexNode e2 = simplify(e);
+    if (e2.getType() == e.getType()) {
+      return e2;
+    }
+    final RexNode e3 = rexBuilder.makeCast(e.getType(), e2, true);
+    if (e3.equals(e)) {
+      return e;
+    }
+    return e3;
+  }
+
+  /**
+   * Simplifies a boolean expression.
+   *
+   * <p>In particular:</p>
+   * <ul>
+   * <li>{@code simplify(x = 1 AND y = 2 AND NOT x = 1)}
+   * returns {@code y = 2}</li>
+   * <li>{@code simplify(x = 1 AND FALSE)}
+   * returns {@code FALSE}</li>
+   * </ul>
+   *
+   * <p>If the expression is a predicate in a WHERE clause, UNKNOWN values have
+   * the same effect as FALSE. In situations like this, specify
+   * {@code unknownAsFalse = true}, so and we can switch from 3-valued logic to
+   * simpler 2-valued logic and make more optimizations.
+   *
+   * @param e Expression to simplify
+   */
+  public RexNode simplify(RexNode e) {
+    switch (e.getKind()) {
+    case AND:
+      return simplifyAnd((RexCall) e);
+    case OR:
+      return simplifyOr((RexCall) e);
+    case NOT:
+      return simplifyNot((RexCall) e);
+    case CASE:
+      return simplifyCase((RexCall) e);
+    case CAST:
+      return simplifyCast((RexCall) e);
+    case IS_NULL:
+    case IS_NOT_NULL:
+    case IS_TRUE:
+    case IS_NOT_TRUE:
+    case IS_FALSE:
+    case IS_NOT_FALSE:
+      assert e instanceof RexCall;
+      return simplifyIs((RexCall) e);
+    case EQUALS:
+    case GREATER_THAN:
+    case GREATER_THAN_OR_EQUAL:
+    case LESS_THAN:
+    case LESS_THAN_OR_EQUAL:
+    case NOT_EQUALS:
+      return simplifyComparison((RexCall) e);
+    default:
+      return e;
+    }
+  }
+
+  // e must be a comparison (=, >, >=, <, <=, !=)
+  private RexNode simplifyComparison(RexCall e) {
+    final List<RexNode> operands = new ArrayList<>(e.operands);
+    simplifyList(operands);
+
+    // Simplify "x <op> x"
+    final RexNode o0 = operands.get(0);
+    final RexNode o1 = operands.get(1);
+    if (RexUtil.eq(o0, o1)
+        && (unknownAsFalse
+            || (!o0.getType().isNullable()
+                && !o1.getType().isNullable()))) {
+      switch (e.getKind()) {
+      case EQUALS:
+      case GREATER_THAN_OR_EQUAL:
+      case LESS_THAN_OR_EQUAL:
+        // "x = x" simplifies to "x is not null" (similarly <= and >=)
+        return simplify(
+            rexBuilder.makeCall(SqlStdOperatorTable.IS_NOT_NULL, o0));
+      default:
+        // "x != x" simplifies to "false" (similarly < and >)
+        return rexBuilder.makeLiteral(false);
+      }
+    }
+
+    // Simplify "<literal1> <op> <literal2>"
+    // For example, "1 = 2" becomes FALSE;
+    // "1 != 1" becomes FALSE;
+    // "1 != NULL" becomes UNKNOWN (or FALSE if unknownAsFalse);
+    // "1 != '1'" is unchanged because the types are not the same.
+    if (o0.isA(SqlKind.LITERAL)
+        && o1.isA(SqlKind.LITERAL)
+        && o0.getType().equals(o1.getType())) {
+      final Comparable v0 = ((RexLiteral) o0).getValue();
+      final Comparable v1 = ((RexLiteral) o1).getValue();
+      if (v0 == null || v1 == null) {
+        return unknownAsFalse
+            ? rexBuilder.makeLiteral(false)
+            : rexBuilder.makeNullLiteral(e.getType());
+      }
+      @SuppressWarnings("unchecked")
+      final int comparisonResult = v0.compareTo(v1);
+      switch (e.getKind()) {
+      case EQUALS:
+        return rexBuilder.makeLiteral(comparisonResult == 0);
+      case GREATER_THAN:
+        return rexBuilder.makeLiteral(comparisonResult > 0);
+      case GREATER_THAN_OR_EQUAL:
+        return rexBuilder.makeLiteral(comparisonResult >= 0);
+      case LESS_THAN:
+        return rexBuilder.makeLiteral(comparisonResult < 0);
+      case LESS_THAN_OR_EQUAL:
+        return rexBuilder.makeLiteral(comparisonResult <= 0);
+      case NOT_EQUALS:
+        return rexBuilder.makeLiteral(comparisonResult != 0);
+      default:
+        throw new AssertionError();
+      }
+    }
+
+    // If none of the arguments were simplified, return the call unchanged.
+    if (operands.equals(e.operands)) {
+      return e;
+    }
+    return rexBuilder.makeCall(e.op, operands);
+  }
+
+  /**
+   * Simplifies a conjunction of boolean expressions.
+   */
+  public RexNode simplifyAnds(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);
+    }
+    simplifyList(terms);
+    simplifyList(notTerms);
+    if (unknownAsFalse) {
+      return simplifyAnd2ForUnknownAsFalse(terms, notTerms);
+    }
+    return simplifyAnd2(terms, notTerms);
+  }
+
+  private void simplifyList(List<RexNode> terms) {
+    for (int i = 0; i < terms.size(); i++) {
+      terms.set(i, withUnknownAsFalse(false).simplify(terms.get(i)));
+    }
+  }
+
+  private RexNode simplifyNot(RexCall call) {
+    final RexNode a = call.getOperands().get(0);
+    switch (a.getKind()) {
+    case NOT:
+      // NOT NOT x ==> x
+      return simplify(((RexCall) a).getOperands().get(0));
+    }
+    final SqlKind negateKind = a.getKind().negate();
+    if (a.getKind() != negateKind) {
+      return simplify(
+          rexBuilder.makeCall(RexUtil.op(negateKind),
+              ImmutableList.of(((RexCall) a).getOperands().get(0))));
+    }
+    final SqlKind negateKind2 = a.getKind().negateNullSafe();
+    if (a.getKind() != negateKind2) {
+      return simplify(
+          rexBuilder.makeCall(RexUtil.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.makeCall(SqlStdOperatorTable.NOT, operand)));
+      }
+      return simplify(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.makeCall(SqlStdOperatorTable.NOT, operand)));
+      }
+      return simplify(
+          rexBuilder.makeCall(SqlStdOperatorTable.AND, newOperands));
+    }
+    return call;
+  }
+
+  private RexNode simplifyIs(RexCall call) {
+    final SqlKind kind = call.getKind();
+    final RexNode a = call.getOperands().get(0);
+    final RexNode simplified = simplifyIs2(kind, a);
+    if (simplified != null) {
+      return simplified;
+    }
+    return call;
+  }
+
+  private RexNode simplifyIs2(SqlKind kind, RexNode a) {
+    switch (kind) {
+    case IS_NULL:
+      // x IS NULL ==> FALSE (if x is not nullable)
+      if (!a.getType().isNullable()) {
+        return rexBuilder.makeLiteral(false);
+      }
+      break;
+    case IS_NOT_NULL:
+      // x IS NOT NULL ==> TRUE (if x is not nullable)
+      RexNode simplified = simplifyIsNotNull(a);
+      if (simplified != null) {
+        return simplified;
+      }
+      break;
+    case IS_TRUE:
+    case IS_NOT_FALSE:
+      // x IS TRUE ==> x (if x is not nullable)
+      // x IS NOT FALSE ==> x (if x is not nullable)
+      if (!a.getType().isNullable()) {
+        return simplify(a);
+      }
+      break;
+    case IS_FALSE:
+    case IS_NOT_TRUE:
+      // x IS NOT TRUE ==> NOT x (if x is not nullable)
+      // x IS FALSE ==> NOT x (if x is not nullable)
+      if (!a.getType().isNullable()) {
+        return simplify(rexBuilder.makeCall(SqlStdOperatorTable.NOT, a));
+      }
+      break;
+    }
+    switch (a.getKind()) {
+    case NOT:
+      // (NOT x) IS TRUE ==> x IS FALSE
+      // Similarly for IS NOT TRUE, IS FALSE, etc.
+      //
+      // Note that
+      //   (NOT x) IS TRUE !=> x IS FALSE
+      // because of null values.
+      final SqlOperator notKind = RexUtil.op(kind.negate());
+      final RexNode arg = ((RexCall) a).operands.get(0);
+      return simplify(rexBuilder.makeCall(notKind, arg));
+    }
+    RexNode a2 = simplify(a);
+    if (a != a2) {
+      return rexBuilder.makeCall(RexUtil.op(kind), ImmutableList.of(a2));
+    }
+    return null; // cannot be simplified
+  }
+
+  private RexNode simplifyIsNotNull(RexNode a) {
+    if (!a.getType().isNullable()) {
+      return rexBuilder.makeLiteral(true);
+    }
+    switch (Strong.policy(a.getKind())) {
+    case ANY:
+      final List<RexNode> operands = new ArrayList<>();
+      for (RexNode operand : ((RexCall) a).getOperands()) {
+        final RexNode simplified = simplifyIsNotNull(operand);
+        if (simplified == null) {
+          operands.add(
+              rexBuilder.makeCall(SqlStdOperatorTable.IS_NOT_NULL, operand));
+        } else if (simplified.isAlwaysFalse()) {
+          return rexBuilder.makeLiteral(false);
+        } else {
+          operands.add(simplified);
+        }
+      }
+      return RexUtil.composeConjunction(rexBuilder, operands, false);
+    case CUSTOM:
+      switch (a.getKind()) {
+      case LITERAL:
+        return rexBuilder.makeLiteral(((RexLiteral) a).getValue() != null);
+      default:
+        throw new AssertionError("every CUSTOM policy needs a handler, "
+            + a.getKind());
+      }
+    case AS_IS:
+    default:
+      return null;
+    }
+  }
+
+  private RexNode simplifyCase(RexCall call) {
+    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 (RexUtil.isCasePredicate(call, i)) {
+        if (operand.isAlwaysTrue()) {
+          // Predicate is always TRUE. Make value the ELSE and quit.
+          newOperands.add(operands.get(++i));
+          if (unknownAsFalse && RexUtil.isNull(operands.get(i))) {
+            values.add(rexBuilder.makeLiteral(false).toString());
+          } else {
+            values.add(operands.get(i).toString());
+          }
+          break;
+        } else if (operand.isAlwaysFalse() || RexUtil.isNull(operand)) {
+          // Predicate is always FALSE or NULL. Skip predicate and value.
+          ++i;
+          continue;
+        }
+      } else {
+        if (unknownAsFalse && RexUtil.isNull(operand)) {
+          values.add(rexBuilder.makeLiteral(false).toString());
+        } else {
+          values.add(operand.toString());
+        }
+      }
+      newOperands.add(operand);
+    }
+    assert newOperands.size() % 2 == 1;
+    if (newOperands.size() == 1 || values.size() == 1) {
+      final RexNode last = Util.last(newOperands);
+      if (!call.getType().equals(last.getType())) {
+        return rexBuilder.makeAbstractCast(call.getType(), last);
+      }
+      return last;
+    }
+  trueFalse:
+    if (call.getType().getSqlTypeName() == SqlTypeName.BOOLEAN) {
+      // Optimize CASE where every branch returns constant true or constant
+      // 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()
+              && !RexUtil.isNull(pair.getValue())) {
+            break;
+          }
+        }
+        if (pos == pairs.size()) {
+          final RexNode disjunction =
+              RexUtil.composeDisjunction(rexBuilder, terms);
+          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
+      // 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()
+            && (!unknownAsFalse || !RexUtil.isNull(pair.e.getValue()))) {
+          break trueFalse;
+        }
+      }
+      final List<RexNode> terms = new ArrayList<>();
+      final List<RexNode> notTerms = new ArrayList<>();
+      for (Ord<Pair<RexNode, RexNode>> pair : Ord.zip(pairs)) {
+        if (pair.e.getValue().isAlwaysTrue()) {
+          terms.add(RexUtil.andNot(rexBuilder, pair.e.getKey(), notTerms));
+        } else {
+          notTerms.add(pair.e.getKey());
+        }
+      }
+      final RexNode disjunction = RexUtil.composeDisjunction(rexBuilder, terms);
+      if (!call.getType().equals(disjunction.getType())) {
+        return rexBuilder.makeCast(call.getType(), disjunction);
+      }
+      return disjunction;
+    }
+    if (newOperands.equals(operands)) {
+      return call;
+    }
+    return call.clone(call.getType(), newOperands);
+  }
+
+  /** Given "CASE WHEN p1 THEN v1 ... ELSE e END"
+   * returns [(p1, v1), ..., (true, e)]. */
+  private static List<Pair<RexNode, RexNode>> casePairs(RexBuilder rexBuilder,
+      List<RexNode> operands) {
+    final ImmutableList.Builder<Pair<RexNode, RexNode>> builder =
+        ImmutableList.builder();
+    for (int i = 0; i < operands.size() - 1; i += 2) {
+      builder.add(Pair.of(operands.get(i), operands.get(i + 1)));
+    }
+    builder.add(
+        Pair.of((RexNode) rexBuilder.makeLiteral(true), Util.last(operands)));
+    return builder.build();
+  }
+
+  public RexNode simplifyAnd(RexCall e) {
+    final List<RexNode> terms = new ArrayList<>();
+    final List<RexNode> notTerms = new ArrayList<>();
+    RelOptUtil.decomposeConjunction(e, terms, notTerms);
+    simplifyList(terms);
+    simplifyList(notTerms);
+    if (unknownAsFalse) {
+      return simplifyAnd2ForUnknownAsFalse(terms, notTerms);
+    }
+    return simplifyAnd2(terms, notTerms);
+  }
+
+  RexNode simplifyAnd2(List<RexNode> terms, List<RexNode> notTerms) {
+    for (RexNode term : terms) {
+      if (term.isAlwaysFalse()) {
+        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(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.
+    //
+    // 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
+    for (RexNode notDisjunction : notTerms) {
+      final List<RexNode> terms2 = RelOptUtil.conjunctions(notDisjunction);
+      if (terms.containsAll(terms2)) {
+        return rexBuilder.makeLiteral(false);
+      }
+    }
+    // Add the NOT disjunctions back in.
+    for (RexNode notDisjunction : notTerms) {
+      terms.add(
+          simplify(
+              rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction)));
+    }
+    return RexUtil.composeConjunction(rexBuilder, terms, false);
+  }
+
+  /** As {@link #simplifyAnd2(List, List)} but we assume that if the expression
+   * returns UNKNOWN it will be interpreted as FALSE. */
+  RexNode simplifyAnd2ForUnknownAsFalse(List<RexNode> terms,
+      List<RexNode> notTerms) {
+    for (RexNode term : terms) {
+      if (term.isAlwaysFalse()) {
+        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(terms.get(0));
+    }
+    // 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++) {
+      RexNode term = terms.get(i);
+      if (!RexUtil.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.set(i, term);
+          continue;
+        } else if (call.getOperands().get(1).isAlwaysTrue()) {
+          term = call.getOperands().get(0);
+          terms.set(i, term);
+          continue;
+        }
+        break;
+      }
+      switch (term.getKind()) {
+      case EQUALS:
+      case NOT_EQUALS:
+      case LESS_THAN:
+      case GREATER_THAN:
+      case LESS_THAN_OR_EQUAL:
+      case GREATER_THAN_OR_EQUAL:
+        RexCall call = (RexCall) term;
+        RexNode left = call.getOperands().get(0);
+        comparedOperands.add(left.toString());
+        // if it is a cast, we include the inner reference
+        if (left.getKind() == SqlKind.CAST) {
+          RexCall leftCast = (RexCall) left;
+          comparedOperands.add(leftCast.getOperands().get(0).toString());
+        }
+        RexNode right = call.getOperands().get(1);
+        comparedOperands.add(right.toString());
+        // if it is a cast, we include the inner reference
+        if (right.getKind() == SqlKind.CAST) {
+          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 = RexUtil.isReferenceOrAccess(left, true);
+          final boolean rightRef = RexUtil.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 comparison is string-based and thus operands order-dependent,
+        // we should also add the inverted negated term: 5 >= a.
+        // Observe that for creating the inverted term we invert the list of
+        // operands.
+        RexNode negatedTerm = RexUtil.negate(rexBuilder, call);
+        if (negatedTerm != null) {
+          negatedTerms.add(negatedTerm.toString());
+          RexNode invertNegatedTerm =
+              RexUtil.invert(rexBuilder, (RexCall) negatedTerm);
+          if (invertNegatedTerm != null) {
+            negatedTerms.add(invertNegatedTerm.toString());
+          }
+        }
+        break;
+      case IN:
+        comparedOperands.add(((RexCall) term).operands.get(0).toString());
+        break;
+      case BETWEEN:
+        comparedOperands.add(((RexCall) term).operands.get(1).toString());
+        break;
+      case IS_NOT_NULL:
+        notNullOperands.add(((RexCall) term).getOperands().get(0));
+        terms.remove(i);
+        --i;
+        break;
+      case IS_NULL:
+        nullOperands.add(((RexCall) term).getOperands().get(0).toString());
+      }
+    }
+    // If one column should be null and is in a comparison predicate,
+    // it is not satisfiable.
+    // Example. IS NULL(x) AND x < 5  - not satisfiable
+    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
+    for (RexNode operand : notNullOperands) {
+      if (!comparedOperands.contains(operand.toString())) {
+        terms.add(
+            rexBuilder.makeCall(SqlStdOperatorTable.IS_NOT_NULL, operand));
+      }
+    }
+    // If one of the not-disjunctions is a disjunction that is wholly
+    // contained in the disjunctions list, the expression is not
+    // satisfiable.
+    //
+    // 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 = new HashSet<String>(RexUtil.strings(terms));
+    for (RexNode notDisjunction : notTerms) {
+      if (!RexUtil.isDeterministic(notDisjunction)) {
+        continue;
+      }
+      final List<String> terms2Set =
+          RexUtil.strings(RelOptUtil.conjunctions(notDisjunction));
+      if (termsSet.containsAll(terms2Set)) {
+        return rexBuilder.makeLiteral(false);
+      }
+    }
+    // Add the NOT disjunctions back in.
+    for (RexNode notDisjunction : notTerms) {
+      final RexNode call =
+          rexBuilder.makeCall(SqlStdOperatorTable.NOT, notDisjunction);
+      terms.add(simplify(call));
+    }
+    // The negated terms: only deterministic expressions
+    for (String negatedTerm : negatedTerms) {
+      if (termsSet.contains(negatedTerm)) {
+        return rexBuilder.makeLiteral(false);
+      }
+    }
+    return RexUtil.composeConjunction(rexBuilder, terms, false);
+  }
+
+  /** Simplifies OR(x, x) into x, and similar. */
+  public RexNode simplifyOr(RexCall call) {
+    assert call.getKind() == SqlKind.OR;
+    final List<RexNode> terms = RelOptUtil.disjunctions(call);
+    return simplifyOrs(terms);
+  }
+
+  /** Simplifies a list of terms and combines them into an OR.
+   * Modifies the list in place. */
+  public RexNode simplifyOrs(List<RexNode> terms) {
+    for (int i = 0; i < terms.size(); i++) {
+      final RexNode term = simplify(terms.get(i));
+      switch (term.getKind()) {
+      case LITERAL:
+        if (!RexLiteral.isNullLiteral(term)) {
+          if (RexLiteral.booleanValue(term)) {
+            return term; // true
+          } else {
+            terms.remove(i);
+            --i;
+            continue;
+          }
+        }
+      }
+      terms.set(i, term);
+    }
+    return RexUtil.composeDisjunction(rexBuilder, terms);
+  }
+
+  private RexNode simplifyCast(RexCall e) {
+    final RexNode operand = e.getOperands().get(0);
+    switch (operand.getKind()) {
+    case LITERAL:
+      final RexLiteral literal = (RexLiteral) operand;
+      final Comparable value = literal.getValue();
+      final SqlTypeName typeName = literal.getTypeName();
+
+      // First, try to remove the cast without changing the value.
+      // makeCast and canRemoveCastFromLiteral have the same logic, so we are
+      // sure to be able to remove the cast.
+      if (rexBuilder.canRemoveCastFromLiteral(e.getType(), value, typeName)) {
+        return rexBuilder.makeCast(e.getType(), operand);
+      }
+
+      // Next, try to convert the value to a different type,
+      // e.g. CAST('123' as integer)
+      switch (literal.getTypeName()) {
+      case TIME:
+        switch (e.getType().getSqlTypeName()) {
+        case TIMESTAMP:
+          return e;
+        }
+      }
+      final List<RexNode> reducedValues = new ArrayList<>();
+      executor.reduce(rexBuilder, ImmutableList.<RexNode>of(e), reducedValues);
+      return Preconditions.checkNotNull(
+          Iterables.getOnlyElement(reducedValues));
+    default:
+      return e;
+    }
+  }
+
+}
+
+// End RexSimplify.java


Mime
View raw message