org.eigenbase.relopt.hep
Class HepPlanner

java.lang.Object
  org.eigenbase.relopt.AbstractRelOptPlanner
      org.eigenbase.relopt.hep.HepPlanner

All Implemented Interfaces:

RelOptPlanner

Direct Known Subclasses:

FarragoDefaultHeuristicPlanner, FarragoTestPlanner, LucidDbSessionPersonality.LucidDbPlanner

public class HepPlanner
extends AbstractRelOptPlanner

HepPlanner is a heuristic implementation of the RelOptPlanner interface.

Version:

$Id: //open/dev/farrago/src/org/eigenbase/relopt/hep/HepPlanner.java#18 $

Author:

John V. Sichi

Field Summary

private Set<RelOptRule>	allRules
private HepProgram	currentProgram
private org.jgrapht.DirectedGraph<HepRelVertex,org.jgrapht.graph.DefaultEdge>	graph Query graph, with edges directed from parent to child.
private int	graphSizeLastGC
private HepProgram	mainProgram
private Map<String,HepRelVertex>	mapDigestToVertex
private boolean	noDAG
private int	nTransformations
private int	nTransformationsLastGC
private RelTraitSet	requestedRootTraits
private HepRelVertex	root

Fields inherited from interface org.eigenbase.relopt.RelOptPlanner

tracer

Constructor Summary

HepPlanner(HepProgram program)
Creates a new HepPlanner that allows DAG.

HepPlanner(HepProgram program, boolean noDAG)
Creates a new HepPlanner with the option to keep the graph a tree(noDAG=true) or allow DAG(noDAG=false).

Method Summary

private HepRelVertex	addRelToGraph(RelNode rel)
boolean	addRule(RelOptRule rule) Registers a rule.
private HepRelVertex	applyRule(RelOptRule rule, HepRelVertex vertex, boolean forceConversions)
private void	applyRules(Collection<RelOptRule> rules, boolean forceConversions)
private HepRelVertex	applyTransformationResults(HepRelVertex vertex, HepRuleCall call, RelTrait parentTrait)
private void	assertNoCycles()
private RelNode	buildFinalPlan(HepRelVertex vertex)
RelNode	changeTraits(RelNode rel, RelTraitSet toTraits) Changes a relational expression to an equivalent one with a different set of traits.
private void	collectGarbage()
private void	contractVertices(HepRelVertex preservedVertex, HepRelVertex discardedVertex, List<HepRelVertex> parents)
private boolean	doesConverterApply(ConverterRule converterRule, HepRelVertex vertex)
private void	dumpGraph()
RelNode	ensureRegistered(RelNode rel, RelNode equivRel) Registers a relational expression if it is not already registered.
(package private) void	executeInstruction(HepInstruction.BeginGroup instruction)
(package private) void	executeInstruction(HepInstruction.CommonRelSubExprRules instruction)
(package private) void	executeInstruction(HepInstruction.ConverterRules instruction)
(package private) void	executeInstruction(HepInstruction.EndGroup instruction)
(package private) void	executeInstruction(HepInstruction.MatchLimit instruction)
(package private) void	executeInstruction(HepInstruction.MatchOrder instruction)
(package private) void	executeInstruction(HepInstruction.RuleClass instruction)
(package private) void	executeInstruction(HepInstruction.RuleCollection instruction)
(package private) void	executeInstruction(HepInstruction.RuleInstance instruction)
(package private) void	executeInstruction(HepInstruction.Subprogram instruction)
private void	executeProgram(HepProgram program)
RelNode	findBestExp() Finds the most efficient expression to implement this query.
private Iterator<HepRelVertex>	getGraphIterator(HepRelVertex start)
long	getRelMetadataTimestamp(RelNode rel) Gets a timestamp for a given rel's metadata.
RelNode	getRoot() Returns the root node of this query.
private List<HepRelVertex>	getVertexParents(HepRelVertex vertex) Retrieves the parent vertices of a vertex.
boolean	isRegistered(RelNode rel) Determines whether a relational expression has been registered.
private boolean	matchOperands(RelOptRuleOperand operand, RelNode rel, List<RelNode> bindings, Map<RelNode,List<RelNode>> nodeChildren)
RelNode	register(RelNode rel, RelNode equivRel) Registers a relational expression in the expression bank.
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.
boolean	removeRule(RelOptRule rule) Removes a rule.
void	setRoot(RelNode rel) Sets the root node of this query.
private boolean	skippingGroup()
private void	updateVertex(HepRelVertex vertex, RelNode rel)

Methods inherited from class org.eigenbase.relopt.AbstractRelOptPlanner

