Package net.sf.farrago.query

Implements Farrago query processing.


Interface Summary
FarragoQueryColumnSet FarragoQueryColumnSet represents a specialization of FarragoMedColumnSet which knows how to interact with FarragoPreparingStmt.
FennelRel FennelRel defines the interface which must be implemented by any RelNode corresponding to a C++ physical implementation conforming to the fennel::ExecStream interface.
FennelRelImplementor Callback used to hold state while converting a tree of FennelRel objects into a plan consisting of FemExecutionStreamDef objects.

Class Summary
FarragoColumnMetadata FarragoColumnMetadata is a default Farrago implementation of MedAbstractColumnMetadata for table level RelNodes.
FarragoExecutableExplainStmt FarragoExecutableExplainStmt implements FarragoSessionExecutableStmt for an EXPLAIN PLAN statement.
FarragoExecutableFennelStmt FarragoExecutableFennelStmt implements FarragoSessionExecutableStmt by executing a pure Fennel statement that requires no compiled Java classes.
FarragoExecutableJavaStmt FarragoExecutableJavaStmt implements FarragoSessionExecutableStmt via a compiled Java class.
FarragoExecutableStmtImpl FarragoExecutableStmtImpl is an abstract base for implementations of FarragoSessionExecutableStmt.
FarragoIndexBuilderRel FarragoIndexBuilderRel is the abstract relational expression corresponding to building an index on a table.
FarragoJavaUdxRel FarragoJavaUdxRel is the implementation for a TableFunctionRel which invokes a Java UDX (user-defined transformation).
FarragoJavaUdxRule FarragoJavaUdxRule is a rule for transforming an abstract TableFunctionRel into a FarragoJavaUdxRel.
FarragoPreparingStmt FarragoPreparingStmt subclasses OJPreparingStmt to implement the FarragoSessionPreparingStmt interface.
FarragoQueryNamedColumnSet An abstract base for implementations of RelOptTable which access data described by Farrago's catalog.
FarragoReduceExpressionsRule Collection of planner rules that apply various simplifying transformations on RexNode trees.
FarragoReduceExpressionsRule.ReducibleExprLocator Helper class used to locate expressions that either can be reduced to literals or contain redundant casts.
FarragoReduceExpressionsRule.ReentrantValuesStmt Evaluates constant expressions via a reentrant query of the form "VALUES (exp1, exp2, exp3, ...)".
FarragoReduceExpressionsRule.RexReplacer Replaces expressions with their reductions.
FarragoReduceValuesRule Planner rule which folds projections and filters into an underlying ValuesRel.
FarragoReentrantStmt FarragoReentrantStmt provides infrastructure for safely executing a reentrant statement as part of the preparation of some outer statement.
FarragoReentrantStmtExecutor FarragoReentrantStmtExecutor extends FarragoReentrantStmt by providing a base method for executing a query plan and returning its result.
FarragoReentrantSubquery Extends FarragoReentrantStmtExecutor to handle subqueries.
FarragoRelImplementor FarragoRelImplementor refines JavaRelImplementor with some Farrago specifics.
FarragoRelImplementor.RelPathEntry RelPathEntry keeps track of a RelNode and its input position within that node's parent RelNode in the execution stream graph.
FarragoRelImplementor.UdfAwareOJRexImplementorTable An operator implementor table which knows about UDF's.
FarragoRelMetadataProvider FarragoRelMetadataProvider implements Farrago specific metadata.
FarragoRelMetadataQuery FarragoRelMetadataQuery defines the relational expression metadata queries specific to Farrago.
FarragoRelUtil Static utilities for Farrago RelNode implementations.
FarragoRexBuilder FarragoRexBuilder refines JavaRexBuilder with Farrago-specific details.
FarragoRoutineInvocation FarragoRoutineInvocation represents an invocation of a FarragoUserDefinedRoutine.
FarragoSqlValidator FarragoSqlValidator refines SqlValidator with some Farrago-specifics.
FarragoStmtValidator FarragoStmtValidator is a default implementation of the FarragoSessionStmtValidator interface.
FarragoTransformDef Defines a FarragoTransform, the java peer of a fennel::JavaTransformExecStream.
FarragoUserDefinedRoutine FarragoUserDefinedRoutine extends SqlFunction with a repository reference to a specific user-defined routine.
FarragoUserDefinedRoutineLookup FarragoUserDefinedRoutineLookup implements the SqlOperatorTable interface by looking up user-defined functions from the repository.
FarragoView An implementation of RelOptTable for accessing a view managed by Farrago.
FennelRelParamId FennelRelParamId is an opaque type representing the reservation of a FennelDynamicParamId during query planning.
FennelToIteratorConverter FennelToIteratorConverter is a Converter from the Fennel calling convention to the iterator calling convention.
IteratorToFennelConverter IteratorToFennelConverter is a Converter from the iterator calling convention to the fennel calling convention.
IteratorToFennelConverter.IteratorToFennelPullRule Rule which converts a RelNode of Fennel calling convention to iterator calling convention by adding a IteratorToFennelConverter.
ReposDefaultValueFactory DefaultValueFactory looks up a default value stored in the catalog, parses it, and converts it to an Expression.
ScalarSubqueryConverter ScalarSubqueryConverter converts subqueries to scalar constants by evaulating them and passing back the resulting constant expression.

