Package org.apache.calcite.plan

Class SubstitutionVisitor

java.lang.Object
org.apache.calcite.plan.SubstitutionVisitor
Direct Known Subclasses:
MaterializedViewSubstitutionVisitor
public class SubstitutionVisitor extends 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: TableScan, Filter, Project, Calc, Join, Union, Intersect, Aggregate.

  • Field Details

    • DEFAULT_RULES

      public static final com.google.common.collect.ImmutableList<SubstitutionVisitor.UnifyRule> DEFAULT_RULES

    • relBuilder

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

    • slots

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

  • Constructor Details

  • Method Details

    • splitFilter

      public static @Nullable 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 > 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.

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

    • go0

      public @Nullable RelNode go0(RelNode replacement_)

    • go

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

    • replace

      public static @Nullable org.apache.calcite.plan.SubstitutionVisitor.Replacement replace(MutableRel query, MutableRel find, MutableRel replace)
      Within a relational expression query, replaces occurrences of find with replace.

      Assumes relational expressions (and their descendants) are not null. Does not handle cycles.

    • explainCalc

      public static Pair<RexNode,List<RexNode>> explainCalc(MutableCalc calc)
      Explain filtering condition and projections from MutableCalc.

    • permute

      public static MutableAggregate permute(MutableAggregate aggregate, MutableRel input, Mapping mapping)

    • unifyAggregates

      public static @Nullable MutableRel unifyAggregates(MutableAggregate query, @Nullable RexNode targetCond, MutableAggregate target)

    • getRollup

      @Deprecated public static @Nullable SqlAggFunction getRollup(SqlAggFunction aggregation)
      Deprecated.

    • isWeaker

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

    • equalType

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