[CALCITE-1731] Materialized view rewriting for join and aggregate operators
Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/84b49f5b Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/84b49f5b Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/84b49f5b Branch: refs/heads/master Commit: 84b49f5b48842708e9f4d912b4f9564745d74bc6 Parents: 41b05d7 Author: Jesus Camacho Rodriguez <[email protected]> Authored: Wed Mar 29 07:36:43 2017 +0100 Committer: Jesus Camacho Rodriguez <[email protected]> Committed: Wed Apr 26 19:56:37 2017 +0100 ---------------------------------------------------------------------- .../org/apache/calcite/plan/RelOptCluster.java | 1 - .../org/apache/calcite/plan/RelOptUtil.java | 3 +- .../calcite/plan/SubstitutionVisitor.java | 59 +- .../apache/calcite/plan/volcano/RelSubset.java | 4 +- .../calcite/prepare/CalcitePrepareImpl.java | 5 + .../calcite/rel/metadata/BuiltInMetadata.java | 78 +- .../metadata/DefaultRelMetadataProvider.java | 1 + .../rel/metadata/RelMdExpressionLineage.java | 18 +- .../rel/metadata/RelMdTableReferences.java | 199 +++ .../apache/calcite/rel/metadata/RelMdUtil.java | 1 - .../calcite/rel/metadata/RelMetadataQuery.java | 18 + .../calcite/rel/metadata/RelTableRef.java | 62 - .../apache/calcite/rel/mutable/MutableRels.java | 9 + .../rel/rules/AbstractMaterializedViewRule.java | 1283 ++++++++++++++++++ .../apache/calcite/rex/RexTableInputRef.java | 70 +- .../java/org/apache/calcite/rex/RexUtil.java | 19 +- .../org/apache/calcite/util/BuiltInMethod.java | 2 + .../calcite/test/MaterializationTest.java | 345 ++++- .../apache/calcite/test/RelMetadataTest.java | 48 +- site/_docs/materialized_views.md | 37 +- 20 files changed, 2120 insertions(+), 142 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/plan/RelOptCluster.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptCluster.java b/core/src/main/java/org/apache/calcite/plan/RelOptCluster.java index 034d978..f88e232 100644 --- a/core/src/main/java/org/apache/calcite/plan/RelOptCluster.java +++ b/core/src/main/java/org/apache/calcite/plan/RelOptCluster.java @@ -37,7 +37,6 @@ import java.util.concurrent.atomic.AtomicInteger; * optimization of a query. */ public class RelOptCluster { - //~ Instance fields -------------------------------------------------------- private final RelDataTypeFactory typeFactory; http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java index 662d316..b449417 100644 --- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java +++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java @@ -240,7 +240,8 @@ public abstract class RelOptUtil { } /** - * Returns a list of all tables used by this expression or its children + * Returns a list of all table qualified names used by this expression + * or its children. */ public static List<String> findAllTableQualifiedNames(RelNode rel) { return Lists.transform(findAllTables(rel), http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java index bd6dddf..f7bf106 100644 --- a/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java +++ b/core/src/main/java/org/apache/calcite/plan/SubstitutionVisitor.java @@ -72,6 +72,7 @@ import org.slf4j.Logger; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; +import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; @@ -229,7 +230,7 @@ public class SubstitutionVisitor { * <ul> * <li>condition: x = 1</li> * <li>target: x = 1 OR z = 3</li> - * <li>residue: NOT (z = 3)</li> + * <li>residue: x = 1</li> * </ul> * * <p>Example #3: condition and target are equivalent</p> @@ -258,32 +259,63 @@ public class SubstitutionVisitor { // First, try splitting into ORs. // Given target c1 OR c2 OR c3 OR c4 // and condition c2 OR c4 - // residue is NOT c1 AND NOT c3 + // residue is c2 OR c4 // Also deals with case target [x] condition [x] yields residue [true]. RexNode z = splitOr(simplify.rexBuilder, condition, target); if (z != null) { return z; } + if (isEquivalent(simplify.rexBuilder, condition, target)) { + return simplify.rexBuilder.makeLiteral(true); + } + RexNode x = andNot(simplify.rexBuilder, target, condition); if (mayBeSatisfiable(x)) { - RexNode x2 = andNot(simplify.rexBuilder, condition, target); - return simplify.simplify(x2); + RexNode x2 = RexUtil.composeConjunction(simplify.rexBuilder, + ImmutableList.of(condition, target), false); + RexNode r = simplify.withUnknownAsFalse(true).simplify(x2); + if (!r.isAlwaysFalse() && isEquivalent(simplify.rexBuilder, condition, r)) { + List<RexNode> conjs = RelOptUtil.conjunctions(r); + for (RexNode e : RelOptUtil.conjunctions(target)) { + removeAll(conjs, e); + } + return RexUtil.composeConjunction(simplify.rexBuilder, conjs, false); + } } return null; } private static RexNode splitOr( final RexBuilder rexBuilder, RexNode condition, RexNode target) { - List<RexNode> targets = RelOptUtil.disjunctions(target); - for (RexNode e : RelOptUtil.disjunctions(condition)) { - boolean found = removeAll(targets, e); - if (!found) { - return null; - } + List<RexNode> conditions = RelOptUtil.disjunctions(condition); + int conditionsLength = conditions.size(); + int targetsLength = 0; + for (RexNode e : RelOptUtil.disjunctions(target)) { + removeAll(conditions, e); + targetsLength++; + } + if (conditions.isEmpty() && conditionsLength == targetsLength) { + return rexBuilder.makeLiteral(true); + } else if (conditions.isEmpty()) { + return condition; } - return RexUtil.composeConjunction(rexBuilder, - Lists.transform(targets, RexUtil.notFn(rexBuilder)), false); + return null; + } + + private static boolean isEquivalent(RexBuilder rexBuilder, RexNode condition, RexNode target) { + // Example: + // e: x = 1 AND y = 2 AND z = 3 AND NOT (x = 1 AND y = 2) + // disjunctions: {x = 1, y = 2, z = 3} + // notDisjunctions: {x = 1 AND y = 2} + final Set<String> conditionDisjunctions = new HashSet<>( + RexUtil.strings(RelOptUtil.conjunctions(condition))); + final Set<String> targetDisjunctions = new HashSet<>( + RexUtil.strings(RelOptUtil.conjunctions(target))); + if (conditionDisjunctions.equals(targetDisjunctions)) { + return true; + } + return false; } /** @@ -1137,6 +1169,9 @@ public class SubstitutionVisitor { // target: SELECT x, y, SUM(a) AS s, COUNT(b) AS cb FROM t GROUP BY x, y // transforms to // result: SELECT x, SUM(cb) FROM (target) GROUP BY x + if (query.getInput() != target.getInput()) { + return null; + } if (!target.groupSet.contains(query.groupSet)) { return null; } http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java index af32671..24e15e8 100644 --- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java +++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java @@ -35,8 +35,6 @@ import org.apache.calcite.util.Litmus; import org.apache.calcite.util.Util; import org.apache.calcite.util.trace.CalciteTrace; -import com.google.common.collect.Iterables; - import org.slf4j.Logger; import java.io.PrintWriter; @@ -168,7 +166,7 @@ public class RelSubset extends AbstractRelNode { String s = getDescription(); pw.item("subset", s); final AbstractRelNode input = - (AbstractRelNode) Iterables.getFirst(getRels(), null); + (AbstractRelNode) Util.first(getBest(), getOriginal()); if (input == null) { return; } http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/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 9858b48..e0ae012 100644 --- a/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java +++ b/core/src/main/java/org/apache/calcite/prepare/CalcitePrepareImpl.java @@ -73,6 +73,7 @@ import org.apache.calcite.rel.core.Filter; import org.apache.calcite.rel.core.Project; import org.apache.calcite.rel.core.Sort; import org.apache.calcite.rel.core.TableScan; +import org.apache.calcite.rel.rules.AbstractMaterializedViewRule; import org.apache.calcite.rel.rules.AggregateExpandDistinctAggregatesRule; import org.apache.calcite.rel.rules.AggregateReduceFunctionsRule; import org.apache.calcite.rel.rules.AggregateStarTableRule; @@ -533,6 +534,10 @@ public class CalcitePrepareImpl implements CalcitePrepare { } if (prepareContext.config().materializationsEnabled()) { planner.addRule(MaterializedViewFilterScanRule.INSTANCE); + planner.addRule(AbstractMaterializedViewRule.INSTANCE_PROJECT_JOIN); + planner.addRule(AbstractMaterializedViewRule.INSTANCE_JOIN); + planner.addRule(AbstractMaterializedViewRule.INSTANCE_PROJECT_AGGREGATE); + planner.addRule(AbstractMaterializedViewRule.INSTANCE_AGGREGATE); } if (enableBindable) { for (RelOptRule rule : Bindables.RULES) { http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java b/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java index 0e0cbca..863e3e8 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/BuiltInMetadata.java @@ -22,6 +22,8 @@ import org.apache.calcite.rel.RelCollation; import org.apache.calcite.rel.RelDistribution; import org.apache.calcite.rel.RelNode; import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexTableInputRef; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; import org.apache.calcite.sql.SqlExplainLevel; import org.apache.calcite.util.BuiltInMethod; import org.apache.calcite.util.ImmutableBitSet; @@ -161,13 +163,21 @@ public abstract class BuiltInMetadata { } } - /** Metadata about the node types and count in a relational expression. */ + /** + * Metadata about the node types in a relational expression. + * + * <p>For each relational expression, it returns a multimap from the class + * to the nodes instantiating that class. Each node will appear in the + * multimap only once. + */ public interface NodeTypes extends Metadata { MetadataDef<NodeTypes> DEF = MetadataDef.of(NodeTypes.class, NodeTypes.Handler.class, BuiltInMethod.NODE_TYPES.method); /** - * + * Returns a multimap from the class to the nodes instantiating that + * class. The default implementation for a node classifies it as a + * {@link RelNode}. */ Multimap<Class<? extends RelNode>, RelNode> getNodeTypes(); @@ -393,7 +403,26 @@ public abstract class BuiltInMetadata { ExpressionLineage.Handler.class, BuiltInMethod.EXPRESSION_LINEAGE.method); /** - * + * Given the input expression applied on the given {@link RelNode}, this + * provider returns the expression with its lineage resolved. + * + * <p>In particular, the result will be a set of nodes which might contain + * references to columns in TableScan operators ({@link RexTableInputRef}). + * An expression can have more than one lineage expression due to Union + * operators. However, we do not check column equality in Filter predicates. + * Each TableScan operator below the node is identified uniquely by its + * qualified name and its entity number. + * + * <p>For example, if the expression is {@code $0 + 2} and {@code $0} originated + * from column {@code $3} in the {@code 0} occurrence of table {@code A} in the + * plan, result will be: {@code A.#0.$3 + 2}. Occurrences are generated in no + * particular order, but it is guaranteed that if two expressions referred to the + * same table, the qualified name + occurrence will be the same. + * + * @param expression expression whose lineage we want to resolve + * @return set of expressions with lineage resolved, or null if this information + * cannot be determined (e.g. origin of an expression is an aggregation + * in an {@link Aggregate} operator) */ Set<RexNode> getExpressionLineage(RexNode expression); @@ -404,6 +433,35 @@ public abstract class BuiltInMetadata { } } + /** Metadata to obtain references to tables used by a given expression. */ + public interface TableReferences extends Metadata { + MetadataDef<TableReferences> DEF = MetadataDef.of(TableReferences.class, + TableReferences.Handler.class, BuiltInMethod.TABLE_REFERENCES.method); + + /** + * This provider returns the tables used by a given plan. + * + * <p>In particular, the result will be a set of unique table references + * ({@link RelTableRef}) corresponding to each TableScan operator in the + * plan. These table references are composed by the table qualified name + * and an entity number. + * + * <p>Importantly, the table identifiers returned by this metadata provider + * will be consistent with the unique identifiers used by the {@link ExpressionLineage} + * provider, meaning that it is guaranteed that same table will use same unique + * identifiers in both. + * + * @return set of unique table identifiers, or null if this information + * cannot be determined + */ + Set<RelTableRef> getTableReferences(); + + /** Handler API. */ + interface Handler extends MetadataHandler<TableReferences> { + Set<RelTableRef> getTableReferences(RelNode r, RelMetadataQuery mq); + } + } + /** Metadata about the cost of evaluating a relational expression, including * all of its inputs. */ public interface CumulativeCost extends Metadata { @@ -496,7 +554,14 @@ public abstract class BuiltInMetadata { } /** Metadata about the predicates that hold in the rows emitted from a - * relational expression. */ + * relational expression. + * + * <p>The difference with respect to {@link Predicates} provider is that + * this provider tries to extract ALL predicates even if they are not + * applied on the output expressions of the relational expression; we rely + * on {@link RexTableInputRef} to reference origin columns in {@link TableScan} + * for the result predicates. + */ public interface AllPredicates extends Metadata { MetadataDef<AllPredicates> DEF = MetadataDef.of(AllPredicates.class, AllPredicates.Handler.class, BuiltInMethod.ALL_PREDICATES.method); @@ -505,7 +570,8 @@ public abstract class BuiltInMetadata { * Derives the predicates that hold on rows emitted from a relational * expression. * - * @return Predicate list + * @return predicate list, or null if the provider cannot infer the + * lineage for any of the expressions contained in any of the predicates */ RelOptPredicateList getAllPredicates(); @@ -602,7 +668,7 @@ public abstract class BuiltInMetadata { interface All extends Selectivity, UniqueKeys, RowCount, DistinctRowCount, PercentageOriginalRows, ColumnUniqueness, ColumnOrigin, Predicates, Collation, Distribution, Size, Parallelism, Memory, AllPredicates, - ExpressionLineage, NodeTypes { + ExpressionLineage, TableReferences, NodeTypes { } } http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/metadata/DefaultRelMetadataProvider.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/DefaultRelMetadataProvider.java b/core/src/main/java/org/apache/calcite/rel/metadata/DefaultRelMetadataProvider.java index cb86698..74ef413 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/DefaultRelMetadataProvider.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/DefaultRelMetadataProvider.java @@ -44,6 +44,7 @@ public class DefaultRelMetadataProvider extends ChainedRelMetadataProvider { RelMdPercentageOriginalRows.SOURCE, RelMdColumnOrigins.SOURCE, RelMdExpressionLineage.SOURCE, + RelMdTableReferences.SOURCE, RelMdNodeTypes.SOURCE, RelMdRowCount.SOURCE, RelMdMaxRowCount.SOURCE, http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/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 5f9e5ba..6ac5cfb 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 @@ -35,6 +35,7 @@ import org.apache.calcite.rex.RexInputRef; import org.apache.calcite.rex.RexNode; import org.apache.calcite.rex.RexShuttle; import org.apache.calcite.rex.RexTableInputRef; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; import org.apache.calcite.rex.RexUtil; import org.apache.calcite.util.BuiltInMethod; import org.apache.calcite.util.ImmutableBitSet; @@ -65,7 +66,7 @@ import java.util.Set; * * The output expressions might contain references to columns produced by TableScan * operators ({@link RexTableInputRef}). In turn, each TableScan operator is identified - * uniquely by its qualified name and an identifier contained in . + * uniquely by a {@link RelTableRef} containing its qualified name and an identifier. * * If the lineage cannot be inferred, we return null. */ @@ -122,7 +123,7 @@ public class RelMdExpressionLineage final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); for (int idx : inputFieldsUsed) { final RexNode inputRef = RexTableInputRef.of( - new RelTableRef(rel.getTable().getQualifiedName().toString(), 0), + RelTableRef.of(rel.getTable().getQualifiedName(), 0), RexInputRef.of(idx, rel.getRowType().getFieldList())); final Set<RexNode> originalExprs = Sets.newHashSet(inputRef); final RexInputRef ref = RexInputRef.of(idx, rel.getRowType().getFieldList()); @@ -193,7 +194,7 @@ public class RelMdExpressionLineage final int nLeftColumns = leftInput.getRowType().getFieldList().size(); // Infer column origin expressions for given references - final Multimap<String, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); + final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); for (int idx = 0; idx < rel.getRowType().getFieldList().size(); idx++) { @@ -232,7 +233,7 @@ public class RelMdExpressionLineage shift = lRefs.size(); } currentTablesMapping.put(rightRef, - new RelTableRef(rightRef.getQualifiedName(), shift + rightRef.getIdentifier())); + RelTableRef.of(rightRef.getQualifiedName(), shift + rightRef.getEntityNumber())); } final Set<RexNode> updatedExprs = Sets.newHashSet( Iterables.transform( @@ -262,7 +263,7 @@ public class RelMdExpressionLineage final RexBuilder rexBuilder = rel.getCluster().getRexBuilder(); // Infer column origin expressions for given references - final Multimap<String, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); + final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); final Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>(); for (RelNode input : rel.getInputs()) { final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); @@ -287,7 +288,7 @@ public class RelMdExpressionLineage shift = lRefs.size(); } currentTablesMapping.put(tableRef, - new RelTableRef(tableRef.getQualifiedName(), shift + tableRef.getIdentifier())); + RelTableRef.of(tableRef.getQualifiedName(), shift + tableRef.getEntityNumber())); } final Set<RexNode> updatedExprs = Sets.newHashSet( Iterables.transform( @@ -388,6 +389,11 @@ public class RelMdExpressionLineage expr.accept(inputFinder); final ImmutableBitSet predFieldsUsed = inputFinder.inputBitSet.build(); + if (predFieldsUsed.isEmpty()) { + // The unique expression is the input expression + return Sets.newHashSet(expr); + } + return createAllPossibleExpressions(rexBuilder, expr, predFieldsUsed, mapping, new HashMap<RexInputRef, RexNode>()); } http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/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 new file mode 100644 index 0000000..358c872 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdTableReferences.java @@ -0,0 +1,199 @@ +/* + * 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.metadata; + +import org.apache.calcite.plan.hep.HepRelVertex; +import org.apache.calcite.plan.volcano.RelSubset; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.core.Aggregate; +import org.apache.calcite.rel.core.Exchange; +import org.apache.calcite.rel.core.Filter; +import org.apache.calcite.rel.core.Join; +import org.apache.calcite.rel.core.Project; +import org.apache.calcite.rel.core.Sort; +import org.apache.calcite.rel.core.TableScan; +import org.apache.calcite.rel.core.Union; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; +import org.apache.calcite.util.BuiltInMethod; +import org.apache.calcite.util.Util; + +import com.google.common.collect.HashMultimap; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; + +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * RelMdTableReferences supplies a default implementation of + * {@link RelMetadataQuery#getTableReferences} for the standard logical algebra. + * + * The goal of this provider is to return all tables used by a given expression + * identified uniquely by a {@link RelTableRef}. + * + * Each unique identifier {@link RelTableRef} of a table will equal to the + * identifier obtained running {@link RelMdExpressionLineage} over the same + * plan node for an expression that refers to the same table. + * + * If tables cannot be obtained, we return null. + */ +public class RelMdTableReferences + implements MetadataHandler<BuiltInMetadata.TableReferences> { + public static final RelMetadataProvider SOURCE = + ReflectiveRelMetadataProvider.reflectiveSource( + BuiltInMethod.TABLE_REFERENCES.method, new RelMdTableReferences()); + + //~ Constructors ----------------------------------------------------------- + + private RelMdTableReferences() {} + + //~ Methods ---------------------------------------------------------------- + + public MetadataDef<BuiltInMetadata.TableReferences> getDef() { + return BuiltInMetadata.TableReferences.DEF; + } + + // Catch-all rule when none of the others apply. + public Set<RelTableRef> getTableReferences(RelNode rel, RelMetadataQuery mq) { + return null; + } + + public Set<RelTableRef> getTableReferences(HepRelVertex rel, RelMetadataQuery mq) { + return mq.getTableReferences(rel.getCurrentRel()); + } + + public Set<RelTableRef> getTableReferences(RelSubset rel, RelMetadataQuery mq) { + return mq.getTableReferences(Util.first(rel.getBest(), rel.getOriginal())); + } + + /** + * TableScan table reference. + */ + public Set<RelTableRef> getTableReferences(TableScan rel, RelMetadataQuery mq) { + return Sets.newHashSet(RelTableRef.of(rel.getTable().getQualifiedName(), 0)); + } + + /** + * Table references from Aggregate. + */ + public Set<RelTableRef> getTableReferences(Aggregate rel, RelMetadataQuery mq) { + return mq.getTableReferences(rel.getInput()); + } + + /** + * Table references from Join. + */ + public Set<RelTableRef> getTableReferences(Join rel, RelMetadataQuery mq) { + final RelNode leftInput = rel.getLeft(); + final RelNode rightInput = rel.getRight(); + final Set<RelTableRef> result = new HashSet<>(); + + // Gather table references, left input references remain unchanged + final Multimap<List<String>, RelTableRef> leftQualifiedNamesToRefs = HashMultimap.create(); + for (RelTableRef leftRef : mq.getTableReferences(leftInput)) { + assert !result.contains(leftRef); + result.add(leftRef); + leftQualifiedNamesToRefs.put(leftRef.getQualifiedName(), leftRef); + } + + // Gather table references, right input references might need to be + // updated if there are table names clashes with left input + for (RelTableRef rightRef : mq.getTableReferences(rightInput)) { + int shift = 0; + Collection<RelTableRef> lRefs = leftQualifiedNamesToRefs.get(rightRef.getQualifiedName()); + if (lRefs != null) { + shift = lRefs.size(); + } + RelTableRef shiftTableRef = RelTableRef.of( + rightRef.getQualifiedName(), shift + rightRef.getEntityNumber()); + assert !result.contains(shiftTableRef); + result.add(shiftTableRef); + } + + // Return result + return result; + } + + /** + * Table references from Union. + * + * For Union operator, we might be able to extract multiple table references. + */ + public Set<RelTableRef> getTableReferences(Union rel, RelMetadataQuery mq) { + final Set<RelTableRef> result = new HashSet<>(); + + // Infer column origin expressions for given references + final Multimap<List<String>, RelTableRef> qualifiedNamesToRefs = HashMultimap.create(); + for (RelNode input : rel.getInputs()) { + final Map<RelTableRef, RelTableRef> currentTablesMapping = new HashMap<>(); + for (RelTableRef tableRef : mq.getTableReferences(input)) { + int shift = 0; + Collection<RelTableRef> lRefs = qualifiedNamesToRefs.get( + tableRef.getQualifiedName()); + if (lRefs != null) { + shift = lRefs.size(); + } + RelTableRef shiftTableRef = RelTableRef.of( + tableRef.getQualifiedName(), shift + tableRef.getEntityNumber()); + assert !result.contains(shiftTableRef); + result.add(shiftTableRef); + currentTablesMapping.put(tableRef, shiftTableRef); + } + // Add to existing qualified names + for (RelTableRef newRef : currentTablesMapping.values()) { + qualifiedNamesToRefs.put(newRef.getQualifiedName(), newRef); + } + } + + // Return result + return result; + } + + /** + * Table references from Project. + */ + public Set<RelTableRef> getTableReferences(Project rel, final RelMetadataQuery mq) { + return mq.getTableReferences(rel.getInput()); + } + + /** + * Table references from Filter. + */ + public Set<RelTableRef> getTableReferences(Filter rel, RelMetadataQuery mq) { + return mq.getTableReferences(rel.getInput()); + } + + /** + * Table references from Sort. + */ + public Set<RelTableRef> getTableReferences(Sort rel, RelMetadataQuery mq) { + return mq.getTableReferences(rel.getInput()); + } + + /** + * Table references from Exchange. + */ + public Set<RelTableRef> getTableReferences(Exchange rel, RelMetadataQuery mq) { + return mq.getTableReferences(rel.getInput()); + } +} + +// End RelMdTableReferences.java http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java index 4ef5592..7b63ac9 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java @@ -843,7 +843,6 @@ public class RelMdUtil { } return alreadySorted && alreadySmaller; } - } // End RelMdUtil.java http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/metadata/RelMetadataQuery.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelMetadataQuery.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelMetadataQuery.java index 9dd19dc..7298ba3 100644 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelMetadataQuery.java +++ b/core/src/main/java/org/apache/calcite/rel/metadata/RelMetadataQuery.java @@ -23,6 +23,7 @@ import org.apache.calcite.rel.RelCollation; import org.apache.calcite.rel.RelDistribution; import org.apache.calcite.rel.RelNode; import org.apache.calcite.rex.RexNode; +import org.apache.calcite.rex.RexTableInputRef.RelTableRef; import org.apache.calcite.sql.SqlExplainLevel; import org.apache.calcite.util.ImmutableBitSet; @@ -86,6 +87,7 @@ public class RelMetadataQuery { private BuiltInMetadata.Collation.Handler collationHandler; private BuiltInMetadata.ColumnOrigin.Handler columnOriginHandler; private BuiltInMetadata.ExpressionLineage.Handler expressionLineageHandler; + private BuiltInMetadata.TableReferences.Handler tableReferencesHandler; private BuiltInMetadata.ColumnUniqueness.Handler columnUniquenessHandler; private BuiltInMetadata.CumulativeCost.Handler cumulativeCostHandler; private BuiltInMetadata.DistinctRowCount.Handler distinctRowCountHandler; @@ -119,6 +121,7 @@ public class RelMetadataQuery { this.collationHandler = prototype.collationHandler; this.columnOriginHandler = prototype.columnOriginHandler; this.expressionLineageHandler = prototype.expressionLineageHandler; + this.tableReferencesHandler = prototype.tableReferencesHandler; this.columnUniquenessHandler = prototype.columnUniquenessHandler; this.cumulativeCostHandler = prototype.cumulativeCostHandler; this.distinctRowCountHandler = prototype.distinctRowCountHandler; @@ -170,6 +173,7 @@ public class RelMetadataQuery { this.collationHandler = initialHandler(BuiltInMetadata.Collation.Handler.class); this.columnOriginHandler = initialHandler(BuiltInMetadata.ColumnOrigin.Handler.class); this.expressionLineageHandler = initialHandler(BuiltInMetadata.ExpressionLineage.Handler.class); + this.tableReferencesHandler = initialHandler(BuiltInMetadata.TableReferences.Handler.class); this.columnUniquenessHandler = initialHandler(BuiltInMetadata.ColumnUniqueness.Handler.class); this.cumulativeCostHandler = initialHandler(BuiltInMetadata.CumulativeCost.Handler.class); this.distinctRowCountHandler = initialHandler(BuiltInMetadata.DistinctRowCount.Handler.class); @@ -394,6 +398,20 @@ public class RelMetadataQuery { } /** + * Determines the tables used by a plan. + */ + public Set<RelTableRef> getTableReferences(RelNode rel) { + for (;;) { + try { + return tableReferencesHandler.getTableReferences(rel, this); + } catch (JaninoRelMetadataProvider.NoHandler e) { + tableReferencesHandler = + revise(e.relClass, BuiltInMetadata.TableReferences.DEF); + } + } + } + + /** * Determines the origin of a {@link RelNode}, provided it maps to a single * table, optionally with filtering and projection. * http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/metadata/RelTableRef.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/metadata/RelTableRef.java b/core/src/main/java/org/apache/calcite/rel/metadata/RelTableRef.java deleted file mode 100644 index bdd032f..0000000 --- a/core/src/main/java/org/apache/calcite/rel/metadata/RelTableRef.java +++ /dev/null @@ -1,62 +0,0 @@ -/* - * 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.metadata; - -/** - * - * - */ -public class RelTableRef { - - private final String qualifiedName; - private final int identifier; - private final String digest; - - public RelTableRef(String qualifiedName, int identifier) { - this.qualifiedName = qualifiedName; - this.identifier = identifier; - this.digest = qualifiedName + ".#" + identifier; - } - - //~ Methods ---------------------------------------------------------------- - - @Override public boolean equals(Object obj) { - return this == obj - || obj instanceof RelTableRef - && qualifiedName.equals(((RelTableRef) obj).qualifiedName) - && identifier == ((RelTableRef) obj).identifier; - } - - @Override public int hashCode() { - return digest.hashCode(); - } - - public String getQualifiedName() { - return qualifiedName; - } - - public int getIdentifier() { - return identifier; - } - - @Override public String toString() { - return digest; - } - -} - -// End RelTableRef.java http://git-wip-us.apache.org/repos/asf/calcite/blob/84b49f5b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java index 04b1849..ed1f1b1 100644 --- a/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java +++ b/core/src/main/java/org/apache/calcite/rel/mutable/MutableRels.java @@ -17,6 +17,8 @@ package org.apache.calcite.rel.mutable; import org.apache.calcite.plan.RelOptUtil; +import org.apache.calcite.plan.hep.HepRelVertex; +import org.apache.calcite.plan.volcano.RelSubset; import org.apache.calcite.rel.RelNode; import org.apache.calcite.rel.core.Aggregate; import org.apache.calcite.rel.core.Calc; @@ -271,6 +273,13 @@ public abstract class MutableRels { } public static MutableRel toMutable(RelNode rel) { + if (rel instanceof HepRelVertex) { + return toMutable(((HepRelVertex) rel).getCurrentRel()); + } + if (rel instanceof RelSubset) { + return toMutable( + Util.first(((RelSubset) rel).getBest(), ((RelSubset) rel).getOriginal())); + } if (rel instanceof TableScan) { return MutableScan.of((TableScan) rel); }
