calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jh...@apache.org
Subject [12/50] incubator-calcite git commit: [CALCITE-786] Detect if materialized view can be used to rewrite a query in non-trivial cases (Amogh Margoor)
Date Wed, 02 Sep 2015 22:16:00 GMT
[CALCITE-786] Detect if materialized view can be used to rewrite a query in non-trivial cases (Amogh Margoor)

Close apache/incubator-calcite#102


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

Branch: refs/heads/branch-release
Commit: 4a9b19390b2f9ab5a6d3bc2340c323d3a39cfa80
Parents: 220a085
Author: Amogh Margoor <amoghm@qubole.com>
Authored: Thu Jun 11 15:18:52 2015 +0530
Committer: Julian Hyde <jhyde@apache.org>
Committed: Thu Jul 16 13:22:39 2015 -0700

----------------------------------------------------------------------
 .../MaterializedViewSubstitutionVisitor.java    | 170 +++++++
 .../org/apache/calcite/plan/RelOptUtil.java     |   4 +-
 .../calcite/plan/RexImplicationChecker.java     | 377 ++++++++++++++++
 .../calcite/plan/SubstitutionVisitor.java       | 183 +++++---
 .../apache/calcite/plan/VisitorDataContext.java | 186 ++++++++
 .../calcite/plan/volcano/VolcanoPlanner.java    |   9 +-
 .../java/org/apache/calcite/rex/RexUtil.java    | 105 +++++
 .../org/apache/calcite/test/CalciteSuite.java   |   1 +
 .../calcite/test/MaterializationTest.java       | 140 +++++-
 .../calcite/test/RexImplicationCheckerTest.java | 448 +++++++++++++++++++
 10 files changed, 1558 insertions(+), 65 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java
new file mode 100644
index 0000000..e367f93
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/plan/MaterializedViewSubstitutionVisitor.java
@@ -0,0 +1,170 @@
+/*
+ * 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.plan;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+/**
+ * Substitutes part of a tree of relational expressions with another tree.
+ *
+ * <p>The call {@code new MaterializedSubstitutionVisitor(target, query).go(replacement))}
+ * will return {@code query} with every occurrence of {@code target} replaced
+ * by {@code replacement}.</p>
+ *
+ * <p>The following example shows how {@code MaterializedSubstitutionVisitor} can be used
+ * for materialized view recognition.</p>
+ *
+ * <ul>
+ * <li>query = SELECT a, c FROM t WHERE x = 5 AND b = 4</li>
+ * <li>target = SELECT a, b, c FROM t WHERE x = 5</li>
+ * <li>replacement = SELECT * FROM mv</li>
+ * <li>result = SELECT a, c FROM mv WHERE b = 4</li>
+ * </ul>
+ *
+ * <p>Note that {@code result} uses the materialized view table {@code mv} and a
+ * simplified condition {@code b = 4}.</p>
+ *
+ * <p>Uses a bottom-up matching algorithm. Nodes do not need to be identical.
+ * At each level, returns the residue.</p>
+ *
+ * <p>The inputs must only include the core relational operators:
+ * {@link org.apache.calcite.rel.logical.LogicalTableScan},
+ * {@link LogicalFilter},
+ * {@link LogicalProject},
+ * {@link org.apache.calcite.rel.logical.LogicalJoin},
+ * {@link LogicalUnion},
+ * {@link LogicalAggregate}.</p>
+ */
+public class MaterializedViewSubstitutionVisitor extends SubstitutionVisitor {
+
+  public MaterializedViewSubstitutionVisitor(RelNode target_, RelNode query_) {
+    super(target_, query_);
+    ImmutableList.Builder<UnifyRule> builder = new ImmutableList.Builder<UnifyRule>();
+    builder.addAll(this.unifyRules);
+    builder.add(ProjectToProjectUnifyRule1.INSTANCE);
+    this.unifyRules = builder.build();
+  }
+
+  public RelNode go(RelNode replacement_) {
+    return super.go(replacement_);
+  }
+
+  /**
+   * Project to Project Unify rule.
+   */
+
+  private static class ProjectToProjectUnifyRule1 extends AbstractUnifyRule {
+    public static final ProjectToProjectUnifyRule1 INSTANCE =
+        new ProjectToProjectUnifyRule1();
+
+    private ProjectToProjectUnifyRule1() {
+      super(operand(MutableProject.class, query(0)),
+          operand(MutableProject.class, target(0)), 1);
+    }
+
+    @Override
+    protected UnifyResult apply(UnifyRuleCall call) {
+      final MutableProject query = (MutableProject) call.query;
+
+      final List<RelDataTypeField> oldFieldList = query.getInput().getRowType().getFieldList();
+      final List<RelDataTypeField> newFieldList = call.target.getRowType().getFieldList();
+      List<RexNode> newProjects;
+      try {
+        newProjects = transformRex(query.getProjects(), oldFieldList, newFieldList);
+      } catch (MatchFailed e) {
+        return null;
+      }
+
+      final MutableProject newProject =
+          MutableProject.of(
+              query.getRowType(), call.target, newProjects);
+
+      final MutableRel newProject2 = MutableRels.strip(newProject);
+      return call.result(newProject2);
+    }
+
+    @Override
+    protected UnifyRuleCall match(SubstitutionVisitor visitor, MutableRel query,
+        MutableRel target) {
+      assert query instanceof MutableProject && target instanceof MutableProject;
+
+      if (queryOperand.matches(visitor, query)) {
+        if (targetOperand.matches(visitor, target)) {
+          return null;
+        } else if (targetOperand.isWeaker(visitor, target)) {
+
+          final MutableProject queryProject = (MutableProject) query;
+          if (queryProject.getInput() instanceof MutableFilter) {
+
+            final MutableFilter innerFilter = (MutableFilter) (queryProject.getInput());
+            RexNode newCondition;
+            try {
+              newCondition = transformRex(innerFilter.getCondition(),
+                  innerFilter.getInput().getRowType().getFieldList(),
+                  target.getRowType().getFieldList());
+            } catch (MatchFailed e) {
+              return null;
+            }
+            final MutableFilter newFilter = MutableFilter.of(target,
+                newCondition);
+
+            return visitor.new UnifyRuleCall(this, query, newFilter,
+                copy(visitor.getSlots(), slotCount));
+          }
+        }
+      }
+      return null;
+    }
+
+    private RexNode transformRex(
+        RexNode node,
+        final List<RelDataTypeField> oldFields,
+        final List<RelDataTypeField> newFields) {
+      List<RexNode> nodes = transformRex(ImmutableList.of(node), oldFields, newFields);
+      return nodes.get(0);
+    }
+
+    private List<RexNode> transformRex(
+        List<RexNode> nodes,
+        final List<RelDataTypeField> oldFields,
+        final List<RelDataTypeField> newFields) {
+      RexShuttle shuttle = new RexShuttle() {
+        @Override public RexNode visitInputRef(RexInputRef ref) {
+          RelDataTypeField f = oldFields.get(ref.getIndex());
+          for (int index = 0; index < newFields.size(); index++) {
+            RelDataTypeField newf = newFields.get(index);
+            if (f.getKey().equals(newf.getKey())
+                && f.getValue() == newf.getValue()) {
+              return new RexInputRef(index, f.getValue());
+            }
+          }
+          throw MatchFailed.INSTANCE;
+        }
+      };
+      return shuttle.apply(nodes);
+    }
+  }
+}
+
+// End MaterializedViewSubstitutionVisitor.java

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
index 5aa2177..c1f8af5 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
@@ -1199,7 +1199,7 @@ public abstract class RelOptUtil {
         false);
   }
 