Enum Summary

Exception Summary
FarragoPreparingStmt.InvalidPlanException Exception describing why a plan is invalid.
FarragoUnvalidatedDependencyException Special exception to flag a reference to an unvalidated dependency.

Package net.sf.farrago.query Description

Implements Farrago query processing.

Revision $Id: //open/dev/farrago/src/net/sf/farrago/query/package.html#18 $
Copyright Copyright (C) 2005-2009 The Eigenbase Project
Copyright (C) 2005-2009 SQLstream, Inc.
Copyright (C) 2005-2009 LucidEra, Inc.
Author John V. Sichi

Farrago Query Processing

This document provides an overview of how Farrago produces a JDBC ResultSet corresponding to the text of a SELECT statement. This should provide some appreciation for the term SQL engine, as well as a grasp of the most important interfaces and components in the system.

We'll use a simple, innocent-looking statement as an example:

select *,42 as the_answer
from sales.depts as d
where deptno = 10


Our story begins when the prepareStatement method of FarragoJdbcEngineConnection processes an SQL string by creating a new instance of FarragoParser and asking it to parse the statement. This is accomplished via an extension of SqlParser, and the result (assuming no syntax error is thrown) is a tree of SqlNode objects:

Query Implementation Cache Lookup

FarragoJdbcEngineConnection delegates the rest of the preparation to the prepareStmt method of FarragoDatabase, which manages a shared cache of query plan implementations. For this discussion, we'll assume nothing is cached initially, so FarragoDatabase creates a new instance of FarragoPreparingStmt to oversee the preparation process, and calls its validate() and implement() methods.

TODO: details on caching


After parsing, the parse tree must be validated. prepareSql in OJPreparingStmt is called, this time taking the root SqlNode and an instance of SqlValidator (we supply a FarragoSqlValidator). SqlValidator walks the parse tree performing validation tasks such as type inference, resolving identifiers, and expanding '*' in select lists; this results in a transformation of the parse tree (or a thrown exception if validation fails):

In addition, notice that the validator has augmented the parse tree with a scope tree (in this case a simple two-level linear tree since there are no joins). The top-level scope represents the columns produced by the SELECT list; the bottom scope represents the columns to be read from table SALES.DEPT. Note that each SqlIdentifier node in the validated tree is either In the presence of subqueries, there are other possibilities such as a reference to a column produced by an enclosing scope.

Translation to Relational Algebra

The next step is to convert the validated SQL parse tree into a relational algebra expression. The dirty work is all performed by SqlToRelConverter, relying on the validator's scope and type information. The result is again a tree, but this time of instances of RelNode. The target set of relational expressions is constrained to the following abstract operators: The EXPLAIN PLAN statement can be used to see the translated tree for our example:

explain plan without implementation for
select *,42 as the_answer
from sales.depts as d
where deptno = 10

This yields:

ProjectRel(DEPTNO=[$0], NAME=[$1], THE_ANSWER=[42])

Here's a graphical representation:

The three-dimensional boxes are relational algebra nodes (instances of RelNode); the two-dimensional boxes are validated row expressions represented by the RexNode object model. Besides children and row expressions, relational expressions may have additional attributes; e.g. ProjectRel has an array of names to be assigned to the columns it produces, and TableAccessRel has a reference to the table to be scanned. Within a row expression, a RexInputRef may refer to the output of a child relational expression via variables with names like $N (hence the $0 in the ProjectRel's expression refers to something different from the $0 in the FilterRel's condition expression, since the expression is relative to the containing RelNode).


Query optimization transforms the abstract relational algebra expression described above into an equivalent expression consisting only of operators for which physical implementations are available. For an overview of the process, see the Volcano optimizer docs. To tailor the optimization process for our requirements, FarragoDefaultPlanner subclasses VolcanoPlanner to define Farrago-specific rules, relational expressions, and calling conventions.

Farrago constrains the optimizer to the following calling conventions:

To see the output of the optimizer, we can use EXPLAIN PLAN again:

explain plan for
select *,42 as the_answer
from sales.depts as d
where deptno = 10

(This time WITHOUT IMPLEMENTATION was left out, and the default is WITH IMPLEMENTATION, which is what we want.) This yields:

IterCalcRel(DEPTNO=[$0], NAME=[$1], THE_ANSWER=[42])
    FtrsIndexSearchRel(table=[SALES.DEPTS], projection=[*], index=[SYS$CONSTRAINT_INDEX$DEPTS$SYS$PRIMARY_KEY], uniqueKey=[true], preserveOrder=[false],outer=[false],inputKeyProj=[*],inputJoinProj=[[]])

which corresponds to the following relational expression tree:

Wow, what happened? The optimizer found that the table's clustered index could satisfy the WHERE clause, and accordingly transformed the query using a FtrsIndexSearchRel for the table access. (It knew how to do this because FarragoDefaultPlanner told it about FtrsScanToSearchRule.) What's interesting is that this search is sandwiched between Java iterators. The lowest level (IterOneRowRel) produces a single row with no columns; the next level up (IterCalcRel) produces the constant DEPTNO value (10) which we're searching for. (This can remain anonymous as $f0 since Fennel accesses data by tuple position, not name.) Now, the optimizer wants to feed this into the Fennel search as the input key, but the search has FENNEL_PULL calling convention, while IterCalcRel has ITERATOR calling convention. So, a ConverterRel is required; in this case, IteratorToFennelConverter.

But wait, there's more! The FtrsIndexSearchRel is going to produce matching rows in FENNEL_PULL representation, but in order to compute the select list and return results via JDBC, we need another converter: FennelToIteratorConverter. The top-level IterCalcRel then implements the original abstract ProjectRel.

Physical Implementation

Once the optimizer has decided on the best implementation, it's time to generate corresponding executable code. This is the job of JavaRelImplementor, which walks the optimized RelNode tree calling implement on each expression, producing the parse tree representation of a Java class. From this, the query processor generates the Java class definition as text, saves it to a file, and then invokes the Java compiler and loads the resulting classfile. Here's the Java class generated for our example:

package net.sf.farrago.dynamic.stmt39449;

public class ExecutableStmt
    public static class Ojp_0 extends net.sf.farrago.type.runtime.FarragoSyntheticObject
        public Ojp_0()

    public static class Ojp_1 extends net.sf.farrago.type.runtime.FarragoSyntheticObject
        public int $f0;

        public Ojp_1()

        public Ojp_1( int $f0 )
            this.$f0 = $f0;

    public static class Oj_VARCHAR_128_ISO_8859_1 extends net.sf.farrago.type.runtime.EncodedCharPointer
        protected java.lang.String getCharsetName()
            return "ISO-8859-1";

    public static class Ojp_2 extends net.sf.farrago.type.runtime.FarragoSyntheticObject
        public int DEPTNO;

        public net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Oj_VARCHAR_128_ISO_8859_1 NAME;

        public Ojp_2()

        public Ojp_2( int DEPTNO, net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Oj_VARCHAR_128_ISO_8859_1 NAME )
            this.DEPTNO = DEPTNO;
            this.NAME = NAME;

    public static class Ojp_3 extends net.sf.farrago.type.runtime.FarragoSyntheticObject
        public int DEPTNO;

        public net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Oj_VARCHAR_128_ISO_8859_1 NAME;

        public long THE_ANSWER;

        public Ojp_3()

        public Ojp_3( int DEPTNO, net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Oj_VARCHAR_128_ISO_8859_1 NAME, long THE_ANSWER )
            this.DEPTNO = DEPTNO;
            this.NAME = NAME;
            this.THE_ANSWER = THE_ANSWER;


    public static java.lang.Object execute( net.sf.farrago.runtime.FarragoRuntimeContext connection_p )
        throws java.sql.SQLException
        final net.sf.farrago.runtime.FarragoRuntimeContext connection = connection_p;
        return new org.eigenbase.runtime.CalcIterator( connection.newFennelIterator( new net.sf.farrago.runtime.FennelTupleReader(){

            private net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_2 oj_var3 = new net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_2();

            public java.lang.Object unmarshalTuple( java.nio.ByteBuffer byteBuffer, byte[] byteArray, java.nio.ByteBuffer sliceBuffer )
                int oj_var4 = byteBuffer.position();
                oj_var3.DEPTNO = sliceBuffer.getInt( 0 );
                int oj_var5 = oj_var4 + sliceBuffer.getShort( 4 );
                oj_var3.NAME.setPointer( byteArray, 6 + oj_var4, oj_var5 );
                sliceBuffer.position( oj_var5 - oj_var4 );
                return oj_var3;
        }, "FtrsIndexSearchRel#74:315", connection.newJavaTupleStream( 96, new net.sf.farrago.runtime.FennelTupleWriter(){

            protected void marshalTupleOrThrow( java.nio.ByteBuffer sliceBuffer, java.lang.Object object )
                net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_1 oj_var2 = (net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_1) object;
                sliceBuffer.putInt( 0, oj_var2.$f0 );
                sliceBuffer.position( 4 );
        }, new org.eigenbase.runtime.CalcIterator( java.util.Collections.singletonList( new net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_0() ).iterator() ){

            private net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_1 oj_var1 = new net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_1();

            protected java.lang.Object calcNext()
                while (inputIterator.hasNext()) {
                    net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_0 oj_var0 = (net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_0);
                    oj_var1.$f0 = (int) (int) 10;
                    return oj_var1;
                return null;
        } ) ) ){

            private net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_3 oj_var7 = new net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_3();

            protected java.lang.Object calcNext()
                while (inputIterator.hasNext()) {
                    net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_2 oj_var6 = (net.sf.farrago.dynamic.stmt39449.ExecutableStmt$Ojp_2);
                    oj_var7.DEPTNO = (int) oj_var6.DEPTNO;
                    oj_var7.NAME.assignFrom( oj_var6.NAME );
                    oj_var7.THE_ANSWER = (long) 42;
                    return oj_var7;
                return null;

Yeesh, that's ugly! How can we interpret this jumble in the context of the implementation plan?

Fennel Implementation

Let's look more deeply into the Fennel portion of the plan. When RelImplementor reaches a FennelToIteratorConverter in its traversal of the optimized tree, the corresponding implement method performs a sub-traversal of the connected subtree of nodes implementing the FennelRel interface. Rather than generating Java code, these nodes generate (via the FennelRel.toTupleStreamDef method) a tree of FemTupleStreamDef instances specifying the Fennel portion of the plan. This tree is later saved as an XMI string from which the plan can be reconstructed at any time. Here's the XML for our example:

<XMI xmi.version = '1.2' xmlns:CWM = 'org.omg.xmi.namespace.CWM' xmlns:FEM = 'org.omg.xmi.namespace.FEM'
  xmlns:CWMRDB = 'org.omg.xmi.namespace.CWMRDB' xmlns:FEMFennel = 'org.omg.xmi.namespace.FEMFennel'
  xmlns:FEMConfig = 'org.omg.xmi.namespace.FEMConfig' timestamp = 'Tue May 11 11:01:22 PDT 2004'>
      <XMI.exporter>Netbeans XMI Writer</XMI.exporter>
    <FEMFennel:CmdPrepareExecutionStreamGraph = 'a1'>
        <FEMFennel:IndexSearchDef = 'a2' name = 'FtrsIndexSearchRel#74:315'
          cachePageQuota = '2' cachePageMin = '2' cachePageMax = '2' rootPageId = '3'
          segmentId = '1' indexId = '2709' uniqueKey = 'true' outerJoin = 'false'>
            <FEMFennel:TupleProjection = 'a3'>
                <FEMFennel:TupleAttrProjection = 'a4' attributeIndex = '0'/>
            <FEMFennel:TupleDescriptor = 'a5'>
                <FEMFennel:TupleAttrDescriptor = 'a6' typeOrdinal = '5' isNullable = 'false'
                  byteLength = '0'/>
                <FEMFennel:TupleAttrDescriptor = 'a7' typeOrdinal = '13' isNullable = 'false'
                  byteLength = '128'/>
            <FEMFennel:TupleProjection = 'a8'>
                <FEMFennel:TupleAttrProjection = 'a9' attributeIndex = '0'/>
                <FEMFennel:TupleAttrProjection = 'a10' attributeIndex = '1'/>
            <FEMFennel:JavaTupleStreamDef xmi.idref = 'a11'/>
        <FEMFennel:JavaTupleStreamDef = 'a11' name = 'IteratorToFennelConverter#96:324'
          cachePageQuota = '1' cachePageMin = '1' cachePageMax = '1' streamId = '96'>
            <FEMFennel:TupleDescriptor = 'a12'>
                <FEMFennel:TupleAttrDescriptor = 'a13' typeOrdinal = '5' isNullable = 'false'
                  byteLength = '0'/>
            <FEMFennel:IndexSearchDef xmi.idref = 'a2'/>
        <FEMFennel:StreamGraphHandle xmi.idref = 'a14'/>
    <FEMFennel:StreamGraphHandle = 'a14' longHandle = '137731624'/>

(The easiest way to obtain this XML is to set net.sf.farrago.fennel.level=FINE in and then dig through FarragoTrace.log after executing an SQL statement. Search for "CmdPrepareExecutionStreamGraph". For more information on the Java representation of Fennel TupleStreams, see the JNI design doc.)

The root of the TupleStream tree above is the FEMFennel:IndexSearchDef node (whose name attribute corresponds to the stream name referenced in the generated Java code above). The leaf is the FEMFennel:JavaTupleStreamDef node, which tells Fennel how to get the search key from the lower-level Java iterators. (TBD: more about this and IteratorToFennelConverter).


Whew. Now we actually want to execute the generated code. This part is easy. We use reflection to invoke the generated execute() method, which returns an Iterator instance, and pass that to a new instance of FarragoTupleIterResultSet, which produces JDBC result data and metadata, as well as taking care of cleanup when the result set is closed.

Try This at Home

You can see the Fennel portion of the data processing by setting net.sf.fennel.xo.level=FINE in, executing an SQL statement, and then perusing FarragoTrace.log. Warning: The output can be huge for non-trivial queries. Here's the output for our example:

May 11, 2004 11:08:27 AM net.sf.farrago.db.FarragoDbSession prepare
INFO: select *,42 as the_answer from sales.depts d where deptno=10
May 11, 2004 11:08:32 AM net.sf.farrago.db.FarragoDbStmtContext traceExecute
FINE: select *,42 as the_answer from sales.depts d where deptno=10
May 11, 2004 11:08:33 AM net.sf.fennel.xo.IteratorToFennelConverter#96:324 <native>
FINE: [ 10 ]
May 11, 2004 11:08:33 AM net.sf.fennel.xo.FtrsIndexSearchRel#74:315 <native>
FINE: [ 10, 'Sales' ]

The entry for IteratorToFennelConverter is the search key read from Java, and the entry for FtrsIndexSearchRel is the result of the search which is returned to Java.


If you have read through this entire doc, you are probably wondering how such a heavyweight procedure is ever going to provide decent performance in the context of the kind of rapid-fire statement execution used in transactional applications. Here are some planned improvements: TODO: overview of datatype issues.