saffron.opt
Class VolcanoPlanner

java.lang.Object
  |
  +--saffron.opt.VolcanoPlanner

All Implemented Interfaces:

Planner

class VolcanoPlanner

extends Object

implements Planner

VolcanoPlanner optimizes queries by transforming expressions selectively according to a dynamic programming algorithm.

Nested Class Summary

private static class

VolcanoPlanner.DeferringRuleCall A rule call which defers its actions.

Field Summary

(package private) ArrayList	allOperands List of all operands of all rules.
(package private) ArrayList	allSets List of all sets.
private ArrayList	callingConventions
private Graph	conversionGraph
private MultiMap	mapArcToConverterRule For a given source/target convention, there may be several possible conversion rules.
private HashMap	mapDescToRule Maps rule description to rule, just to ensure that rules' descriptions are unique.
(package private) HashMap	mapDigestToRel Canonical map from digest to the unique relational expression with that digest.
(package private) HashMap	mapRel2Subset Map each registered expression (Rel) to its equivalence set (RelSubset).
private int	nextSetId
private int	registerCount Incremented every time a relational expression is registered or two sets are merged.
(package private) HashSet	registeredSchemas List of all schemas which have been registered.
protected RelSubset	root
(package private) RuleQueue	ruleQueue Holds rule calls waiting to be fired.

Constructor Summary

(package private)

VolcanoPlanner() Creates a VolcanoPlanner.

Method Summary

void	addCallingConvention(CallingConvention convention) Registers a calling convention.
void	addRule(Rule rule) Registers a rule.
boolean	canConvert(CallingConvention fromConvention, CallingConvention toConvention)
private RelSubset	canonize(RelSubset subset)
Rel	changeConvention(Rel rel, CallingConvention toConvention) Changes a relational expression to an equivalent one of a different calling convention.
private Rel	changeConvention(Rel rel, Graph.Arc arc) Tries to convert a relational expression to the target convention of an arc.
(package private) Rel	changeConventionUsingConverters(Rel rel, CallingConvention toConvention)
(package private) void	checkForSatisfiedConverters(RelSet set, Rel rel)
Planner	chooseDelegate() Negotiates an appropriate planner to deal with distributed queries.
(package private) void	dump()
Rel	findBestExp() Find the most efficient expression to implement this query.
private RelSubset	findBestPlan_old(RelSubset subset, Cost targetCost)
private void	fireRules(Rel rel, boolean deferred) Fire all rules matched by a relational expression.
private void	fireRulesForSubset(RelSubset childSubset)
private boolean	fixupInputs(Rel rel)
Operand[]	getConversionOperands(CallingConvention toConvention)
(package private) Cost	getCost(Rel rel) Finds the cost of a node.
Rel	getRoot()
RelSet	getSet(Rel rel) Find an expression's equivalence set.
(package private) RelSubset	getSubset(Rel rel)
(package private) RelSubset	getSubset(Rel rel, CallingConvention convention)
(package private) void	init() Initializes the rule set.
boolean	isRegistered(Rel rel)
Cost	makeCost(double dRows, double dCpu, double dIo) Create a cost object.
Cost	makeHugeCost() Create a cost object representing infinite cost.
Cost	makeInfiniteCost() Create a cost object representing infinite cost.
Cost	makeTinyCost() Create a cost object representing a small positive cost.
Cost	makeZeroCost() Create a cost object representing zero cost.
private void	merge(RelSet set, RelSet set2)
private Cost	optimize(Rel rel, Cost targetCost) By optimizing its children, find the best implementation of relational expression rel.
Rel	register(Rel rel, Rel equivRel) Registers a relational expression in the expression bank.
private RelSubset	registerImpl(Rel rel, RelSet set) Register a new expression exp.
void	registerSchema(Schema schema) Tells this planner that a schema exists.
private RelSubset	registerSubset(RelSet set, RelSubset subset)
(package private) void	rename(Rel rel)
(package private) void	reregister(RelSet set, Rel rel)
void	setRoot(Rel rel)

Methods inherited from class java.lang.Object

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

Field Detail

mapRel2Subset

HashMap mapRel2Subset

Map each registered expression (Rel) to its equivalence set (RelSubset).

mapDigestToRel

HashMap mapDigestToRel

Canonical map from digest to the unique relational expression with that digest.

allOperands

ArrayList allOperands

List of all operands of all rules. Any operand can be an 'entry point' to a rule call, when a relexp is registered which matches the.

allSets

ArrayList allSets

List of all sets. Used only for debugging.

nextSetId

private int nextSetId

registeredSchemas

HashSet registeredSchemas

List of all schemas which have been registered.

registerCount

private int registerCount

Incremented every time a relational expression is registered or two sets are merged. Tells us whether anything is going on.

conversionGraph

private final Graph conversionGraph

mapArcToConverterRule

private final MultiMap mapArcToConverterRule

For a given source/target convention, there may be several possible conversion rules. Maps Graph.Arc to a collection of ConverterRule.

root

protected RelSubset root

ruleQueue

RuleQueue ruleQueue

Holds rule calls waiting to be fired.

callingConventions

private final ArrayList callingConventions

mapDescToRule

private final HashMap mapDescToRule

Maps rule description to rule, just to ensure that rules' descriptions are unique.

