HowToWriteNewOptimizerRules

From LucidDB Wiki
Jump to: navigation, search

Contents

How To Write New Optimizer Rules


Optimizer Overview

For background on planners, see HowToWriteAnOptimizer. In this page, we'll assume the Volcano planner, since it is generally the most challenging to write rules for; if a rule works with Volcano, it will usually work with HEP too.

The Volcano Planner is a cost-based query planner which supports an extensible ruleset. It starts with a plan, which is a tree of relational expressions (e.g. table scan -> filter -> project). In most instances, the plan is a logical construction without a concrete implementation. The optimizer applies transformation rules, triggered by the types of relational expressions in the plan, in an attempt to find the lowest "cost," implementable plan that physically represents the input plan.


Cost is represented as a combination of computational complexity, I/O requirements, and row count. See org.eigenbase.relopt.RelOptCost.

Multiple rules may match the same relational expressions and provide several alternative transformations. The optimizer explores these paths in an effort to find less expensive implementations. Transformed relational expressions are maintained in parallel with the relational expressions that spawned them. The optimizer sorts the set of rules that matches the current state of planning and fires them in an order that seems likely to produce the greatest immediate benefit. For example, rules that match a non-implementable relational expression that has never been transformed will fire before rules that match a relational expression that already has a valid transformation to an implementable relational expression.

A planner rule transforms a relational expression and (optionally) its children into another set of relational expressions. The resulting relational expression usually differs from the original in implementation or in cost. Often, logical relational expressions are simply replaced with implementable relational expressions. In some cases there are several ways to implement a logical relational expression and multiple rules will exist to perform the various transformations. For example, the logical org.eigenbase.rel.CalcRel can be implemented as a Java-based org.eigenbase.rel.oj.IterCalcRel or a com.disruptivetech.farrago.rel.FennelCalcRel (assuming the appropriate rules are enabled).


Relational expressions are represented in the optimizer as instances of org.eigenbase.rel.RelNode.

Traits

Relational expressions have a set of traits (see org.eigenbase.relopt.RelTraitSet) composed of one or more traits (see org.eigenbase.relopt.RelTrait) which fall into different categories (see org.eigenbases.relopt.RelTraitDef). In Farrago, the only standard category of trait is "calling convention." Calling convention specifies whether the relational expression is implemented by iterable Java XOs (iterator calling convention) or Fennel XOs (fennel ExecStream calling convention). It may also specify that a relational expression cannot be implemented at all (the "none" calling convention). Farrago extensions may define additional categories of traits, such as sort order or physical location. When a relational expression and one of its children have different traits, the optimizer can be instructed to insert a conversion between the two relational expressions. Typically the optimizer avoids conversions where possible, since they add cost. When relational expressions are transformed, the optimizer automatically propagates traits other than calling convention unless the rule specifically sets them. So, unless you are extending Farrago to use additional traits you need not concern yourself with anything but calling convention.


(Note from JVS: sort order may eventually become a first-class Farrago trait.)

Converter Rules

Rules fall into two basic types: those that transform a RelNode into another RelNode with different traits, but identical semantics, and those that change the semantics of a RelNode.

The former is referred to as a converter. An example of a conversion rule is org.eigenbase.oj.rel.IterCalcRule. It converts a CalcRel with the "none" calling convention into an IterCalcRel with the iterator calling convention.

An example of the other type of rule is the org.eigenbase.rel.MergeFilterOntoCalcRule which transforms an org.eigenbase.rel.FilterRel (which often represents a SQL where clause) with a CalcRel child into a single CalcRel. In this case the semantics of the RelNode are changed: the new CalcRel performs the old CalcRel's functions plus those of the FilterRel.

Recipe For Creating New Optimizer Rules

First, determine whether your rule is a converter or not. If so, extend org.eigenbase.rel.convert.ConverterRule. Otherwise extend org.eigenbase.relopt.RelOptRule.


In any event, your rule must not maintain state between invocations. It must also be re-entrant.

