|
||||||||||
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 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. |
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 rule-matches 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 unit-test 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 2003-2003 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 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:
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
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:
|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |