HowToWriteAnOptimizer
From Eigenpedia
Contents |
Overview
This document provides an introduction to writing a new DBMS optimizer within the Eigenbase extensibility frameworks. You may be thinking to yourself that optimizers can only be developed by people who tend to mutter to themselves in Klingon; the goal of this page is to demonstrate that it is not that hard to get started...we just can't promise you won't end up uttering phrases like "Hab SoSlI' Quch!" when someone interrupts you while you are tracking down a bug in join tree enumeration.
Constructing an optimizer involves plugging together the following components:
- an algebra of relational expressions: these instantiate org.eigenbase.rel.RelNode, and together they define the space of logical and physical plan representations which the optimizer is capable of manipulating
- a set of relational expression traits: these define aspects of relational expressions which are to be preserved or transformed by the optimizer (the most common example is the calling convention, which specifies whether the expression corresponds to a particular physical implementation such as a Java iterator or Fennel ExecStream)
- a set of rules: these instantiate org.eigenbase.relopt.RelOptRule, defining the logic for individual transformations between equivalent relational expressions, as well as the conditions under which they can be legally applied
- a cost metric: this instantiates org.eigenbase.relopt.RelOptCost, and may vary from basic (e.g. number of rows produced by an expression) to sophisticated (CPU cost, I/O cost)
- a set of providers for relational expression metadata: these instantiate org.eigenbase.rel.metadata.RelMetadataProvider and supply information such as costing functions and integrity constraint definitions; these are used by the optimizer to produce a plan which is both optimized and valid
- a planner implementation: the planner instantiates org.eigenbase.relopt.RelOptPlanner and drives the optimization process, starting with a purely logical representation of a plan and invoking rules to transform it into a purely physical representation suitable for execution (and with the lowest value known for the cost metric); different planner implementations have different strategies for choosing which rules to invoke, and in what order
- a generic planner may require additional configuration; for example, a heuristic planner may require a program specifying the order in which to invoke rules
For the most part, implementations of the interfaces above are mix-and-match; however, some combinations may not work well; for example, certain combinations of rules may cause a cost-based optimizer to get trapped in an infeasible region of the algebraic search space.
Terminology note: sometimes "planner" and "optimizer" are used interchangeably; in this page, we'll use planner to refer to the component which fires the rules, and optimizer as the overall system including all of the components listed above.
Optimizer Flow
This diagram illustrates the overall context in which query optimization takes place:
Query processing starts with SQL text, which is fed through the parser and validator and then converted into a tree of relational algebra expressions. These are purely logical expressions such as JoinRel and FilterRel (represented using the traditional relational algebra symbols in the diagram). The dollar signs indicate that references to input tuple attributes are by ordinal position, since the optimizer is always free to substitute equivalent expressions which produce the same tuple shape at any point in the tree. From here, the optimizer takes over, converting the tree into equivalent purely physical operators (the yellow boxes such as FtrsIndexSearchRel on the right hand side; this is what EXPLAIN PLAN renders). Finally, the physical relational expressions are converted by RelImplementor into a lower-level form (a Fennel stream graph and/or generated Java code).
Although some of the work done by SqlToRelConverter (pre-optimization) and RelImplementor (post-optimization) can be considered as part of query optimization, in this page we are going to focus on what happens in the green box.
For more information on Farrago query processing in general, see the slightly out of date net.sf.farrago.query Javadoc.
Optimizer Search Space
So, what does happen inside the green box? That depends on how the optimizer has been constructed, but there are several possibilities for how the optimizer will traverse the search space; it is easiest to explain these with an example:
- A non-cost-based heuristic optimizer will apply rules in a fixed order, regardless of whether they improve cost. In this example, supposing the only rule is PushFilterThroughJoinRule, the optimizer will start at the upper left, move down, and stop. (SwapJoinRule doesn't make sense in a non-cost-based optimizer.) The Hep planner implementation can be used to construct such an optimizer.
- A locally cost-based heuristic optimizer will apply rules in a fixed order, skipping rules which do not improve cost. In this example, suppose the order is first PushFilterThroughJoinRule, then SwapJoinRule. In that case, the optimizer will start at the upper left. If pushing the filter improves the cost, it will move down; and then possibly right if the SwapJoinRule further improves the cost. However, if pushing the filter does not improve the cost, it will move to the top right instead, assuming the SwapJoinRule improves the cost. However, in this case it will never consider the bottom right, unless its rule ordering includes a second phase of filter pushing. Hep can be used to construct this kind of optimizer also, but it does not handle the costing itself--that is up to the individual rules.
- A globally cost-based optimizer will decide its own ordering for rule firing, and it will keep track of multiple potential candidates in the search space simultaneously. In this example, it can traverse all four possibilities (plus various corresponding physical expressions), compute a cost for each one, and then take the best one. The Volcano planner can be used to construct such an optimizer. Volcano uses dynamic programming; other possibilities for global cost-based optimization are randomized approaches such as simulated annealing and genetic algorithms.
- A hybrid optimizer may combine aspects of the approaches above, possibly using a heuristic planner to feed a globally cost-based planner with good candidates for further search.
When applying transformations, it is useful for planners to be able to recognize that a result has been seen before. In a dynamic-programming optimizer such as Volcano, this is an essential part of the algorithm; it is also useful even in Hep for recognizing common subexpressions (saving optimization work and optionally producing non-tree execution graphs). To facilitate this, planners rely on relational expressions to compute digests; these are strings which serve as keys for recognizing identical expressions quickly via string equality. When writing new relational expressions, it is important to get the digest right. A digest which contains non-essential information will prevent the optimizer from recognizing equivalence; a digest which contains insufficient information may cause the optimizer to replace an expression with a non-equivalent expression (leading to an illegal plan, which in the best case will cause assertion errors, and in the worst case will silently cause incorrect execution results).
Miniplanner Example
Enough theory! The following subsections walk through the construction of a tiny but real optimizer from scratch. The source code annotated here is available as a plugin under dev/farrago/examples/miniplan; you are encouraged to compile, test, and modify it yourself as a way of getting your hands dirty with a real optimizer implementation which is small enough to be easy to understand.
Premise
Our tiny optimizer will not be able to deal with very many expressions; for example, it will throw up its hands when it sees a join. However, to make it interesting, it will understand GROUP BY and UNION ALL, and in particular, we'll teach it how to push a GROUP BY down through a UNION ALL. There is a very real-world use case for this optimization technique. For big databases, it is common to horizontally partition a large table into a number of physical slices, and then put a logical UNION ALL view on top of them so that their combination is accessible as a single logical table. When an aggregation query is executed against that view, we want the optimizer to be able to push down the GROUP BY through the UNION ALL so that the executor can aggregate each horizontal partition independently in parallel, and then merge the results.
Depending on the query, this optimization technique may help in some cases, and hurt in others; this will give us an opportunity to compare heuristic vs cost-based optimization.
Here's the code for the pushdown rule (note that just for fun, there's a bug in it for you to find):
package net.sf.farrago.miniplan;
import org.eigenbase.rel.*;
import org.eigenbase.relopt.*;
import org.eigenbase.reltype.*;
import org.eigenbase.rel.metadata.*;
import java.util.*;
/**
* PushAggThroughUnionAllRule implements the rule for pushing an
* {@link AggregateRel} past a non-distinct {@link UnionRel}.
*
* @author John Sichi
* @version $Id:$
*/
public class PushAggThroughUnionAllRule extends RelOptRule
{
public static final PushAggThroughUnionAllRule instance =
new PushAggThroughUnionAllRule();
public PushAggThroughUnionAllRule()
{
super(
new RelOptRuleOperand(
AggregateRel.class,
new RelOptRuleOperand[] {
new RelOptRuleOperand(UnionRel.class, null)
}));
}
public void onMatch(RelOptRuleCall call)
{
AggregateRel aggRel = (AggregateRel) call.rels[0];
UnionRel unionRel = (UnionRel) call.rels[1];
if (unionRel.isDistinct()) {
// This transformation is only valid for UNION ALL.
// Consider t1(i) with rows (5), (5) and t2(i) with
// rows (5), (10), and the query
// select sum(i) from (select i from t1) union (select i from t2).
// The correct answer is 15. If we apply the transformation,
// we get
// select sum(i) from
// (select sum(i) as i from t1) union (select sum(i) as i from t2)
// which yields 25 (incorrect).
return;
}
// NOTE jvs 24-Aug-2008: There's a bug in this code. When
// you find it, please don't fix it! Finding it is an exercise
// in http://wiki.eigenbase.org/pub/HowToWriteAnOptimizer,
// so we want it to stay around.
RelNode [] unionInputs = unionRel.getInputs();
int nUnionInputs = unionInputs.length;
RelNode [] newUnionInputs = new RelNode[nUnionInputs];
RelOptCluster cluster = unionRel.getCluster();
BitSet groupByKeyMask = new BitSet();
for (int i = 0; i < aggRel.getGroupCount(); i++) {
groupByKeyMask.set(i);
}
boolean anyTransformed = false;
// create corresponding aggs on top of each union child
for (int i = 0; i < nUnionInputs; i++) {
boolean alreadyUnique =
RelMdUtil.areColumnsDefinitelyUnique(
unionInputs[i],
groupByKeyMask);
if (alreadyUnique) {
newUnionInputs[i] = unionInputs[i];
} else {
anyTransformed = true;
newUnionInputs[i] =
new AggregateRel(
cluster,
unionInputs[i],
aggRel.getGroupCount(),
aggRel.getAggCallList());
}
}
if (!anyTransformed) {
// none of the children could benefit from the pushdown,
// so bail out (preventing the infinite loop to which most
// planners would succumb)
return;
}
// create a new union whose children are the aggs created above
UnionRel newUnionRel = new UnionRel(cluster, newUnionInputs, true);
AggregateRel newTopAggRel = new AggregateRel(
cluster,
newUnionRel,
aggRel.getGroupCount(),
aggRel.getAggCallList());
call.transformTo(newTopAggRel);
}
}
For background on rule construction, read HowToWriteNewOptimizerRules. In this case, note the logic for skipping the transformation in cases where it will have no effect. This is necessary for preventing an infinite loop, since the result of the transformation still matches the firing pattern. This NOP detection is based on having relational expression metadata available for areColumnsDefinitelyUnique; the standard metadata providers for Farrago guarantee the necessary logic for reporting that the pushed-down aggregations will produce unique values for the GROUP BY columns.
Build
Make sure you have a working Farrago source build before continuing.
From dev/farrago/examples/miniplan, run ant to build the miniplanner plugin. This will produce dev/farrago/examples/miniplan/plugin/FarragoMiniplan.jar; this contains the compiled plugin we'll dynamically load into Farrago to change the optimizer.
The buildfile is quite short because it leverages standard Farrago plugin compilation macros:
<project name="farragoMiniplan" basedir="." default="jar">
<dirname property="farragoMiniplan.dir" file="${ant.file}" />
<!-- Definitions for Farrago build properties and macros -->
<import file="../../buildMacros.xml"/>
<!-- Specialization definitions required by buildPlugin.xml -->
<property name="plugin.dir" location="${farragoMiniplan.dir}"/>
<property name="plugin.jar.basename" value="FarragoMiniplan"/>
<property name="plugin.factory.class"
value="net.sf.farrago.miniplan.FarragoMiniplanPersonalityFactory"/>
<!-- Classpath for plugin dependencies (none in this case) -->
<path id="plugin.3p.classpath">
</path>
<property name="plugin.3p.classpath" refid="plugin.3p.classpath"/>
<!-- Standard definitions for Farrago plugin build -->
<import file="../../plugin/buildPlugin.xml"/>
<target name="compile">
<mkdir dir="${plugin.classes.dir}"/>
<farrago.javaCompile
deprecation="off"
srcdir="${plugin.src.dir}"
destdir="${plugin.classes.dir}"
classpathref="plugin.classpath">
<include name="**/*.java" />
</farrago.javaCompile>
</target>
<target name="jar" depends="compile">
<antcall target="plugin.buildJar"/>
</target>
<target name="createPlugin">
<antcall target="clean"/>
<antcall target="jar"/>
</target>
<target name="clean" depends="plugin.clean">
</target>
</project>
Setup Test Schema
Now, execute the following via sqlline using the default Farrago personality:
create schema miniplan; set schema 'miniplan'; set path 'miniplan'; -- register UDX we'll use to populate test data create function ramp(n int) returns table(i int) language java parameter style system defined java no sql external name 'class net.sf.farrago.test.FarragoTestUDR.ramp'; -- define two physical partitions with identical table definition -- column pk: primary key -- column hicard: will contain mostly distinct values -- column locard: will contain mostly duplicate values create table t1(pk int not null primary key, hicard int, locard int); create table t2(pk int not null primary key, hicard int, locard int); -- define a logical view combining the physical partitions create view v as select * from t1 union all select * from t2; -- populate the first partition, manipulating the UDX output to produce the desired data patterns insert into t1(pk,hicard,locard) select i,i*0.9,i*0.04 from table(ramp(1000)); -- populate the second partition (with a similar but not identical data distribution) insert into t2(pk,hicard,locard) select i+1000,i*0.8,i*0.05 from table(ramp(1000)); -- make some stats on the data distribution available to the optimizer analyze table t1 compute statistics for all columns; analyze table t2 compute statistics for all columns;
Install Miniplanner Plugin
Now execute this DDL to install the plugin:
create jar miniplan.miniplan_plugin
library 'file:${FARRAGO_HOME}/examples/miniplan/plugin/FarragoMiniplan.jar'
options(0);
The .jar manifest specifies class FarragoMiniplanPersonalityFactory to be loaded for implementing net.sf.farrago.session.FarragoSessionPersonalityFactory:
package net.sf.farrago.miniplan;
import com.disruptivetech.farrago.rel.*;
import com.disruptivetech.farrago.volcano.*;
import com.lucidera.opt.*;
import net.sf.farrago.fem.config.*;
import net.sf.farrago.query.*;
import net.sf.farrago.db.*;
import net.sf.farrago.session.*;
import net.sf.farrago.defimpl.*;
import org.eigenbase.oj.rel.*;
import org.eigenbase.rel.*;
import org.eigenbase.rel.rules.*;
import org.eigenbase.relopt.*;
import org.eigenbase.relopt.hep.*;
import java.util.*;
/**
* FarragoMiniplanPersonalityFactory implements the {@link
* FarragoSessionPersonalityFactory} interface by plugging in
* a "mini" planner meant only for tutorial purposes.
*
* @author John V. Sichi
* @version $Id: //open/dev/farrago/src/net/sf/farrago/defimpl/FarragoVolcanoPersonalityFactory.java#4 $
*/
public class FarragoMiniplanPersonalityFactory
implements FarragoSessionPersonalityFactory
{
//~ Methods ----------------------------------------------------------------
// implement FarragoSessionPersonalityFactory
public FarragoSessionPersonality newSessionPersonality(
FarragoSession session,
FarragoSessionPersonality defaultPersonality)
{
return new FarragoMiniplanSessionPersonality(
(FarragoDbSession) session);
}
private static void addMiniplannerRules(FarragoSessionPlanner planner)
{
...
}
private static HepProgram createMiniplannerHepProgram(
Collection<RelOptRule> medPluginRules)
{
...
}
private static class FarragoMiniplanSessionPersonality
extends FarragoDefaultSessionPersonality
{
...
}
private static class FarragoVolcanoMiniplanner
extends FarragoDefaultPlanner
{
...
}
}
Next, change the current session's personality to use the plugin:
alter session implementation set jar miniplan.miniplan_plugin;
Here's the corresponding implementation of net.sf.farrago.session.FarragoSessionPersonality, which introduces a session parameter for switching between heuristic (the default) and Volcano (cost-based):
private static class FarragoMiniplanSessionPersonality
extends FarragoDefaultSessionPersonality
{
private static final String MINIPLAN_VOLCANO = "volcano";
protected FarragoMiniplanSessionPersonality(FarragoDbSession session)
{
super(session);
paramValidator.registerBoolParam(MINIPLAN_VOLCANO, false);
}
// implement FarragoSessionPersonality
public void loadDefaultSessionVariables(
FarragoSessionVariables variables)
{
super.loadDefaultSessionVariables(variables);
variables.setDefault(MINIPLAN_VOLCANO, "false");
}
// implement FarragoSessionPersonality
public FarragoSessionPlanner newPlanner(
FarragoSessionPreparingStmt stmt,
boolean init)
{
...
}
}
To verify that the miniplanner is active, try a query with a join:
explain plan for select * from sales.depts d1, sales.depts d2;
You should get back an error like the one below (whereas this statement would succeed with the default Farrago optimizer):
Error: Optimizer failed to find a valid physical implementation for relational expression rel#6:JoinRel.NONE(left=HepRelVertex#8,right=HepRelVertex#8,condition=true,joinType=inner); see trace for partially optimized plan. Details: reason is [Node's traits (NONE) do not match required traits (ITERATOR)]; while preparing statement [select * from sales.depts d1, sales.depts d2]. (state=,code=0)
Note: This error occurs because the miniplanner has no rule for dealing with a logical JoinRel. Farrago detects that the optimizer has failed to find a physical plan by checking the traits for each relational expression in the final optimizer output and verifying that no expressions remain with calling convention NONE.
In contrast, this statement should succeed with the miniplanner active:
select * from sales.depts union all select * from sales.depts;
Whereas this one should fail, because the miniplanner only understands UNION ALL (not UNION with duplicate removal):
select * from sales.depts union select * from sales.depts;
Test The Heuristic Planner
The heuristic planner implementation involves constructing a Hep program:
private static class FarragoMiniplanSessionPersonality
extends FarragoDefaultSessionPersonality
{
....
// implement FarragoSessionPersonality
public FarragoSessionPlanner newPlanner(
FarragoSessionPreparingStmt stmt,
boolean init)
{
boolean useVolcano =
stmt.getSession().getSessionVariables().getBoolean(
MINIPLAN_VOLCANO);
if (useVolcano) {
FarragoVolcanoMiniplanner planner =
new FarragoVolcanoMiniplanner(stmt);
if (init) {
planner.init();
}
return planner;
} else {
Collection<RelOptRule> medPluginRules =
new LinkedHashSet<RelOptRule>();
HepProgram program =
createMiniplannerHepProgram(
medPluginRules);
FarragoDefaultHeuristicPlanner planner =
new FarragoDefaultHeuristicPlanner(
program,
stmt,
medPluginRules);
addMiniplannerRules(planner);
return planner;
}
}
}
private static HepProgram createMiniplannerHepProgram(
Collection<RelOptRule> medPluginRules)
{
HepProgramBuilder builder = new HepProgramBuilder();
builder.addGroupBegin();
builder.addRuleInstance(RemoveTrivialProjectRule.instance);
builder.addRuleInstance(new PushProjectPastSetOpRule());
builder.addRuleInstance(new MergeProjectRule());
builder.addGroupEnd();
builder.addRuleInstance(PushAggThroughUnionAllRule.instance);
builder.addRuleCollection(medPluginRules);
builder.addRuleInstance(RemoveTrivialProjectRule.instance);
builder.addRuleInstance(new LhxAggRule());
builder.addRuleInstance(new FennelReshapeRule());
builder.addRuleInstance(FennelUnionRule.instance);
builder.addConverters(true);
return builder.createProgram();
}
The Hep program starts with a group of rules which fire together; they involve pushing projections down through the expression tree so that only referenced columns are accessed. This is important since our PushAggThroughUnionAllRule (which fires immediately after) relies on there being nothing in between the aggregation and the underlying union. Up through this point, the rules are all logical->logical transformations. After this, the remaining rules are logical->physical transformations. The medPluginRules is a placeholder which gets expanded with access rules for physical tables. The remaining rules fill in physical implementation for aggregation and union (and any residual projections); finally, converters are added to transform between Fennel and Java calling conventions.
OK, let's try some real queries. (Now would be a good time to read FarragoExplainPlanExplained if you haven't read that before.)
By default, the miniplanner uses the heuristic planner implementation, so we will always see aggregation get pushed down through UNION ALL. First, let's try a full-table aggregation, with no GROUP BY:
0: jdbc:farrago:> !set outputformat csv 0: jdbc:farrago:> explain plan including all attributes for select sum(hicard) from miniplan.v; 'column0' 'FennelToIteratorConverter: rowcount = 1.0, cumulative cost = 20006.0' ' FennelAggRel(groupCount=[0], EXPR$0=[SUM(0)]): rowcount = 1.0, cumulative cost = 20005.0' ' FennelMergeRel: rowcount = 2.0, cumulative cost = 20004.0' ' FennelAggRel(groupCount=[0], EXPR$0=[SUM(0)]): rowcount = 1.0, cumulative cost = 10001.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' ' FennelAggRel(groupCount=[0], EXPR$0=[SUM(0)]): rowcount = 1.0, cumulative cost = 10001.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' 7 rows selected (0.086 seconds)
Notice that the FennelMergeRel is sandwiched between FennelAggRels above and below. You can read this plan as "sum each underlying partition, union those two partial sums into a two-row table, and then sum over that two-row table to produce the final result." (In general, if there are n partitions in the UNION ALL input, there will be n rows to be summed at the end.)
What if we use the default Farrago planner instead? Assuming no one has taught it how to accomplish this pushdown, we get this:
0: jdbc:farrago:> alter session implementation set default; No rows affected (0.021 seconds) 0: jdbc:farrago:> explain plan including all attributes for select sum(hicard) from miniplan.v; 'column0' 'FennelToIteratorConverter: rowcount = 200.0, cumulative cost = 22400.0' ' FennelAggRel(groupCount=[0], EXPR$0=[SUM(0)]): rowcount = 200.0, cumulative cost = 22200.0' ' FennelMergeRel: rowcount = 2000.0, cumulative cost = 22000.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' 5 rows selected (0.165 seconds)
As expected, no pushdown (all the rows will be unioned first before any of them can be aggregated).
Switching back to the miniplanner, let's try a GROUP BY:
0: jdbc:farrago:> alter session implementation set jar miniplan.miniplan_plugin; No rows affected (0.014 seconds) 0: jdbc:farrago:> explain plan including all attributes for select locard,sum(hicard) from miniplan.v group by locard; 'column0' 'FennelToIteratorConverter: rowcount = 9.200000000000001, cumulative cost = 20202.4' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 9.200000000000001, cumulative cost = 20193.2' ' FennelMergeRel: rowcount = 92.0, cumulative cost = 20184.0' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 41.0, cumulative cost = 10041.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[2, 1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 51.0, cumulative cost = 10051.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[2, 1]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' 7 rows selected (0.117 seconds)
We got the pushdown for this one too (this time with hash aggregation), which is good, since according to the optimizer's rowcount estimates, the early aggregation reduces the union input size significantly.
Speaking of rowcounts, they are very accurate for the early aggregations:
0: jdbc:farrago:> select count(distinct locard) from miniplan.t1; 'EXPR$0' '41' 0: jdbc:farrago:> select count(distinct locard) from miniplan.t2; 'EXPR$0' '51' 1 row selected (0.202 seconds)
But note that for the final aggregation, the rowcount estimate is off (the estimate is 9.2 rows, when in fact 51 rows are returned by the query). That's because the cost functions available don't know how to deal with the union, so the estimate for the final aggregation makes a guess that it will reduce the union output size by a factor of 10. In this case, the poor estimate doesn't matter, since nothing else depends on the final output, but if it were used as part of a more complicated plan, we might need to implement an improved cost function.
What if we group by hicard instead of locard?
0: jdbc:farrago:> explain plan including all attributes for select hicard,sum(locard) from miniplan.v group by hicard; 'column0' 'FennelToIteratorConverter: rowcount = 170.0, cumulative cost = 23740.0' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 170.0, cumulative cost = 23570.0' ' FennelMergeRel: rowcount = 1700.0, cumulative cost = 23400.0' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 900.0, cumulative cost = 10900.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' ' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 800.0, cumulative cost = 10800.0' ' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = 10000.0' 7 rows selected (0.122 seconds)
Once again, we got the pushdown. But in this case, we didn't really want it, since the early aggregation did not reduce the union input size by very much, so most of the aggregation work will have to be repeated in the outer LhxAggRel.
Without a cost-based optimizer, Farrago can't discriminate these two syntactically equivalent cases.
Test The Cost Based Planner
Let's retry the last two queries, but this time turning on cost-based optimization. We do this by changing the miniplanner's volcano session parameter:
0: jdbc:farrago:> alter session set "volcano" = true;
No rows affected (0.027 seconds)
0: jdbc:farrago:> explain plan including all attributes for select locard,sum(hicard) from miniplan.v group by locard;
'column0'
'FennelToIteratorConverter: rowcount = 92.0, cumulative cost = {22368.0 rows, 42092.0 cpu, 60000.0 io}'
' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 92.0, cumulative cost = {22276.0 rows, 42000.0 cpu, 60000.0 io}'
' FennelMergeRel: rowcount = 92.0, cumulative cost = {22184.0 rows, 42000.0 cpu, 60000.0 io}'
' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 41.0, cumulative cost = {11041.0 rows, 21000.0 cpu, 30000.0 io}'
' FennelReshapeRel(projection=[[1, 0]], outputRowType=[RecordType(INTEGER LOCARD, INTEGER HICARD) NOT NULL]): rowcount = 1000.0, cumulative cost = {11000.0 rows, 21000.0 cpu, 30000.0 io}'
' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = {10000.0 rows, 20000.0 cpu, 30000.0 io}'
' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 51.0, cumulative cost = {11051.0 rows, 21000.0 cpu, 30000.0 io}'
' FennelReshapeRel(projection=[[1, 0]], outputRowType=[RecordType(INTEGER LOCARD, INTEGER HICARD) NOT NULL]): rowcount = 1000.0, cumulative cost = {11000.0 rows, 21000.0 cpu, 30000.0 io}'
' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = {10000.0 rows, 20000.0 cpu, 30000.0 io}'
9 rows selected (0.335 seconds)
0: jdbc:farrago:> explain plan including all attributes for select hicard,sum(locard) from miniplan.v group by hicard;
'column0'
'FennelToIteratorConverter: rowcount = 200.0, cumulative cost = {23900.0 rows, 41700.0 cpu, 60000.0 io}'
' LhxAggRel(groupCount=[1], EXPR$1=[SUM(1)]): rowcount = 200.0, cumulative cost = {22200.0 rows, 40000.0 cpu, 60000.0 io}'
' FennelMergeRel: rowcount = 2000.0, cumulative cost = {22000.0 rows, 40000.0 cpu, 60000.0 io}'
' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T1]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T1], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = {10000.0 rows, 20000.0 cpu, 30000.0 io}'
' FtrsIndexScanRel(table=[[LOCALDB, MINIPLAN, T2]], projection=[[1, 2]], index=[SYS$CONSTRAINT_INDEX$SYS$PRIMARY_KEY$T2], preserveOrder=[false]): rowcount = 1000.0, cumulative cost = {10000.0 rows, 20000.0 cpu, 30000.0 io}'
5 rows selected (0.167 seconds)
Excellent...we got pushdown when grouping on locard, but not on hicard. (The cost metrics used by Volcano and the heuristic planner are slightly different, so we can't compare them directly across the two optimizers).
The cost-based implementation is even simpler than Hep because it doesn't need to specify any program, just a ruleset; Volcano is free to fire any of the registered rules as it sees fit:
private static void addMiniplannerRules(FarragoSessionPlanner planner)
{
planner.addRule(new PushProjectPastSetOpRule());
planner.addRule(new LhxAggRule());
planner.addRule(RemoveTrivialProjectRule.instance);
planner.addRule(FennelUnionRule.instance);
planner.addRule(new FennelReshapeRule());
planner.addRule(PushAggThroughUnionAllRule.instance);
FennelToIteratorConverter.register(planner);
IteratorToFennelConverter.register(planner);
}
private static class FarragoVolcanoMiniplanner
extends FarragoDefaultPlanner
{
public FarragoVolcanoMiniplanner(FarragoSessionPreparingStmt stmt)
{
super(stmt);
}
public void init()
{
addMiniplannerRules(this);
}
}
So, why would anyone want to use Hep when it's more work than using Volcano, and isn't even cost-based? A full answer is given in FarragoHeuristicPlanner, but in short, Volcano can get lost when operating on large rulesets and plans; so if you're thinking about using it for your optimizer implementation, be sure to test it out on large-scale problems, and be prepared to help improve its generic implementation.
Tracing
To learn how to trace Hep, read HepTracing. This can be very useful for studying how a planner transforms expressions. Try turning it on for the miniplan queries above, and see if you can understand each step in the transformation.
Similar support exists for Volcano, although interpreting the output takes more time since Volcano is keeping track of many different candidates at once.
Collaborative Rules
The examples above illustrate individual rules working in isolation. A useful technique is to make rules work together, so that the output of one rule can be recognized as the input of another.
For example, in LucidDB join optimization, the join optimization is carried out by a big locally cost-based rule which rearranges many joins at once. Normally, this would not be possible, since JoinRel instances in Eigenbase only have two inputs. To address this, the LucidDB optimizer introduces a multi-way join expression (called MultiJoinRel) into the algebra. A family of rules (ConvertMultiJoinRule, PushProjectIntoMultiJoinRule, and PullUpProjectsOnTopOfMultiJoinRule) work together to roll up two-way joins into multi-way joins, taking care of intervening projection expressions as well:
After that phase, LoptOptimizeJoinRule fires on the single remaining MultiJoinRel, optimizing it and transforming the result back into a tree of normal 2-way joins (which is what the rest of the optimizer expects to see). You will never see MultiJoinRel in an EXPLAIN PLAN, because it is purely an intermediate representation.
Real World Optimizers
The following real optimizers have been implemented as part of Eigenbase:
- The default Farrago optimizer uses Hep; it's a grab-bag of just about everything in Eigenbase. See net.sf.farrago.defimpl.FarragoDefaultHeuristicPlanner.
- An alternate Farrago optimizer uses Volcano; see net.sf.farrago.defimpl.FarragoDefaultPlanner (it used to be the default planner, but has not yet been renamed). For an example of how to activate it, see dev/farrago/unitsql/optimizer/index.sql.
- LucidDB uses Hep, but with its own program and ruleset. See com.lucidera.farrago.LucidDbSessionPersonality along with com.lucidera.opt and com.lucidera.lcs.
Others exist in extension projects outside of Eigenbase.
Some unresolved issues are noted in FarragoSortOrder.
Exercises
If you want to gain a deeper understanding, try some of these.
- Reorder or remove some of the miniplanner rules in the heuristic program and see what happens. Use tracing to help see the effect.
- Add rules to the miniplanner to make it capable of implementing filters.
- Suppose you are modeling a distributed executor, where the cost of transmitting tuples across a slow network may be high. Modify the cost-based miniplanner to take this into account, and see how it changes plans for different queries. You can make a simplifying assumption that the UNION ALL represents the network transmission. (For a real optimizer, you could make network location a trait, with a converter representing the transmission cost, but this is a lot more work.)
- Find and fix the bug in PushAggThroughUnionAllRule. Hint: try the COUNT function.