ConverterRule Implementation

  1. Create a private constructor that calls ConverterRule's constructor, passing the type of RelNode that your rule operates on (e.g., CalcRel.class) , the trait (or trait set) that your rule converts, and the trait (or trait set) or your rule's output.
  2. Override isGuaranteed(), if appropriate.
  3. Implement convert(RelNode) to generate a new RelNode with the appropriate trait(s).
  4. If the RelNode you're converting has children, use RelOptRule.mergeTraitsAndConvert(RelTraitSet, RelTrait, RelNode) to convert their trait(s) to match your new RelNode. See below.
  5. Register your rule. See below.


RelOptRule Implementation

  1. Determine the operands to your rule. This may be as simple as any RelNode or as complicated as RelNode of type Foo with children of type Bar and Qux. The optimizer will use these operands to match your rule against subgraphs of tentative plans. This means your operand pattern should be as narrow as possible to minimize rule invocations (and the sizes of the rule queues maintained internally by the optimizer), but wide enough to match all cases you're interested in. Note that if you do not reference a particular operand of interest here, you won't be able to access its class in your rule's code, since most planners will give you a proxy reference instead for all expressions other than operands.
  2. Create a private constructor that creates a tree of org.eigenbase.relopt.RelOptRuleOperand objects and passes them to RelOptRule's constructor. See below.
  3. Implement RelOptRule.onMatch(RelOptRuleCall call).
  4. The RelOptRuleCall will contain the RelNode(s) that matched your RelOptRuleOperand.
  5. If your rule operates on a subset of RelNodes that match the RelOptRuleOperand (e.g., it operates only on CalcRels that contain certain expressions), examine the RelNodes in the RelOptRuleCall to determine whether they pass those criteria. If it turns out your rule is inapplicable, simply return. The optimizer uses the coarse-grained RelOptRuleOperand pattern-matching to narrow down the set of applicable rules, so where possible, it's best to provide the most specific RelOptRuleOperand possible in favor of matching all RelNodes and only aborting in onMatch.
  6. Create new RelNode implementations that replace the top-most RelNode (e.g., call.rels[0]).
  7. Use RelOptRule.mergeTraitsAndConvert(RelTraitSet, RelTrait, RelNode) to convert children of the RelNodes you're converting to the correct traits. See below.
  8. Invoke call.transformTo(newRel) to register the result of the transformation.
  9. Make sure your rule implementation is reentrant; this means it should not have any state other than immutable variables initialized in the rule's constructor. Any other state should be local to the onMatch implementation. If you find yourself passing around big argument lists, a good way to fix it is to make a helper class for the state and have the onMatch implementation manipulate that.
  10. Once your rule class is implemented, register it with the optimizer so that it will get used during query planning. See below.


Sample RelOptRuleOperands

Match a CalcRel (or any subclass) with any traits and zero or more children:

new RelOptRuleOperand(CalcRel.class, null)


Match a CalcRel (or any subclass) with any traits and exactly one child of any kind:

new RelOptRuleOperand(
    CalcRel.class,
    new RelOptRuleOperand[] {
        new RelOptRuleOperand(RelNode.class, null)
    })


Note that if you don't actually care about the child, then this is less efficient than the previous one, because this rule will fire once for every possible child of the CalcRel, while the previous one will only fire once for the CalcRel itself.

Match a FilterRel (or any subclass) with any traits and a single ProjectRel child:

new RelOptRuleOperand(
    FilterRel.class,
    new RelOptRuleOperand[] {
        new RelOptRuleOperand(ProjectRel.class, null)
    })


Match a JoinRel (or any subclass) with any traits and two children; one of any type and other of type FtrsIndexScanRel:

new RelOptRuleOperand(
    JoinRel.class,
    new RelOptRuleOperand[] {
        new RelOptRuleOperand(RelNode.class, null),
        new RelOptRuleOperand(FtrsIndexScanRel, null),
    })


RelOptRuleOperands can be nested as many levels deep as is necessary for your rule.

Creating New Rels

When faced with a choice between creating a logical rel or an equivalent physical rel, it is generally better to create the logical rel unless the purpose of your rule is actually to generate the physical rel. This gives the optimizer a chance to try to find the best implementation by itself. For example, suppose your rule transforms a filter on top of a table scan into an index lookup. Not all of the filter may be indexable, so you have to put the leftovers back on top of the index lookup in the result. You might think you should create a FennelCalcRel to do the filtering, but it's better to put a new FilterRel back; that way, the optimizer can decide which calculator to use to implement it, or whether it should be combined with other filters, etc.

