Package org.apache.calcite.rel.rules.materialize

Class MaterializedViewRule<C extends MaterializedViewRule.Config>

java.lang.Object
org.apache.calcite.plan.RelOptRule
org.apache.calcite.plan.RelRule<C>
org.apache.calcite.rel.rules.materialize.MaterializedViewRule<C>
Type Parameters:
C - Configuration type
Direct Known Subclasses:
MaterializedViewAggregateRule, MaterializedViewJoinRule
public abstract class MaterializedViewRule<C extends MaterializedViewRule.Config> extends RelRule<C>
Planner rule that converts a Project followed by Aggregate or an Aggregate to a scan (and possibly other operations) over a materialized view.

  • Method Details

    • matches

      public boolean matches(RelOptRuleCall call)
      Description copied from class: RelOptRule
      Returns whether this rule could possibly match the given operands.

      This method is an opportunity to apply side-conditions to a rule. The RelOptPlanner calls this method after matching all operands of the rule, and before calling RelOptRule.onMatch(RelOptRuleCall).

      In implementations of RelOptPlanner which may queue up a matched RelOptRuleCall for a long time before calling RelOptRule.onMatch(RelOptRuleCall), this method is beneficial because it allows the planner to discard rules earlier in the process.

      The default implementation of this method returns true. It is acceptable for any implementation of this method to give a false positives, that is, to say that the rule matches the operands but have RelOptRule.onMatch(RelOptRuleCall) subsequently not generate any successors.

      The following script is useful to identify rules which commonly produce no successors. You should override this method for these rules: 

      awk '
 /Apply rule/ {rule=$4; ruleCount[rule]++;}
 /generated 0 successors/ {ruleMiss[rule]++;}
 END {
   printf "%-30s %s %s\n", "Rule", "Fire", "Miss";
   for (i in ruleCount) {
     printf "%-30s %5d %5d\n", i, ruleCount[i], ruleMiss[i];
   }
 } ' FarragoTrace.log
      Overrides:
      matches in class RelOptRule
      Parameters:
      call - Rule call which has been determined to match all operands of this rule
      Returns:
      whether this RelOptRule matches a given RelOptRuleCall

    • perform

      protected void perform(RelOptRuleCall call, @Nullable Project topProject, RelNode node)
      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 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. We might rely on existing Unique-Key - Foreign-Key relationships to extract that information.

      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.

      The rule contains multiple extensions compared to the original paper. One of them is the possibility of creating rewritings using Union operators, e.g., if the result of a query is partially contained in the materialized view.

    • isValidPlan

      protected abstract boolean isValidPlan(@Nullable Project topProject, RelNode node, RelMetadataQuery mq)

    • compensateViewPartial

      protected abstract @Nullable MaterializedViewRule.ViewPartialRewriting compensateViewPartial(RelBuilder relBuilder, RexBuilder rexBuilder, RelMetadataQuery mq, RelNode input, @Nullable Project topProject, RelNode node, Set<RexTableInputRef.RelTableRef> queryTableRefs, MaterializedViewRule.EquivalenceClasses queryEC, @Nullable Project topViewProject, RelNode viewNode, Set<RexTableInputRef.RelTableRef> viewTableRefs)
      It checks whether the query can be rewritten using the view even though the query uses additional tables.

      Rules implementing the method should follow different approaches depending on the operators they rewrite.

      Returns:
      ViewPartialRewriting, or null if the rewrite can't be done

    • rewriteQuery

      protected abstract @Nullable RelNode rewriteQuery(RelBuilder relBuilder, RexBuilder rexBuilder, RexSimplify simplify, RelMetadataQuery mq, RexNode compensationColumnsEquiPred, RexNode otherCompensationPred, @Nullable Project topProject, RelNode node, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> viewToQueryTableMapping, MaterializedViewRule.EquivalenceClasses viewEC, MaterializedViewRule.EquivalenceClasses queryEC)
      If the view will be used in a union rewriting, this method is responsible for rewriting the query branch of the union using the given compensation predicate.

      If a rewriting can be produced, we return that rewriting. If it cannot be produced, we will return null.

    • createUnion

      protected abstract @Nullable RelNode createUnion(RelBuilder relBuilder, RexBuilder rexBuilder, @Nullable RelNode topProject, RelNode unionInputQuery, RelNode unionInputView)
      If the view will be used in a union rewriting, this method is responsible for generating the union and any other operator needed on top of it, e.g., a Project operator.

    • rewriteView

      protected abstract @Nullable RelNode rewriteView(RelBuilder relBuilder, RexBuilder rexBuilder, RexSimplify simplify, RelMetadataQuery mq, MaterializedViewRule.MatchModality matchModality, boolean unionRewriting, RelNode input, @Nullable Project topProject, RelNode node, @Nullable Project topViewProject, RelNode viewNode, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> queryToViewTableMapping, MaterializedViewRule.EquivalenceClasses queryEC)
      Rewrites the query using the given view query.

      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.

    • pushFilterToOriginalViewPlan

      protected abstract Pair<@Nullable RelNode,RelNode> pushFilterToOriginalViewPlan(RelBuilder builder, @Nullable RelNode topViewProject, RelNode viewNode, RexNode cond)
      Once we create a compensation predicate, this method is responsible for pushing the resulting filter through the view nodes. This might be useful for rewritings containing Aggregate operators, as some of the grouping columns might be removed, which results in additional matching possibilities.

      The method will return a pair of nodes: the new top project on the left and the new node on the right.

    • extractReferences

      protected List<RexNode> extractReferences(RexBuilder rexBuilder, RelNode node)
      If the node is an Aggregate, it returns a list of references to the grouping columns. Otherwise, it returns a list of references to all columns in the node. The returned list is immutable.

    • generateTableMappings

      protected List<com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef>> generateTableMappings(com.google.common.collect.Multimap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> multiMapTables)
      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.

    • isValidRelNodePlan

      protected boolean isValidRelNodePlan(RelNode node, RelMetadataQuery mq)
      Returns whether a RelNode is a valid tree. Currently we only support TableScan - Project - Filter - Inner Join.

    • splitPredicates

      protected Pair<RexNode,RexNode> splitPredicates(RexBuilder rexBuilder, RexNode pred)
      Classifies each of the predicates in the list into one of these two categories:
      • 1-l) column equality predicates, or
      • 2-r) residual predicates, all the rest

      For each category, it creates the conjunction of the predicates. The result is an pair of RexNode objects corresponding to each category.

    • compensatePartial

      protected boolean compensatePartial(Set<RexTableInputRef.RelTableRef> sourceTableRefs, MaterializedViewRule.EquivalenceClasses sourceEC, Set<RexTableInputRef.RelTableRef> targetTableRefs, @Nullable com.google.common.collect.Multimap<RexTableInputRef,RexTableInputRef> compensationEquiColumns)
      It checks whether the target can be rewritten using the source even though the source uses additional tables. In order to do that, we need to double-check that every join that exists in the source and is not in the target is a cardinality-preserving join, i.e., it only appends columns to the row without changing its multiplicity. Thus, the join needs to be:
      • Equi-join
      • Between all columns in the keys
      • Foreign-key columns do not allow NULL values
      • Foreign-key
      • Unique-key

      If it can be rewritten, it returns true. Further, it inserts the missing equi-join predicates in the input compensationEquiColumns multimap if it is provided. If it cannot be rewritten, it returns false.

    • computeCompensationPredicates

      protected @Nullable Pair<RexNode,RexNode> computeCompensationPredicates(RexBuilder rexBuilder, RexSimplify simplify, MaterializedViewRule.EquivalenceClasses sourceEC, Pair<RexNode,RexNode> sourcePreds, MaterializedViewRule.EquivalenceClasses targetEC, Pair<RexNode,RexNode> targetPreds, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> sourceToTargetTableMapping)
      We check whether the predicates in the source are contained in the predicates in the target. The method treats separately the equi-column predicates, the range predicates, and the rest of predicates.

      If the containment is confirmed, we produce compensation predicates that need to be added to the target to produce the results in the source. Thus, if source and target expressions are equivalent, those predicates will be the true constant.

      In turn, if containment cannot be confirmed, the method returns null.

    • generateEquivalenceClasses

      protected @Nullable RexNode generateEquivalenceClasses(RexBuilder rexBuilder, MaterializedViewRule.EquivalenceClasses sourceEC, MaterializedViewRule.EquivalenceClasses targetEC)
      Given the equi-column predicates of the source and the target 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, it will return a compensation predicate that evaluates to true. Finally, if a compensation predicate needs to be enforced on top of the target to make the equivalences classes match, it returns that compensation predicate.

    • extractPossibleMapping

      protected @Nullable com.google.common.collect.Multimap<Integer,Integer> extractPossibleMapping(List<Set<RexTableInputRef>> sourceEquivalenceClasses, List<Set<RexTableInputRef>> targetEquivalenceClasses)
      Given the source and target equivalence classes, it extracts the possible mappings from each source equivalence class to each target equivalence class.

      If any of the source equivalence classes cannot be mapped to a target equivalence class, it returns null.

    • rewriteExpression

      protected @Nullable RexNode rewriteExpression(RexBuilder rexBuilder, RelMetadataQuery mq, RelNode targetNode, RelNode node, List<RexNode> nodeExprs, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> tableMapping, MaterializedViewRule.EquivalenceClasses ec, boolean swapTableColumn, RexNode exprToRewrite)
      First, the method takes the node expressions nodeExprs and swaps the table and column references using the table mapping and the equivalence classes. If swapTableColumn is true, it swaps the table reference and then the column reference, otherwise it swaps the column reference and then the table reference.

      Then, the method will rewrite the input expression exprToRewrite, replacing the RexTableInputRef by references to the positions in nodeExprs.

      The method will return the rewritten expression. If any of the expressions in the input expression cannot be mapped, it will return null.

    • rewriteExpressions

      protected @Nullable List<RexNode> rewriteExpressions(RexBuilder rexBuilder, RelMetadataQuery mq, RelNode targetNode, RelNode node, List<RexNode> nodeExprs, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> tableMapping, MaterializedViewRule.EquivalenceClasses ec, boolean swapTableColumn, List<RexNode> exprsToRewrite)
      First, the method takes the node expressions nodeExprs and swaps the table and column references using the table mapping and the equivalence classes. If swapTableColumn is true, it swaps the table reference and then the column reference, otherwise it swaps the column reference and then the table reference.

      Then, the method will rewrite the input expressions exprsToRewrite, replacing the RexTableInputRef by references to the positions in nodeExprs.

      The method will return the rewritten expressions. If any of the subexpressions in the input expressions cannot be mapped, it will return null.

    • generateSwapTableColumnReferencesLineage

      protected MaterializedViewRule.NodeLineage generateSwapTableColumnReferencesLineage(RexBuilder rexBuilder, RelMetadataQuery mq, RelNode node, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> tableMapping, MaterializedViewRule.EquivalenceClasses ec, List<RexNode> nodeExprs)
      It swaps the table references and then the column references of the input expressions using the table mapping and the equivalence classes.

    • generateSwapColumnTableReferencesLineage

      protected MaterializedViewRule.NodeLineage generateSwapColumnTableReferencesLineage(RexBuilder rexBuilder, RelMetadataQuery mq, RelNode node, com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,RexTableInputRef.RelTableRef> tableMapping, MaterializedViewRule.EquivalenceClasses ec, List<RexNode> nodeExprs)
      It swaps the column references and then the table references of the input expressions using the equivalence classes and the table mapping.

    • replaceWithOriginalReferences

      protected RexNode replaceWithOriginalReferences(RexBuilder rexBuilder, RelNode node, MaterializedViewRule.NodeLineage nodeLineage, RexNode exprToRewrite)
      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.

    • shuttleReferences

      protected @Nullable RexNode shuttleReferences(RexBuilder rexBuilder, RexNode node, Mapping mapping)
      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.

    • shuttleReferences

      protected @Nullable RexNode shuttleReferences(RexBuilder rexBuilder, RexNode expr, com.google.common.collect.Multimap<RexNode,Integer> exprsLineage)
      Replaces all the possible sub-expressions by input references to the input node.

    • shuttleReferences

      protected @Nullable RexNode shuttleReferences(RexBuilder rexBuilder, RexNode expr, com.google.common.collect.Multimap<RexNode,Integer> exprsLineage, @Nullable RelNode node, @Nullable com.google.common.collect.Multimap<Integer,Integer> rewritingMapping)
      Replaces all the possible sub-expressions by input references to the input node. If available, it uses the rewriting mapping to change the position to reference. Takes the reference type from the input node.