org.eigenbase.relopt.volcano
Class RuleQueue

java.lang.Object
  org.eigenbase.relopt.volcano.RuleQueue

 class RuleQueue
extends Object

Priority queue of relexps whose rules have not been called, and rule-matches which have not yet been acted upon.

Nested Class Summary

private static class	RuleQueue.PhaseMatchList PhaseMatchList represents a set of rule-matches for a particular phase of the planner's execution.
private class	RuleQueue.RelImportanceComparator Compares RelNode objects according to their cached 'importance'.
private class	RuleQueue.RuleMatchImportanceComparator Compares VolcanoRuleMatch objects according to their importance.

Field Summary

private static Set<String>	allRules
(package private) Set<RelSubset>	boostedSubsets The set of RelSubsets whose importance is currently in an artificially raised state.
(package private) Map<VolcanoPlannerPhase,RuleQueue.PhaseMatchList>	matchListMap Map of VolcanoPlannerPhase to a list of rule-matches.
private static double	OneMinusEpsilon Largest value which is less than one.
private Map<VolcanoPlannerPhase,Set<String>>	phaseRuleMapping
private VolcanoPlanner	planner
private Comparator<RelSubset>	relImportanceComparator Compares relexps according to their cached 'importance'.
private Comparator<VolcanoRuleMatch>	ruleMatchImportanceComparator Sorts rule-matches into decreasing order of importance.
(package private) Map<RelSubset,Double>	subsetImportances The importance of each subset.
private static Logger	tracer

Constructor Summary

RuleQueue(VolcanoPlanner planner)

Method Summary

(package private) void	addMatch(VolcanoRuleMatch match) Adds a rule match.
void	boostImportance(Collection<RelSubset> subsets, double factor) Artificially boosts the importance of the given RelSubsets by a given factor.
(package private) static int	compareRels(RelNode[] rels0, RelNode[] rels1)
(package private) double	computeImportance(RelSubset subset) Computes the importance of a node.
private double	computeImportanceOfChild(RelSubset child, RelSubset parent) Returns the importance of a child to a parent.
private static double	computeOneMinusEpsilon()
private void	dump()
private void	dump(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.
boolean	hasNextMatch(VolcanoPlannerPhase phase) Returns whether there is a rule match in the queue for the given phase.
void	phaseCompleted(VolcanoPlannerPhase phase) Removes the rule-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 to recompute(subset, false).
void	recompute(RelSubset subset, boolean force) Recomputes the importance of the given RelSubset.
private double	toDouble(RelOptCost cost) Converts a cost to a scalar quantity.
(package private) void	updateImportance(RelSubset subset, Double importance)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

tracer

private static final Logger tracer

allRules

private static final Set<String> allRules

OneMinusEpsilon

private static final double OneMinusEpsilon

Largest value which is less than one.

subsetImportances

final Map<RelSubset,Double> subsetImportances

The importance of each subset.

boostedSubsets

final 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 Map<VolcanoPlannerPhase,RuleQueue.PhaseMatchList> matchListMap

Map of VolcanoPlannerPhase to a list of rule-matches. Initially, there is an empty RuleQueue.PhaseMatchList for each planner phase. As the planner invokes addMatch(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.

ruleMatchImportanceComparator

private final Comparator<VolcanoRuleMatch> ruleMatchImportanceComparator

Sorts rule-matches into decreasing order of importance.

planner

private final VolcanoPlanner planner

relImportanceComparator

private final Comparator<RelSubset> relImportanceComparator

Compares relexps according to their cached 'importance'.

phaseRuleMapping

private final Map<VolcanoPlannerPhase,Set<String>> phaseRuleMapping

Constructor Detail

RuleQueue

RuleQueue(VolcanoPlanner planner)

Method Detail

phaseCompleted

public void phaseCompleted(VolcanoPlannerPhase phase)

Removes the rule-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).

hasNextMatch

public boolean hasNextMatch(VolcanoPlannerPhase phase)

Returns whether there is a rule match in the queue for the given phase.

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:

NullPointerException - if this method is called with a phase previously marked as completed via phaseCompleted(VolcanoPlannerPhase).

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

recompute

public void recompute(RelSubset subset)

Equivalent to recompute(subset, false).

boostImportance

public void boostImportance(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,
                      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 existing per-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:

I_n = Sum_{parents p of n}{I_p . W _{n, p}}

where W_{n, p}, the weight of n within its parent p, is

W_{n, p} = Cost_n / (SelfCost_p + Cost_n0 + ... + Cost_nk)

dump

private void dump()

dump

private void dump(PrintWriter pw)

popMatch

VolcanoRuleMatch popMatch(VolcanoPlannerPhase phase)

Removes the rule match with the highest importance, and returns it.

"Precondition:"

hasNextMatch()

computeImportanceOfChild

private double computeImportanceOfChild(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.

compareRels

static int compareRels(RelNode[] rels0,
                       RelNode[] rels1)

computeOneMinusEpsilon

private static double computeOneMinusEpsilon()