net.sf.saffron.opt
Class RuleQueue

java.lang.Object
  |
  +--net.sf.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 SaffronRel objects according to their cached 'importance'.
private class	RuleQueue.RuleMatchImportanceComparator Compares VolcanoRuleMatch 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(RelSubset subset) Registers a subset, if it has not already been registered.
(package private) void	add(SaffronRel rel) Registers that a relational expression's rules have not been fired.
(package private) void	addMatch(VolcanoRuleMatch 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(SaffronRel rel)
(package private) void	dump()
(package private) SaffronRel	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) SaffronRel	pop() Returns the relational expression whose cost is highest
(package private) VolcanoRuleMatch	popMatch() Removes the rule match with the highest importance, and returns it.
void	recompute(RelSubset subset)
(package private) boolean	remove(SaffronRel rel)
private double	toDouble(PlanCost 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

subsetImportances

HashMap subsetImportances

Maps RelSubset to Double.

matchList

private final ArrayList matchList

ruleMatchImportanceComparator

private final Comparator ruleMatchImportanceComparator

matchNames

private final HashSet matchNames

planner

private final VolcanoPlanner planner

relImportanceComparator

private Comparator relImportanceComparator

Compares relexps according to their cached 'importance'.

relQueue

private BinaryHeap relQueue

rels

private HashSet rels

Constructor Detail

RuleQueue

RuleQueue(VolcanoPlanner planner)

Method Detail

getImportance

public double getImportance(RelSet set)

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

contains

public boolean contains(SaffronRel rel)

hasNextMatch

public boolean hasNextMatch()

Returns whether there is a rule match in the queue.

recompute

public void recompute(RelSubset subset)

isEmpty

boolean isEmpty()

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

add

void add(SaffronRel 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.

addMatch

void addMatch(VolcanoRuleMatch match)

Adds a rule 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

void dump()

findCheapestMember

SaffronRel findCheapestMember(RelSubset childSubset)

pop

SaffronRel pop()

Returns the relational expression whose cost is highest

Pre-condition:

!isEmpty()

Post-condition:

return != null

popMatch

VolcanoRuleMatch popMatch()

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

Pre-condition:

hasNextMatch()

remove

boolean remove(SaffronRel rel)

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(PlanCost cost)

Converts a cost to a scalar quantity.