Constructor Detail

VolcanoPlanner

VolcanoPlanner()

Creates a VolcanoPlanner. You must now call init().

Method Detail

setRoot

public void setRoot(Rel rel)

Specified by:

setRoot in interface Planner

getRoot

public Rel getRoot()

Specified by:

getRoot in interface Planner

chooseDelegate

public Planner chooseDelegate()

Description copied from interface: Planner

Negotiates an appropriate planner to deal with distributed queries. The idea is that the schemas decide among themselves which has the most knowledge. Right now, the local planner retains control.

Specified by:

chooseDelegate in interface Planner

addRule

public void addRule(Rule rule)

Description copied from interface: Planner

Registers a rule.

Specified by:

addRule in interface Planner

init

void init()

Initializes the rule set.

addCallingConvention

public void addCallingConvention(CallingConvention convention)

Description copied from interface: Planner

Registers a calling convention.

Specified by:

addCallingConvention in interface Planner

makeCost

public Cost makeCost(double dRows,
                     double dCpu,
                     double dIo)

Description copied from interface: Planner

Create a cost object.

Specified by:

makeCost in interface Planner

makeInfiniteCost

public Cost makeInfiniteCost()

Description copied from interface: Planner

Create a cost object representing infinite cost.

Specified by:

makeInfiniteCost in interface Planner

makeHugeCost

public Cost makeHugeCost()

Description copied from interface: Planner

Create a cost object representing infinite cost.

Specified by:

makeHugeCost in interface Planner

makeZeroCost

public Cost makeZeroCost()

Description copied from interface: Planner

Create a cost object representing zero cost.

Specified by:

makeZeroCost in interface Planner

makeTinyCost

public Cost makeTinyCost()

Description copied from interface: Planner

Create a cost object representing a small positive cost.

Specified by:

makeTinyCost in interface Planner

changeConvention

public Rel changeConvention(Rel rel,
                            CallingConvention toConvention)

Description copied from interface: Planner

Changes a relational expression to an equivalent one of a different calling convention. The return is never null, but may be abstract.

Specified by:

changeConvention in interface Planner

fireRules

private void fireRules(Rel rel,
                       boolean deferred)

Fire all rules matched by a relational expression.

Parameters:

rel - Relational expression which has just been created (or maybe from the queue)

deferred - If true, each time a rule matches, just add an entry to the queue.

fireRulesForSubset

private void fireRulesForSubset(RelSubset childSubset)

changeConventionUsingConverters

Rel changeConventionUsingConverters(Rel rel,
                                    CallingConvention toConvention)

changeConvention

private Rel changeConvention(Rel rel,
                             Graph.Arc arc)

Tries to convert a relational expression to the target convention of an arc.

findBestExp

public Rel findBestExp()

Description copied from interface: Planner

Find the most efficient expression to implement this query.

Specified by:

findBestExp in interface Planner

dump

void dump()

findBestPlan_old

private RelSubset findBestPlan_old(RelSubset subset,
                                   Cost targetCost)

canonize

private RelSubset canonize(RelSubset subset)

fixupInputs

private boolean fixupInputs(Rel rel)

optimize

private Cost optimize(Rel rel,
                      Cost targetCost)

By optimizing its children, find the best implementation of relational expression rel. The cost is bounded by targetCost.

getCost

Cost getCost(Rel rel)

Finds the cost of a node. Similar to optimize(saffron.rel.Rel, saffron.opt.Cost), but does not create any expressions.

registerSchema

public void registerSchema(Schema schema)

Description copied from interface: Planner

Tells this planner that a schema exists. This is the schema's chance to tell the planner about all of the special transformation rules.

Specified by:

registerSchema in interface Planner

register

public Rel register(Rel rel,
                    Rel equivRel)

Description copied from interface: Planner

Registers a relational expression in the expression bank. After it has been registered, you may not modify it.

Specified by:

register in interface Planner

Parameters:

rel - Relational expression to register

equivRel - Relational expression it is equivalent to (may be null)

Returns:

the same expression, or an equivalent existing expression

registerImpl

private RelSubset registerImpl(Rel rel,
                               RelSet set)

Register a new expression exp. If set is not null, make the expression part of that equivalence set. If an identical expression is already registered, we don't need to register this one.

Parameters:

rel - relational expression to register

set - set that rel belongs to, or null

Returns:

the equivalence-set

checkForSatisfiedConverters

void checkForSatisfiedConverters(RelSet set,
                                 Rel rel)

registerSubset

private RelSubset registerSubset(RelSet set,
                                 RelSubset subset)

merge

private void merge(RelSet set,
                   RelSet set2)

reregister

void reregister(RelSet set,
                Rel rel)

getSet

public RelSet getSet(Rel rel)

Find an expression's equivalence set. If the expression is not registered, return null.

getSubset

RelSubset getSubset(Rel rel)

getSubset

RelSubset getSubset(Rel rel,
                    CallingConvention convention)

rename

void rename(Rel rel)

getConversionOperands

public Operand[] getConversionOperands(CallingConvention toConvention)

isRegistered

public boolean isRegistered(Rel rel)

canConvert

public boolean canConvert(CallingConvention fromConvention,
                          CallingConvention toConvention)