org.eigenbase.relopt.volcano
Class VolcanoPlanner

java.lang.Object
  org.eigenbase.relopt.AbstractRelOptPlanner
      org.eigenbase.relopt.volcano.VolcanoPlanner

All Implemented Interfaces:

RelOptPlanner

Direct Known Subclasses:

FarragoDefaultPlanner

public class VolcanoPlanner
extends AbstractRelOptPlanner

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

private List<RelOptRuleOperand>	allOperands List of all operands of all rules.
(package private) List<RelSet>	allSets List of all sets.
protected boolean	ambitious If true, the planner keeps applying rules as long as they continue to reduce the cost.
protected static double	CostImprovement
protected boolean	impatient If true, and if ambitious is true, the planner waits a finite number of iterations for the cost to improve.
(package private) RelOptListener	listener Listener for this planner, or null if none set.
private Map<String,RelNode>	mapDigestToRel Canonical map from digest to the unique relational expression with that digest.
private IdentityHashMap<RelNode,RelSubset>	mapRel2Subset Map each registered expression (RelNode) to its equivalence set (RelSubset).
private int	nextSetId
private String	originalRootString Dump of the root relational expression, as it was before any rules were applied.
private int	registerCount Incremented every time a relational expression is registered or two sets are merged.
private Set<RelOptSchema>	registeredSchemas List of all schemas which have been registered.
(package private) Map<RelNode,Double>	relImportances The importance of relational expressions.
protected RelSubset	root
(package private) RuleQueue	ruleQueue Holds rule calls waiting to be fired.
protected Set<RelOptRule>	ruleSet Set of all registered rules.
private List<RelTraitDef>	traitDefs Holds the currently registered RelTraitDefs.

Fields inherited from interface org.eigenbase.relopt.RelOptPlanner

tracer

Constructor Summary

VolcanoPlanner()
Creates a uninitialized VolcanoPlanner.

Method Summary

void	addListener(RelOptListener newListener) Adds a listener to this planner.
boolean	addRelTraitDef(RelTraitDef relTraitDef) Registers a rel trait definition.
boolean	addRule(RelOptRule rule) Registers a rule.
boolean	canConvert(RelTraitSet fromTraits, RelTraitSet toTraits)
private RelSubset	canonize(RelSubset subset) If a subset has one or more equivalent subsets (owing to a set having merged with another), returns the subset which is the leader of the equivalence class.
RelNode	changeTraits(RelNode rel, RelTraitSet toTraits) Changes a relational expression to an equivalent one with a different set of traits.
(package private) RelNode	changeTraitsUsingConverters(RelNode rel, RelTraitSet toTraits)
private RelNode	changeTraitsUsingConverters(RelNode rel, RelTraitSet toTraits, boolean allowAbstractConverters)
(package private) void	checkForSatisfiedConverters(RelSet set, RelNode rel)
RelOptPlanner	chooseDelegate() Negotiates an appropriate planner to deal with distributed queries.
private void	clearImportanceBoost() Clear all importance boosts.
void	dump(PrintWriter pw) Dumps the internal state of this VolcanoPlanner to a writer.
RelNode	ensureRegistered(RelNode rel, RelNode equivRel) Registers a relational expression if it is not already registered.
RelNode	findBestExp() Finds the most efficient expression to implement the query given via setRoot(RelNode).
(package private) void	fireRules(RelNode rel, boolean deferred) Fires all rules matched by a relational expression.
private boolean	fixupInputs(RelNode rel)
RelOptRuleOperand[]	getConversionOperands(CallingConvention toConvention)
RelOptCost	getCost(RelNode rel) Computes the cost of a RelNode.
JavaRelImplementor	getJavaRelImplementor(RelNode rel) Retrieves an implementor appropriate for the context in which this planner was created.
protected VolcanoPlannerPhaseRuleMappingInitializer	getPhaseRuleMappingInitializer()
long	getRelMetadataTimestamp(RelNode rel) Gets a timestamp for a given rel's metadata.
RelNode	getRoot() Returns the root node of this query.
RelSet	getSet(RelNode rel) Finds an expression's equivalence set.
RelSubset	getSubset(RelNode rel) Returns the subset that a relational expression belongs to.
RelSubset	getSubset(RelNode rel, RelTraitSet traits)
RelSubset	getSubset(RelNode rel, RelTraitSet traits, boolean createIfMissing)
private void	injectImportanceBoost() Finds RelSubsets in the plan that contain only rels of CallingConvention.NONE and boosts their importance by 25%.
boolean	isRegistered(RelNode rel) Determines whether a relational expression has been registered.
RelOptCost	makeCost(double dRows, double dCpu, double dIo) Creates a cost object.
RelOptCost	makeHugeCost() Creates a cost object representing an enormous non-infinite cost.
RelOptCost	makeInfiniteCost() Creates a cost object representing infinite cost.
RelOptCost	makeTinyCost() Creates a cost object representing a small positive cost.
RelOptCost	makeZeroCost() Creates a cost object representing zero cost.
private void	merge(RelSet set, RelSet set2)
static String	normalizePlan(String plan) Normalizes references to subsets within the string representation of a plan.
RelNode	register(RelNode rel, RelNode equivRel) Registers a relational expression in the expression bank.
void	registerAbstractRelationalRules()
private RelSubset	registerImpl(RelNode rel, RelSet set) Registers a new expression exp and queues up rule matches.
void	registerMetadataProviders(ChainedRelMetadataProvider chain) Gives this planner a chance to register one or more RelMetadataProviders in the chain which will be used to answer metadata queries.
void	registerSchema(RelOptSchema schema) Tells this planner that a schema exists.
private RelSubset	registerSubset(RelSet set, RelSubset subset)
boolean	removeRule(RelOptRule rule) Removes a rule.
(package private) void	rename(RelNode rel) Re-computes the digest of a RelNode.
(package private) void	reregister(RelSet set, RelNode rel) Registers a RelNode, which has already been registered, in a new RelSet.
void	setImportance(RelNode rel, double importance) Sets the importance of a relational expression.
private void	setInitialImportance()
void	setRoot(RelNode rel) Sets the root node of this query.
protected void	validate() Checks internal consistency.

Methods inherited from class org.eigenbase.relopt.AbstractRelOptPlanner

checkCancel, fireRule, getListener, getRuleByDescription, isRuleExcluded, mapRuleDescription, notifyChosen, notifyDiscard, notifyEquivalence, notifyTransformation, setCancelFlag, setRuleDescExclusionFilter, unmapRuleDescription

Methods inherited from class java.lang.Object

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

Field Detail

CostImprovement

protected static final double CostImprovement

See Also:

Constant Field Values

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.

impatient

protected boolean impatient

If true, and if ambitious is true, the planner waits a finite number of iterations for the cost to improve.

The number of iterations K is equal to the number of iterations required to get the first finite plan. After the first finite plan, it continues to fire rules to try to improve it. The planner sets a target cost of the current best cost multiplied by CostImprovement. If it does not meet that cost target within K steps, it quits, and uses the current best plan. If it meets the cost, it sets a new, lower target, and has another K iterations to meet it. And so forth.

If false, the planner continues to fire rules until the rule queue is empty.

allOperands

private final List<RelOptRuleOperand> 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

final List<RelSet> allSets

List of all sets. Used only for debugging.

mapDigestToRel

private final Map<String,RelNode> mapDigestToRel

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

mapRel2Subset

private final IdentityHashMap<RelNode,RelSubset> mapRel2Subset

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

We use an IdentityHashMap to simplify the process of merging RelSet objects. Most RelNode objects are identified by their digest, which involves the set that their child relational expressions belong to. If those children belong to the same set, we have to be careful, otherwise it gets incestuous.

relImportances

final Map<RelNode,Double> relImportances

The importance of relational expressions.

The map contains only RelNodes whose importance has been overridden using RelOptPlanner.setImportance(RelNode, double). Other RelNodes are presumed to have 'normal' importance.

If a RelNode has 0 importance, all RelOptRuleCalls using it are ignored, and future RelOptRuleCalls are not queued up.

registeredSchemas

private final Set<RelOptSchema> registeredSchemas

List of all schemas which have been registered.

ruleQueue

final RuleQueue ruleQueue

Holds rule calls waiting to be fired.

traitDefs

private final List<RelTraitDef> traitDefs

Holds the currently registered RelTraitDefs.

ruleSet

protected final Set<RelOptRule> ruleSet

Set of all registered rules.

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.

listener

RelOptListener listener

Listener for this planner, or null if none set.

originalRootString

private String originalRootString

Dump of the root relational expression, as it was before any rules were applied. For debugging.

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

