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)

SourceForge.net_Logo