calcite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jcama...@apache.org
Subject [07/11] calcite git commit: [CALCITE-1731] Materialized view rewriting for join and aggregate operators
Date Wed, 26 Apr 2017 19:18:41 GMT
[CALCITE-1731] Materialized view rewriting for join and aggregate operators

* Support for rewriting when view contains cardinality-preserving joins that are not present in the query

Close apache/calcite#414


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

Branch: refs/heads/master
Commit: 1f81e1353605fc2d16de9b4d56821736b0e82464
Parents: 84b49f5
Author: Jesus Camacho Rodriguez <jcamacho@apache.org>
Authored: Thu Apr 20 17:39:18 2017 +0100
Committer: Jesus Camacho Rodriguez <jcamacho@apache.org>
Committed: Wed Apr 26 20:02:10 2017 +0100

----------------------------------------------------------------------
 .../calcite/adapter/java/ReflectiveSchema.java  |  40 +-
 .../calcite/plan/RelOptAbstractTable.java       |   6 +
 .../org/apache/calcite/plan/RelOptTable.java    |   7 +
 .../calcite/prepare/CalcitePrepareImpl.java     |   2 +
 .../apache/calcite/prepare/RelOptTableImpl.java |   8 +
 .../calcite/rel/RelReferentialConstraint.java   |  46 ++
 .../rel/RelReferentialConstraintImpl.java       |  68 +++
 .../rel/metadata/RelMdExpressionLineage.java    |   6 +-
 .../rel/metadata/RelMdTableReferences.java      |   6 +-
 .../rel/rules/AbstractMaterializedViewRule.java | 500 ++++++++++++++-----
 .../apache/calcite/rex/RexTableInputRef.java    |  23 +-
 .../org/apache/calcite/schema/Statistic.java    |   5 +
 .../org/apache/calcite/schema/Statistics.java   |  33 +-
 .../java/org/apache/calcite/test/JdbcTest.java  |   2 +-
 .../calcite/test/MaterializationTest.java       | 322 ++++++++++--
 .../apache/calcite/test/MockCatalogReader.java  |  11 +
 .../apache/calcite/test/SqlToRelTestBase.java   |   9 +
 site/_docs/materialized_views.md                |   1 -
 18 files changed, 885 insertions(+), 210 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/adapter/java/ReflectiveSchema.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/adapter/java/ReflectiveSchema.java b/core/src/main/java/org/apache/calcite/adapter/java/ReflectiveSchema.java
index 91fe3e7..0a07f35 100644
--- a/core/src/main/java/org/apache/calcite/adapter/java/ReflectiveSchema.java
+++ b/core/src/main/java/org/apache/calcite/adapter/java/ReflectiveSchema.java
@@ -27,6 +27,7 @@ import org.apache.calcite.linq4j.tree.Expression;
 import org.apache.calcite.linq4j.tree.Expressions;
 import org.apache.calcite.linq4j.tree.Primitive;
 import org.apache.calcite.linq4j.tree.Types;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeFactory;
 import org.apache.calcite.schema.Function;
@@ -44,9 +45,12 @@ import org.apache.calcite.schema.impl.AbstractSchema;
 import org.apache.calcite.schema.impl.AbstractTableQueryable;
 import org.apache.calcite.schema.impl.ReflectiveFunctionBase;
 import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Util;
 
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Multimap;
 
 import java.lang.reflect.Constructor;
@@ -54,6 +58,7 @@ import java.lang.reflect.Field;
 import java.lang.reflect.InvocationTargetException;
 import java.lang.reflect.Method;
 import java.lang.reflect.Type;
+import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 
@@ -90,6 +95,7 @@ public class ReflectiveSchema
     return target;
   }
 
+  @SuppressWarnings({ "rawtypes", "unchecked" })
   @Override protected Map<String, Table> getTableMap() {
     final ImmutableMap.Builder<String, Table> builder = ImmutableMap.builder();
     for (Field field : clazz.getFields()) {
@@ -100,7 +106,28 @@ public class ReflectiveSchema
       }
       builder.put(fieldName, table);
     }
