Package org.apache.calcite.plan.volcano

Class VolcanoPlanner

  • All Implemented Interfaces:
    RelOptPlanner
    public class VolcanoPlanner
extends AbstractRelOptPlanner
    VolcanoPlanner optimizes queries by transforming expressions selectively according to a dynamic programming algorithm.

    • Field Detail

      • ambitious

        protected boolean ambitious
        If true, the planner keeps applying rules as long as they continue to reduce the cost. If false, the planner terminates as soon as it has found any implementation, no matter how expensive.

      • impatient

        protected boolean impatient
        If true, and if ambitious is true, the planner waits a finite number of iterations for the cost to improve.

        The number of iterations K is equal to the number of iterations required to get the first finite plan. After the first finite plan, it continues to fire rules to try to improve it. The planner sets a target cost of the current best cost multiplied by COST_IMPROVEMENT. If it does not meet that cost target within K steps, it quits, and uses the current best plan. If it meets the cost, it sets a new, lower target, and has another K iterations to meet it. And so forth.

        If false, the planner continues to fire rules until the rule queue is empty.

      • classOperands

        private final com.google.common.collect.Multimap<java.lang.Class<? extends RelNode>,​RelOptRuleOperand> classOperands
        Operands that apply to a given class of RelNode.

        Any operand can be an 'entry point' to a rule call, when a RelNode is registered which matches the operand. This map allows us to narrow down operands based on the class of the RelNode.

      • allSets

        final java.util.List<RelSet> allSets
        List of all sets. Used only for debugging.

      • mapDigestToRel

        private final java.util.Map<Pair<java.lang.String,​RelDataType>,​RelNode> mapDigestToRel
        Canonical map from digest to the unique relational expression with that digest.

        Row type is part of the key for the rare occasion that similar expressions have different types, e.g. variants of Project(child=rel#1, a=null) where a is a null INTEGER or a null VARCHAR(10).

      • mapRel2Subset

        private final java.util.IdentityHashMap<RelNode,​RelSubset> mapRel2Subset
        Map each registered expression (RelNode) to its equivalence set (RelSubset).

        We use an IdentityHashMap to simplify the process of merging RelSet objects. Most RelNode objects are identified by their digest, which involves the set that their child relational expressions belong to. If those children belong to the same set, we have to be careful, otherwise it gets incestuous.

      • relImportances

        final java.util.Map<RelNode,​java.lang.Double> relImportances
        The importance of relational expressions.

        The map contains only RelNodes whose importance has been overridden using RelOptPlanner.setImportance(RelNode, double). Other RelNodes are presumed to have 'normal' importance.

        If a RelNode has 0 importance, all RelOptRuleCalls using it are ignored, and future RelOptRuleCalls are not queued up.

      • registeredSchemas

        private final java.util.Set<RelOptSchema> registeredSchemas
        List of all schemas which have been registered.

      • ruleQueue

        final RuleQueue ruleQueue
        Holds rule calls waiting to be fired.

      • traitDefs

        private final java.util.List<RelTraitDef> traitDefs
        Holds the currently registered RelTraitDefs.

      • ruleSet

        protected final java.util.Set<RelOptRule> ruleSet
        Set of all registered rules.

      • nextSetId

        private int nextSetId

      • registerCount

        private int registerCount
        Incremented every time a relational expression is registered or two sets are merged. Tells us whether anything is going on.

      • listener

        RelOptListener listener
        Listener for this planner, or null if none set.

      • originalRootString

        private java.lang.String originalRootString
        Dump of the root relational expression, as it was before any rules were applied. For debugging.

      • originalRoot

        private RelNode originalRoot

      • locked

        private boolean locked
        Whether the planner can accept new rules.

      • latticeByName

        private final java.util.Map<java.util.List<java.lang.String>,​RelOptLattice> latticeByName
        Map of lattices by the qualified name of their star table.

      • ruleCallStack

        private final java.util.Deque<VolcanoRuleCall> ruleCallStack

      • ruleNames

        private final com.google.common.collect.SetMultimap<java.lang.String,​java.lang.Class> ruleNames
        Maps rule classes to their name, to ensure that the names are unique and conform to rules.

    • Constructor Detail

      • VolcanoPlanner

        public VolcanoPlanner()
        Creates a uninitialized VolcanoPlanner. To fully initialize it, the caller must register the desired set of relations, rules, and calling conventions.

      • VolcanoPlanner

        public VolcanoPlanner​(Context externalContext)
        Creates a uninitialized VolcanoPlanner. To fully initialize it, the caller must register the desired set of relations, rules, and calling conventions.

      • VolcanoPlanner

        public VolcanoPlanner​(RelOptCostFactory costFactory,
                      Context externalContext)
        Creates a VolcanoPlanner with a given cost factory.

    • Method Detail

      • isRegistered

        public boolean isRegistered​(RelNode rel)
        Description copied from interface: RelOptPlanner
        Determines whether a relational expression has been registered.
        Parameters:
        rel - expression to test
        Returns:
        whether rel has been registered

      • setRoot

        public void setRoot​(RelNode rel)
        Description copied from interface: RelOptPlanner
        Sets the root node of this query.
        Parameters:
        rel - Relational expression

      • getRoot

        public RelNode getRoot()
        Description copied from interface: RelOptPlanner
        Returns the root node of this query.
        Returns:
        Root node

      • addMaterialization

        public void addMaterialization​(RelOptMaterialization materialization)
        Description copied from interface: RelOptPlanner
        Defines a pair of relational expressions that are equivalent.

        Typically tableRel is a LogicalTableScan representing a table that is a materialized view and queryRel is the SQL expression that populates that view. The intention is that tableRel is cheaper to evaluate and therefore if the query being optimized uses (or can be rewritten to use) queryRel as a sub-expression then it can be optimized by using tableRel instead.

        Specified by:
        addMaterialization in interface RelOptPlanner
        Overrides:
        addMaterialization in class AbstractRelOptPlanner

      • registerMaterializations

        private void registerMaterializations()

      • getSet

        public RelSet getSet​(RelNode rel)
        Finds an expression's equivalence set. If the expression is not registered, returns null.
        Parameters:
        rel - Relational expression
        Returns:
        Equivalence set that expression belongs to, or null if it is not registered

      • emptyTraitSet

        public RelTraitSet emptyTraitSet()
        Description copied from interface: RelOptPlanner
        Creates an empty trait set. It contains all registered traits, and the default values of any traits that have them.

        The empty trait set acts as the prototype (a kind of factory) for all subsequently created trait sets.

        Specified by:
        emptyTraitSet in interface RelOptPlanner
        Overrides:
        emptyTraitSet in class AbstractRelOptPlanner
        Returns:
        Empty trait set

      • getRules

        public java.util.List<RelOptRule> getRules()
        Description copied from interface: RelOptPlanner
        Returns the list of all registered rules.

      • addRule

        public boolean addRule​(RelOptRule rule)
        Description copied from interface: RelOptPlanner
        Registers a rule.

        If the rule has already been registered, does nothing. This method determines if the given rule is a ConverterRule and pass the ConverterRule to all registered RelTraitDef instances.

        Returns:
        whether the rule was added, as per Collection.add(E)

      • removeRule

        public boolean removeRule​(RelOptRule rule)
        Description copied from interface: RelOptPlanner
        Removes a rule.
        Returns:
        true if the rule was present, as per Collection.remove(Object)

      • changeTraits

        public RelNode changeTraits​(RelNode rel,
                            RelTraitSet toTraits)
        Description copied from interface: RelOptPlanner
        Changes a relational expression to an equivalent one with a different set of traits.
        Parameters:
        rel - Relational expression (may or may not have been registered; must not have the desired traits)
        toTraits - Trait set to convert the relational expression to
        Returns:
        Relational expression with desired traits. Never null, but may be abstract

      • findBestExp

        public RelNode findBestExp()
        Finds the most efficient expression to implement the query given via RelOptPlanner.setRoot(org.apache.calcite.rel.RelNode).

        The algorithm executes repeatedly in a series of phases. In each phase the exact rules that may be fired varies. The mapping of phases to rule sets is maintained in the ruleQueue.

        In each phase, the planner sets the initial importance of the existing RelSubSets (setInitialImportance()). The planner then iterates over the rule matches presented by the rule queue until:

        1. The rule queue becomes empty.
        2. For ambitious planners: No improvements to the plan have been made recently (specifically within a number of iterations that is 10% of the number of iterations necessary to first reach an implementable plan or 25 iterations whichever is larger).
        3. For non-ambitious planners: When an implementable plan is found.

        Furthermore, after every 10 iterations without an implementable plan, RelSubSets that contain only logical RelNodes are given an importance boost via injectImportanceBoost(). Once an implementable plan is found, the artificially raised importance values are cleared (see clearImportanceBoost()).

        Returns:
        the most efficient RelNode tree found for implementing the given query

      • registerMetadataRels

        private void registerMetadataRels()
        Informs JaninoRelMetadataProvider about the different kinds of RelNode that we will be dealing with. It will reduce the number of times that we need to re-generate the provider.

      • ensureRootConverters

        void ensureRootConverters()
        Ensures that the subset that is the root relational expression contains converters to all other subsets in its equivalence set.

        Thus the planner tries to find cheap implementations of those other subsets, which can then be converted to the root. This is the only place in the plan where explicit converters are required; elsewhere, a consumer will be asking for the result in a particular convention, but the root has no consumers.

      • provenance

        private java.lang.String provenance​(RelNode root)
        Returns a multi-line string describing the provenance of a tree of relational expressions. For each node in the tree, prints the rule that created the node, if any. Recursively describes the provenance of the relational expressions that are the arguments to that rule.

        Thus, every relational expression and rule invocation that affected the final outcome is described in the provenance. This can be useful when finding the root cause of "mistakes" in a query plan.

        Parameters:
        root - Root relational expression in a tree
        Returns:
        Multi-line string describing the rules that created the tree

      • setInitialImportance

        private void setInitialImportance()

      • injectImportanceBoost

        private void injectImportanceBoost()
        Finds RelSubsets in the plan that contain only rels of Convention.NONE and boosts their importance by 25%.

      • clearImportanceBoost

        private void clearImportanceBoost()
        Clear all importance boosts.

      • register

        public RelSubset register​(RelNode rel,
                          RelNode equivRel)
        Description copied from interface: RelOptPlanner
        Registers a relational expression in the expression bank.

        After it has been registered, you may not modify it.

        The expression must not already have been registered. If you are not sure whether it has been registered, call RelOptPlanner.ensureRegistered(RelNode, RelNode).

        Parameters:
        rel - Relational expression to register (must not already be registered)
        equivRel - Relational expression it is equivalent to (may be null)
        Returns:
        the same expression, or an equivalent existing expression

      • ensureRegistered

        public RelSubset ensureRegistered​(RelNode rel,
                                  RelNode equivRel)
        Description copied from interface: RelOptPlanner
        Registers a relational expression if it is not already registered.

        If equivRel is specified, rel is placed in the same equivalence set. It is OK if equivRel has different traits; rel will end up in a different subset of the same set.

        It is OK if rel is a subset.

        Parameters:
        rel - Relational expression to register
        equivRel - Relational expression it is equivalent to (may be null)
        Returns:
        Registered relational expression

      • isValid

        protected boolean isValid​(Litmus litmus)
        Checks internal consistency.

      • registerAbstractRelationalRules

        public void registerAbstractRelationalRules()

      • getSubset

        public RelSubset getSubset​(RelNode rel)
        Returns the subset that a relational expression belongs to.
        Parameters:
        rel - Relational expression
        Returns:
        Subset it belongs to, or null if it is not registered

      • changeTraitsUsingConverters

        private RelNode changeTraitsUsingConverters​(RelNode rel,
                                            RelTraitSet toTraits,
                                            boolean allowAbstractConverters)

      • completeConversion

        private RelNode completeConversion​(RelNode rel,
                                   boolean allowInfiniteCostConverters,
                                   RelTraitSet toTraits,
                                   Expressions.FluentList<RelTraitDef> usedTraits)
        Converts traits using well-founded induction. We don't require that each conversion preserves all traits that have previously been converted, but if it changes "locked in" traits we'll try some other conversion.
        Parameters:
        rel - Relational expression
        allowInfiniteCostConverters - Whether to allow infinite converters
        toTraits - Target trait set
        usedTraits - Traits that have been locked in
        Returns:
        Converted relational expression

      • checkForSatisfiedConverters

        void checkForSatisfiedConverters​(RelSet set,
                                 RelNode rel)

      • setImportance

        public void setImportance​(RelNode rel,
                          double importance)
        Description copied from interface: RelOptPlanner
        Sets the importance of a relational expression.

        An important use of this method is when a RelOptRule has created a relational expression which is indisputably better than the original relational expression. The rule set the original relational expression's importance to zero, to reduce the search space. Pending rule calls are cancelled, and future rules will not fire.

        Specified by:
        setImportance in interface RelOptPlanner
        Overrides:
        setImportance in class AbstractRelOptPlanner
        Parameters:
        rel - Relational expression
        importance - Importance

      • dump

        public void dump​(java.io.PrintWriter pw)
        Dumps the internal state of this VolcanoPlanner to a writer.
        Parameters:
        pw - Print writer
        See Also:
        normalizePlan(String)

      • rename

        void rename​(RelNode rel)
        Re-computes the digest of a RelNode.

        Since a relational expression's digest contains the identifiers of its children, this method needs to be called when the child has been renamed, for example if the child's set merges with another.

        Parameters:
        rel - Relational expression

      • reregister

        void reregister​(RelSet set,
                RelNode rel)
        Registers a RelNode, which has already been registered, in a new RelSet.
        Parameters:
        set - Set
        rel - Relational expression

      • canonize

        private RelSubset canonize​(RelSubset subset)
        If a subset has one or more equivalent subsets (owing to a set having merged with another), returns the subset which is the leader of the equivalence class.
        Parameters:
        subset - Subset
        Returns:
        Leader of subset's equivalence class

      • fireRules

        void fireRules​(RelNode rel,
               boolean deferred)
        Fires all rules matched by a relational expression.
        Parameters:
        rel - Relational expression which has just been created (or maybe from the queue)
        deferred - If true, each time a rule matches, just add an entry to the queue.

      • fixUpInputs

        private boolean fixUpInputs​(RelNode rel)

      • forward2

        private static RelSet forward2​(RelSet s,
                               RelSet p)
        Moves forward two links, checking for a cycle at each.

      • forward1

        private static RelSet forward1​(RelSet s,
                               RelSet p)
        Moves forward one link, checking for a cycle.

      • registerImpl

        private RelSubset registerImpl​(RelNode rel,
                               RelSet set)
        Registers a new expression exp and queues up rule matches. If set is not null, makes the expression part of that equivalence set. If an identical expression is already registered, we don't need to register this one and nor should we queue up rule matches.
        Parameters:
        rel - relational expression to register. Must be either a RelSubset, or an unregistered RelNode
        set - set that rel belongs to, or null
        Returns:
        the equivalence-set

      • registerMetadataProviders

        public void registerMetadataProviders​(java.util.List<RelMetadataProvider> list)
        Description copied from interface: RelOptPlanner
        Gives this planner a chance to register one or more RelMetadataProviders in the chain which will be used to answer metadata queries.

        Planners which use their own relational expressions internally to represent concepts such as equivalence classes will generally need to supply corresponding metadata providers.

        Specified by:
        registerMetadataProviders in interface RelOptPlanner
        Overrides:
        registerMetadataProviders in class AbstractRelOptPlanner
        Parameters:
        list - receives planner's custom providers, if any

      • normalizePlan

        public static java.lang.String normalizePlan​(java.lang.String plan)
        Normalizes references to subsets within the string representation of a plan.

        This is useful when writing tests: it helps to ensure that tests don't break when an extra rule is introduced that generates a new subset and causes subsequent subset numbers to be off by one.

        For example,

        FennelAggRel.FENNEL_EXEC(child=Subset#17.FENNEL_EXEC,groupCount=1, EXPR$1=COUNT())
          FennelSortRel.FENNEL_EXEC(child=Subset#2.FENNEL_EXEC, key=[0], discardDuplicates=false)
            FennelCalcRel.FENNEL_EXEC( child=Subset#4.FENNEL_EXEC, expr#0..8={inputs}, expr#9=3456, DEPTNO=$t7, $f0=$t9)
              MockTableImplRel.FENNEL_EXEC( table=[CATALOG, SALES, EMP])

        becomes

        FennelAggRel.FENNEL_EXEC(child=Subset#{0}.FENNEL_EXEC, groupCount=1, EXPR$1=COUNT())
          FennelSortRel.FENNEL_EXEC(child=Subset#{1}.FENNEL_EXEC, key=[0], discardDuplicates=false)
            FennelCalcRel.FENNEL_EXEC( child=Subset#{2}.FENNEL_EXEC,expr#0..8={inputs},expr#9=3456,DEPTNO=$t7, $f0=$t9)
              MockTableImplRel.FENNEL_EXEC( table=[CATALOG, SALES, EMP])
        Parameters:
        plan - Plan
        Returns:
        Normalized plan

      • setLocked

        public void setLocked​(boolean locked)
        Sets whether this planner is locked. A locked planner does not accept new rules. addRule(org.apache.calcite.plan.RelOptRule) will do nothing and return false.
        Parameters:
        locked - Whether planner is locked