Package org.eigenbase.relopt.volcano

Optimizes relational expressions.

See:
          Description

Interface Summary
VolcanoPlannerPhaseRuleMappingInitializer VolcanoPlannerPhaseRuleMappingInitializer describes an inteface for initializing the mapping of VolcanoPlannerPhases to sets of rule descriptions.
 

Class Summary
AbstractConverter Converts a relational expression to any given output convention.
AbstractConverter.ExpandConversionRule Rule which converts an AbstractConverter into a chain of converters from the source relation to the target traits.
ChainedPhaseRuleMappingInitializer ChainedPhaseRuleMappingInitializer is an abstract implementation of VolcanoPlannerPhaseRuleMappingInitializer that allows additional rules to be layered ontop of those configured by a subordinate VolcanoPlannerPhaseRuleMappingInitializer.
RelSet A RelSet is an equivalence-set of expressions; that is, a set of expressions which have identical semantics.
RelSubset A RelSubset is set of expressions in a set which have the same calling convention.
RuleQueue Priority queue of relexps whose rules have not been called, and rule-matches which have not yet been acted upon.
RuleQueue.PhaseMatchList PhaseMatchList represents a set of rule-matches for a particular phase of the planner's execution.
VolcanoCost VolcanoCost represents the cost of a plan node.
VolcanoPlanner VolcanoPlanner optimizes queries by transforming expressions selectively according to a dynamic programming algorithm.
VolcanoPlanner.DeferringRuleCall A rule call which defers its actions.
VolcanoPlannerTest A VolcanoPlannerTest is a unit-test for the optimizer.
VolcanoPlannerTest.GoodRemoveSingleRule  
VolcanoPlannerTest.GoodSingleRule  
VolcanoPlannerTest.NoneLeafRel  
VolcanoPlannerTest.NoneSingleRel  
VolcanoPlannerTest.PhysLeafRel  
VolcanoPlannerTest.PhysLeafRule  
VolcanoPlannerTest.PhysProjectRule  
VolcanoPlannerTest.PhysSingleRel  
VolcanoPlannerTest.ReformedRemoveSingleRule  
VolcanoPlannerTest.ReformedSingleRule  
VolcanoPlannerTest.TestEnvironment  
VolcanoPlannerTest.TestLeafRel  
VolcanoPlannerTest.TestListener  
VolcanoPlannerTest.TestSingleRel  
VolcanoPlannerTraitTest VolcanoPlannerTraitTest
VolcanoPlannerTraitTest.AltTrait  
VolcanoPlannerTraitTest.AltTraitConverter  
VolcanoPlannerTraitTest.AltTraitConverterRule  
VolcanoPlannerTraitTest.AltTraitDef  
VolcanoPlannerTraitTest.IterSingleRel  
VolcanoPlannerTraitTest.IterSingleRule  
VolcanoPlannerTraitTest.IterSingleRule2  
VolcanoPlannerTraitTest.NoneLeafRel  
VolcanoPlannerTraitTest.NoneSingleRel  
VolcanoPlannerTraitTest.PhysLeafRel  
VolcanoPlannerTraitTest.PhysLeafRule  
VolcanoPlannerTraitTest.PhysToIteratorConverter  
VolcanoPlannerTraitTest.PhysToIteratorConverterRule  
VolcanoPlannerTraitTest.TestLeafRel  
VolcanoPlannerTraitTest.TestSingleRel  
VolcanoRelMetadataProvider VolcanoRelMetadataProvider implements the RelMetadataProvider interface by combining metadata from the rels making up an equivalence class.
VolcanoRuleCall VolcanoRuleCall implements the RelOptRuleCall interface for VolcanoPlanner.
VolcanoRuleMatch A match of a rule to a particular set of target relational expressions, frozen in time.
 

Enum Summary
VolcanoPlannerPhase VolcanoPlannerPhase represents the phases of operation that the VolcanoPlanner passes through during optimization of a tree of RelNode objects.
 

Package org.eigenbase.relopt.volcano Description

Optimizes relational expressions.

 

Revision $Id: //open/dev/farrago/src/org/eigenbase/relopt/volcano/package.html#1 $
Copyright Copyright (C) 2005-2009 The Eigenbase Project
Copyright (C) 2003-2009 SQLstream, Inc.
Copyright (C) 2009-2009 LucidEra, Inc.
Author Julian Hyde, Stephan Zuercher

Overview

A planner (also known as an optimizer) finds the most efficient implementation of a relational expression.