-    return builder.build();
+    Map<String, Table> tableMap = builder.build();
+    // Unique-Key - Foreign-Key
+    for (Field field : clazz.getFields()) {
+      if (RelReferentialConstraint.class.isAssignableFrom(field.getType())) {
+        RelReferentialConstraint rc;
+        try {
+          rc = (RelReferentialConstraint) field.get(target);
+        } catch (IllegalAccessException e) {
+          throw new RuntimeException(
+              "Error while accessing field " + field, e);
+        }
+        FieldTable table =
+            (FieldTable) tableMap.get(Util.last(rc.getSourceQualifiedName()));
+        assert table != null;
+        table.statistic = Statistics.of(
+            ImmutableList.copyOf(
+                Iterables.concat(
+                    table.getStatistic().getReferentialConstraints(),
+                    Collections.singleton(rc))));
+      }
+    }
+    return tableMap;
   }
 
   @Override protected Multimap<String, Function> getFunctionMultimap() {
@@ -319,16 +346,27 @@ public class ReflectiveSchema
   /** Table based on a Java field. */
   private static class FieldTable<T> extends ReflectiveTable {
     private final Field field;
+    private Statistic statistic;
 
     FieldTable(Field field, Type elementType, Enumerable<T> enumerable) {
+      this(field, elementType, enumerable, Statistics.UNKNOWN);
+    }
+
+    FieldTable(Field field, Type elementType, Enumerable<T> enumerable,
+        Statistic statistic) {
       super(elementType, enumerable);
       this.field = field;
+      this.statistic = statistic;
     }
 
     public String toString() {
       return "Relation {field=" + field.getName() + "}";
     }
 
+    @Override public Statistic getStatistic() {
+      return statistic;
+    }
+
     @Override public Expression getExpression(SchemaPlus schema,
         String tableName, Class clazz) {
       return Expressions.field(

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java b/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
index 187a542..d640aa8 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptAbstractTable.java
@@ -21,6 +21,7 @@ import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelDistribution;
 import org.apache.calcite.rel.RelDistributions;
 import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.rel.logical.LogicalTableScan;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelDataTypeField;
@@ -94,6 +95,11 @@ public abstract class RelOptAbstractTable implements RelOptTable {
     return false;
   }
 
+  // Override to define foreign keys
+  public List<RelReferentialConstraint> getReferentialConstraints() {
+    return Collections.emptyList();
+  }
+
   public RelNode toRel(ToRelContext context) {
     return LogicalTableScan.create(context.getCluster(), this);
   }

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptTable.java b/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
index 9529a5a..668dc1c 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptTable.java
@@ -20,6 +20,7 @@ import org.apache.calcite.linq4j.tree.Expression;
 import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelDistribution;
 import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.rel.RelRoot;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
 import org.apache.calcite.rel.type.RelDataType;
@@ -98,6 +99,12 @@ public interface RelOptTable extends Wrapper {
   boolean isKey(ImmutableBitSet columns);
 
   /**
+   * Returns the referential constraints existing for this table. These constraints
+   * are represented over other tables using {@link RelReferentialConstraint} nodes.
+   */
+  List<RelReferentialConstraint> getReferentialConstraints();
+
+  /**
    * Generates code for this table.
    *
    * @param clazz The desired collection class; for example {@code Queryable}.

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java b/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java
index e0ae012..a5059ae 100644
--- a/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java
+++ b/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java
@@ -534,6 +534,8 @@ public class CalcitePrepareImpl implements CalcitePrepare {
     }
     if (prepareContext.config().materializationsEnabled()) {
       planner.addRule(MaterializedViewFilterScanRule.INSTANCE);
+      planner.addRule(AbstractMaterializedViewRule.INSTANCE_PROJECT_FILTER);
+      planner.addRule(AbstractMaterializedViewRule.INSTANCE_FILTER);
       planner.addRule(AbstractMaterializedViewRule.INSTANCE_PROJECT_JOIN);
       planner.addRule(AbstractMaterializedViewRule.INSTANCE_JOIN);
       planner.addRule(AbstractMaterializedViewRule.INSTANCE_PROJECT_AGGREGATE);

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java b/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
index ccc25d8..2cc8492 100644
--- a/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
+++ b/core/src/main/java/org/apache/calcite/prepare/RelOptTableImpl.java
@@ -28,6 +28,7 @@ import org.apache.calcite.rel.RelDistribution;
 import org.apache.calcite.rel.RelDistributionTraitDef;
 import org.apache.calcite.rel.RelFieldCollation;
 import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.rel.logical.LogicalTableScan;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.rel.type.RelRecordType;
@@ -284,6 +285,13 @@ public class RelOptTableImpl extends Prepare.AbstractPreparingTable {
     return false;
   }
 
+  public List<RelReferentialConstraint> getReferentialConstraints() {
+    if (table != null) {
+      return table.getStatistic().getReferentialConstraints();
+    }
+    return ImmutableList.of();
+  }
+
   public RelDataType getRowType() {
     return rowType;
   }

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraint.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraint.java b/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraint.java
new file mode 100644
index 0000000..00b8f8f
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraint.java
@@ -0,0 +1,46 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel;
+
+import org.apache.calcite.util.mapping.IntPair;
+
+import java.util.List;
+
+/**
+ * Interface for a referential constraint, i.e., Foreign-Key - Unique-Key relationship,
+ * between two tables.
+ */
+public interface RelReferentialConstraint {
+  //~ Methods ----------------------------------------------------------------
+
+  /**
+   * Returns the number of columns in the keys.
+   */
+  int getNumColumns();
+
+  /**The qualified name of the referencing table, e.g. DEPT. */
+  List<String> getSourceQualifiedName();
+
+  /** The qualified name of the referenced table, e.g. EMP. */
+  List<String> getTargetQualifiedName();
+
+  /** The (source, target) column ordinals. */
+  List<IntPair> getColumnPairs();
+
+}
+
+// End RelReferentialConstraint.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraintImpl.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraintImpl.java b/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraintImpl.java
new file mode 100644
index 0000000..91dbd32
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/rel/RelReferentialConstraintImpl.java
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel;
+
+import org.apache.calcite.util.mapping.IntPair;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.List;
+
+/** RelOptReferentialConstraint base implementation. */
+public class RelReferentialConstraintImpl implements RelReferentialConstraint {
+
+  private final List<String> sourceQualifiedName;
+  private final List<String> targetQualifiedName;
+  private final List<IntPair> columnPairs;
+
+  private RelReferentialConstraintImpl(List<String> sourceQualifiedName,
+      List<String> targetQualifiedName, List<IntPair> columnPairs) {
+    this.sourceQualifiedName = ImmutableList.copyOf(sourceQualifiedName);
+    this.targetQualifiedName = ImmutableList.copyOf(targetQualifiedName);
+    this.columnPairs = ImmutableList.copyOf(columnPairs);
+  }
+
+  @Override public List<String> getSourceQualifiedName() {
+    return sourceQualifiedName;
+  }
+
+  @Override public List<String> getTargetQualifiedName() {
+    return targetQualifiedName;
+  }
+
+  @Override public List<IntPair> getColumnPairs() {
+    return columnPairs;
+  }
+
+  @Override public int getNumColumns() {
+    return columnPairs.size();
+  }
+
+  public static RelReferentialConstraintImpl of(List<String> sourceQualifiedName,
+      List<String> targetQualifiedName, List<IntPair> columnPairs) {
+    return new RelReferentialConstraintImpl(
+        sourceQualifiedName, targetQualifiedName, columnPairs);
+  }
+
+  @Override public String toString() {
+    return "{ " + sourceQualifiedName + ", " + targetQualifiedName + ", "
+        + columnPairs + " }";
+  }
+
+}
+
+// End RelReferentialConstraintImpl.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java
index 6ac5cfb..87c752d 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java
@@ -123,7 +123,7 @@ public class RelMdExpressionLineage
     final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>();
     for (int idx : inputFieldsUsed) {
       final RexNode inputRef = RexTableInputRef.of(
-          RelTableRef.of(rel.getTable().getQualifiedName(), 0),
+          RelTableRef.of(rel.getTable(), 0),
           RexInputRef.of(idx, rel.getRowType().getFieldList()));
       final Set<RexNode> originalExprs = Sets.newHashSet(inputRef);
       final RexInputRef ref = RexInputRef.of(idx, rel.getRowType().getFieldList());
@@ -233,7 +233,7 @@ public class RelMdExpressionLineage
             shift = lRefs.size();
           }
           currentTablesMapping.put(rightRef,
-              RelTableRef.of(rightRef.getQualifiedName(), shift + rightRef.getEntityNumber()));
+              RelTableRef.of(rightRef.getTable(), shift + rightRef.getEntityNumber()));
         }
         final Set<RexNode> updatedExprs = Sets.newHashSet(
             Iterables.transform(
@@ -288,7 +288,7 @@ public class RelMdExpressionLineage
             shift = lRefs.size();
           }
           currentTablesMapping.put(tableRef,
-              RelTableRef.of(tableRef.getQualifiedName(), shift + tableRef.getEntityNumber()));
+              RelTableRef.of(tableRef.getTable(), shift + tableRef.getEntityNumber()));
         }
         final Set<RexNode> updatedExprs = Sets.newHashSet(
             Iterables.transform(

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java
index 358c872..b12b425 100644
--- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java
+++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java
@@ -88,7 +88,7 @@ public class RelMdTableReferences
    * TableScan table reference.
    */
   public Set<RelTableRef> getTableReferences(TableScan rel, RelMetadataQuery mq) {
-    return Sets.newHashSet(RelTableRef.of(rel.getTable().getQualifiedName(), 0));
+    return Sets.newHashSet(RelTableRef.of(rel.getTable(), 0));
   }
 
   /**
@@ -123,7 +123,7 @@ public class RelMdTableReferences
         shift = lRefs.size();
       }
       RelTableRef shiftTableRef = RelTableRef.of(
-          rightRef.getQualifiedName(), shift + rightRef.getEntityNumber());
+          rightRef.getTable(), shift + rightRef.getEntityNumber());
       assert !result.contains(shiftTableRef);
       result.add(shiftTableRef);
     }
@@ -152,7 +152,7 @@ public class RelMdTableReferences
           shift = lRefs.size();
         }
         RelTableRef shiftTableRef = RelTableRef.of(
-            tableRef.getQualifiedName(), shift + tableRef.getEntityNumber());
+            tableRef.getTable(), shift + tableRef.getEntityNumber());
         assert !result.contains(shiftTableRef);
         result.add(shiftTableRef);
         currentTablesMapping.put(tableRef, shiftTableRef);

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java b/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java
index fdc3774..071d9af 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/AbstractMaterializedViewRule.java
@@ -23,20 +23,20 @@ import org.apache.calcite.plan.RelOptPredicateList;
 import org.apache.calcite.plan.RelOptRule;
 import org.apache.calcite.plan.RelOptRuleCall;
 import org.apache.calcite.plan.RelOptRuleOperand;
-import org.apache.calcite.plan.RelOptTable;
 import org.apache.calcite.plan.RelOptUtil;
 import org.apache.calcite.plan.SubstitutionVisitor;
 import org.apache.calcite.plan.volcano.VolcanoPlanner;
 import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.rel.core.Aggregate;
 import org.apache.calcite.rel.core.AggregateCall;
 import org.apache.calcite.rel.core.Filter;
 import org.apache.calcite.rel.core.Join;
-import org.apache.calcite.rel.core.JoinRelType;
 import org.apache.calcite.rel.core.Project;
 import org.apache.calcite.rel.core.RelFactories;
 import org.apache.calcite.rel.core.TableScan;
 import org.apache.calcite.rel.metadata.RelMetadataQuery;
+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;
@@ -54,25 +54,31 @@ import org.apache.calcite.tools.RelBuilder.AggCall;
 import org.apache.calcite.tools.RelBuilderFactory;
 import org.apache.calcite.util.ImmutableBitSet;
 import org.apache.calcite.util.Util;
+import org.apache.calcite.util.graph.DefaultDirectedGraph;
+import org.apache.calcite.util.graph.DefaultEdge;
+import org.apache.calcite.util.graph.DirectedGraph;
 import org.apache.calcite.util.mapping.IntPair;
 import org.apache.calcite.util.mapping.Mapping;
 import org.apache.calcite.util.mapping.MappingType;
 import org.apache.calcite.util.mapping.Mappings;
 import org.apache.calcite.util.trace.CalciteLogger;
 
+import org.apache.commons.lang3.tuple.ImmutableTriple;
+import org.apache.commons.lang3.tuple.Triple;
+
 import com.google.common.collect.ArrayListMultimap;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableMultiset;
 import com.google.common.collect.Multimap;
-import com.google.common.collect.Multiset;
+import com.google.common.collect.Sets;
 
 import org.slf4j.LoggerFactory;
 
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashSet;
@@ -92,6 +98,12 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
   private static final CalciteLogger LOGGER =
       new CalciteLogger(LoggerFactory.getLogger(AbstractMaterializedViewRule.class));
 
+  public static final MaterializedViewProjectFilterRule INSTANCE_PROJECT_FILTER =
+      new MaterializedViewProjectFilterRule(RelFactories.LOGICAL_BUILDER);
+
+  public static final MaterializedViewOnlyFilterRule INSTANCE_FILTER =
+      new MaterializedViewOnlyFilterRule(RelFactories.LOGICAL_BUILDER);
+
   public static final MaterializedViewProjectJoinRule INSTANCE_PROJECT_JOIN =
       new MaterializedViewProjectJoinRule(RelFactories.LOGICAL_BUILDER);
 
@@ -116,33 +128,36 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
    * Rewriting logic is based on "Optimizing Queries Using Materialized Views:
    * A Practical, Scalable Solution" by Goldstein and Larson.
    *
-   * On the query side, rules matches a Project-node chain or node, where node
+   * <p>On the query side, rules matches a Project-node chain or node, where node
    * is either an Aggregate or a Join. Subplan rooted at the node operator must
    * be composed of one or more of the following operators: TableScan, Project,
    * Filter, and Join.
    *
-   * For each join MV, we need to check the following:
-   * 1) The plan rooted at the Join operator in the view produces all rows
-   * needed by the plan rooted at the Join operator in the query.
-   * 2) All columns required by compensating predicates, i.e., predicates that
-   * need to be enforced over the view, are available at the view output.
-   * 3) All output expressions can be computed from the output of the view.
-   * 4) All output rows occur with the correct duplication factor.
-   * TODO: Currently we only allow the same tables in the view and the query,
-   * thus we are sure condition 4 is met. This restriction will be lifted in
-   * the future.
+   * <p>For each join MV, we need to check the following:
+   * <ol>
+   * <li> The plan rooted at the Join operator in the view produces all rows
+   * needed by the plan rooted at the Join operator in the query.</li>
+   * <li> All columns required by compensating predicates, i.e., predicates that
+   * need to be enforced over the view, are available at the view output.</li>
+   * <li> All output expressions can be computed from the output of the view.</li>
+   * <li> All output rows occur with the correct duplication factor. We might
+   * rely on existing Unique-Key - Foreign-Key relationships to extract that
+   * information.</li>
+   * </ol>
    *
-   * In turn, for each aggregate MV, we need to check the following:
-   * 1) The plan rooted at the Aggregate operator in the view produces all rows
-   * needed by the plan rooted at the Aggregate operator in the query.
-   * 2) All columns required by compensating predicates, i.e., predicates that
-   * need to be enforced over the view, are available at the view output.
-   * 3) The grouping columns in the query are a subset of the grouping columns
-   * in the view.
-   * 4) All columns required to perform further grouping are available in the
-   * view output.
-   * 5) All columns required to compute output expressions are available in the
-   * view output.
+   * <p>In turn, for each aggregate MV, we need to check the following:
+   * <ol>
+   * <li> The plan rooted at the Aggregate operator in the view produces all rows
+   * needed by the plan rooted at the Aggregate operator in the query.</li>
+   * <li> All columns required by compensating predicates, i.e., predicates that
+   * need to be enforced over the view, are available at the view output.</li>
+   * <li> The grouping columns in the query are a subset of the grouping columns
+   * in the view.</li>
+   * <li> All columns required to perform further grouping are available in the
+   * view output.</li>
+   * <li> All columns required to compute output expressions are available in the
+   * view output.</li>
+   * </ol>
    */
   protected void perform(RelOptRuleCall call, Project topProject, RelNode node) {
     final RexBuilder rexBuilder = node.getCluster().getRexBuilder();
@@ -174,9 +189,6 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
       if (!applicableMaterializations.isEmpty()) {
         // 2. Initialize all query related auxiliary data structures
         // that will be used throughout query rewriting process
-        final Multiset<RelOptTable> qTableBag = ImmutableMultiset.copyOf(
-            RelOptUtil.findAllTables(node));
-
         // Generate query table references
         final Set<RelTableRef> queryTableRefs = mq.getTableReferences(node);
         if (queryTableRefs == null) {
@@ -191,13 +203,16 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
           // Bail out
           return;
         }
-        final RexNode[] queryPreds = splitPredicates(
-            rexBuilder, queryPredicateList.pulledUpPredicates);
+        final RexNode pred = simplify.simplify(
+            RexUtil.composeConjunction(
+                rexBuilder, queryPredicateList.pulledUpPredicates, false));
+        final Triple<RexNode, RexNode, RexNode> queryPreds =
+            splitPredicates(rexBuilder, pred);
 
         // Extract query equivalence classes. An equivalence class is a set
         // of columns in the query output that are known to be equal.
         final EquivalenceClasses qEC = new EquivalenceClasses();
-        for (RexNode conj : RelOptUtil.conjunctions(queryPreds[0])) {
+        for (RexNode conj : RelOptUtil.conjunctions(queryPreds.getLeft())) {
           assert conj.isA(SqlKind.EQUALS);
           RexCall equiCond = (RexCall) conj;
           qEC.addEquivalenceClass(
@@ -210,11 +225,6 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
         for (RelOptMaterialization materialization : applicableMaterializations) {
           final Project topViewProject;
           final RelNode viewNode;
-          // 3.1. Check whether it is a valid view
-          if (!isViewMatching(materialization.queryRel)) {
-            // Skip it
-            continue;
-          }
           if (materialization.queryRel instanceof Project) {
             topViewProject = (Project) materialization.queryRel;
             viewNode = topViewProject.getInput();
@@ -223,24 +233,14 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             viewNode = materialization.queryRel;
           }
 
-          // 3.2. View checks before proceeding
+          // 3.1. View checks before proceeding
           if (!isValidPlan(topViewProject, viewNode, mq)) {
             // Skip it
             continue;
           }
 
-          // 3.3. Initialize all query related auxiliary data structures
+          // 3.2. Initialize all query related auxiliary data structures
           // that will be used throughout query rewriting process
-          // Extract view tables
-          Multiset<RelOptTable> vTableBag = ImmutableMultiset.copyOf(
-              RelOptUtil.findAllTables(viewNode));
-          if (!qTableBag.equals(vTableBag)) {
-            // Currently we only support rewriting with views that use
-            // the same set of tables than the query, thus we skip it
-            // TODO: Extend to lift this restriction
-            continue;
-          }
-
           // Extract view predicates
           final RelOptPredicateList viewPredicateList =
               mq.getAllPredicates(viewNode);
@@ -248,8 +248,11 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             // Skip it
             continue;
           }
-          final RexNode[] viewPreds = splitPredicates(
-              rexBuilder, viewPredicateList.pulledUpPredicates);
+          final RexNode viewPred = simplify.simplify(
+              RexUtil.composeConjunction(
+                  rexBuilder, viewPredicateList.pulledUpPredicates, false));
+          final Triple<RexNode, RexNode, RexNode> viewPreds =
+              splitPredicates(rexBuilder, viewPred);
 
           // Extract view table references
           final Set<RelTableRef> viewTableRefs = mq.getTableReferences(viewNode);
@@ -258,6 +261,43 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             return;
           }
 
+          // Extract view tables
+          MatchModality matchModality;
+          Multimap<RexTableInputRef, RexTableInputRef> compensationEquiColumns =
+              ArrayListMultimap.create();
+          if (!queryTableRefs.equals(viewTableRefs)) {
+            // We try to compensate, e.g., for join queries it might be
+            // possible to join missing tables with view to compute result.
+            // Two supported cases: query tables are subset of view tables (we need to
+            // check whether they are cardinality-preserving joins), or view tables are
+            // subset of query tables (add additional tables through joins if possible)
+            if (viewTableRefs.containsAll(queryTableRefs)) {
+              matchModality = MatchModality.QUERY_PARTIAL;
+              final EquivalenceClasses vEC = new EquivalenceClasses();
+              for (RexNode conj : RelOptUtil.conjunctions(viewPreds.getLeft())) {
+                assert conj.isA(SqlKind.EQUALS);
+                RexCall equiCond = (RexCall) conj;
+                vEC.addEquivalenceClass(
+                    (RexTableInputRef) equiCond.getOperands().get(0),
+                    (RexTableInputRef) equiCond.getOperands().get(1));
+              }
+              if (!compensateQueryPartial(compensationEquiColumns,
+                  viewTableRefs, vEC, queryTableRefs)) {
+                // Cannot rewrite, skip it
+                continue;
+              }
+            } else if (queryTableRefs.containsAll(viewTableRefs)) {
+              // TODO: implement latest case
+              matchModality = MatchModality.VIEW_PARTIAL;
+              continue;
+            } else {
+              // Skip it
+              continue;
+            }
+          } else {
+            matchModality = MatchModality.COMPLETE;
+          }
+
           // 4. We map every table in the query to a view table with the same qualified
           // name.
           final Multimap<RelTableRef, RelTableRef> multiMapTables = ArrayListMultimap.create();
@@ -279,6 +319,23 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
           final List<BiMap<RelTableRef, RelTableRef>> flatListMappings =
               generateTableMappings(multiMapTables);
           for (BiMap<RelTableRef, RelTableRef> tableMapping : flatListMappings) {
+            // 4.0. If compensation equivalence classes exist, we need to add
+            // the mapping to the query mapping
+            final EquivalenceClasses currQEC = EquivalenceClasses.copy(qEC);
+            if (matchModality == MatchModality.QUERY_PARTIAL) {
+              for (Entry<RexTableInputRef, RexTableInputRef> e
+                  : compensationEquiColumns.entries()) {
+                // Copy origin
+                RelTableRef queryTableRef = tableMapping.inverse().get(e.getKey().getTableRef());
+                RexTableInputRef queryColumnRef = RexTableInputRef.of(queryTableRef,
+                    e.getKey().getIndex(), e.getKey().getType());
+                // Add to query equivalence classes and table mapping
+                currQEC.addEquivalenceClass(queryColumnRef, e.getValue());
+                tableMapping.put(
+                    e.getValue().getTableRef(), e.getValue().getTableRef()); //identity
+              }
+            }
+
             final RexNode compensationColumnsEquiPred;
             final RexNode compensationRangePred;
             final RexNode compensationResidualPred;
@@ -291,17 +348,17 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             // view predicates and check that every view equivalence class is a subset of a
             // query equivalence class: if it is not, we bail out.
             final RexNode viewColumnsEquiPred = RexUtil.swapTableReferences(
-                rexBuilder, viewPreds[0], tableMapping.inverse());
-            final EquivalenceClasses vEC = new EquivalenceClasses();
+                rexBuilder, viewPreds.getLeft(), tableMapping.inverse());
+            final EquivalenceClasses queryBasedVEC = new EquivalenceClasses();
             for (RexNode conj : RelOptUtil.conjunctions(viewColumnsEquiPred)) {
               assert conj.isA(SqlKind.EQUALS);
               RexCall equiCond = (RexCall) conj;
-              vEC.addEquivalenceClass(
+              queryBasedVEC.addEquivalenceClass(
                   (RexTableInputRef) equiCond.getOperands().get(0),
                   (RexTableInputRef) equiCond.getOperands().get(1));
             }
             compensationColumnsEquiPred = generateEquivalenceClasses(
-                rexBuilder, queryPreds[0], qEC, viewColumnsEquiPred, vEC);
+                rexBuilder, currQEC, queryBasedVEC);
             if (compensationColumnsEquiPred == null) {
               // Skip it
               continue;
@@ -310,9 +367,10 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             // 4.2. We check that range intervals for the query are contained in the view.
             // Compute compensating predicates.
             final RexNode queryRangePred = RexUtil.swapColumnReferences(
-                rexBuilder, queryPreds[1], qEC.getEquivalenceClassesMap());
+                rexBuilder, queryPreds.getMiddle(), currQEC.getEquivalenceClassesMap());
             final RexNode viewRangePred = RexUtil.swapTableColumnReferences(
-                rexBuilder, viewPreds[1], tableMapping.inverse(), qEC.getEquivalenceClassesMap());
+                rexBuilder, viewPreds.getMiddle(), tableMapping.inverse(),
+                currQEC.getEquivalenceClassesMap());
             compensationRangePred = SubstitutionVisitor.splitFilter(
                 simplify, queryRangePred, viewRangePred);
             if (compensationRangePred == null) {
@@ -324,9 +382,10 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             // within the view.
             // Compute compensating predicates.
             final RexNode queryResidualPred = RexUtil.swapColumnReferences(
-                rexBuilder, queryPreds[2], qEC.getEquivalenceClassesMap());
+                rexBuilder, queryPreds.getRight(), currQEC.getEquivalenceClassesMap());
             final RexNode viewResidualPred = RexUtil.swapTableColumnReferences(
-                rexBuilder, viewPreds[2], tableMapping.inverse(), qEC.getEquivalenceClassesMap());
+                rexBuilder, viewPreds.getRight(), tableMapping.inverse(),
+                currQEC.getEquivalenceClassesMap());
             compensationResidualPred = SubstitutionVisitor.splitFilter(
                 simplify, queryResidualPred, viewResidualPred);
             if (compensationResidualPred == null) {
@@ -348,7 +407,7 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
               List<RexNode> viewExprs = extractExpressions(topViewProject, viewNode,
                   rexBuilder);
               compensationPred = rewriteExpression(rexBuilder, viewNode, viewExprs,
-                  compensationPred, tableMapping, qEC.getEquivalenceClassesMap(), mq);
+                  compensationPred, tableMapping, currQEC.getEquivalenceClassesMap(), mq);
               if (compensationPred == null) {
                 // Skip it
                 continue;
@@ -367,7 +426,7 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             }
             RelNode result = unify(rexBuilder, builder, builder.build(),
                 topProject, node, topViewProject, viewNode, tableMapping,
-                qEC.getEquivalenceClassesMap(), mq);
+                currQEC.getEquivalenceClassesMap(), mq);
             if (result == null) {
               // Skip it
               continue;
@@ -382,16 +441,16 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
   protected abstract boolean isValidPlan(Project topProject, RelNode node,
       RelMetadataQuery mq);
 
-  protected abstract boolean isViewMatching(RelNode node);
-
   protected abstract List<RexNode> extractExpressions(Project topProject,
       RelNode node, RexBuilder rexBuilder);
 
-  /* This method is responsible for rewriting the query using the given view query.
+  /**
+   * This method is responsible for rewriting the query using the given view query.
    *
-   * The input node is a Scan on the view table and possibly a compensation Filter
+   * <p>The input node is a Scan on the view table and possibly a compensation Filter
    * on top. If a rewriting can be produced, we return that rewriting. If it cannot
-   * be produced, we will return null. */
+   * be produced, we will return null.
+   */
   protected abstract RelNode unify(RexBuilder rexBuilder, RelBuilder relBuilder,
       RelNode input, Project topProject, RelNode node,
       Project topViewProject, RelNode viewNode,
@@ -412,35 +471,19 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
 
     @Override protected boolean isValidPlan(Project topProject, RelNode node,
         RelMetadataQuery mq) {
-      Join join = (Join) node;
-      if (join.getJoinType() != JoinRelType.INNER) {
-        // TODO: Rewriting for non-inner joins not supported yet
-        return false;
-      }
-      return isValidRexNodePlan(join, mq);
-    }
-
-    @Override protected boolean isViewMatching(RelNode node) {
-      if (node instanceof Join) {
-        return true;
-      }
-      if (node instanceof Project && ((Project) node).getInput() instanceof Join) {
-        return true;
-      }
-      return false;
+      return isValidRexNodePlan(node, mq);
     }
 
     @Override protected List<RexNode> extractExpressions(Project topProject,
         RelNode node, RexBuilder rexBuilder) {
-      Join viewJoin = (Join) node;
       List<RexNode> viewExprs = new ArrayList<>();
       if (topProject != null) {
         for (RexNode e : topProject.getChildExps()) {
           viewExprs.add(e);
         }
       } else {
-        for (int i = 0; i < viewJoin.getRowType().getFieldCount(); i++) {
-          viewExprs.add(rexBuilder.makeInputRef(viewJoin, i));
+        for (int i = 0; i < node.getRowType().getFieldCount(); i++) {
+          viewExprs.add(rexBuilder.makeInputRef(node, i));
         }
       }
       return viewExprs;
@@ -498,6 +541,23 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     }
   }
 
+  /** Rule that matches Project on Filter. */
+  public static class MaterializedViewProjectFilterRule extends MaterializedViewJoinRule {
+    public MaterializedViewProjectFilterRule(RelBuilderFactory relBuilderFactory) {
+      super(
+          operand(Project.class,
+              operand(Filter.class, any())),
+          relBuilderFactory,
+          "MaterializedViewJoinRule(Project-Filter)");
+    }
+
+    @Override public void onMatch(RelOptRuleCall call) {
+      final Project project = call.rel(0);
+      final Filter filter = call.rel(1);
+      perform(call, project, filter);
+    }
+  }
+
   /** Rule that matches Join. */
   public static class MaterializedViewOnlyJoinRule extends MaterializedViewJoinRule {
     public MaterializedViewOnlyJoinRule(RelBuilderFactory relBuilderFactory) {
@@ -513,6 +573,21 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     }
   }
 
+  /** Rule that matches Filter. */
+  public static class MaterializedViewOnlyFilterRule extends MaterializedViewJoinRule {
+    public MaterializedViewOnlyFilterRule(RelBuilderFactory relBuilderFactory) {
+      super(
+          operand(Filter.class, any()),
+          relBuilderFactory,
+          "MaterializedViewJoinRule(Filter)");
+    }
+
+    @Override public void onMatch(RelOptRuleCall call) {
+      final Filter filter = call.rel(0);
+      perform(call, null, filter);
+    }
+  }
+
   //~ Instances Aggregate ----------------------------------------------------
 
   /** Materialized view rewriting for aggregate */
@@ -526,6 +601,9 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
 
     @Override protected boolean isValidPlan(Project topProject, RelNode node,
         RelMetadataQuery mq) {
+      if (!(node instanceof Aggregate)) {
+        return false;
+      }
       Aggregate aggregate = (Aggregate) node;
       if (aggregate.getGroupType() != Aggregate.Group.SIMPLE) {
         // TODO: Rewriting with grouping sets not supported yet
@@ -534,16 +612,6 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
       return isValidRexNodePlan(aggregate.getInput(), mq);
     }
 
-    @Override protected boolean isViewMatching(RelNode node) {
-      if (node instanceof Aggregate) {
-        return true;
-      }
-      if (node instanceof Project && ((Project) node).getInput() instanceof Aggregate) {
-        return true;
-      }
-      return false;
-    }
-
     @Override protected List<RexNode> extractExpressions(Project topProject,
         RelNode node, RexBuilder rexBuilder) {
       Aggregate viewAggregate = (Aggregate) node;
@@ -638,7 +706,10 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
           continue;
         }
         AggregateCall queryAggCall = queryAggregate.getAggCallList().get(idx);
-        List<Integer> queryAggCallIndexes = queryAggCall.getArgList();
+        List<Integer> queryAggCallIndexes = new ArrayList<>();
+        for (int aggCallIdx : queryAggCall.getArgList()) {
+          queryAggCallIndexes.add(m.get(aggCallIdx).iterator().next());
+        }
         for (int j = 0; j < viewAggregate.getAggCallList().size(); j++) {
           AggregateCall viewAggCall = viewAggregate.getAggCallList().get(j);
           if (queryAggCall.getAggregation() != viewAggCall.getAggregation()
@@ -648,11 +719,7 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
             // Continue
             continue;
           }
-          List<Integer> viewAggCallIndexes = new ArrayList<>();
-          for (int aggCallIdx : viewAggCall.getArgList()) {
-            viewAggCallIndexes.add(m.get(aggCallIdx).iterator().next());
-          }
-          if (!queryAggCallIndexes.equals(viewAggCallIndexes)) {
+          if (!queryAggCallIndexes.equals(viewAggCall.getArgList())) {
             // Continue
             continue;
           }
@@ -864,9 +931,11 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
 
   //~ Methods ----------------------------------------------------------------
 
-  /* It will flatten a multimap containing table references to table references,
+  /**
+   * It will flatten a multimap containing table references to table references,
    * producing all possible combinations of mappings. Each of the mappings will
-   * be bi-directional. */
+   * be bi-directional.
+   */
   private static List<BiMap<RelTableRef, RelTableRef>> generateTableMappings(
       Multimap<RelTableRef, RelTableRef> multiMapTables) {
     final List<BiMap<RelTableRef, RelTableRef>> result = new ArrayList<>();
@@ -897,7 +966,7 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return result;
   }
 
-  /* Currently we only support TableScan - Project - Filter - Join */
+  /** Currently we only support TableScan - Project - Filter - Join */
   private static boolean isValidRexNodePlan(RelNode node, RelMetadataQuery mq) {
     final Multimap<Class<? extends RelNode>, RelNode> m =
             mq.getNodeTypes(node);
@@ -913,22 +982,26 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return true;
   }
 
-  /* Classifies each of the predicates in the list into one of these three
+  /**
+   * Classifies each of the predicates in the list into one of these three
    * categories:
-   * - column equality predicates, or
-   * - range predicates, comprising <, <=, >, >=, and = between a reference
-   * and a constant, or
-   * - residual predicates, all the rest
+   * <ul>
+   * <li> 1-l) column equality predicates, or </li>
+   * <li> 2-m) range predicates, comprising <, <=, >, >=, and = between a reference
+   * and a constant, or </li>
+   * <li> 3-r) residual predicates, all the rest</li>
+   * </ul>
    *
-   * For each category, it creates the conjunction of the predicates. The
+   * <p>For each category, it creates the conjunction of the predicates. The
    * result is an array of three RexNode objects corresponding to each
-   * category. */
-  private static RexNode[] splitPredicates(
-      RexBuilder rexBuilder, ImmutableList<RexNode> predicates) {
+   * category.
+   */
+  private static Triple<RexNode, RexNode, RexNode> splitPredicates(
+      RexBuilder rexBuilder, RexNode pred) {
     List<RexNode> equiColumnsPreds = new ArrayList<>();
     List<RexNode> rangePreds = new ArrayList<>();
     List<RexNode> residualPreds = new ArrayList<>();
-    for (RexNode e : predicates) {
+    for (RexNode e : RelOptUtil.conjunctions(pred)) {
       switch (e.getKind()) {
       case EQUALS:
         RexCall eqCall = (RexCall) e;
@@ -963,33 +1036,144 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
         residualPreds.add(e);
       }
     }
-    return new RexNode[] {
+    return ImmutableTriple.<RexNode, RexNode, RexNode>of(
         RexUtil.composeConjunction(rexBuilder, equiColumnsPreds, false),
         RexUtil.composeConjunction(rexBuilder, rangePreds, false),
-        RexUtil.composeConjunction(rexBuilder, residualPreds, false)};
+        RexUtil.composeConjunction(rexBuilder, residualPreds, false));
+  }
+
+  /**
+   * It checks whether the query can be rewritten using the view even though the
+   * view uses additional tables. In order to do that, we need to double-check
+   * that every join that exists in the view and is not in the query is a
+   * cardinality-preserving join, i.e., it only appends columns to the row
+   * without changing its multiplicity. Thus, the join needs to be:
+   * <ul>
+   * <li> Equi-join </li>
+   * <li> Between all columns in the keys </li>
+   * <li> Foreign-key columns do not allow NULL values </li>
+   * <li> Foreign-key </li>
+   * <li> Unique-key </li>
+   * </ul>
+   *
+   * <p>If it can be rewritten, it returns true and it inserts the missing equi-join
+   * predicates in the input compensationEquiColumns multimap. Otherwise, it returns
+   * false.
+   */
+  private static boolean compensateQueryPartial(
+      Multimap<RexTableInputRef, RexTableInputRef> compensationEquiColumns,
+      Set<RelTableRef> viewTableRefs, EquivalenceClasses vEC, Set<RelTableRef> queryTableRefs) {
+    // Create UK-FK graph with view tables
+    final DirectedGraph<RelTableRef, Edge> graph =
+        DefaultDirectedGraph.create(Edge.FACTORY);
+    final Multimap<List<String>, RelTableRef> tableQNameToTableRefs =
+        ArrayListMultimap.create();
+    final Set<RelTableRef> extraTableRefs = new HashSet<>();
+    for (RelTableRef tRef : viewTableRefs) {
+      // Add tables in view as vertices
+      graph.addVertex(tRef);
+      tableQNameToTableRefs.put(tRef.getQualifiedName(), tRef);
+      if (!queryTableRefs.contains(tRef)) {
+        // Add to extra tables if table is not part of the query
+        extraTableRefs.add(tRef);
+      }
+    }
+    for (RelTableRef tRef : graph.vertexSet()) {
+      // Add edges between tables
+      List<RelReferentialConstraint> constraints =
+          tRef.getTable().getReferentialConstraints();
+      for (RelReferentialConstraint constraint : constraints) {
+        Collection<RelTableRef> parentTableRefs =
+            tableQNameToTableRefs.get(constraint.getTargetQualifiedName());
+        if (parentTableRefs == null || parentTableRefs.isEmpty()) {
+          continue;
+        }
+        for (RelTableRef parentTRef : parentTableRefs) {
+          boolean canBeRewritten = true;
+          Multimap<RexTableInputRef, RexTableInputRef> equiColumns =
+                  ArrayListMultimap.create();
+          for (int pos = 0; pos < constraint.getNumColumns(); pos++) {
+            int foreignKeyPos = constraint.getColumnPairs().get(pos).source;
+            RelDataType foreignKeyColumnType =
+                tRef.getTable().getRowType().getFieldList().get(foreignKeyPos).getType();
+            RexTableInputRef foreignKeyColumnRef =
+                RexTableInputRef.of(tRef, foreignKeyPos, foreignKeyColumnType);
+            int uniqueKeyPos = constraint.getColumnPairs().get(pos).target;
+            RexTableInputRef uniqueKeyColumnRef = RexTableInputRef.of(parentTRef, uniqueKeyPos,
+                parentTRef.getTable().getRowType().getFieldList().get(uniqueKeyPos).getType());
+            if (!foreignKeyColumnType.isNullable()
+                && vEC.getEquivalenceClassesMap().get(uniqueKeyColumnRef).contains(
+                    foreignKeyColumnRef)) {
+              equiColumns.put(foreignKeyColumnRef, uniqueKeyColumnRef);
+            } else {
+              canBeRewritten = false;
+              break;
+            }
+          }
+          if (canBeRewritten) {
+            // Add edge FK -> UK
+            Edge edge = graph.getEdge(tRef, parentTRef);
+            if (edge == null) {
+              edge = graph.addEdge(tRef, parentTRef);
+            }
+            edge.equiColumns.putAll(equiColumns);
+            break;
+          }
+        }
+      }
+    }
+
+    // Try to eliminate tables from graph: if we can do it, it means extra tables in
+    // view are cardinality-preserving joins
+    boolean done = false;
+    do {
+      List<RelTableRef> nodesToRemove = new ArrayList<>();
+      for (RelTableRef tRef : graph.vertexSet()) {
+        if (graph.getInwardEdges(tRef).size() == 1
+            && graph.getOutwardEdges(tRef).isEmpty()) {
+          // UK-FK join
+          nodesToRemove.add(tRef);
+          if (extraTableRefs.contains(tRef)) {
+            // We need to add to compensation columns as the table is not present in the query
+            compensationEquiColumns.putAll(graph.getInwardEdges(tRef).get(0).equiColumns);
+          }
+        }
+      }
+      if (!nodesToRemove.isEmpty()) {
+        graph.removeAllVertices(nodesToRemove);
+      } else {
+        done = true;
+      }
+    } while (!done);
+
+    // After removing them, we check whether all the remaining tables in the graph
+    // are tables present in the query: if they are, we can try to rewrite
+    if (!Collections.disjoint(graph.vertexSet(), extraTableRefs)) {
+      return false;
+    }
+    return true;
   }
 
-  /* Given the equi-column predicates of the query and the view and the
+  /**
+   * Given the equi-column predicates of the query and the view and the
    * computed equivalence classes, it extracts possible mappings between
    * the equivalence classes.
    *
-   * If there is no mapping, it returns null. If there is a exact match,
+   * <p>If there is no mapping, it returns null. If there is a exact match,
    * it will return a compensation predicate that evaluates to true.
    * Finally, if a compensation predicate needs to be enforced on top of
    * the view to make the equivalences classes match, it returns that
-   * compensation predicate */
+   * compensation predicate
+   */
   private static RexNode generateEquivalenceClasses(RexBuilder rexBuilder,
-      RexNode queryEquiColumnsPreds, EquivalenceClasses qEC,
-      RexNode viewEquiColumnsPreds, EquivalenceClasses vEC) {
-    if (queryEquiColumnsPreds.isAlwaysTrue() && viewEquiColumnsPreds.isAlwaysTrue()) {
+      EquivalenceClasses qEC, EquivalenceClasses vEC) {
+    if (qEC.getEquivalenceClasses().isEmpty() && vEC.getEquivalenceClasses().isEmpty()) {
       // No column equality predicates in query and view
       // Empty mapping and compensation predicate
-      assert qEC.getEquivalenceClasses().isEmpty() && vEC.getEquivalenceClasses().isEmpty();
       return rexBuilder.makeLiteral(true);
     }
-    if (queryEquiColumnsPreds.isAlwaysTrue() || viewEquiColumnsPreds.isAlwaysTrue()) {
+    if (qEC.getEquivalenceClasses().isEmpty() || vEC.getEquivalenceClasses().isEmpty()) {
       // No column equality predicates in query or view
-      assert qEC.getEquivalenceClasses().isEmpty() || vEC.getEquivalenceClasses().isEmpty();
       return null;
     }
 
@@ -1020,11 +1204,13 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return compensationPredicate;
   }
 
-  /* Given the query and view equivalence classes, it extracts the possible mappings
+  /**
+   * Given the query and view equivalence classes, it extracts the possible mappings
    * from each view equivalence class to each query equivalence class.
    *
-   * If any of the view equivalence classes cannot be mapped to a query equivalence
-   * class, it returns null. */
+   * <p>If any of the view equivalence classes cannot be mapped to a query equivalence
+   * class, it returns null.
+   */
   private static Mapping extractPossibleMapping(
       List<Set<RexTableInputRef>> queryEquivalenceClasses,
       List<Set<RexTableInputRef>> viewEquivalenceClasses) {
@@ -1051,10 +1237,11 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return mapping;
   }
 
-  /* Given the input expression that references source expressions in the query,
+  /**
+   * Given the input expression that references source expressions in the query,
    * it will rewrite it to refer to the view output.
    *
-   * If any of the subexpressions in the input expression cannot be mapped to
+   * <p>If any of the subexpressions in the input expression cannot be mapped to
    * the query, it will return null.
    */
   private static RexNode rewriteExpression(
@@ -1115,9 +1302,11 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return rewrittenExprs;
   }
 
-  /* Mapping from node expressions to target expressions.
+  /**
+   * Mapping from node expressions to target expressions.
    *
-   * If any of the expressions cannot be mapped, we return null. */
+   * <p>If any of the expressions cannot be mapped, we return null.
+   */
   private static Multimap<Integer, Integer> generateMapping(
       RexBuilder rexBuilder,
       RelNode node,
@@ -1171,10 +1360,12 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return m;
   }
 
-  /* Given the input expression, it will replace (sub)expressions when possible
+  /**
+   * Given the input expression, it will replace (sub)expressions when possible
    * using the content of the mapping. In particular, the mapping contains the
    * digest of the expression and the index that the replacement input ref should
-   * point to. */
+   * point to.
+   */
   private static RexNode replaceWithOriginalReferences(final RexBuilder rexBuilder,
       final RexNode expr, final Map<String, Integer> mapping) {
     // Currently we allow the following:
@@ -1203,9 +1394,11 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     return visitor.apply(expr);
   }
 
-  /* Replaces all the input references by the position in the
+  /**
+   * Replaces all the input references by the position in the
    * input column set. If a reference index cannot be found in
-   * the input set, then we return null. */
+   * the input set, then we return null.
+   */
   private static RexNode shuttleReferences(final RexBuilder rexBuilder,
       final RexNode node, final Mapping mapping) {
     try {
@@ -1277,7 +1470,42 @@ public abstract class AbstractMaterializedViewRule extends RelOptRule {
     protected List<Set<RexTableInputRef>> getEquivalenceClasses() {
       return ImmutableList.copyOf(nodeToEquivalenceClass.values());
     }
+
+    protected static EquivalenceClasses copy(EquivalenceClasses ec) {
+      final EquivalenceClasses newEc = new EquivalenceClasses();
+      for (Entry<RexTableInputRef, Set<RexTableInputRef>> e
+          : ec.nodeToEquivalenceClass.entrySet()) {
+        newEc.nodeToEquivalenceClass.put(
+            e.getKey(), Sets.newLinkedHashSet(e.getValue()));
+      }
+      return newEc;
+    }
+  }
+
+  /** Edge for graph */
+  private static class Edge extends DefaultEdge {
+    public static final DirectedGraph.EdgeFactory<RelTableRef, Edge> FACTORY =
+        new DirectedGraph.EdgeFactory<RelTableRef, Edge>() {
+          public Edge createEdge(RelTableRef source, RelTableRef target) {
+            return new Edge(source, target);
+          }
+        };
+
+    final Multimap<RexTableInputRef, RexTableInputRef> equiColumns =
+        ArrayListMultimap.create();
+
+    public Edge(RelTableRef source, RelTableRef target) {
+      super(source, target);
+    }
   }
+
+  /** Complete, view partial, or query partial. */
+  private enum MatchModality {
+    COMPLETE,
+    VIEW_PARTIAL,
+    QUERY_PARTIAL
+  }
+
 }
 
 // End AbstractMaterializedViewRule.java

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java b/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java
index b986684..a8d9fe0 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexTableInputRef.java
@@ -16,11 +16,10 @@
  */
 package org.apache.calcite.rex;
 
+import org.apache.calcite.plan.RelOptTable;
 import org.apache.calcite.rel.type.RelDataType;
 import org.apache.calcite.sql.SqlKind;
 
-import com.google.common.collect.ImmutableList;
-
 import java.util.List;
 
 /**
@@ -98,14 +97,14 @@ public class RexTableInputRef extends RexInputRef {
   /** Identifies uniquely a table by its qualified name and its entity number (occurrence) */
   public static class RelTableRef {
 
-    private final List<String> qualifiedName;
+    private final RelOptTable table;
     private final int entityNumber;
     private final String digest;
 
-    private RelTableRef(List<String> qualifiedName, int entityNumber) {
-      this.qualifiedName = ImmutableList.copyOf(qualifiedName);
+    private RelTableRef(RelOptTable table, int entityNumber) {
+      this.table = table;
       this.entityNumber = entityNumber;
-      this.digest = qualifiedName + ".#" + entityNumber;
+      this.digest = table.getQualifiedName() + ".#" + entityNumber;
     }
 
     //~ Methods ----------------------------------------------------------------
@@ -113,7 +112,7 @@ public class RexTableInputRef extends RexInputRef {
     @Override public boolean equals(Object obj) {
       return this == obj
           || obj instanceof RelTableRef
-          && qualifiedName.equals(((RelTableRef) obj).qualifiedName)
+          && table.getQualifiedName().equals(((RelTableRef) obj).getQualifiedName())
           && entityNumber == ((RelTableRef) obj).entityNumber;
     }
 
@@ -121,8 +120,12 @@ public class RexTableInputRef extends RexInputRef {
       return digest.hashCode();
     }
 
+    public RelOptTable getTable() {
+      return table;
+    }
+
     public List<String> getQualifiedName() {
-      return qualifiedName;
+      return table.getQualifiedName();
     }
 
     public int getEntityNumber() {
@@ -133,8 +136,8 @@ public class RexTableInputRef extends RexInputRef {
       return digest;
     }
 
-    public static RelTableRef of(List<String> qualifiedName, int entityNumber) {
-      return new RelTableRef(qualifiedName, entityNumber);
+    public static RelTableRef of(RelOptTable table, int entityNumber) {
+      return new RelTableRef(table, entityNumber);
     }
   }
 }

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/schema/Statistic.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistic.java b/core/src/main/java/org/apache/calcite/schema/Statistic.java
index ced3bae..4b53d89 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistic.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistic.java
@@ -18,6 +18,7 @@ package org.apache.calcite.schema;
 
 import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelDistribution;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.util.ImmutableBitSet;
 
 import java.util.List;
@@ -38,6 +39,10 @@ public interface Statistic {
    */
   boolean isKey(ImmutableBitSet columns);
 
+  /** Returns the collection of referential constraints (foreign-keys)
+   * for this table. */
+  List<RelReferentialConstraint> getReferentialConstraints();
+
   /** Returns the collections of columns on which this table is sorted. */
   List<RelCollation> getCollations();
 

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/main/java/org/apache/calcite/schema/Statistics.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/calcite/schema/Statistics.java b/core/src/main/java/org/apache/calcite/schema/Statistics.java
index fe5a091..d3d4173 100644
--- a/core/src/main/java/org/apache/calcite/schema/Statistics.java
+++ b/core/src/main/java/org/apache/calcite/schema/Statistics.java
@@ -19,6 +19,7 @@ package org.apache.calcite.schema;
 import org.apache.calcite.rel.RelCollation;
 import org.apache.calcite.rel.RelDistribution;
 import org.apache.calcite.rel.RelDistributionTraitDef;
+import org.apache.calcite.rel.RelReferentialConstraint;
 import org.apache.calcite.util.ImmutableBitSet;
 
 import com.google.common.collect.ImmutableList;
@@ -43,6 +44,10 @@ public class Statistics {
           return false;
         }
 
+        public List<RelReferentialConstraint> getReferentialConstraints() {
+          return ImmutableList.<RelReferentialConstraint>of();
+        }
+
         public List<RelCollation> getCollations() {
           return ImmutableList.of();
         }
@@ -52,15 +57,33 @@ public class Statistics {
         }
       };
 
+  /** Returns a statistic with a given set of referential constraints. */
+  public static Statistic of(final List<RelReferentialConstraint> referentialConstraints) {
+    return of(null, ImmutableList.<ImmutableBitSet>of(),
+        referentialConstraints, ImmutableList.<RelCollation>of());
+  }
+
   /** Returns a statistic with a given row count and set of unique keys. */
   public static Statistic of(final double rowCount,
       final List<ImmutableBitSet> keys) {
-    return of(rowCount, keys, ImmutableList.<RelCollation>of());
+    return of(rowCount, keys, ImmutableList.<RelReferentialConstraint>of(),
+        ImmutableList.<RelCollation>of());
   }
 
-  /** Returns a statistic with a given row count and set of unique keys. */
+  /** Returns a statistic with a given row count, set of unique keys,
+   * and collations. */
   public static Statistic of(final double rowCount,
-      final List<ImmutableBitSet> keys, final List<RelCollation> collations) {
+      final List<ImmutableBitSet> keys,
+      final List<RelCollation> collations) {
+    return of(rowCount, keys, ImmutableList.<RelReferentialConstraint>of(), collations);
+  }
+
+  /** Returns a statistic with a given row count, set of unique keys,
+   * referential constraints, and collations. */
+  public static Statistic of(final Double rowCount,
+      final List<ImmutableBitSet> keys,
+      final List<RelReferentialConstraint> referentialConstraints,
+      final List<RelCollation> collations) {
     return new Statistic() {
       public Double getRowCount() {
         return rowCount;
@@ -75,6 +98,10 @@ public class Statistics {
         return false;
       }
 
+      public List<RelReferentialConstraint> getReferentialConstraints() {
+        return referentialConstraints;
+      }
+
       public List<RelCollation> getCollations() {
         return collations;
       }

http://git-wip-us.apache.org/repos/asf/calcite/blob/1f81e135/core/src/test/java/org/apache/calcite/test/JdbcTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/calcite/test/JdbcTest.java b/core/src/test/java/org/apache/calcite/test/JdbcTest.java
index 6819052..62a526b 100644
--- a/core/src/test/java/org/apache/calcite/test/JdbcTest.java
+++ b/core/src/test/java/org/apache/calcite/test/JdbcTest.java
@@ -4536,7 +4536,7 @@ public class JdbcTest {
             "select \"deptno\", \"employees\"[1] as e from \"hr\".\"depts\"\n").returnsUnordered(
         "deptno=10; E={100, 10, Bill, 10000.0, 1000}",
         "deptno=30; E=null",
-            "deptno=40; E={200, 20, Eric, 8000.0, 500}");
+        "deptno=40; E={200, 20, Eric, 8000.0, 500}");
   }
 
   @Test public void testVarcharEquals() {


Mime
View raw message