[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 <[email protected]> Authored: Thu Apr 20 17:39:18 2017 +0100 Committer: Jesus Camacho Rodriguez <[email protected]> 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() {
