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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	MaterializedViewRule.Config Rule configuration.
protected static class	MaterializedViewRule.Edge Edge for graph.
protected static class	MaterializedViewRule.EquivalenceClasses Class representing an equivalence class, i.e., a set of equivalent columns
protected static class	MaterializedViewRule.MatchModality Complete, view partial, or query partial.
protected static class	MaterializedViewRule.NodeLineage Expression lineage details.
protected static class	MaterializedViewRule.ViewPartialRewriting View partitioning result.

Nested classes/interfaces inherited from class org.apache.calcite.plan.RelRule

RelRule.Done, RelRule.MatchHandler<R extends RelOptRule>, RelRule.OperandBuilder, RelRule.OperandDetailBuilder<R extends RelNode>, RelRule.OperandTransform

Nested classes/interfaces inherited from class org.apache.calcite.plan.RelOptRule

RelOptRule.ConverterRelOptRuleOperand

Field Summary

Fields inherited from class org.apache.calcite.plan.RelRule

config

Fields inherited from class org.apache.calcite.plan.RelOptRule

description, operands, relBuilderFactory

Method Summary

Modifier and Type	Method and Description
protected boolean	compensatePartial(Set<RexTableInputRef.RelTableRef> sourceTableRefs, MaterializedViewRule.EquivalenceClasses sourceEC, Set<RexTableInputRef.RelTableRef> targetTableRefs, 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.
protected abstract MaterializedViewRule.ViewPartialRewriting	compensateViewPartial(RelBuilder relBuilder, RexBuilder rexBuilder, RelMetadataQuery mq, RelNode input, Project topProject, RelNode node, Set<RexTableInputRef.RelTableRef> queryTableRefs, MaterializedViewRule.EquivalenceClasses queryEC, 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.
protected 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.
protected abstract RelNode	createUnion(RelBuilder relBuilder, RexBuilder rexBuilder, 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.
protected 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.
protected List<RexNode>	extractReferences(RexBuilder rexBuilder, RelNode node) If the node is an Aggregate, it returns a list of references to the grouping columns.
protected 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.
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.
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.
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.
protected abstract boolean	isValidPlan(Project topProject, RelNode node, RelMetadataQuery mq)
protected boolean	isValidRelNodePlan(RelNode node, RelMetadataQuery mq) Returns whether a RelNode is a valid tree.
boolean	matches(RelOptRuleCall call) Returns whether this rule could possibly match the given operands.
protected void	perform(RelOptRuleCall call, Project topProject, RelNode node) Rewriting logic is based on "Optimizing Queries Using Materialized Views: A Practical, Scalable Solution" by Goldstein and Larson.
protected abstract Pair<RelNode,RelNode>	pushFilterToOriginalViewPlan(RelBuilder builder, 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.
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.
protected 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.
protected 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.
protected abstract RelNode	rewriteQuery(RelBuilder relBuilder, RexBuilder rexBuilder, RexSimplify simplify, RelMetadataQuery mq, RexNode compensationColumnsEquiPred, RexNode otherCompensationPred, 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.
protected abstract RelNode	rewriteView(RelBuilder relBuilder, RexBuilder rexBuilder, RexSimplify simplify, RelMetadataQuery mq, MaterializedViewRule.MatchModality matchModality, boolean unionRewriting, RelNode input, Project topProject, RelNode node, 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.
protected RexNode	shuttleReferences(RexBuilder rexBuilder, RexNode node, Mapping mapping) Replaces all the input references by the position in the input column set.
protected 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.
protected RexNode	shuttleReferences(RexBuilder rexBuilder, RexNode expr, com.google.common.collect.Multimap<RexNode,Integer> exprsLineage, RelNode node, com.google.common.collect.Multimap<Integer,Integer> rewritingMapping) Replaces all the possible sub-expressions by input references to the input node.
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.

Methods inherited from class org.apache.calcite.plan.RelOptRule

any, convert, convert, convertList, convertOperand, convertOperand, equals, equals, getOperand, getOperands, getOutConvention, getOutTrait, hashCode, none, onMatch, operand, operand, operand, operand, operand, operandJ, operandJ, some, toString, unordered

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Method Detail

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,
                       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(Project topProject,
                                       RelNode node,
                                       RelMetadataQuery mq)

compensateViewPartial

protected abstract MaterializedViewRule.ViewPartialRewriting compensateViewPartial(RelBuilder relBuilder,
                                                                                   RexBuilder rexBuilder,
                                                                                   RelMetadataQuery mq,
                                                                                   RelNode input,
                                                                                   Project topProject,
                                                                                   RelNode node,
                                                                                   Set<RexTableInputRef.RelTableRef> queryTableRefs,
                                                                                   MaterializedViewRule.EquivalenceClasses queryEC,
                                                                                   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.

rewriteQuery

protected abstract RelNode rewriteQuery(RelBuilder relBuilder,
                                        RexBuilder rexBuilder,
                                        RexSimplify simplify,
                                        RelMetadataQuery mq,
                                        RexNode compensationColumnsEquiPred,
                                        RexNode otherCompensationPred,
                                        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 RelNode createUnion(RelBuilder relBuilder,
                                       RexBuilder rexBuilder,
                                       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 RelNode rewriteView(RelBuilder relBuilder,
                                       RexBuilder rexBuilder,
                                       RexSimplify simplify,
                                       RelMetadataQuery mq,
                                       MaterializedViewRule.MatchModality matchModality,
                                       boolean unionRewriting,
                                       RelNode input,
                                       Project topProject,
                                       RelNode node,
                                       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<RelNode,RelNode> pushFilterToOriginalViewPlan(RelBuilder builder,
                                                                      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,
                                    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 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 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 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 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 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 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 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 RexNode shuttleReferences(RexBuilder rexBuilder,
                                    RexNode expr,
                                    com.google.common.collect.Multimap<RexNode,Integer> exprsLineage,
                                    RelNode node,
                                    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.