Package net.sf.saffron.opt

Optimizes Saffron relational expressions.


Interface Summary
PlanCost todo:
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 SaffronRels.
RelImplementor RelImplementor deals with the nastiness of converting a tree of relational expressions into an implementation, generally an openjava parse tree.
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 SaffronRelational 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.
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 expressions as arguments.
VolcanoRuleMatch A match of a rule to a particular set of target relational expressions, frozen in time.

Package net.sf.saffron.opt Description

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:

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



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.


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:
  2. CombineProjectsRule. Operands:

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.


  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.


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