net.sf.saffron.opt
Class VolcanoPlanner

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

All Implemented Interfaces:

SaffronPlanner

public class VolcanoPlanner

extends Object

implements SaffronPlanner

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.
protected boolean	ambitious If true, the planner keeps applying rules as long as they continue to reduce the cost.
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 (SaffronRel) 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

VolcanoPlanner()
Creates a uninitialized VolcanoPlanner.

Method Summary

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

Methods inherited from class java.lang.Object

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

Field Detail

root

protected RelSubset root

ambitious

protected boolean ambitious

If true, the planner keeps applying rules as long as they continue to reduce the cost. If false, the planner terminates as soon as it has found any implementation, no matter how expensive. The default is false due to unresolved bugs with various rules.

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.

mapDigestToRel

HashMap mapDigestToRel

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

mapRel2Subset

HashMap mapRel2Subset

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

registeredSchemas

HashSet registeredSchemas

List of all schemas which have been registered.

ruleQueue

RuleQueue ruleQueue

Holds rule calls waiting to be fired.

callingConventions

private final ArrayList callingConventions

conversionGraph

private final Graph conversionGraph

mapDescToRule

private final HashMap mapDescToRule

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

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

nextSetId

private int nextSetId

registerCount

private int registerCount

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

Constructor Detail

VolcanoPlanner

public VolcanoPlanner()

Creates a uninitialized VolcanoPlanner. To fully initialize it, the caller must register the desired set of relations, rules, and calling conventions.

Method Detail

getConversionOperands

public RuleOperand[] getConversionOperands(CallingConvention toConvention)

isRegistered

public boolean isRegistered(SaffronRel rel)

setRoot

public void setRoot(SaffronRel rel)

Specified by:

setRoot in interface SaffronPlanner

getRoot

public SaffronRel getRoot()

Specified by:

getRoot in interface SaffronPlanner

getSet

public RelSet getSet(SaffronRel rel)

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

addCallingConvention

public void addCallingConvention(CallingConvention convention)

Description copied from interface: SaffronPlanner

Registers a calling convention.

Specified by:

addCallingConvention in interface SaffronPlanner

addRule

public void addRule(VolcanoRule rule)

Description copied from interface: SaffronPlanner

Registers a rule.

Specified by:

addRule in interface SaffronPlanner

canConvert

public boolean canConvert(CallingConvention fromConvention,
                          CallingConvention toConvention)

changeConvention

public SaffronRel changeConvention(SaffronRel rel,
                                   CallingConvention toConvention)

Description copied from interface: SaffronPlanner

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 SaffronPlanner

chooseDelegate

public SaffronPlanner chooseDelegate()

Description copied from interface: SaffronPlanner

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 SaffronPlanner

findBestExp

public SaffronRel findBestExp()

Description copied from interface: SaffronPlanner

Find the most efficient expression to implement this query.

Specified by:

findBestExp in interface SaffronPlanner

makeCost

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

Description copied from interface: SaffronPlanner

Create a cost object.

Specified by:

makeCost in interface SaffronPlanner

makeHugeCost

public PlanCost makeHugeCost()

Description copied from interface: SaffronPlanner

Create a cost object representing an enormous non-infinite cost.

Specified by:

makeHugeCost in interface SaffronPlanner

makeInfiniteCost

public PlanCost makeInfiniteCost()

Description copied from interface: SaffronPlanner

Create a cost object representing infinite cost.

Specified by:

makeInfiniteCost in interface SaffronPlanner

makeTinyCost

public PlanCost makeTinyCost()

Description copied from interface: SaffronPlanner

Create a cost object representing a small positive cost.

Specified by:

makeTinyCost in interface SaffronPlanner

makeZeroCost

public PlanCost makeZeroCost()

Description copied from interface: SaffronPlanner

Create a cost object representing zero cost.

Specified by:

makeZeroCost in interface SaffronPlanner

register

public SaffronRel register(SaffronRel rel,
                           SaffronRel equivRel)

Description copied from interface: SaffronPlanner

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

Specified by:

register in interface SaffronPlanner

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

registerAbstractRelationalRules

public void registerAbstractRelationalRules()

registerAbstractRels

public void registerAbstractRels()

registerSchema

public void registerSchema(SaffronSchema schema)

Description copied from interface: SaffronPlanner

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 SaffronPlanner

getCost

PlanCost getCost(SaffronRel rel)

Finds the cost of a node. Similar to optimize(net.sf.saffron.rel.SaffronRel, net.sf.saffron.opt.PlanCost), but does not create any expressions.

getSubset

RelSubset getSubset(SaffronRel rel)

getSubset

RelSubset getSubset(SaffronRel rel,
                    CallingConvention convention)

changeConventionUsingConverters

SaffronRel changeConventionUsingConverters(SaffronRel rel,
                                           CallingConvention toConvention)

checkForSatisfiedConverters

void checkForSatisfiedConverters(RelSet set,
                                 SaffronRel rel)

dump

void dump()

rename

void rename(SaffronRel rel)

reregister

void reregister(RelSet set,
                SaffronRel rel)

canonize

private RelSubset canonize(RelSubset subset)

changeConvention

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

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

findBestPlan_old

private RelSubset findBestPlan_old(RelSubset subset,
                                   PlanCost targetCost)

fireRules

private void fireRules(SaffronRel 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)

fixupInputs

private boolean fixupInputs(SaffronRel rel)

merge

private void merge(RelSet set,
                   RelSet set2)

optimize

private PlanCost optimize(SaffronRel rel,
                          PlanCost targetCost)

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

registerImpl

private RelSubset registerImpl(SaffronRel 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

registerSubset

private RelSubset registerSubset(RelSet set,
                                 RelSubset subset)