addListener, addRelTraitDef, checkCancel, chooseDelegate, fireRule, getCost, getJavaRelImplementor, getListener, getRuleByDescription, isRuleExcluded, makeCost, makeHugeCost, makeInfiniteCost, makeTinyCost, makeZeroCost, mapRuleDescription, notifyChosen, notifyDiscard, notifyEquivalence, notifyTransformation, registerSchema, setCancelFlag, setImportance, setRuleDescExclusionFilter, unmapRuleDescription

Methods inherited from class java.lang.Object

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

Field Detail

mainProgram

private HepProgram mainProgram

currentProgram

private HepProgram currentProgram

root

private HepRelVertex root

requestedRootTraits

private RelTraitSet requestedRootTraits

mapDigestToVertex

private Map<String,HepRelVertex> mapDigestToVertex

allRules

private Set<RelOptRule> allRules

nTransformations

private int nTransformations

graphSizeLastGC

private int graphSizeLastGC

nTransformationsLastGC

private int nTransformationsLastGC

noDAG

private boolean noDAG

graph

private org.jgrapht.DirectedGraph<HepRelVertex,org.jgrapht.graph.DefaultEdge> graph

Query graph, with edges directed from parent to child. This is a single-rooted DAG, possibly with additional roots corresponding to discarded plan fragments which remain to be garbage-collected.

Constructor Detail

HepPlanner

public HepPlanner(HepProgram program)

Creates a new HepPlanner that allows DAG.

Parameters:

program - program controlling rule application

HepPlanner

public HepPlanner(HepProgram program,
                  boolean noDAG)

Creates a new HepPlanner with the option to keep the graph a tree(noDAG=true) or allow DAG(noDAG=false).

Parameters:

program - program controlling rule application

Method Detail

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

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)

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

findBestExp

public RelNode findBestExp()

Description copied from interface: RelOptPlanner

Finds the most efficient expression to implement this query.

executeProgram

private void executeProgram(HepProgram program)

executeInstruction

void executeInstruction(HepInstruction.MatchLimit instruction)

executeInstruction

void executeInstruction(HepInstruction.MatchOrder instruction)

executeInstruction

void executeInstruction(HepInstruction.RuleInstance instruction)

executeInstruction

void executeInstruction(HepInstruction.RuleClass instruction)

executeInstruction

void executeInstruction(HepInstruction.RuleCollection instruction)

skippingGroup

private boolean skippingGroup()

executeInstruction

void executeInstruction(HepInstruction.ConverterRules instruction)

executeInstruction

void executeInstruction(HepInstruction.CommonRelSubExprRules instruction)

executeInstruction

void executeInstruction(HepInstruction.Subprogram instruction)

executeInstruction

void executeInstruction(HepInstruction.BeginGroup instruction)

executeInstruction

void executeInstruction(HepInstruction.EndGroup instruction)

applyRules

private void applyRules(Collection<RelOptRule> rules,
                        boolean forceConversions)

getGraphIterator

private Iterator<HepRelVertex> getGraphIterator(HepRelVertex start)

applyRule

private HepRelVertex applyRule(RelOptRule rule,
                               HepRelVertex vertex,
                               boolean forceConversions)

doesConverterApply

private boolean doesConverterApply(ConverterRule converterRule,
                                   HepRelVertex vertex)

getVertexParents

private List<HepRelVertex> getVertexParents(HepRelVertex vertex)

Retrieves the parent vertices of a vertex. If a vertex appears multiple times as an input into a parent, then that counts as multiple parents, one per input reference.

Parameters:

vertex - the vertex

Returns:

the list of parents for the vertex

matchOperands

private boolean matchOperands(RelOptRuleOperand operand,
                              RelNode rel,
                              List<RelNode> bindings,
                              Map<RelNode,List<RelNode>> nodeChildren)

applyTransformationResults

private HepRelVertex applyTransformationResults(HepRelVertex vertex,
                                                HepRuleCall call,
                                                RelTrait parentTrait)

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

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

addRelToGraph

private HepRelVertex addRelToGraph(RelNode rel)

contractVertices

private void contractVertices(HepRelVertex preservedVertex,
                              HepRelVertex discardedVertex,
                              List<HepRelVertex> parents)

updateVertex

private void updateVertex(HepRelVertex vertex,
                          RelNode rel)

buildFinalPlan

private RelNode buildFinalPlan(HepRelVertex vertex)

collectGarbage

private void collectGarbage()

assertNoCycles

private void assertNoCycles()

dumpGraph

private void dumpGraph()

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