getPhaseRuleMappingInitializer

protected VolcanoPlannerPhaseRuleMappingInitializer getPhaseRuleMappingInitializer()

getConversionOperands

public RelOptRuleOperand[] getConversionOperands(CallingConvention toConvention)

isRegistered

public boolean isRegistered(RelNode rel)

Description copied from interface: RelOptPlanner

Determines whether a relational expression has been registered.

Parameters:

rel - expression to test

Returns:

whether rel has been registered

setRoot

public void setRoot(RelNode rel)

Description copied from interface: RelOptPlanner

Sets the root node of this query.

Parameters:

rel - Relational expression

getRoot

public RelNode getRoot()

Description copied from interface: RelOptPlanner

Returns the root node of this query.

Returns:

Root node

getSet

public RelSet getSet(RelNode rel)

Finds an expression's equivalence set. If the expression is not registered, returns null.

Parameters:

rel - Relational expression

Returns:

Equivalence set that expression belongs to, or null if it is not registered

"Precondition:"

rel != null

addRelTraitDef

public boolean addRelTraitDef(RelTraitDef relTraitDef)

Description copied from interface: RelOptPlanner

Registers a rel trait definition. If the RelTraitDef has already been registered, does nothing.

Specified by:

addRelTraitDef in interface RelOptPlanner

Overrides:

addRelTraitDef in class AbstractRelOptPlanner

Returns:

whether the RelTraitDef was added, as per Collection.add(E)

addRule

public boolean addRule(RelOptRule rule)

Description copied from interface: RelOptPlanner

Registers a rule. If the rule has already been registered, does nothing. This method should determine if the given rule is a ConverterRule and pass the ConverterRule to all registered RelTraitDef instances.

Returns:

whether the rule was added, as per Collection.add(E)

removeRule

public boolean removeRule(RelOptRule rule)

Description copied from interface: RelOptPlanner

Removes a rule.

Returns:

true if the rule was present, as per Collection.remove(Object)

canConvert

public boolean canConvert(RelTraitSet fromTraits,
                          RelTraitSet toTraits)

changeTraits

public RelNode changeTraits(RelNode rel,
                            RelTraitSet toTraits)

Description copied from interface: RelOptPlanner

Changes a relational expression to an equivalent one with a different set of traits.

Parameters:

rel - Relational expression, may or may not have been registered

toTraits - Trait set to convert relational expression to

Returns:

Relational expression with desired traits. Never null, but may be abstract

chooseDelegate

public RelOptPlanner chooseDelegate()

Description copied from interface: RelOptPlanner

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 RelOptPlanner

Overrides:

chooseDelegate in class AbstractRelOptPlanner

findBestExp

public RelNode findBestExp()

Finds the most efficient expression to implement the query given via setRoot(RelNode).

The algorithm executes repeatedly in a series of phases. In each phase the exact rules that may be fired varies. The mapping of phases to rule sets is maintained in the ruleQueue.

In each phase, the planner sets the initial importance of the existing RelSubSets (setInitialImportance()). The planner then iterates over the rule matches presented by the rule queue until:

1. The rule queue becomes empty.
2. For ambitious planners: No improvements to the plan have been made recently (specifically within a number of iterations that is 10% of the number of iterations necessary to first reach an implementable plan or 25 iterations whichever is larger).
3. For non-ambitious planners: When an implementable plan is found.

Furthermore, after every 10 iterations without an implementable plan, RelSubSets that contain only logical RelNodes are given an importance boost via injectImportanceBoost(). Once an implementable plan is found, the artificially raised importances are cleared (clearImportanceBoost()).

Returns:

the most efficient RelNode tree found for implementing the given query

setInitialImportance

private void setInitialImportance()

injectImportanceBoost

private void injectImportanceBoost()

Finds RelSubsets in the plan that contain only rels of CallingConvention.NONE and boosts their importance by 25%.

clearImportanceBoost

private void clearImportanceBoost()

Clear all importance boosts.

makeCost

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

Description copied from interface: RelOptPlanner

Creates a cost object.

Specified by:

makeCost in interface RelOptPlanner

Overrides:

makeCost in class AbstractRelOptPlanner

makeHugeCost

public RelOptCost makeHugeCost()

Description copied from interface: RelOptPlanner

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

Specified by:

makeHugeCost in interface RelOptPlanner