-  private static SqlKind reverse(SqlKind kind) {
+  public static SqlKind reverse(SqlKind kind) {
     switch (kind) {
     case GREATER_THAN:
       return SqlKind.LESS_THAN;
@@ -1214,7 +1214,7 @@ public abstract class RelOptUtil {
     }
   }
 
-  private static SqlOperator op(SqlKind kind, SqlOperator operator) {
+  public static SqlOperator op(SqlKind kind, SqlOperator operator) {
     switch (kind) {
     case EQUALS:
       return SqlStdOperatorTable.EQUALS;

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java b/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
new file mode 100644
index 0000000..1eb019d
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/plan/RexImplicationChecker.java
@@ -0,0 +1,377 @@
+/*
+ * 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.plan;
+
+import org.apache.calcite.DataContext;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexExecutable;
+import org.apache.calcite.rex.RexExecutorImpl;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVisitorImpl;
+import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.sql.SqlOperator;
+import org.apache.calcite.sql.fun.SqlCastFunction;
+import org.apache.calcite.util.Pair;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+
+
+/** Checks if Condition X logically implies Condition Y
+ *
+ * <p>(x > 10) implies (x > 5)</p>
+ *
+ * <p>(y = 10) implies (y < 30 AND x > 30)</p>
+ */
+public class RexImplicationChecker {
+  final RexBuilder builder;
+  final RexExecutorImpl rexImpl;
+  final RelDataType rowType;
+
+  public RexImplicationChecker(
+      RexBuilder builder,
+      RexExecutorImpl rexImpl,
+      RelDataType rowType) {
+    this.builder = builder;
+    this.rexImpl = rexImpl;
+    this.rowType = rowType;
+  }
+
+  /**
+   * Checks if condition first implies (=>) condition second
+   * This reduces to SAT problem which is NP-Complete
+   * When func says first => second then it is definitely true
+   * It cannot prove if first doesnot imply second.
+   * @param first first condition
+   * @param second second condition
+   * @return true if it can prove first => second, otherwise false i.e.,
+   * it doesn't know if implication holds .
+   */
+  public boolean implies(RexNode first, RexNode second) {
+
+    // Validation
+    if (!validate(first, second)) {
+      return false;
+    }
+
+    RexCall firstCond = (RexCall) first;
+    RexCall secondCond = (RexCall) second;
+
+    // Get DNF
+    RexNode firstDnf = RexUtil.toDnf(builder, first);
+    RexNode secondDnf = RexUtil.toDnf(builder, second);
+
+    // Check Trivial Cases
+    if (firstDnf.isAlwaysFalse()
+        || secondDnf.isAlwaysTrue()) {
+      return true;
+    }
+
+    /** Decompose DNF into List of Conjunctions
+     *
+     * (x > 10 AND y > 30) OR (z > 90) will be converted to
+     * list of 2 conditions:
+     * 1. (x > 10 AND y > 30)
+     * 2. (z > 90)
+     *
+     */
+    List<RexNode> firstDnfs = RelOptUtil.disjunctions(firstDnf);
+    List<RexNode> secondDnfs = RelOptUtil.disjunctions(secondDnf);
+
+    for (RexNode f : firstDnfs) {
+      if (!f.isAlwaysFalse()) {
+        //Check if f implies atleast
+        // one of the conjunctions in list secondDnfs
+        boolean implyOneConjuntion = false;
+        for (RexNode s : secondDnfs) {
+          if (s.isAlwaysFalse()) { // f cannot imply s
+            continue;
+          }
+
+          if (impliesConjunction(f, s)) {
+            // Satisfies one of the condition, so lets
+            // move to next conjunction in firstDnfs
+            implyOneConjuntion = true;
+            break;
+          }
+        } //end of inner loop
+
+        // If f couldnot imply even one conjunction in
+        // secondDnfs, then final implication may be false
+        if (!implyOneConjuntion) {
+          return false;
+        }
+      }
+    } //end of outer loop
+
+    return true;
+  }
+
+  /** Checks if Conjunction first => Conjunction second**/
+  private boolean impliesConjunction(RexNode first, RexNode second) {
+
+    InputUsageFinder firstUsgFinder = new InputUsageFinder();
+    InputUsageFinder secondUsgFinder = new InputUsageFinder();
+
+    RexUtil.apply(firstUsgFinder, new ArrayList<RexNode>(), first);
+    RexUtil.apply(secondUsgFinder, new ArrayList<RexNode>(), second);
+
+    // Check Support
+    if (!checkSupport(firstUsgFinder, secondUsgFinder)) {
+      return false;
+    }
+
+    List<Pair<RexInputRef, RexNode>> usgList = new ArrayList<>();
+    for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> entry: firstUsgFinder.usageMap.entrySet()) {
+      final List<Pair<SqlOperator, RexNode>> list = entry.getValue().getUsageList();
+      usgList.add(Pair.of(entry.getKey(), list.get(0).getValue()));
+    }
+
+    /* Get the literals from first conjunction and execute second conjunction using them
+     * E.g., for x >30 => x > 10,
+     * we will replace x by 30 in second expression and execute it i.e., 30>10
+     * If it's true then we infer implication.
+     */
+    final DataContext dataValues = VisitorDataContext.getDataContext(rowType, usgList);
+
+    if (dataValues == null) {
+      return false;
+    }
+
+    ImmutableList<RexNode> constExps = ImmutableList.of(second);
+    final RexExecutable exec = rexImpl.getExecutable(builder,
+        constExps, rowType);
+
+    Object[] result;
+    exec.setDataContext(dataValues);
+    try {
+      result = exec.execute();
+    } catch (Exception e) {
+      // TODO: CheckSupport should not allow this exception to be thrown
+      // Need to monitor it and handle all the cases raising them.
+      return false;
+    }
+    return result != null && result.length == 1 && result[0] instanceof Boolean
+        && (Boolean) result[0];
+  }
+
+  /**
+   * Looks at the usage of variables in first and second conjunction to decide
+   * if this kind of expression is currently supported for proving first => second.
+   * 1. Variables should be used only once in both the conjunction against
+   *    given set of operations only: >,<,<=,>=,=,!=
+   * 2. All the variables used in second condition should be used even in the first.
+   * 3. If operator used for variable in first is op1 and op2 for second, then we support
+   *    these combination for conjunction (op1, op2) then op1, op2 belongs to
+   *    one of the following sets:
+   *    a. (<,<=) X (<,<=) , X represents cartesian product
+   *    b. (>/>=) X (>,>=)
+   *    c. (=) X (>,>=,<,<=,=,!=)
+   *    d. (!=, =)
+   * @return true, if input usage pattern is supported. Otherwise, false.
+   */
+  private boolean checkSupport(
+      InputUsageFinder firstUsgFinder,
+      InputUsageFinder secondUsgFinder) {
+    Map<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> firstUsgMap = firstUsgFinder.usageMap;
+    Map<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> secondUsgMap = secondUsgFinder.usageMap;
+
+    for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> entry: firstUsgMap.entrySet()) {
+      if (entry.getValue().usageCount > 1) {
+        return false;
+      }
+    }
+
+    for (Map.Entry<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> entry: secondUsgMap.entrySet()) {
+      final InputRefUsage<SqlOperator, RexNode> secondUsage = entry.getValue();
+      if (secondUsage.getUsageCount() > 1
+          || secondUsage.getUsageList().size() != 1) {
+        return false;
+      }
+
+      final InputRefUsage<SqlOperator, RexNode> firstUsage = firstUsgMap.get(entry.getKey());
+      if (firstUsage == null
+          || firstUsage.getUsageList().size() != 1) {
+        return false;
+      }
+
+      final Pair<SqlOperator, RexNode> fUse = firstUsage.getUsageList().get(0);
+      final Pair<SqlOperator, RexNode> sUse = secondUsage.getUsageList().get(0);
+
+      final SqlKind fkind = fUse.getKey().getKind();
+
+      if (fkind != SqlKind.EQUALS) {
+        switch (sUse.getKey().getKind()) {
+        case GREATER_THAN:
+        case GREATER_THAN_OR_EQUAL:
+          if (!(fkind == SqlKind.GREATER_THAN)
+              && !(fkind == SqlKind.GREATER_THAN_OR_EQUAL)) {
+            return false;
+          }
+          break;
+        case LESS_THAN:
+        case LESS_THAN_OR_EQUAL:
+          if (!(fkind == SqlKind.LESS_THAN)
+              && !(fkind == SqlKind.LESS_THAN_OR_EQUAL)) {
+            return false;
+          }
+          break;
+        default:
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  private boolean validate(RexNode first, RexNode second) {
+    if (first == null || second == null) {
+      return false;
+    }
+    if (!(first instanceof RexCall)
+        || !(second instanceof RexCall)) {
+      return false;
+    }
+    return true;
+  }
+
+
+  /**
+   * Visitor which builds a Usage Map of inputs used by an expression.
+   * E.g: for x >10 AND y < 20 AND x =40, Usage Map would look like:
+   * key:x value: {(>,10),(=,40), usageCount = 2}
+   * key:y value: {(>,20),usageCount=1}
+   */
+  private static class InputUsageFinder extends RexVisitorImpl<Void> {
+    public final Map<RexInputRef, InputRefUsage<SqlOperator,
+        RexNode>> usageMap = new HashMap<>();
+
+    public InputUsageFinder() {
+      super(true);
+    }
+
+    public Void visitInputRef(RexInputRef inputRef) {
+      InputRefUsage<SqlOperator,
+          RexNode> inputRefUse = getUsageMap(inputRef);
+      inputRefUse.incrUsage();
+      return null;
+    }
+
+    @Override public Void visitCall(RexCall call) {
+      switch (call.getOperator().getKind()) {
+      case GREATER_THAN:
+      case GREATER_THAN_OR_EQUAL:
+      case LESS_THAN:
+      case LESS_THAN_OR_EQUAL:
+      case EQUALS:
+      case NOT_EQUALS:
+        updateUsage(call);
+        break;
+      default:
+      }
+      return super.visitCall(call);
+    }
+
+    private void updateUsage(RexCall call) {
+      final List<RexNode> operands = call.getOperands();
+      RexNode first = removeCast(operands.get(0));
+      RexNode second = removeCast(operands.get(1));
+
+      if (first.isA(SqlKind.INPUT_REF)
+          && second.isA(SqlKind.LITERAL)) {
+        updateUsage(call.getOperator(), (RexInputRef) first, second);
+      }
+
+      if (first.isA(SqlKind.LITERAL)
+          && second.isA(SqlKind.INPUT_REF)) {
+        updateUsage(reverse(call.getOperator()), (RexInputRef) second, first);
+      }
+    }
+
+    private SqlOperator reverse(SqlOperator op) {
+      return RelOptUtil.op(
+          RelOptUtil.reverse(op.getKind()), op);
+    }
+
+    private static RexNode removeCast(RexNode inputRef) {
+      if (inputRef instanceof RexCall) {
+        final RexCall castedRef = (RexCall) inputRef;
+        final SqlOperator operator = castedRef.getOperator();
+        if (operator instanceof SqlCastFunction) {
+          inputRef = castedRef.getOperands().get(0);
+        }
+      }
+      return inputRef;
+    }
+
+    private void updateUsage(SqlOperator op, RexInputRef inputRef, RexNode literal) {
+      InputRefUsage<SqlOperator,
+          RexNode> inputRefUse = getUsageMap(inputRef);
+      Pair<SqlOperator, RexNode> use = Pair.of(op, literal);
+      inputRefUse.getUsageList().add(use);
+    }
+
+    private InputRefUsage<SqlOperator, RexNode> getUsageMap(RexInputRef rex) {
+      InputRefUsage<SqlOperator, RexNode> inputRefUse = usageMap.get(rex);
+      if (inputRefUse == null) {
+        inputRefUse = new InputRefUsage<>();
+        usageMap.put(rex, inputRefUse);
+      }
+
+      return inputRefUse;
+    }
+  }
+
+  /**
+   * DataStructure to store usage of InputRefs in expression
+   */
+
+  private static class InputRefUsage<T1, T2> {
+    private final List<Pair<T1, T2>> usageList =
+        new ArrayList<Pair<T1, T2>>();
+    private int usageCount = 0;
+
+    public InputRefUsage() {}
+
+    public int getUsageCount() {
+      return usageCount;
+    }
+
+    public void incrUsage() {
+      usageCount++;
+    }
+
+    public List<Pair<T1, T2>> getUsageList() {
+      return usageList;
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/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 b1c89e6..62b2d9d 100644
--- a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
+++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java
@@ -42,6 +42,7 @@ 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.RexExecutorImpl;
 import org.apache.calcite.rex.RexInputRef;
 import org.apache.calcite.rex.RexLiteral;
 import org.apache.calcite.rex.RexNode;
@@ -144,15 +145,7 @@ public class SubstitutionVisitor {
   private static final Equivalence<List<?>> PAIRWISE_STRING_EQUIVALENCE =
       (Equivalence) STRING_EQUIVALENCE.pairwise();
 
-  private static final List<UnifyRule> RULES =
-      ImmutableList.<UnifyRule>of(
-//          TrivialRule.INSTANCE,
-          ProjectToProjectUnifyRule.INSTANCE,
-          FilterToProjectUnifyRule.INSTANCE,
-//          ProjectToFilterUnifyRule.INSTANCE,
-          FilterToFilterUnifyRule.INSTANCE,
-          AggregateToAggregateUnifyRule.INSTANCE,
-          AggregateOnProjectToAggregateUnifyRule.INSTANCE);
+  protected static List<UnifyRule> unifyRules;
 
   private static final Map<Pair<Class, Class>, List<UnifyRule>> RULE_MAP =
       new HashMap<>();
@@ -208,6 +201,28 @@ public class SubstitutionVisitor {
     visitor.go(query);
     allNodes.removeAll(parents);
     queryLeaves = ImmutableList.copyOf(allNodes);
+    initUnifyRules();
+    initRuleMap();
+  }
+
+  public void initUnifyRules() {
+    unifyRules =
+            ImmutableList.<UnifyRule>of(
+//          TrivialRule.INSTANCE,
+                    ProjectToProjectUnifyRule.INSTANCE,
+                    FilterToProjectUnifyRule.INSTANCE,
+//          ProjectToFilterUnifyRule.INSTANCE,
+                    FilterToFilterUnifyRule.INSTANCE,
+                    AggregateToAggregateUnifyRule.INSTANCE,
+                    AggregateOnProjectToAggregateUnifyRule.INSTANCE);
+  }
+
+  public void initRuleMap() {
+    this.RULE_MAP.clear();
+  }
+
+  public MutableRel[] getSlots() {
+    return slots;
   }
 
   private static MutableRel toMutable(RelNode rel) {
@@ -457,7 +472,8 @@ public class SubstitutionVisitor {
               final UnifyResult result = rule.apply(call);
               if (result != null) {
                 ++count;
-                result.call.query.replaceInParent(result.result);
+                MutableRel parent = result.call.query.replaceInParent(result.result);
+
                 // Replace previous equivalents with new equivalents, higher up
                 // the tree.
                 for (int i = 0; i < rule.slotCount; i++) {
@@ -612,7 +628,7 @@ public class SubstitutionVisitor {
     if (list == null) {
       final ImmutableList.Builder<UnifyRule> builder =
           ImmutableList.builder();
-      for (UnifyRule rule : RULES) {
+      for (UnifyRule rule : unifyRules) {
         //noinspection unchecked
         if (mightMatch(rule, queryClass, targetClass)) {
           builder.add(rule);
@@ -631,8 +647,8 @@ public class SubstitutionVisitor {
   }
 
   /** Exception thrown to exit a matcher. Not really an error. */
-  private static class MatchFailed extends ControlFlowException {
-    static final MatchFailed INSTANCE = new MatchFailed();
+  protected static class MatchFailed extends ControlFlowException {
+    public static final MatchFailed INSTANCE = new MatchFailed();
   }
 
   /** Rule that attempts to match a query relational expression
@@ -641,7 +657,7 @@ public class SubstitutionVisitor {
    * <p>The rule declares the query and target types; this allows the
    * engine to fire only a few rules in a given context.</p>
    */
-  private abstract static class UnifyRule {
+  protected abstract static class UnifyRule {
     protected final int slotCount;
     protected final Operand queryOperand;
     protected final Operand targetOperand;
@@ -679,9 +695,9 @@ public class SubstitutionVisitor {
      *
      * @param call Input parameters
      */
-    abstract UnifyResult apply(UnifyRuleCall call);
+    protected abstract UnifyResult apply(UnifyRuleCall call);
 
-    UnifyRuleCall match(SubstitutionVisitor visitor, MutableRel query,
+    protected UnifyRuleCall match(SubstitutionVisitor visitor, MutableRel query,
         MutableRel target) {
       if (queryOperand.matches(visitor, query)) {
         if (targetOperand.matches(visitor, target)) {
@@ -692,7 +708,7 @@ public class SubstitutionVisitor {
       return null;
     }
 
-    private <E> ImmutableList<E> copy(E[] slots, int slotCount) {
+    protected <E> ImmutableList<E> copy(E[] slots, int slotCount) {
       // Optimize if there are 0 or 1 slots.
       switch (slotCount) {
       case 0:
@@ -708,11 +724,11 @@ public class SubstitutionVisitor {
   /**
    * Arguments to an application of a {@link UnifyRule}.
    */
-  private class UnifyRuleCall {
-    final UnifyRule rule;
-    final MutableRel query;
-    final MutableRel target;
-    final ImmutableList<MutableRel> slots;
+  protected class UnifyRuleCall {
+    protected final UnifyRule rule;
+    public final MutableRel query;
+    public final MutableRel target;
+    protected final ImmutableList<MutableRel> slots;
 
     public UnifyRuleCall(UnifyRule rule, MutableRel query, MutableRel target,
         ImmutableList<MutableRel> slots) {
@@ -722,7 +738,7 @@ public class SubstitutionVisitor {
       this.slots = Preconditions.checkNotNull(slots);
     }
 
-    UnifyResult result(MutableRel result) {
+    public UnifyResult result(MutableRel result) {
       assert MutableRels.contains(result, target);
       assert MutableRels.equalType("result", result, "query", query, true);
       MutableRel replace = replacementMap.get(target);
@@ -753,7 +769,7 @@ public class SubstitutionVisitor {
    * generated a {@code result} that is equivalent to {@code query} and
    * contains {@code target}.
    */
-  private static class UnifyResult {
+  protected static class UnifyResult {
     private final UnifyRuleCall call;
     // equivalent to "query", contains "result"
     private final MutableRel result;
@@ -766,7 +782,7 @@ public class SubstitutionVisitor {
   }
 
   /** Abstract base class for implementing {@link UnifyRule}. */
-  private abstract static class AbstractUnifyRule extends UnifyRule {
+  protected abstract static class AbstractUnifyRule extends UnifyRule {
     public AbstractUnifyRule(Operand queryOperand, Operand targetOperand,
         int slotCount) {
       super(slotCount, queryOperand, targetOperand);
@@ -787,24 +803,24 @@ public class SubstitutionVisitor {
     }
 
     /** Creates an operand with given inputs. */
-    static Operand operand(Class<? extends MutableRel> clazz,
+    protected static Operand operand(Class<? extends MutableRel> clazz,
         Operand... inputOperands) {
       return new InternalOperand(clazz, ImmutableList.copyOf(inputOperands));
     }
 
     /** Creates an operand that doesn't check inputs. */
-    static Operand any(Class<? extends MutableRel> clazz) {
+    protected static Operand any(Class<? extends MutableRel> clazz) {
       return new AnyOperand(clazz);
     }
 
     /** Creates an operand that matches a relational expression in the query. */
-    static Operand query(int ordinal) {
+    protected static Operand query(int ordinal) {
       return new QueryOperand(ordinal);
     }
 
     /** Creates an operand that matches a relational expression in the
      * target. */
-    static Operand target(int ordinal) {
+    protected static Operand target(int ordinal) {
       return new TargetOperand(ordinal);
     }
   }
@@ -860,6 +876,7 @@ public class SubstitutionVisitor {
     }
   }
 
+
   /** Implementation of {@link UnifyRule} that matches a {@link MutableFilter}
    * to a {@link MutableProject}. */
   private static class FilterToProjectUnifyRule extends AbstractUnifyRule {
@@ -899,7 +916,7 @@ public class SubstitutionVisitor {
       }
     }
 
-    private MutableRel invert(List<Pair<RexNode, String>> namedProjects,
+    protected MutableRel invert(List<Pair<RexNode, String>> namedProjects,
         MutableRel input,
         RexShuttle shuttle) {
       if (LOGGER.isLoggable(Level.FINER)) {
@@ -924,7 +941,7 @@ public class SubstitutionVisitor {
       return MutableProject.of(input, exprList, Pair.right(namedProjects));
     }
 
-    private MutableRel invert(MutableRel model, MutableRel input,
+    protected MutableRel invert(MutableRel model, MutableRel input,
         MutableProject project) {
       if (LOGGER.isLoggable(Level.FINER)) {
         LOGGER.finer("SubstitutionVisitor: invert:\n"
@@ -1194,7 +1211,7 @@ public class SubstitutionVisitor {
 
   /** Builds a shuttle that stores a list of expressions, and can map incoming
    * expressions to references to them. */
-  private static RexShuttle getRexShuttle(MutableProject target) {
+  protected static RexShuttle getRexShuttle(MutableProject target) {
     final Map<String, Integer> map = new HashMap<>();
     for (RexNode e : target.getProjects()) {
       map.put(e.toString(), map.size());
@@ -1258,7 +1275,7 @@ public class SubstitutionVisitor {
    * For this reason, you should use {@code MutableRel} for short-lived
    * operations, and transcribe back to {@code RelNode} when you are done.</p>
    */
-  private abstract static class MutableRel {
+  protected abstract static class MutableRel {
     MutableRel parent;
     int ordinalInParent;
     public final RelOptCluster cluster;
@@ -1317,6 +1334,8 @@ public class SubstitutionVisitor {
     @Override public final String toString() {
       return deep();
     }
+
+    public MutableRel getParent() { return parent; }
   }
 
   /** Implementation of {@link MutableRel} whose only purpose is to have a
@@ -1337,7 +1356,7 @@ public class SubstitutionVisitor {
 
    /** Abstract base class for implementations of {@link MutableRel} that have
    * no inputs. */
-  private abstract static class MutableLeafRel extends MutableRel {
+  protected abstract static class MutableLeafRel extends MutableRel {
     protected final RelNode rel;
 
     MutableLeafRel(MutableRelType type, RelNode rel) {
@@ -1359,7 +1378,7 @@ public class SubstitutionVisitor {
   }
 
   /** Mutable equivalent of {@link SingleRel}. */
-  private abstract static class MutableSingleRel extends MutableRel {
+  protected abstract static class MutableSingleRel extends MutableRel {
     protected MutableRel input;
 
     MutableSingleRel(MutableRelType type, RelDataType rowType,
@@ -1396,7 +1415,7 @@ public class SubstitutionVisitor {
 
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalTableScan}. */
-  private static class MutableScan extends MutableLeafRel {
+  protected static class MutableScan extends MutableLeafRel {
     private MutableScan(TableScan rel) {
       super(MutableRelType.SCAN, rel);
     }
@@ -1422,7 +1441,7 @@ public class SubstitutionVisitor {
   }
 
   /** Mutable equivalent of {@link org.apache.calcite.rel.core.Values}. */
-  private static class MutableValues extends MutableLeafRel {
+  protected static class MutableValues extends MutableLeafRel {
     private MutableValues(Values rel) {
       super(MutableRelType.VALUES, rel);
     }
@@ -1449,7 +1468,7 @@ public class SubstitutionVisitor {
 
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalProject}. */
-  private static class MutableProject extends MutableSingleRel {
+  protected static class MutableProject extends MutableSingleRel {
     private final List<RexNode> projects;
 
     private MutableProject(RelDataType rowType, MutableRel input,
@@ -1459,7 +1478,7 @@ public class SubstitutionVisitor {
       assert RexUtil.compatibleTypes(projects, rowType, true);
     }
 
-    static MutableProject of(RelDataType rowType, MutableRel input,
+    public static MutableProject of(RelDataType rowType, MutableRel input,
         List<RexNode> projects) {
       return new MutableProject(rowType, input, projects);
     }
@@ -1467,7 +1486,7 @@ public class SubstitutionVisitor {
     /** Equivalent to
      * {@link RelOptUtil#createProject(org.apache.calcite.rel.RelNode, java.util.List, java.util.List)}
      * for {@link MutableRel}. */
-    static MutableRel of(MutableRel child, List<RexNode> exprList,
+    public static MutableRel of(MutableRel child, List<RexNode> exprList,
         List<String> fieldNameList) {
       final RelDataType rowType =
           RexUtil.createStructType(child.cluster.getTypeFactory(), exprList,
@@ -1512,7 +1531,7 @@ public class SubstitutionVisitor {
 
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalFilter}. */
-  private static class MutableFilter extends MutableSingleRel {
+  protected static class MutableFilter extends MutableSingleRel {
     private final RexNode condition;
 
     private MutableFilter(MutableRel input, RexNode condition) {
@@ -1520,7 +1539,7 @@ public class SubstitutionVisitor {
       this.condition = condition;
     }
 
-    static MutableFilter of(MutableRel input, RexNode condition) {
+    public static MutableFilter of(MutableRel input, RexNode condition) {
       return new MutableFilter(input, condition);
     }
 
@@ -1547,7 +1566,7 @@ public class SubstitutionVisitor {
 
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalAggregate}. */
-  private static class MutableAggregate extends MutableSingleRel {
+  protected static class MutableAggregate extends MutableSingleRel {
     public final boolean indicator;
     private final ImmutableBitSet groupSet;
     private final ImmutableList<ImmutableBitSet> groupSets;
@@ -1611,7 +1630,7 @@ public class SubstitutionVisitor {
   }
 
   /** Mutable equivalent of {@link org.apache.calcite.rel.core.Sort}. */
-  private static class MutableSort extends MutableSingleRel {
+  protected static class MutableSort extends MutableSingleRel {
     private final RelCollation collation;
     private final RexNode offset;
     private final RexNode fetch;
@@ -1655,7 +1674,7 @@ public class SubstitutionVisitor {
   }
 
   /** Base class for set-operations. */
-  private abstract static class MutableSetOp extends MutableRel {
+  protected abstract static class MutableSetOp extends MutableRel {
     protected final List<MutableRel> inputs;
 
     private MutableSetOp(RelOptCluster cluster, RelDataType rowType,
@@ -1681,7 +1700,7 @@ public class SubstitutionVisitor {
 
   /** Mutable equivalent of
    * {@link org.apache.calcite.rel.logical.LogicalUnion}. */
-  private static class MutableUnion extends MutableSetOp {
+  protected static class MutableUnion extends MutableSetOp {
     public boolean all;
 
     private MutableUnion(RelOptCluster cluster, RelDataType rowType,
@@ -1820,7 +1839,7 @@ public class SubstitutionVisitor {
   }
 
   /** Utilities for dealing with {@link MutableRel}s. */
-  private static class MutableRels {
+  protected static class MutableRels {
     public static boolean contains(MutableRel ancestor,
         final MutableRel target) {
       if (ancestor.equals(target)) {
@@ -1951,7 +1970,7 @@ public class SubstitutionVisitor {
   }
 
   /** Visitor that prints an indented tree of {@link MutableRel}s. */
-  private static class MutableRelDumper extends MutableRelVisitor {
+  protected static class MutableRelDumper extends MutableRelVisitor {
     private final StringBuilder buf = new StringBuilder();
     private int level;
 
@@ -1975,14 +1994,18 @@ public class SubstitutionVisitor {
   }
 
   /** Operand to a {@link UnifyRule}. */
-  private abstract static class Operand {
+  protected abstract static class Operand {
     protected final Class<? extends MutableRel> clazz;
 
     protected Operand(Class<? extends MutableRel> clazz) {
       this.clazz = clazz;
     }
 
-    abstract boolean matches(SubstitutionVisitor visitor, MutableRel rel);
+    public abstract boolean matches(SubstitutionVisitor visitor, MutableRel rel);
+
+    public boolean isWeaker(SubstitutionVisitor visitor, MutableRel rel) {
+      return false;
+    }
   }
 
   /** Operand to a {@link UnifyRule} that matches a relational expression of a
@@ -1995,11 +2018,15 @@ public class SubstitutionVisitor {
       this.inputs = inputs;
     }
 
-    @Override boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
+    @Override public boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
       return clazz.isInstance(rel)
           && allMatch(visitor, inputs, rel.getInputs());
     }
 
+    @Override public boolean isWeaker(SubstitutionVisitor visitor, MutableRel rel) {
+      return clazz.isInstance(rel)
+          && allWeaker(visitor, inputs, rel.getInputs());
+    }
     private static boolean allMatch(SubstitutionVisitor visitor,
         List<Operand> operands, List<MutableRel> rels) {
       if (operands.size() != rels.size()) {
@@ -2012,6 +2039,20 @@ public class SubstitutionVisitor {
       }
       return true;
     }
+
+    private static boolean allWeaker(
+        SubstitutionVisitor visitor,
+        List<Operand> operands, List<MutableRel> rels) {
+      if (operands.size() != rels.size()) {
+        return false;
+      }
+      for (Pair<Operand, MutableRel> pair : Pair.zip(operands, rels)) {
+        if (!pair.left.isWeaker(visitor, pair.right)) {
+          return false;
+        }
+      }
+      return true;
+    }
   }
 
   /** Operand to a {@link UnifyRule} that matches a relational expression of a
@@ -2021,7 +2062,7 @@ public class SubstitutionVisitor {
       super(clazz);
     }
 
-    @Override boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
+    @Override public boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
       return clazz.isInstance(rel);
     }
   }
@@ -2042,7 +2083,7 @@ public class SubstitutionVisitor {
       this.ordinal = ordinal;
     }
 
-    @Override boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
+    @Override public boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
       visitor.slots[ordinal] = rel;
       return true;
     }
@@ -2058,11 +2099,45 @@ public class SubstitutionVisitor {
       this.ordinal = ordinal;
     }
 
-    @Override boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
+    @Override public boolean matches(SubstitutionVisitor visitor, MutableRel rel) {
       final MutableRel rel0 = visitor.slots[ordinal];
       assert rel0 != null : "QueryOperand should have been called first";
       return rel0 == rel || visitor.equivalents.get(rel0).contains(rel);
     }
+
+    @Override public boolean isWeaker(SubstitutionVisitor visitor, MutableRel rel) {
+      final MutableRel rel0 = visitor.slots[ordinal];
+      assert rel0 != null : "QueryOperand should have been called first";
+
+      if (rel0 == rel || visitor.equivalents.get(rel0).contains(rel)) {
+        return false;
+      }
+
+      if (!(rel0 instanceof MutableFilter)
+          || !(rel instanceof MutableFilter)) {
+        return false;
+      }
+
+      if (!rel.getRowType().equals(rel0.getRowType())) {
+        return false;
+      }
+
+      final MutableRel rel0input = ((MutableFilter) rel0).getInput();
+      final MutableRel relinput = ((MutableFilter) rel).getInput();
+      if (rel0input != relinput
+          && !visitor.equivalents.get(rel0input).contains(relinput)) {
+        return false;
+      }
+
+      RexExecutorImpl rexImpl =
+          (RexExecutorImpl) (rel.cluster.getPlanner().getExecutor());
+      RexImplicationChecker rexImplicationChecker = new RexImplicationChecker(
+          rel.cluster.getRexBuilder(),
+          rexImpl, rel.getRowType());
+
+      return rexImplicationChecker.implies(((MutableFilter) rel0).getCondition(),
+          ((MutableFilter) rel).getCondition());
+    }
   }
 
   /** Visitor that counts how many {@link QueryOperand} and

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java b/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
new file mode 100644
index 0000000..a941347
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/plan/VisitorDataContext.java
@@ -0,0 +1,186 @@
+/*
+ * 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.plan;
+
+import org.apache.calcite.DataContext;
+import org.apache.calcite.adapter.java.JavaTypeFactory;
+import org.apache.calcite.linq4j.QueryProvider;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rex.RexCall;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.sql.SqlOperator;
+import org.apache.calcite.sql.fun.SqlCastFunction;
+import org.apache.calcite.util.NlsString;
+import org.apache.calcite.util.Pair;
+
+import java.math.BigDecimal;
+import java.sql.Date;
+import java.util.Calendar;
+import java.util.List;
+
+/**
+ * DataContext for evaluating an RexExpression
+ */
+public class VisitorDataContext implements DataContext {
+  private final Object[] values;
+
+  public VisitorDataContext(Object[] values) {
+    this.values = values;
+  }
+
+  public SchemaPlus getRootSchema() {
+    throw new RuntimeException("Unsupported");
+  }
+
+  public JavaTypeFactory getTypeFactory() {
+    throw new RuntimeException("Unsupported");
+  }
+
+  public QueryProvider getQueryProvider() {
+    throw new RuntimeException("Unsupported");
+  }
+
+  public Object get(String name) {
+    if (name.equals("inputRecord")) {
+      return values;
+    } else {
+      return null;
+    }
+  }
+  public static DataContext getDataContext(RelNode targetRel, LogicalFilter queryRel) {
+    return getDataContext(targetRel.getRowType(), queryRel.getCondition());
+  }
+
+  public static DataContext getDataContext(RelDataType rowType, RexNode rex) {
+    int size = rowType.getFieldList().size();
+    Object[] values = new Object[size];
+    List<RexNode> operands = ((RexCall) rex).getOperands();
+    final RexNode firstOperand = operands.get(0);
+    final RexNode secondOperand = operands.get(1);
+    final Pair<Integer, ? extends Object> value = getValue(firstOperand, secondOperand);
+    if (value != null) {
+      int index = value.getKey();
+      values[index] = value.getValue();
+      return new VisitorDataContext(values);
+    } else {
+      return null;
+    }
+  }
+
+  public static DataContext getDataContext(RelDataType rowType, List<Pair<RexInputRef,
+      RexNode>> usgList) {
+    int size = rowType.getFieldList().size();
+    Object[] values = new Object[size];
+    for (Pair<RexInputRef, RexNode> elem: usgList) {
+      Pair<Integer, ? extends Object> value = getValue(elem.getKey(), elem.getValue());
+      if (value == null) {
+        return null;
+      }
+      int index = value.getKey();
+      values[index] = value.getValue();
+    }
+    return new VisitorDataContext(values);
+  }
+
+  public static Pair<Integer, ? extends Object> getValue(RexNode inputRef, RexNode literal) {
+    inputRef = removeCast(inputRef);
+    literal = removeCast(literal);
+
+    if (inputRef instanceof RexInputRef
+        && literal instanceof RexLiteral)  {
+      Integer index = ((RexInputRef) inputRef).getIndex();
+      Object value = ((RexLiteral) literal).getValue();
+      final RelDataType type = inputRef.getType();
+
+      switch (type.getSqlTypeName()) {
+      case INTEGER:
+        if (value instanceof BigDecimal) {
+          final Integer intValue = new Integer(((BigDecimal) value).intValue());
+          return Pair.of(index, intValue);
+        }
+      case DOUBLE:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index,
+              new Double(((BigDecimal) value).doubleValue()));
+        }
+      case REAL:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index,
+              new Float(((BigDecimal) value).floatValue()));
+        }
+      case BIGINT:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index,
+              new Long(((BigDecimal) value).longValue()));
+        }
+      case SMALLINT:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index,
+              new Short(((BigDecimal) value).shortValue()));
+        }
+      case TINYINT:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index,
+              new Short(((BigDecimal) value).byteValue()));
+        }
+      case DECIMAL:
+        if (value instanceof BigDecimal) {
+          return Pair.of(index, value);
+        }
+      case DATE:
+        if (value instanceof NlsString) {
+          value = ((RexLiteral) literal).getValue2();
+          final Date dateValue = Date.valueOf((String) value);
+          return Pair.of(index, dateValue);
+        } else if (value instanceof Calendar) {
+          final long timeInMillis = ((Calendar) value).getTimeInMillis();
+          return Pair.of(index, new Date(timeInMillis));
+        }
+      case CHAR:
+        if (value instanceof NlsString) {
+          // TODO: Support coallation. Not supported in {@link #NlsString} compare too.
+          final NlsString nl = (NlsString) value;
+          Character c = new Character(nl.getValue().charAt(0));
+          return Pair.of(index, c);
+        }
+      default:
+        //TODO: Support few more supported cases
+        return Pair.of(index, value);
+      }
+    }
+
+    //Unsupported Arguments
+    return null;
+  }
+
+  private static RexNode removeCast(RexNode inputRef) {
+    if (inputRef instanceof RexCall) {
+      final RexCall castedRef = (RexCall) inputRef;
+      final SqlOperator operator = castedRef.getOperator();
+      if (operator instanceof SqlCastFunction) {
+        inputRef = castedRef.getOperands().get(0);
+      }
+    }
+    return inputRef;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
index 3bb3a16..6634cf3 100644
--- a/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
+++ b/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java
@@ -23,6 +23,7 @@ import org.apache.calcite.plan.AbstractRelOptPlanner;
 import org.apache.calcite.plan.Context;
 import org.apache.calcite.plan.Convention;
 import org.apache.calcite.plan.ConventionTraitDef;
+import org.apache.calcite.plan.MaterializedViewSubstitutionVisitor;
 import org.apache.calcite.plan.RelOptCost;
 import org.apache.calcite.plan.RelOptCostFactory;
 import org.apache.calcite.plan.RelOptLattice;
@@ -38,7 +39,6 @@ import org.apache.calcite.plan.RelOptUtil;
 import org.apache.calcite.plan.RelTrait;
 import org.apache.calcite.plan.RelTraitDef;
 import org.apache.calcite.plan.RelTraitSet;
-import org.apache.calcite.plan.SubstitutionVisitor;
 import org.apache.calcite.plan.hep.HepPlanner;
 import org.apache.calcite.plan.hep.HepProgram;
 import org.apache.calcite.plan.hep.HepProgramBuilder;
@@ -365,6 +365,9 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
     // query. If that is possible, register the remnant query as equivalent
     // to the root.
     //
+
+    // This call modifies originalRoot. Doesn't look like originalRoot should be mutable though.
+    // Need to check.
     RelNode sub = substitute(originalRoot, materialization);
     if (sub != null) {
       // TODO: try to substitute other materializations in the remnant.
@@ -407,8 +410,8 @@ public class VolcanoPlanner extends AbstractRelOptPlanner {
     hepPlanner.setRoot(root);
     root = hepPlanner.findBestExp();
 
-    return new SubstitutionVisitor(target, root)
-        .go(materialization.tableRel);
+    return new MaterializedViewSubstitutionVisitor(target, root)
+            .go(materialization.tableRel);
   }
 
   private void useApplicableMaterializations() {

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/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 ee384e1..5347855 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
@@ -1024,6 +1024,38 @@ public class RexUtil {
     return new CnfHelper(rexBuilder).toCnf(rex);
   }
 
+  /** Converts an expression to disjunctive normal form (DNF).
+   *
+   * <p>DNF: It is a form of logical formula which is disjunction of conjunctive clauses</p>
+   *
+   * <p>All logicl formulas can be converted into DNF.</p>
+   *
+   * <p>The following expression is in DNF:
+   *
+   * <blockquote>(a AND b) OR (c AND d)</blockquote>
+   *
+   * <p>The following expression is not in CNF:
+   *
+   * <blockquote>(a OR b) AND c</blockquote>
+   *
+   * but can be converted to DNF:
+   *
+   * <blockquote>(a AND c) OR (b AND c)</blockquote>
+   *
+   * <p>The following expression is not in CNF:
+   *
+   * <blockquote>NOT (a OR NOT b)</blockquote>
+   *
+   * but can be converted to DNF by applying de Morgan's theorem:
+   *
+   * <blockquote>NOT a AND b</blockquote>
+   *
+   * <p>Expressions not involving AND, OR or NOT at the top level are in DNF.
+   */
+  public static RexNode toDnf(RexBuilder rexBuilder, RexNode rex) {
+    return new DnfHelper(rexBuilder).toDnf(rex);
+  }
+
   /**
    * Returns whether an operator is associative. AND is associative,
    * which means that "(x AND y) and z" is equivalent to "x AND (y AND z)".
@@ -1723,6 +1755,79 @@ public class RexUtil {
     }
   }
 
+  /** Helps {@link org.apache.calcite.rex.RexUtil#toDnf}. */
+  private static class DnfHelper {
+    final RexBuilder rexBuilder;
+
+    private DnfHelper(RexBuilder rexBuilder) {
+      this.rexBuilder = rexBuilder;
+    }
+
+    public RexNode toDnf(RexNode rex) {
+      final List<RexNode> operands;
+      switch (rex.getKind()) {
+      case AND:
+        operands = flattenAnd(((RexCall) rex).getOperands());
+        final RexNode head = operands.get(0);
+        final RexNode headDnf = toDnf(head);
+        final List<RexNode> headDnfs = RelOptUtil.disjunctions(headDnf);
+        final RexNode tail = and(Util.skip(operands));
+        final RexNode tailDnf = toDnf(tail);
+        final List<RexNode> tailDnfs = RelOptUtil.disjunctions(tailDnf);
+        final List<RexNode> list = Lists.newArrayList();
+        for (RexNode h : headDnfs) {
+          for (RexNode t : tailDnfs) {
+            list.add(and(ImmutableList.of(h, t)));
+          }
+        }
+        return or(list);
+      case OR:
+        operands = flattenOr(((RexCall) rex).getOperands());
+        return or(toDnfs(operands));
+      case NOT:
+        final RexNode arg = ((RexCall) rex).getOperands().get(0);
+        switch (arg.getKind()) {
+        case NOT:
+          return toDnf(((RexCall) arg).getOperands().get(0));
+        case OR:
+          operands = ((RexCall) arg).getOperands();
+          return toDnf(and(Lists.transform(flattenOr(operands), ADD_NOT)));
+        case AND:
+          operands = ((RexCall) arg).getOperands();
+          return toDnf(or(Lists.transform(flattenAnd(operands), ADD_NOT)));
+        default:
+          return rex;
+        }
+      default:
+        return rex;
+      }
+    }
+
+    private List<RexNode> toDnfs(List<RexNode> nodes) {
+      final List<RexNode> list = Lists.newArrayList();
+      for (RexNode node : nodes) {
+        RexNode dnf = toDnf(node);
+        switch (dnf.getKind()) {
+        case OR:
+          list.addAll(((RexCall) dnf).getOperands());
+          break;
+        default:
+          list.add(dnf);
+        }
+      }
+      return list;
+    }
+
+    private RexNode and(Iterable<? extends RexNode> nodes) {
+      return composeConjunction(rexBuilder, nodes, false);
+    }
+
+    private RexNode or(Iterable<? extends RexNode> nodes) {
+      return composeDisjunction(rexBuilder, nodes, false);
+    }
+  }
+
+
   /** Shuttle that adds {@code offset} to each {@link RexInputRef} in an
    * expression. */
   private static class RexShiftShuttle extends RexShuttle {

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
index 5a87733..0621a73 100644
--- a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
+++ b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
@@ -114,6 +114,7 @@ import org.junit.runners.Suite;
     // slow tests (above 1s)
     PlannerTest.class,
     RelBuilderTest.class,
+    RexImplicationCheckerTest.class,
     MaterializationTest.class,
     JdbcAdapterTest.class,
     LinqFrontJdbcBackTest.class,

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/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 f0fb54b..ae235ab 100644
--- a/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
+++ b/core/src/test/java/org/apache/calcite/test/MaterializationTest.java
@@ -179,7 +179,8 @@ public class MaterializationTest {
         + "from \"emps\" where \"deptno\" - 10 = 2",
         JdbcTest.HR_MODEL,
         CalciteAssert.checkResultContains(
-            "EnumerableCalc(expr#0..2=[{inputs}], expr#3=[2], expr#4=[=($t0, $t3)], name=[$t2], E=[$t1], $condition=[$t4])\n"
+            "EnumerableCalc(expr#0..2=[{inputs}], expr#3=[2], "
+                + "expr#4=[=($t0, $t3)], name=[$t2], E=[$t1], $condition=[$t4])\n"
                 + "  EnumerableTableScan(table=[[hr, m0]]"));
   }
 
@@ -212,7 +213,8 @@ public class MaterializationTest {
   @Test public void testFilterQueryOnFilterView2() {
     checkMaterialize(
         "select \"deptno\", \"empid\", \"name\" from \"emps\" where \"deptno\" = 10",
-        "select \"empid\" + 1 as x, \"name\" from \"emps\" where \"deptno\" = 10 and \"empid\" < 150");
+        "select \"empid\" + 1 as x, \"name\" from \"emps\" "
+            + "where \"deptno\" = 10 and \"empid\" < 150");
   }
 
   /** As {@link #testFilterQueryOnFilterView()} but condition is weaker in
@@ -220,14 +222,131 @@ public class MaterializationTest {
   @Ignore("not implemented")
   @Test public void testFilterQueryOnFilterView3() {
     checkMaterialize(
-        "select \"deptno\", \"empid\", \"name\" from \"emps\" where \"deptno\" = 10 or \"deptno\" = 20 or \"empid\" < 160",
+        "select \"deptno\", \"empid\", \"name\" from \"emps\" "
+            + "where \"deptno\" = 10 or \"deptno\" = 20 or \"empid\" < 160",
         "select \"empid\" + 1 as x, \"name\" from \"emps\" where \"deptno\" = 10",
         JdbcTest.HR_MODEL,
         CalciteAssert.checkResultContains(
-            "EnumerableCalcRel(expr#0..2=[{inputs}], expr#3=[1], expr#4=[+($t1, $t3)], X=[$t4], name=[$t2], condition=?)\n"
+            "EnumerableCalcRel(expr#0..2=[{inputs}], expr#3=[1], "
+                + "expr#4=[+($t1, $t3)], X=[$t4], name=[$t2], condition=?)\n"
                 + "  EnumerableTableScan(table=[[hr, m0]])"));
   }
 
+  /** As {@link #testFilterQueryOnFilterView()} but condition is stronger in
+   * query. */
+  @Test public void testFilterQueryOnFilterView4() {
+    checkMaterialize(
+            "select * from \"emps\" where \"deptno\" > 10",
+            "select \"name\" from \"emps\" where \"deptno\" > 30");
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is stronger in
+   * query and columns selected are subset of columns in materialized view */
+  @Test public void testFilterQueryOnFilterView5() {
+    checkMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where \"deptno\" > 10",
+            "select \"name\" from \"emps\" where \"deptno\" > 30");
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is stronger in
+   * query and columns selected are subset of columns in materialized view */
+  @Test public void testFilterQueryOnFilterView6() {
+    checkMaterialize(
+            "select \"name\", \"deptno\", \"salary\" from \"emps\" "
+                + "where \"salary\" > 2000.5",
+            "select \"name\" from \"emps\" where \"deptno\" > 30 and \"salary\" > 3000");
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is stronger in
+   * query and columns selected are subset of columns in materialized view
+   * Condition here is complex*/
+  @Test public void testFilterQueryOnFilterView7() {
+    checkMaterialize(
+            "select * from \"emps\" where "
+                + "((\"salary\" < 1111.9 and \"deptno\" > 10)"
+                + "or (\"empid\" > 400 and \"salary\" > 5000) "
+                + "or \"salary\" > 500)",
+            "select \"name\" from \"emps\" where (\"salary\" > 1000 "
+                + "or (\"deptno\" >= 30 and \"salary\" <= 500))");
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is stronger in
+   * query. However, columns selected are not present in columns of materialized view,
+   * hence should not use materialized view*/
+  @Test public void testFilterQueryOnFilterView8() {
+    checkNoMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where \"deptno\" > 10",
+            "select \"name\", \"empid\" from \"emps\" where \"deptno\" > 30",
+            JdbcTest.HR_MODEL);
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is weaker in
+   * query.*/
+  @Test public void testFilterQueryOnFilterView9() {
+    checkNoMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where \"deptno\" > 10",
+            "select \"name\", \"empid\" from \"emps\" "
+                + "where \"deptno\" > 30 or \"empid\" > 10",
+            JdbcTest.HR_MODEL);
+  }
+  /** As {@link #testFilterQueryOnFilterView()} but condition currently
+   * has unsupported type being checked on query.
+   */
+  @Test public void testFilterQueryOnFilterView10() {
+    checkNoMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where \"deptno\" > 10 "
+                    + "and \"name\" = \'calcite\'",
+            "select \"name\", \"empid\" from \"emps\" where \"deptno\" > 30 "
+                    + "or \"empid\" > 10",
+            JdbcTest.HR_MODEL);
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is weaker in
+   * query and columns selected are subset of columns in materialized view
+   * Condition here is complex*/
+  @Test public void testFilterQueryOnFilterView11() {
+    checkNoMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where "
+                    + "(\"salary\" < 1111.9 and \"deptno\" > 10)"
+                    + "or (\"empid\" > 400 and \"salary\" > 5000)",
+            "select \"name\" from \"emps\" where \"deptno\" > 30 and \"salary\" > 3000",
+            JdbcTest.HR_MODEL);
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition of
+   * query is stronger but is on the column not present in MV (salary).
+   */
+  @Test public void testFilterQueryOnFilterView12() {
+    checkNoMaterialize(
+            "select \"name\", \"deptno\" from \"emps\" where \"salary\" > 2000.5",
+            "select \"name\" from \"emps\" where \"deptno\" > 30 and \"salary\" > 3000",
+            JdbcTest.HR_MODEL);
+  }
+
+  /** As {@link #testFilterQueryOnFilterView()} but condition is weaker in
+   * query and columns selected are subset of columns in materialized view
+   * Condition here is complex*/
+  @Test public void testFilterQueryOnFilterView13() {
+    checkNoMaterialize(
+            "select * from \"emps\" where "
+                    + "(\"salary\" < 1111.9 and \"deptno\" > 10)"
+                    + "or (\"empid\" > 400 and \"salary\" > 5000)",
+            "select \"name\" from \"emps\" where \"salary\" > 1000 "
+                    + "or (\"deptno\" > 30 and \"salary\" > 3000)",
+            JdbcTest.HR_MODEL);
+  }
+
+  /** As {@link #testFilterQueryOnFilterView13()} but using alias
+   * and condition of query is stronger*/
+  @Test public void testAlias() {
+    checkMaterialize(
+            "select * from \"emps\" as em where "
+                    + "(em.\"salary\" < 1111.9 and em.\"deptno\" > 10)"
+                    + "or (em.\"empid\" > 400 and em.\"salary\" > 5000)",
+            "select \"name\" as n from \"emps\" as e where "
+                    + "(e.\"empid\" > 500 and e.\"salary\" > 6000)");
+  }
+
   /** Aggregation query at same level of aggregation as aggregation
    * materialization. */
   @Test public void testAggregate() {
@@ -241,11 +360,13 @@ public class MaterializationTest {
    * COUNT is rolled up using SUM. */
   @Test public void testAggregateRollUp() {
     checkMaterialize(
-        "select \"empid\", \"deptno\", count(*) as c, sum(\"empid\") as s from \"emps\" group by \"empid\", \"deptno\"",
+        "select \"empid\", \"deptno\", count(*) as c, sum(\"empid\") as s from \"emps\" "
+            + "group by \"empid\", \"deptno\"",
         "select count(*) + 1 as c, \"deptno\" from \"emps\" group by \"deptno\"",
         JdbcTest.HR_MODEL,
         CalciteAssert.checkResultContains(
-            "EnumerableCalc(expr#0..1=[{inputs}], expr#2=[1], expr#3=[+($t1, $t2)], C=[$t3], deptno=[$t0])\n"
+            "EnumerableCalc(expr#0..1=[{inputs}], expr#2=[1], "
+                + "expr#3=[+($t1, $t2)], C=[$t3], deptno=[$t0])\n"
                 + "  EnumerableAggregate(group=[{1}], agg#0=[$SUM0($2)])\n"
                 + "    EnumerableTableScan(table=[[hr, m0]])"));
   }
@@ -621,6 +742,13 @@ public class MaterializationTest {
         + "join \"depts\" using (\"deptno\")";
     checkNoMaterialize(q, q, JdbcTest.HR_MODEL);
   }
+
+  @Test public void testJoinMaterialization() {
+    String q = "select *\n"
+            + "from (select * from \"emps\" where \"empid\" < 300)\n"
+            + "join \"depts\" using (\"deptno\")";
+    checkMaterialize("select * from \"emps\" where \"empid\" < 500", q);
+  }
 }
 
 // End MaterializationTest.java

http://git-wip-us.apache.org/repos/asf/incubator-calcite/blob/4a9b1939/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java b/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
new file mode 100644
index 0000000..7e693b0
--- /dev/null
+++ b/core/src/test/java/org/apache/calcite/test/RexImplicationCheckerTest.java
@@ -0,0 +1,448 @@
+/*
+ * 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.test;
+
+import org.apache.calcite.DataContext;
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptSchema;
+import org.apache.calcite.plan.RexImplicationChecker;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.rel.type.RelDataTypeSystem;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexExecutorImpl;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.schema.Schemas;
+import org.apache.calcite.server.CalciteServerStatement;
+import org.apache.calcite.sql.SqlCollation;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.tools.Frameworks;
+import org.apache.calcite.util.NlsString;
+
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Test;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.math.BigDecimal;
+import java.sql.Date;
+import java.sql.Time;
+import java.sql.Timestamp;
+import java.util.Calendar;
+
+/**
+ * Tests the RexImplication checker
+ */
+public class RexImplicationCheckerTest {
+  //~ Instance fields --------------------------------------------------------
+
+  private RexBuilder rexBuilder = null;
+  private RexNode bl;
+  private RexNode i;
+  private RexNode dec;
+  private RexNode lg;
+  private RexNode sh;
+  private RexNode by;
+  private RexNode fl;
+  private RexNode dt;
+  private RexNode ch;
+  private RexNode ts;
+  private RexNode t;
+
+  private RelDataType boolRelDataType;
+  private RelDataType intRelDataType;
+  private RelDataType decRelDataType;
+  private RelDataType longRelDataType;
+  private RelDataType shortDataType;
+  private RelDataType byteDataType;
+  private RelDataType floatDataType;
+  private RelDataType charDataType;
+  private RelDataType dateDataType;
+  private RelDataType timeStampDataType;
+  private RelDataType timeDataType;
+  private RelDataTypeFactory typeFactory;
+  private RexImplicationChecker checker;
+  private RelDataType rowType;
+  private RexExecutorImpl executor;
+
+  //~ Methods ----------------------------------------------------------------
+
+  @Before
+  public void setUp() {
+    typeFactory = new JavaTypeFactoryImpl(RelDataTypeSystem.DEFAULT);
+    rexBuilder = new RexBuilder(typeFactory);
+    boolRelDataType = typeFactory.createJavaType(Boolean.class);
+    intRelDataType = typeFactory.createJavaType(Integer.class);
+    decRelDataType = typeFactory.createJavaType(Double.class);
+    longRelDataType = typeFactory.createJavaType(Long.class);
+    shortDataType = typeFactory.createJavaType(Short.class);
+    byteDataType = typeFactory.createJavaType(Byte.class);
+    floatDataType = typeFactory.createJavaType(Float.class);
+    charDataType = typeFactory.createJavaType(Character.class);
+    dateDataType = typeFactory.createJavaType(Date.class);
+    timeStampDataType = typeFactory.createJavaType(Timestamp.class);
+    timeDataType = typeFactory.createJavaType(Time.class);
+
+    bl = new RexInputRef(
+        0,
+        typeFactory.createTypeWithNullability(boolRelDataType, true));
+    i = new RexInputRef(
+        1,
+        typeFactory.createTypeWithNullability(intRelDataType, true));
+    dec = new RexInputRef(
+        2,
+        typeFactory.createTypeWithNullability(decRelDataType, true));
+    lg = new RexInputRef(
+        3,
+        typeFactory.createTypeWithNullability(longRelDataType, true));
+    sh = new RexInputRef(
+        4,
+        typeFactory.createTypeWithNullability(shortDataType, true));
+    by = new RexInputRef(
+        5,
+        typeFactory.createTypeWithNullability(byteDataType, true));
+    fl = new RexInputRef(
+        6,
+        typeFactory.createTypeWithNullability(floatDataType, true));
+    ch = new RexInputRef(
+        7,
+        typeFactory.createTypeWithNullability(charDataType, true));
+    dt = new RexInputRef(
+        8,
+        typeFactory.createTypeWithNullability(dateDataType, true));
+    ts = new RexInputRef(
+        9,
+        typeFactory.createTypeWithNullability(timeStampDataType, true));
+    t = new RexInputRef(
+        10,
+        typeFactory.createTypeWithNullability(timeDataType, true));
+
+    rowType =  typeFactory.builder()
+        .add("bool", boolRelDataType)
+        .add("int", intRelDataType)
+        .add("dec", decRelDataType)
+        .add("long", longRelDataType)
+        .add("short", shortDataType)
+        .add("byte", byteDataType)
+        .add("float", floatDataType)
+        .add("char", charDataType)
+        .add("date", dateDataType)
+        .add("timestamp", timeStampDataType)
+        .add("time", timeDataType)
+        .build();
+
+    Frameworks.withPrepare(
+        new Frameworks.PrepareAction<Void>() {
+          public Void apply(RelOptCluster cluster,
+                            RelOptSchema relOptSchema,
+                            SchemaPlus rootSchema,
+                            CalciteServerStatement statement) {
+            DataContext dataContext =
+                Schemas.createDataContext(statement.getConnection());
+            executor = new RexExecutorImpl(dataContext);
+            return null;
+          }
+        });
+
+    checker = new RexImplicationChecker(rexBuilder, executor, rowType);
+  }
+
+  private void checkImplies(RexNode node1, RexNode node2) {
+    assertTrue(node1.toString() + " doesnot imply " + node2.toString()
+        + " when it should.", checker.implies(node1, node2));
+  }
+
+  private void checkNotImplies(RexNode node1, RexNode node2) {
+    assertFalse(node1.toString() + " implies " + node2.toString()
+        + " when it should not", checker.implies(node1, node2));
+  }
+
+  // Simple Tests for Operators
+  @Test public void testSimpleGreaterCond() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node3 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node4 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    RexNode node5 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node6 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.NOT_EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    checkImplies(node2, node1);
+    checkNotImplies(node1, node2);
+    checkNotImplies(node1, node3);
+    checkImplies(node3, node1);
+    checkImplies(node5, node1);
+    checkNotImplies(node1, node5);
+    checkNotImplies(node1, node6);
+    checkNotImplies(node4, node6);
+    // TODO: Need to support Identity
+    //checkImplies(node1, node1);
+    //checkImplies(node3, node3);
+  }
+
+  @Test public void testSimpleLesserCond() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node3 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node4 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    RexNode node5 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    RexNode node6 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.NOT_EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+    checkImplies(node1, node3);
+    checkNotImplies(node3, node1);
+    checkImplies(node5, node2);
+    checkNotImplies(node2, node5);
+    checkNotImplies(node1, node5);
+    checkNotImplies(node1, node6);
+    checkNotImplies(node4, node6);
+    // TODO: Need to support Identity
+    //checkImplies(node1, node1);
+    //checkImplies(node3, node3);
+  }
+
+  @Test public void testSimpleEq() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(30)));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.NOT_EQUALS,
+            i,
+            rexBuilder.makeExactLiteral(new BigDecimal(10)));
+
+    //Check Identity
+    checkImplies(node1, node1);
+    //TODO: Support Identity
+    // checkImplies(node2, node2);
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+  }
+
+  // Simple Tests for DataTypes
+  @Test public void testSimpleDec() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN,
+            dec,
+            rexBuilder.makeApproxLiteral(new BigDecimal(30.9)));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN,
+            dec,
+            rexBuilder.makeApproxLiteral(new BigDecimal(40.33)));
+
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+  }
+
+  @Test public void testSimpleBoolean() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            bl,
+            rexBuilder.makeLiteral(true));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            bl,
+            rexBuilder.makeLiteral(false));
+
+    //TODO: Need to support false => true
+    //checkImplies(node2, node1);
+    checkNotImplies(node1, node2);
+  }
+
+  @Test public void testSimpleLong() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            lg,
+            rexBuilder.makeLiteral(new Long(324324L), longRelDataType, true));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN,
+            lg,
+            rexBuilder.makeLiteral(new Long(324325L), longRelDataType, true));
+
+    checkImplies(node2, node1);
+    checkNotImplies(node1, node2);
+  }
+
+  @Test public void testSimpleShort() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            sh,
+            rexBuilder.makeLiteral(new Short((short) 10), shortDataType, true));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            sh,
+            rexBuilder.makeLiteral(new Short((short) 11), shortDataType, true));
+
+    checkImplies(node2, node1);
+    checkNotImplies(node1, node2);
+  }
+
+  @Test public void testSimpleChar() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            ch,
+            rexBuilder.makeCharLiteral(new NlsString("b", null, SqlCollation.COERCIBLE)));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            ch,
+            rexBuilder.makeCharLiteral(new NlsString("a", null, SqlCollation.COERCIBLE)));
+
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+  }
+
+  @Test public void testSimpleDate() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.GREATER_THAN_OR_EQUAL,
+            dt,
+            rexBuilder.makeDateLiteral(Calendar.getInstance()));
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.EQUALS,
+            dt,
+            rexBuilder.makeDateLiteral(Calendar.getInstance()));
+
+    checkImplies(node2, node1);
+    checkNotImplies(node1, node2);
+  }
+
+  @Ignore("work in progress")
+  @Test public void testSimpleTimeStamp() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            ts,
+            rexBuilder.makeTimestampLiteral(Calendar.getInstance(),
+                timeStampDataType.getPrecision()));
+
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            ts,
+            rexBuilder.makeTimestampLiteral(Calendar.getInstance(),
+                timeStampDataType.getPrecision()));
+
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+  }
+
+  @Ignore("work in progress")
+  @Test public void testSimpleTime() {
+    RexNode node1 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            t,
+            rexBuilder.makeTimeLiteral(Calendar.getInstance(),
+                timeDataType.getPrecision()));
+
+
+    RexNode node2 =
+        rexBuilder.makeCall(
+            SqlStdOperatorTable.LESS_THAN_OR_EQUAL,
+            t,
+            rexBuilder.makeTimestampLiteral(Calendar.getInstance(),
+                timeDataType.getPrecision()));
+
+    checkImplies(node1, node2);
+    checkNotImplies(node2, node1);
+  }
+
+}


Mime
View raw message