

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
See:
Description
Interface Summary  
PlanCost  todo: 
RelImplementor.Bind  
RelImplementor.VariableInitializerThunk  A VariableInitializerThunk yields a VariableInitializer . 
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 calling convention. 
CallingConvention  CallingConvention enumerates all calling conventions defined
by Saffron itself. 
OptUtil  OptUtil defines static utility methods for use in optimizing
SaffronRel s. 
OptUtil.RelHolder  
OptUtil.VariableSetVisitor  
OptUtil.VariableUsedVisitor  
RelImplementor  RelImplementor deals with the nastiness of converting a tree
of relational expressions into an implementation, generally an openjava parse tree . 
RelImplementor.EagerBind  
RelImplementor.Frame  
RelImplementor.LazyBind  
RelImplementor.Translator  Translator is a shuttle used to implement
RelImplementor.translate(net.sf.saffron.rel.SaffronRel, net.sf.saffron.rex.RexNode) . 
RelImplementor.Translator.WhichInputResult  Result of call to RelImplementor.Translator.whichInput(int, net.sf.saffron.rel.SaffronRel) , contains the input relational
expression, its index, and the index of the field within that
relational expression. 
RelSet  A RelSet is an equivalenceset 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. 
RuleOperand  A RuleOperand determines whether a VolcanoRule can be applied to a particular expression. 
RuleQueue  Priority queue of relexps whose rules have not been called, and rulematches which have not yet been acted upon. 
TableAccessMap  TableAccessMap represents the tables accessed by a query plan,
with READ/WRITE information. 
VisitorRelVisitor  Walks over a tree of relational expressions , walking a
RexShuttle over every expression in that tree. 
VolcanoCluster  A VolcanoCluster is a collection of SaffronRel ational
expressions which have the same environment. 
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. 
VolcanoPlannerFactory  A VolcanoPlannerFactory produces new uninitialized instances
of VolcanoPlanner. 
VolcanoPlannerTest  A VolcanoPlannerTest is a unittest for the optimizer . 
VolcanoPlannerTest.BadSingleRule  
VolcanoPlannerTest.GoodSingleRule  
VolcanoPlannerTest.NoneLeafRel  
VolcanoPlannerTest.NoneSingleRel  
VolcanoPlannerTest.PhysLeafRel  
VolcanoPlannerTest.PhysLeafRule  
VolcanoPlannerTest.PhysSingleRel  
VolcanoPlannerTest.TestEnvironment  
VolcanoPlannerTest.TestLeafRel  
VolcanoPlannerTest.TestSingleRel  
VolcanoQuery  A VolcanoQuery represents a set of relational
expressions which derive from the same select statement. 
VolcanoRule  A VolcanoRule transforms an expression into another. 
VolcanoRuleCall  A VolcanoRuleCall is an invocation of a VolcanoRule
with a set of relational expression s as arguments. 
VolcanoRuleMatch  A match of a rule to a particular set of target relational expressions, frozen in time. 
Optimizes Saffron relational expressions.
Revision  $Id: //open/saffron/src/net/sf/saffron/opt/package.html#2 $ 

Copyright  (C) Copyright 20032003 Disruptive Technologies, Inc. 
Author  Julian Hyde 
A planner (also known as an optimizer) finds the most
efficient implementation of a relational expression
.
Interface SaffronPlanner
defines a planner, and class VolcanoPlanner
is an implementation which uses a dynamic
programming technique. It is based upon the Volcano optimizer [1].
Interface PlanCost
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 Saffron optimizer is expressions can use a
variety of protocols to receive and transmit data. A CallingConvention
defines such a protocol; every relational
expression has a single calling convention by which it returns its results. Some
examples:
CallingConvention.RESULT_SET
is a fairly conventional
calling convention; the results are rows from a JDBC
result set
.CallingConvention.NONE
means that a relational
expression cannot be implemented; typically there are rules which can
transform it to equivalent, implementable expressions.CallingConvention.JAVA
implements the expression by
generating Java code. The code places the current row in a Java variable, then
calls the piece of code which implements the consuming relational expression.
For example, a Java array reader of the names
array would
generate the following code:String[] names; for (int i = 0; i < names.length; i++) { String name = names[i]; // ... code for consuming relational expression ... }
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.
saffron.rel
defines relational expressions
.openjava.ptree
defines an object model for Java expressions....
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 rulecalls for all applicable rules.
3. Rank the rule calls by importance.
4. Call the most important rule
5. Repeat.
Importance. A rulecall 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:
PushFilterThroughProjectRule
. Operands:Filter Project
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:
CombineProjectsRule
(exp 1, exp 5),
which createsProject (deptno) [exp 7, subset A] Filter (gender='F') [exp 6, subset E] Project (deptno, gender, empno, salary) [exp 4, subset D] TableScan (emp) [exp 0, subset X]
PushFilterThroughProjectRule
(exp
6, exp 4), which createsProject (deptno) [exp 1, subset A] Project (deptno, gender, empno) [exp 5, subset B] Project (deptno, gender, empno, salary) [exp 8, subset E] Filter (gender='F') [exp 9, subset F] TableScan (emp) [exp 0, subset X]
Each rule application adds additional members to existing subsets. The
nonsingleton 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:


PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 