Package org.apache.calcite.plan

Class SubstitutionVisitor

  • Direct Known Subclasses:
    MaterializedViewSubstitutionVisitor
    public class SubstitutionVisitor
extends java.lang.Object
    Substitutes part of a tree of relational expressions with another tree.

    The call new SubstitutionVisitor(target, query).go(replacement)) will return query with every occurrence of target replaced by replacement.

    The following example shows how SubstitutionVisitor can be used for materialized view recognition.

    • query = SELECT a, c FROM t WHERE x = 5 AND b = 4
    • target = SELECT a, b, c FROM t WHERE x = 5
    • replacement = SELECT * FROM mv
    • result = SELECT a, c FROM mv WHERE b = 4

    Note that result uses the materialized view table mv and a simplified condition b = 4.

    Uses a bottom-up matching algorithm. Nodes do not need to be identical. At each level, returns the residue.

    The inputs must only include the core relational operators: LogicalTableScan, LogicalFilter, LogicalProject, LogicalJoin, LogicalUnion, LogicalAggregate.

    • Field Detail

      • DEBUG

        private static final boolean DEBUG

      • LOGGER

        private static final org.slf4j.Logger LOGGER

      • relBuilder

        protected final RelBuilder relBuilder
        Factory for a builder for relational expressions.

      • query

        private final Holder query

      • targetLeaves

        final java.util.List<MutableRel> targetLeaves
        Nodes in target that have no children.

      • queryLeaves

        final java.util.List<MutableRel> queryLeaves
        Nodes in query that have no children.

      • slots

        protected final MutableRel[] slots
        Workspace while rule is being matched. Careful, re-entrant! Assumes no rule needs more than 2 slots.

    • Method Detail

      • splitFilter

        public static RexNode splitFilter​(RexSimplify simplify,
                                  RexNode condition,
                                  RexNode target)
        Maps a condition onto a target.

        If condition is stronger than target, returns the residue. If it is equal to target, returns the expression that evaluates to the constant true. If it is weaker than target, returns null.

        The terms satisfy the relation

        condition = target AND residue

        and residue must be as weak as possible.

        Example #1: condition stronger than target

        • condition: x = 1 AND y = 2
        • target: x = 1
        • residue: y = 2

        Note that residue x &gt; 0 AND y = 2 would also satisfy the relation condition = target AND residue but is stronger than necessary, so we prefer y = 2.

        Example #2: target weaker than condition (valid, but not currently implemented)

        • condition: x = 1
        • target: x = 1 OR z = 3
        • residue: x = 1

        Example #3: condition and target are equivalent

        • condition: x = 1 AND y = 2
        • target: y = 2 AND x = 1
        • residue: TRUE

        Example #4: condition weaker than target

        • condition: x = 1
        • target: x = 1 AND y = 2
        • residue: null (i.e. no match)

        There are many other possible examples. It amounts to solving whether condition AND NOT target can ever evaluate to true, and therefore is a form of the NP-complete Satisfiability problem.

      • canonizeNode

        private static RexNode canonizeNode​(RexBuilder rexBuilder,
                                    RexNode condition)
        Reorders some of the operands in this expression so structural comparison, i.e., based on string representation, can be more precise.

      • mayBeSatisfiable

        public static boolean mayBeSatisfiable​(RexNode e)
        Returns whether a boolean expression ever returns true.

        This method may give false positives. For instance, it will say that x = 5 AND x > 10 is satisfiable, because at present it cannot prove that it is not.

      • go

        public java.util.List<RelNode> go​(RelNode replacement_)
        Returns a list of all possible rels that result from substituting the matched RelNode with the replacement RelNode within the query.

        For example, the substitution result of A join B, while A and B are both a qualified match for replacement R, is R join B, R join R, A join R.

      • go

        private java.util.List<java.util.List<SubstitutionVisitor.Replacement>> go​(MutableRel replacement)
        Substitutes the query with replacement whenever possible but meanwhile keeps track of all the substitutions and their original rel before replacement, so that in later processing stage, the replacement can be recovered individually to produce a list of all possible rels with substitution in different places.

      • mightMatch

        private static boolean mightMatch​(SubstitutionVisitor.UnifyRule rule,
                                  java.lang.Class queryClass,
                                  java.lang.Class targetClass)

      • getRexShuttle

        protected static RexShuttle getRexShuttle​(MutableProject target)
        Builds a shuttle that stores a list of expressions, and can map incoming expressions to references to them.

      • isWeaker

        protected boolean isWeaker​(MutableRel rel0,
                           MutableRel rel)
        Returns if one rel is weaker than another.

      • equalType

        public static boolean equalType​(java.lang.String desc0,
                                MutableRel rel0,
                                java.lang.String desc1,
                                MutableRel rel1,
                                Litmus litmus)
        Returns whether two relational expressions have the same row-type.