Class RuleQueue


  • class RuleQueue
    extends java.lang.Object
    Priority queue of relexps whose rules have not been called, and rule-matches which have not yet been acted upon.
    • Field Detail

      • LOGGER

        private static final org.slf4j.Logger LOGGER
      • ALL_RULES

        private static final java.util.Set<java.lang.String> ALL_RULES
      • ONE_MINUS_EPSILON

        private static final double ONE_MINUS_EPSILON
        Largest value which is less than one.
      • subsetImportances

        final java.util.Map<RelSubset,​java.lang.Double> subsetImportances
        The importance of each subset.
      • boostedSubsets

        final java.util.Set<RelSubset> boostedSubsets
        The set of RelSubsets whose importance is currently in an artificially raised state. Typically this only includes RelSubsets which have only logical RelNodes.
      • MATCH_COMPARATOR

        private static final java.util.Comparator<VolcanoRuleMatch> MATCH_COMPARATOR
        Sorts rule-matches into decreasing order of importance.
      • relImportanceOrdering

        private final com.google.common.collect.Ordering<RelSubset> relImportanceOrdering
        Compares relexps according to their cached 'importance'.
    • Method Detail

      • clear

        public void clear()
        Clear internal data structure for this rule queue.
      • getImportance

        public double getImportance​(RelSet set)
        Computes the importance of a set (which is that of its most important subset).
      • recompute

        public void recompute​(RelSubset subset,
                              boolean force)
        Recomputes the importance of the given RelSubset.
        Parameters:
        subset - RelSubset whose importance is to be recomputed
        force - if true, forces an importance update even if the subset has not been registered
      • boostImportance

        public void boostImportance​(java.util.Collection<RelSubset> subsets,
                                    double factor)
        Artificially boosts the importance of the given RelSubsets by a given factor.

        Iterates over the currently boosted RelSubsets and removes their importance boost, forcing a recalculation of the RelSubsets' importances (see recompute(RelSubset)).

        Once RelSubsets have been restored to their normal importance, the given RelSubsets have their importances boosted. A RelSubset's boosted importance is always less than 1.0 (and never equal to 1.0).

        Parameters:
        subsets - RelSubsets to boost importance (priority)
        factor - the amount to boost their importances (e.g., 1.25 increases importance by 25%)
      • updateImportance

        void updateImportance​(RelSubset subset,
                              java.lang.Double importance)
      • getImportance

        double getImportance​(RelSubset rel)
        Returns the importance of an equivalence class of relational expressions. Subset importances are held in a lookup table, and importance changes gradually propagate through that table.

        If a subset in the same set but with a different calling convention is deemed to be important, then this subset has at least half of its importance. (This rule is designed to encourage conversions to take place.)

      • computeImportance

        double computeImportance​(RelSubset subset)
        Computes the importance of a node. Importance is defined as follows:
        • the root RelSubset has an importance of 1
        • the importance of any other subset is the max of its importance to its parents
        • The importance of children is pro-rated according to the cost of the children. Consider a node which has a cost of 3, and children with costs of 2 and 5. The total cost is 10. If the node has an importance of .5, then the children will have importance of .1 and .25. The retains .15 importance points, to reflect the fact that work needs to be done on the node's algorithm.

        The formula for the importance I of node n is:

        In = Maxparents p of n{Ip . W n, p}

        where Wn, p, the weight of n within its parent p, is

        Wn, p = Costn / (SelfCostp + Costn0 + ... + Costnk)
      • dump

        private void dump()
      • dump

        private void dump​(java.io.PrintWriter pw)
      • popMatch

        VolcanoRuleMatch popMatch​(VolcanoPlannerPhase phase)
        Removes the rule match with the highest importance, and returns it.

        Returns null if there are no more matches.

        Note that the VolcanoPlanner may still decide to reject rule matches which have become invalid, say if one of their operands belongs to an obsolete set or has importance=0.

        Throws:
        java.lang.AssertionError - if this method is called with a phase previously marked as completed via phaseCompleted(VolcanoPlannerPhase).
      • skipMatch

        private boolean skipMatch​(VolcanoRuleMatch match)
        Returns whether to skip a match. This happens if any of the RelNodes have importance zero.
      • checkDuplicateSubsets

        private void checkDuplicateSubsets​(java.util.Deque<RelSubset> subsets,
                                           RelOptRuleOperand operand,
                                           RelNode[] rels)
        Recursively checks whether there are any duplicate subsets along any path from root of the operand tree to one of the leaves.

        It is OK for a match to have duplicate subsets if they are not on the same path. For example,

           Join
          /   \
         X     X
         

        is a valid match.

        Throws:
        Util.FoundOne - on match
      • computeImportanceOfChild

        private double computeImportanceOfChild​(RelMetadataQuery mq,
                                                RelSubset child,
                                                RelSubset parent)
        Returns the importance of a child to a parent. This is defined by the importance of the parent, pro-rated by the cost of the child. For example, if the parent has importance = 0.8 and cost 100, then a child with cost 50 will have importance 0.4, and a child with cost 25 will have importance 0.2.
      • toDouble

        private double toDouble​(RelOptCost cost)
        Converts a cost to a scalar quantity.
      • computeOneMinusEpsilon

        private static double computeOneMinusEpsilon()