Class AbstractMaterializedViewRule

    • Constructor Detail

      • AbstractMaterializedViewRule

        protected AbstractMaterializedViewRule​(RelOptRuleOperand operand,
                                               RelBuilderFactory relBuilderFactory,
                                               java.lang.String description,
                                               boolean generateUnionRewriting,
                                               HepProgram unionRewritingPullProgram,
                                               boolean fastBailOut)
        Creates a AbstractMaterializedViewRule.
    • Method Detail

      • 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.

      • 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.
      • 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

        private static java.util.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.
      • isValidRelNodePlan

        private static boolean isValidRelNodePlan​(RelNode node,
                                                  RelMetadataQuery mq)
        Currently we only support TableScan - Project - Filter - Inner Join
      • splitPredicates

        private static 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

        private static boolean compensatePartial​(java.util.Set<RexTableInputRef.RelTableRef> sourceTableRefs,
                                                 AbstractMaterializedViewRule.EquivalenceClasses sourceEC,
                                                 java.util.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.

      • generateEquivalenceClasses

        private static RexNode generateEquivalenceClasses​(RexBuilder rexBuilder,
                                                          AbstractMaterializedViewRule.EquivalenceClasses sourceEC,
                                                          AbstractMaterializedViewRule.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

        private static com.google.common.collect.Multimap<java.lang.Integer,​java.lang.Integer> extractPossibleMapping​(java.util.List<java.util.Set<RexTableInputRef>> sourceEquivalenceClasses,
                                                                                                                            java.util.List<java.util.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

        private static RexNode rewriteExpression​(RexBuilder rexBuilder,
                                                 RelMetadataQuery mq,
                                                 RelNode targetNode,
                                                 RelNode node,
                                                 java.util.List<RexNode> nodeExprs,
                                                 com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,​RexTableInputRef.RelTableRef> tableMapping,
                                                 AbstractMaterializedViewRule.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

        private static java.util.List<RexNode> rewriteExpressions​(RexBuilder rexBuilder,
                                                                  RelMetadataQuery mq,
                                                                  RelNode targetNode,
                                                                  RelNode node,
                                                                  java.util.List<RexNode> nodeExprs,
                                                                  com.google.common.collect.BiMap<RexTableInputRef.RelTableRef,​RexTableInputRef.RelTableRef> tableMapping,
                                                                  AbstractMaterializedViewRule.EquivalenceClasses ec,
                                                                  boolean swapTableColumn,
                                                                  java.util.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.

      • replaceWithOriginalReferences

        private static RexNode replaceWithOriginalReferences​(RexBuilder rexBuilder,
                                                             RelNode node,
                                                             AbstractMaterializedViewRule.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

        private static 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

        private static RexNode shuttleReferences​(RexBuilder rexBuilder,
                                                 RexNode expr,
                                                 com.google.common.collect.Multimap<RexNode,​java.lang.Integer> exprsLineage)
        Replaces all the possible sub-expressions by input references to the input node.
      • shuttleReferences

        private static RexNode shuttleReferences​(RexBuilder rexBuilder,
                                                 RexNode expr,
                                                 com.google.common.collect.Multimap<RexNode,​java.lang.Integer> exprsLineage,
                                                 RelNode node,
                                                 Mapping 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.