Overrides:

makeHugeCost in class AbstractRelOptPlanner

makeInfiniteCost

public RelOptCost makeInfiniteCost()

Description copied from interface: RelOptPlanner

Creates a cost object representing infinite cost.

Specified by:

makeInfiniteCost in interface RelOptPlanner

Overrides:

makeInfiniteCost in class AbstractRelOptPlanner

makeTinyCost

public RelOptCost makeTinyCost()

Description copied from interface: RelOptPlanner

Creates a cost object representing a small positive cost.

Specified by:

makeTinyCost in interface RelOptPlanner

Overrides:

makeTinyCost in class AbstractRelOptPlanner

makeZeroCost

public RelOptCost makeZeroCost()

Description copied from interface: RelOptPlanner

Creates a cost object representing zero cost.

Specified by:

makeZeroCost in interface RelOptPlanner

Overrides:

makeZeroCost in class AbstractRelOptPlanner

register

public RelNode register(RelNode rel,
                        RelNode equivRel)

Description copied from interface: RelOptPlanner

Registers a relational expression in the expression bank.

After it has been registered, you may not modify it.

The expression must not already have been registered. If you are not sure whether it has been registered, call RelOptPlanner.ensureRegistered(RelNode,RelNode).

Parameters:

rel - Relational expression to register (must not already be registered)

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

Returns:

the same expression, or an equivalent existing expression

ensureRegistered

public RelNode ensureRegistered(RelNode rel,
                                RelNode equivRel)

Description copied from interface: RelOptPlanner

Registers a relational expression if it is not already registered.

Parameters:

rel - Relational expression to register

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

Returns:

Registered relational expression

validate

protected void validate()

Checks internal consistency.

registerAbstractRelationalRules

public void registerAbstractRelationalRules()

registerSchema

public void registerSchema(RelOptSchema schema)

Description copied from interface: RelOptPlanner

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 RelOptPlanner

Overrides:

registerSchema in class AbstractRelOptPlanner

getJavaRelImplementor

public JavaRelImplementor getJavaRelImplementor(RelNode rel)

Description copied from interface: RelOptPlanner

Retrieves an implementor appropriate for the context in which this planner was created.

Specified by:

getJavaRelImplementor in interface RelOptPlanner

Overrides:

getJavaRelImplementor in class AbstractRelOptPlanner

getCost

public RelOptCost getCost(RelNode rel)

Description copied from interface: RelOptPlanner

Computes the cost of a RelNode. In most cases, this just dispatches to RelMetadataQuery.getCumulativeCost(org.eigenbase.rel.RelNode).

Specified by:

getCost in interface RelOptPlanner

Overrides:

getCost in class AbstractRelOptPlanner

Parameters:

rel - expression of interest

Returns:

estimated cost

getSubset

public RelSubset getSubset(RelNode rel)

Returns the subset that a relational expression belongs to.

Parameters:

rel - Relational expression

Returns:

Subset it belongs to, or null if it is not registered

"Precondition:"

rel != null

getSubset

public RelSubset getSubset(RelNode rel,
                           RelTraitSet traits)

getSubset

public RelSubset getSubset(RelNode rel,
                           RelTraitSet traits,
                           boolean createIfMissing)

changeTraitsUsingConverters

private RelNode changeTraitsUsingConverters(RelNode rel,
                                            RelTraitSet toTraits,
                                            boolean allowAbstractConverters)

changeTraitsUsingConverters

RelNode changeTraitsUsingConverters(RelNode rel,
                                    RelTraitSet toTraits)

checkForSatisfiedConverters

void checkForSatisfiedConverters(RelSet set,
                                 RelNode rel)

setImportance

public void setImportance(RelNode rel,
                          double importance)

Description copied from interface: RelOptPlanner

Sets the importance of a relational expression.

An important use of this method is when a RelOptRule has created a relational expression which is indisputably better than the original relational expression. The rule set the original relational expression's importance to zero, to reduce the search space. Pending rule calls are cancelled, and future rules will not fire.

Specified by:

setImportance in interface RelOptPlanner

Overrides:

setImportance in class AbstractRelOptPlanner

Parameters:

rel - Relational expression

importance - Importance

dump

public void dump(PrintWriter pw)

Dumps the internal state of this VolcanoPlanner to a writer.

Parameters:

pw - Print writer

See Also:

normalizePlan(String)

