saffron.opt
Class RuleQueue

java.lang.Object
  |
  +--saffron.opt.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 class	RuleQueue.RelImportanceComparator Compares Rel objects according to their cached 'importance'.
private class	RuleQueue.RuleMatchImportanceComparator Compares RuleMatch objects according to their importance.

Field Summary

private ArrayList	matchList
private HashSet	matchNames
private VolcanoPlanner	planner
private Comparator	relImportanceComparator Compares relexps according to their cached 'importance'.
private BinaryHeap	relQueue
private HashSet	rels
private Comparator	ruleMatchImportanceComparator
(package private) HashMap	subsetImportances Maps RelSubset to Double.

Constructor Summary

(package private)

RuleQueue(VolcanoPlanner planner)

Method Summary

(package private) void	add(Rel rel) Registers that a relational expression's rules have not been fired.
(package private) void	add(RelSubset subset) Registers a subset, if it has not already been registered.
(package private) void	addMatch(RuleMatch match) Adds a rule match.
(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.
boolean	contains(Rel rel)
(package private) void	dump()
(package private) Rel	findCheapestMember(RelSubset childSubset)
double	getImportance(RelSet set) Computes the importance 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() Returns whether there is a rule match in the queue.
(package private) boolean	isEmpty()
(package private) Rel	pop() Returns the relational expression whose cost is highest
(package private) RuleMatch	popMatch() Removes the rule match with the highest importance, and returns it.
void	recompute(RelSubset subset)
(package private) boolean	remove(Rel rel)
private double	toDouble(Cost cost) Converts a cost to a scalar quantity.

Methods inherited from class java.lang.Object

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

Field Detail

planner

private final VolcanoPlanner planner

subsetImportances

HashMap subsetImportances

Maps RelSubset to Double.

relImportanceComparator

private Comparator relImportanceComparator

Compares relexps according to their cached 'importance'.

relQueue

private BinaryHeap relQueue

rels

private HashSet rels

ruleMatchImportanceComparator

private final Comparator ruleMatchImportanceComparator

matchList

private final ArrayList matchList

matchNames

private final HashSet matchNames

Constructor Detail

RuleQueue

RuleQueue(VolcanoPlanner planner)

Method Detail

add

void add(Rel rel)

Registers that a relational expression's rules have not been fired.

add

void add(RelSubset subset)

Registers a subset, if it has not already been registered.

remove

boolean remove(Rel rel)

isEmpty

boolean isEmpty()

pop

Rel pop()

Returns the relational expression whose cost is highest

Pre-condition:

!isEmpty()

Post-condition:

return != null

dump

void dump()

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 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)

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

toDouble

private double toDouble(Cost cost)

Converts a cost to a scalar quantity.

findCheapestMember

Rel findCheapestMember(RelSubset childSubset)

recompute

public void recompute(RelSubset subset)

contains

public boolean contains(Rel rel)

addMatch

void addMatch(RuleMatch match)

Adds a rule match.

popMatch

RuleMatch popMatch()

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

Pre-condition:

hasNextMatch()

hasNextMatch

public boolean hasNextMatch()

Returns whether there is a rule match in the queue.

getImportance

public double getImportance(RelSet set)

Computes the importance a set (which is that of its most important subset).