MergeTraitsAndConvert

The utility method RelOptUtil.mergeTraitsAndConvert(RelTraitSet, RelTrait, RelNode) merges the trait sets of an existing RelNode with the trait you wish to change and converts the given RelNode to use the merged traits.

For example, if you are writing a rule that takes a RelNode with "none" calling convention and provides an implementation with iterator calling convention, you might write:

RelNode originalRelNode = ...; /* passed in by planner */
RelNode originalChildRelNode = originalRelNode.getInput(0);
RelNode convertedChild =
    RelOptUtil.mergeTraitsAndConvert(
        originalRelNode.getTraits(), CallingConvention.ITERATOR, originalChildRelNode);
RelNode newRelNode = new SomeRelNode(..., convertedChild);


When this method is called on a child RelNode that already has the correct trait(s), it simply returns the child RelNode. Therefore, there's no need to check the child's traits before invoking this method.

Rule Registration

Rule registration is handled differently depending on the author of the rule.

In most cases, the rule has a private constructor. It either has a static instance field or a static register method that takes the RelOptPlanner that should be configured to use the rule.

In the former method, the RelOptPlanner implementation is extended to configure itself with the rule. See net.sf.farrago.defimpl.FarragoDefaultPlanner.init().

In the latter method, the RelOptPlanner implementation is extended to call the static register method.


There are other possibilities, such as non-singleton rules whose constructors take parameters.

Package structure

What package should I create my rule in?

Here are some principles:

  1. Related rels and rules should live in the same package, wherever possible.
  2. There's a core set of rels which are the output of SqlToRelConverter. I'm thinking of CalcRel, AggregateRel, JoinRel. These currently live in the org.eigenbase.rel package; maybe these could be moved into org.eigenbase.rel.core.
  3. If a rule exists to introduce a particular kind of new relational expression, it should live in the same package as its rel, and have a similar name. (Often it's natural to put groups of rels into the same package, e.g. net.sf.farrago.namespace.ftrs; more packages are listed below.)
  4. The org.eigenbase.rel.rules package should be for rules such as UnionEliminatorRule which don't introduce anything new, just improve performance. They should all operate on rels of 'none' calling convention.
  5. There may be other sets of rules -- say for common subexpression elimination, star-join optimization, join-ordering -- which do not introduce new rels, but which still justify having their own package, e.g. org.eigenbase.rel.rules.joinorder. Again, these rules should work on the 'none' calling convention.
  6. Other calling conventions will naturally have their own packages (e.g. org.eigenbase.oj.rel contains things of 'iter' convention).


Some packages which contain rels and rules:


Package Description Notes
org.eigenbase.rel Core relational expressions and rules necessary to implement any query Should be renamed to org.eigenbase.rel.core, and rules should be moved to org.eigenbase.rel.rules
org.eigenbase.rel.rules Logical expressions and rules which are non-core but generally useful (e.g. semijoins, multijoins, filter pushing)
org.eigenbase.rel.convert Rules for converting among calling conventions
org.eigenbase.oj.rel Java iterator convention
net.sf.farrago.query Miscellaneous physical expressions and rules. Fennel-related portions should be moved to a new package net.sf.farrago.fennel.rel
net.sf.farrago.namespace.ftrs Physical expressions and rules for implementing the FTRS row-store local data wrapper
net.sf.farrago.namespace.impl todo
net.sf.farrago.namespace.mdr Physical expressions and rules for implementing the MDR foreign data wrapper.
net.sf.farrago.namespace.mock Physical expressions and rules for implementing the mock data wrapper (both local and foreign).
com.disruptivetech.farrago.rel todo
com.lucidera.lcs Physical expressions and rules for implementing the LucidDB column-store local data wrapper.



Gotchas

TBD

  • Tracing the planner; using plannerviz. For now, see FarragoTracing.
  • Steps to take when you get the dreaded "node could not be implemented" assertion, which is the optimizer's way of telling you that based on the ruleset you provided, it couldn't produce any physical implementation at all, not even a bad one.
  • Steps to take when you think your rule should be getting fired, but isn't.
  • Steps to take when you get mysterious assertions about your rule not preserving RelDataType.
Product Documentation