rename

void rename(RelNode rel)

Re-computes the digest of a RelNode.

Since a relational expression's digest contains the identifiers of its children, this method needs to be called when the child has been renamed, for example if the child's set merges with another.

Parameters:

rel - Relational expression

reregister

void reregister(RelSet set,
                RelNode rel)

Registers a RelNode, which has already been registered, in a new RelSet.

Parameters:

set - Set

rel - Relational expression

canonize

private RelSubset canonize(RelSubset subset)

If a subset has one or more equivalent subsets (owing to a set having merged with another), returns the subset which is the leader of the equivalence class.

Parameters:

subset - Subset

Returns:

Leader of subset's equivalence class

fireRules

void fireRules(RelNode rel,
               boolean deferred)

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

fixupInputs

private boolean fixupInputs(RelNode rel)

merge

private void merge(RelSet set,
                   RelSet set2)

registerImpl

private RelSubset registerImpl(RelNode rel,
                               RelSet set)

Registers a new expression exp and queues up rule matches. If set is not null, makes the expression part of that equivalence set. If an identical expression is already registered, we don't need to register this one and nor should we queue up rule matches.

Parameters:

rel - relational expression to register. Must be either a RelSubset, or an unregistered RelNode

set - set that rel belongs to, or null

Returns:

the equivalence-set

"Precondition:"

rel instanceof RelSubset || !isRegistered(rel)

registerSubset

private RelSubset registerSubset(RelSet set,
                                 RelSubset subset)

addListener

public void addListener(RelOptListener newListener)

Description copied from interface: RelOptPlanner

Adds a listener to this planner.

Specified by:

addListener in interface RelOptPlanner

Overrides:

addListener in class AbstractRelOptPlanner

Parameters:

newListener - new listener to be notified of events

registerMetadataProviders

public void registerMetadataProviders(ChainedRelMetadataProvider chain)

Description copied from interface: RelOptPlanner

Gives this planner a chance to register one or more RelMetadataProviders in the chain which will be used to answer metadata queries. Planners which use their own relational expressions internally to represent concepts such as equivalence classes will generally need to supply corresponding metadata providers.

Specified by:

registerMetadataProviders in interface RelOptPlanner

Overrides:

registerMetadataProviders in class AbstractRelOptPlanner

Parameters:

chain - receives planner's custom providers, if any

getRelMetadataTimestamp

public long getRelMetadataTimestamp(RelNode rel)

Description copied from interface: RelOptPlanner

Gets a timestamp for a given rel's metadata. This timestamp is used by CachingRelMetadataProvider to decide whether cached metadata has gone stale.

Specified by:

getRelMetadataTimestamp in interface RelOptPlanner

Overrides:

getRelMetadataTimestamp in class AbstractRelOptPlanner

Parameters:

rel - rel of interest

Returns:

timestamp of last change which might affect metadata derivation

normalizePlan

public static String normalizePlan(String plan)

Normalizes references to subsets within the string representation of a plan.

This is useful when writing tests: it helps to ensure that tests don't break when an extra rule is introduced that generates a new subset and causes subsequent subset numbers to be off by one.

For example,

FennelAggRel.FENNEL_EXEC(child=Subset#17.FENNEL_EXEC,groupCount=1, EXPR$1=COUNT())
FennelSortRel.FENNEL_EXEC(child=Subset#2.FENNEL_EXEC, key=[0], discardDuplicates=false)
FennelCalcRel.FENNEL_EXEC( child=Subset#4.FENNEL_EXEC, expr#0..8={inputs}, expr#9=3456, DEPTNO=$t7, $f0=$t9)
MockTableImplRel.FENNEL_EXEC( table=[CATALOG, SALES, EMP])

becomes

FennelAggRel.FENNEL_EXEC(child=Subset#{0}.FENNEL_EXEC, groupCount=1, EXPR$1=COUNT())
FennelSortRel.FENNEL_EXEC(child=Subset#{1}.FENNEL_EXEC, key=[0], discardDuplicates=false)
FennelCalcRel.FENNEL_EXEC( child=Subset#{2}.FENNEL_EXEC,expr#0..8={inputs},expr#9=3456,DEPTNO=$t7, $f0=$t9)
MockTableImplRel.FENNEL_EXEC( table=[CATALOG, SALES, EMP])

Parameters:

plan - Plan

Returns:

Normalized plan