Class RuleQueue
- java.lang.Object
-
- org.apache.calcite.plan.volcano.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
RuleQueue.PhaseMatchList
PhaseMatchList represents a set ofrule-matches
for a particularphase of the planner's execution
.private class
RuleQueue.RelImportanceComparator
ComparesRelNode
objects according to their cached 'importance'.private static class
RuleQueue.RuleMatchImportanceComparator
ComparesVolcanoRuleMatch
objects according to their importance.
-
Field Summary
Fields Modifier and Type Field Description private static java.util.Set<java.lang.String>
ALL_RULES
(package private) java.util.Set<RelSubset>
boostedSubsets
The set of RelSubsets whose importance is currently in an artificially raised state.private static org.slf4j.Logger
LOGGER
private static java.util.Comparator<VolcanoRuleMatch>
MATCH_COMPARATOR
Sorts rule-matches into decreasing order of importance.(package private) java.util.Map<VolcanoPlannerPhase,RuleQueue.PhaseMatchList>
matchListMap
Map ofVolcanoPlannerPhase
to a list of rule-matches.private static double
ONE_MINUS_EPSILON
Largest value which is less than one.private java.util.Map<VolcanoPlannerPhase,java.util.Set<java.lang.String>>
phaseRuleMapping
Maps aVolcanoPlannerPhase
to a set of rule names.private VolcanoPlanner
planner
private com.google.common.collect.Ordering<RelSubset>
relImportanceOrdering
Compares relexps according to their cached 'importance'.(package private) java.util.Map<RelSubset,java.lang.Double>
subsetImportances
The importance of each subset.
-
Constructor Summary
Constructors Constructor Description RuleQueue(VolcanoPlanner planner)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
addMatch(VolcanoRuleMatch match)
Adds a rule match.void
boostImportance(java.util.Collection<RelSubset> subsets, double factor)
Artificially boosts the importance of the givenRelSubset
s by a given factor.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.void
clear()
Clear internal data structure for this rule queue.(package private) double
computeImportance(RelSubset subset)
Computes the importance of a node.private double
computeImportanceOfChild(RelMetadataQuery mq, RelSubset child, RelSubset parent)
Returns the importance of a child to a parent.private static double
computeOneMinusEpsilon()
private void
dump()
private void
dump(java.io.PrintWriter pw)
double
getImportance(RelSet set)
Computes the importance of a set (which is that of its most important subset).(package private) double
getImportance(RelSubset rel)
Returns the importance of an equivalence class of relational expressions.void
phaseCompleted(VolcanoPlannerPhase phase)
Removes therule-match list
for the given planner phase.(package private) VolcanoRuleMatch
popMatch(VolcanoPlannerPhase phase)
Removes the rule match with the highest importance, and returns it.void
recompute(RelSubset subset)
Equivalent torecompute(subset, false)
.void
recompute(RelSubset subset, boolean force)
Recomputes the importance of the given RelSubset.private boolean
skipMatch(VolcanoRuleMatch match)
Returns whether to skip a match.private double
toDouble(RelOptCost cost)
Converts a cost to a scalar quantity.(package private) void
updateImportance(RelSubset subset, java.lang.Double importance)
-
-
-
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.
-
matchListMap
final java.util.Map<VolcanoPlannerPhase,RuleQueue.PhaseMatchList> matchListMap
Map ofVolcanoPlannerPhase
to a list of rule-matches. Initially, there is an emptyRuleQueue.PhaseMatchList
for each planner phase. As the planner invokesaddMatch(VolcanoRuleMatch)
the rule-match is added to the appropriate PhaseMatchList(s). As the planner completes phases, the matching entry is removed from this list to avoid unused work.
-
MATCH_COMPARATOR
private static final java.util.Comparator<VolcanoRuleMatch> MATCH_COMPARATOR
Sorts rule-matches into decreasing order of importance.
-
planner
private final VolcanoPlanner planner
-
relImportanceOrdering
private final com.google.common.collect.Ordering<RelSubset> relImportanceOrdering
Compares relexps according to their cached 'importance'.
-
phaseRuleMapping
private final java.util.Map<VolcanoPlannerPhase,java.util.Set<java.lang.String>> phaseRuleMapping
Maps aVolcanoPlannerPhase
to a set of rule names. Named rules may be invoked in their corresponding phase.
-
-
Constructor Detail
-
RuleQueue
RuleQueue(VolcanoPlanner planner)
-
-
Method Detail
-
clear
public void clear()
Clear internal data structure for this rule queue.
-
phaseCompleted
public void phaseCompleted(VolcanoPlannerPhase phase)
Removes therule-match list
for the given planner phase.
-
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 recomputedforce
- if true, forces an importance update even if the subset has not been registered
-
recompute
public void recompute(RelSubset subset)
Equivalent torecompute(subset, false)
.
-
boostImportance
public void boostImportance(java.util.Collection<RelSubset> subsets, double factor)
Artificially boosts the importance of the givenRelSubset
s 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.)
-
addMatch
void addMatch(VolcanoRuleMatch match)
Adds a rule match. The rule-matches are automatically added to all existingper-phase rule-match lists
which allow the rule referenced by the match.
-
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 sum 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 = Sumparents 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)
- the root
-
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 viaphaseCompleted(VolcanoPlannerPhase)
.
-
skipMatch
private boolean skipMatch(VolcanoRuleMatch match)
Returns whether to skip a match. This happens if any of theRelNode
s 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()
-
-