Interface RelOptPlanner defines a planner, and class VolcanoPlanner is an implementation which uses a dynamic programming technique. It is based upon the Volcano optimizer [1].

Interface RelOptCost defines a cost model; class VolcanoCost is the implementation for a VolcanoPlanner.

A RelSet is a set of equivalent relational expressions. They are equivalent because they will produce the same result for any set of input data. It is an equivalence class: two expressions are in the same set if and only if they are in the same RelSet.

One of the unique features of the optimizer is that expressions can take on a variety of physical traits. Each relational expression has a set of traits. Each trait is described by an implementation of RelTraitDef. Manifestations of the trait implement RelTrait. The most common example of a trait is calling convention: the protocol used to receive and transmit data. CallingConventionTraitDef defines the trait and CallingConvention enumerates the protocols. Every relational expression has a single calling convention by which it returns its results. Some examples:

New traits are added to the planner in one of two ways:

  1. If the new trait is integral to Farrago, then each and every implementation of RelNode should include its manifestation of the trait as part of the RelTraitSet passed to AbstractRelNode's constructor. It may be useful to provide alternate AbstractRelNode constructors if most relational expressions use a single manifestation of the trait.
  2. If the new trait describes some aspect of a Farrago extension, then the RelNodes passed to VolcanoPlanner.setRoot(org.eigenbase.rel.RelNode) should have their trait sets expanded before the setRoot(RelNode) call.

The second trait extension mechanism requires that implementations of AbstractRelNode.clone() must not assume the type and quantity of traits in their trait set. In either case, the new RelTraitDef implementation must be VolcanoPlanner.addRelTraitDef(org.eigenbase.relopt.RelTraitDef) registered with the planner.

A RelSubset is a subset of a RelSet containing expressions which are equivalent and which have the same CallingConvention. Like RelSet, it is an equivalence class.

Related packages

Details

...

Sets merge when the result of a rule already exists in another set. This implies that all of the expressions are equivalent. The RelSets are merged, and so are the contained RelSubsets.

Expression registration.

Algorithm

To optimize a relational expression R:

1. Register R.

2. Create rule-calls for all applicable rules.

3. Rank the rule calls by importance.

4. Call the most important rule

5. Repeat.

Importance. A rule-call is important if it is likely to produce better implementation of a relexp on the plan's critical path. Hence (a) it produces a member of an important RelSubset, (b) its children are cheap.

Conversion. Conversions are difficult because we have to work backwards from the goal.

Rule triggering

The rules are:

  1. PushFilterThroughProjectRule. Operands:
    Filter
      Project
  2. CombineProjectsRule. Operands:
    Project
      Project

A rule can be triggered by a change to any of its operands. Consider the rule to combine two filters into one. It would have operands [Filter [Filter]]. If I register a new Filter, it will trigger the rule in 2 places. Consider:

Project (deptno)                              [exp 1, subset A]
  Filter (gender='F')                         [exp 2, subset B]
    Project (deptno, gender, empno)           [exp 3, subset C]
      Project (deptno, gender, empno, salary) [exp 4, subset D]
        TableScan (emp)                       [exp 0, subset X]

Apply PushFilterThroughProjectRule to [exp 2, exp 3]:

Project (deptno)                              [exp 1, subset A]
  Project (deptno, gender, empno)             [exp 5, subset B]
    Filter (gender='F')                       [exp 6, subset E]
      Project (deptno, gender, empno, salary) [exp 4, subset D]
        TableScan (emp)                       [exp 0, subset X]

Two new expressions are created. Expression 5 is in subset B (because it is equivalent to expression 2), and expression 6 is in a new equivalence class, subset E.

The products of a applying a rule can trigger a cascade of rules. Even in this simple system (2 rules and 4 initial expressions), two more rules are triggered:

Each rule application adds additional members to existing subsets. The non-singleton subsets are now A {1, 7}, B {2, 5} and E {6, 8}, and new combinations are possible. For example, CombineProjectsRule(exp 7, exp 8) further reduces the depth of the tree to:

Project (deptno)                          [exp 10, subset A]
  Filter (gender='F')                     [exp 9, subset F]
    TableScan (emp)                       [exp 0, subset X]

Todo: show how rules can cause subsets to merge.

Conclusion:

  1. A rule can be triggered by any of its operands.
  2. If a subset is a child of more than one parent, it can trigger rule matches for any of its parents.
  3. Registering one relexp can trigger several rules (and even the same rule several times).
  4. Firing rules can cause subsets to merge.

References

1. The Volcano Optimizer Generator: Extensibility and Efficient Search - Goetz Graefe, William J. McKenna (1993).