Algebra

Relational algebra is at the heart of Calcite. Every query isrepresented as a tree of relational operators. You can translate fromSQL to relational algebra, or you can build the tree directly.

Planner rules transform expression trees using mathematical identitiesthat preserve semantics. For example, it is valid to push a filterinto an input of an inner join if the filter does not referencecolumns from the other input.

Calcite optimizes queries by repeatedly applying planner rules to arelational expression. A cost model guides the process, and theplanner engine generates an alternative expression that has the samesemantics as the original but a lower cost.

The planning process is extensible. You can add your own relationaloperators, planner rules, cost model, and statistics.

Algebra builder

The simplest way to build a relational expression is to use the algebra builder,RelBuilder.Here is an example:

TableScan

final FrameworkConfig config;
final RelBuilder builder = RelBuilder.create(config);
final RelNode node = builder
  .scan("EMP")
  .build();
System.out.println(RelOptUtil.toString(node));

(You can find the full code for this and other examples inRelBuilderExample.java.)

The code prints

LogicalTableScan(table=[[scott, EMP]])

It has created a scan of the EMP table; equivalent to the SQL

SELECT *
FROM scott.EMP;

Adding a Project

Now, let’s add a Project, the equivalent of

SELECT ename, deptno
FROM scott.EMP;

We just add a call to the project method before callingbuild:

final RelNode node = builder
  .scan("EMP")
  .project(builder.field("DEPTNO"), builder.field("ENAME"))
  .build();
System.out.println(RelOptUtil.toString(node));

and the output is

LogicalProject(DEPTNO=[$7], ENAME=[$1])
  LogicalTableScan(table=[[scott, EMP]])

The two calls to builder.field create simple expressionsthat return the fields from the input relational expression,namely the TableScan created by the scan call.

Calcite has converted them to field references by ordinal,$7 and $1.

Adding a Filter and Aggregate

A query with an Aggregate, and a Filter:

final RelNode node = builder
  .scan("EMP")
  .aggregate(builder.groupKey("DEPTNO"),
      builder.count(false, "C"),
      builder.sum(false, "S", builder.field("SAL")))
  .filter(
      builder.call(SqlStdOperatorTable.GREATER_THAN,
          builder.field("C"),
          builder.literal(10)))
  .build();
System.out.println(RelOptUtil.toString(node));

is equivalent to SQL

SELECT deptno, count(*) AS c, sum(sal) AS s
FROM emp
GROUP BY deptno
HAVING count(*) > 10

and produces

LogicalFilter(condition=[>($1, 10)])
  LogicalAggregate(group=[{7}], C=[COUNT()], S=[SUM($5)])
    LogicalTableScan(table=[[scott, EMP]])

Push and pop

The builder uses a stack to store the relational expression produced byone step and pass it as an input to the next step. This allows themethods that produce relational expressions to produce a builder.

Most of the time, the only stack method you will use is build(), to get thelast relational expression, namely the root of the tree.

Sometimes the stack becomes so deeply nested it gets confusing. To keep thingsstraight, you can remove expressions from the stack. For example, here we arebuilding a bushy join:

.
               join
             /      \
        join          join
      /      \      /      \
CUSTOMERS ORDERS LINE_ITEMS PRODUCTS

We build it in three stages. Store the intermediate results in variablesleft and right, and use push() to put them back on the stack when it istime to create the final Join:

final RelNode left = builder
  .scan("CUSTOMERS")
  .scan("ORDERS")
  .join(JoinRelType.INNER, "ORDER_ID")
  .build();
final RelNode right = builder
  .scan("LINE_ITEMS")
  .scan("PRODUCTS")
  .join(JoinRelType.INNER, "PRODUCT_ID")
  .build();
final RelNode result = builder
  .push(left)
  .push(right)
  .join(JoinRelType.INNER, "ORDER_ID")
  .build();

Field names and ordinals

You can reference a field by name or ordinal.

Ordinals are zero-based. Each operator guarantees the order in which its outputfields occur. For example, Project returns the fields in the generated byeach of the scalar expressions.

The field names of an operator are guaranteed to be unique, but sometimes thatmeans that the names are not exactly what you expect. For example, when youjoin EMP to DEPT, one of the output fields will be called DEPTNO and anotherwill be called something like DEPTNO_1.

Some relational expression methods give you more control over field names:

• project lets you wrap expressions using alias(expr, fieldName). Itremoves the wrapper but keeps the suggested name (as long as it is unique).
• values(String[] fieldNames, Object… values) accepts an array of fieldnames. If any element of the array is null, the builder will generate a uniquename.

If an expression projects an input field, or a cast of an input field, it willuse the name of that input field.

Once the unique field names have been assigned, the names are immutable.If you have a particular RelNode instance, you can rely on the field names notchanging. In fact, the whole relational expression is immutable.

But if a relational expression has passed through several rewrite rules (seeRelOptRule), the fieldnames of the resulting expression might not look much like the originals.At that point it is better to reference fields by ordinal.

When you are building a relational expression that accepts multiple inputs,you need to build field references that take that into account. This occursmost often when building join conditions.

Suppose you are building a join on EMP,which has 8 fields [EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTNO]and DEPT,which has 3 fields [DEPTNO, DNAME, LOC].Internally, Calcite represents those fields as offsets intoa combined input row with 11 fields: the first field of the left input isfield #0 (0-based, remember), and the first field of the right input isfield #8.

But through the builder API, you specify which field of which input.To reference “SAL”, internal field #5,write builder.field(2, 0, "SAL"), builder.field(2, "EMP", "SAL"),or builder.field(2, 0, 5).This means “the field #5 of input #0 of two inputs”.(Why does it need to know that there are two inputs? Because they are stored onthe stack; input #1 is at the top of the stack, and input #0 is below it.If we did not tell the builder that were two inputs, it would not know how deepto go for input #0.)

Similarly, to reference “DNAME”, internal field #9 (8 + 1),write builder.field(2, 1, "DNAME"), builder.field(2, "DEPT", "DNAME"),or builder.field(2, 1, 1).

Recursive Queries

Warning: The current API is experimental and subject to change without notice.A SQL recursive query, e.g. this one that generates the sequence 1, 2, 3, …10:

WITH RECURSIVE aux(i) AS (
  VALUES (1)
  UNION ALL
  SELECT i+1 FROM aux WHERE i < 10
)
SELECT * FROM aux

can be generated using a scan on a TransientTable and a RepeatUnion:

final RelNode node = builder
  .values(new String[] { "i" }, 1)
  .transientScan("aux")
  .filter(
      builder.call(
          SqlStdOperatorTable.LESS_THAN,
          builder.field(0),
          builder.literal(10)))
  .project(
      builder.call(
          SqlStdOperatorTable.PLUS,
          builder.field(0),
          builder.literal(1)))
  .repeatUnion("aux", true)
  .build();
System.out.println(RelOptUtil.toString(node));

which produces:

LogicalRepeatUnion(all=[true])
  LogicalTableSpool(readType=[LAZY], writeType=[LAZY], tableName=[aux])
    LogicalValues(tuples=[[{ 1 }]])
  LogicalTableSpool(readType=[LAZY], writeType=[LAZY], tableName=[aux])
    LogicalProject($f0=[+($0, 1)])
      LogicalFilter(condition=[<($0, 10)])
        LogicalTableScan(table=[[aux]])

API summary

Relational operators

The following methods create a relational expression(RelNode),push it onto the stack, andreturn the RelBuilder.

Argument types:

• expr, interval RexNode
• expr…, requiredField… Array ofRexNode
• exprList, measureList, partitionKeys, orderKeys,requiredFieldList Iterable ofRexNode
• fieldOrdinal Ordinal of a field within its row (starting from 0)
• fieldName Name of a field, unique within its row
• fieldName… Array of String
• fieldNames Iterable of String
• rowType RelDataType
• groupKey RelBuilder.GroupKey
• aggCall… Array of RelBuilder.AggCall
• aggCallList Iterable of RelBuilder.AggCall
• value… Array of Object
• value Object
• tupleList Iterable of List of RexLiteral
• all, distinct, strictStart, strictEnd, allRows boolean
• alias String
• correlationId CorrelationId
• variablesSet Iterable ofCorrelationId
• varHolder Holder of RexCorrelVariable
• patterns Map whose key is String, value is RexNode
• subsets Map whose key is String, value is a sorted set of String
• distribution RelDistribution
• collation RelCollation
• operator SqlOperator
• joinType JoinRelType

The builder methods perform various optimizations, including:

• project returns its input if asked to project all columns in order
• filter flattens the condition (so an AND and OR may have more than 2 children),simplifies (converting say x = 1 AND TRUE to x = 1)
• If you apply sort then limit, the effect is as if you had called sortLimit

There are annotation methods that add information to the top relationalexpression on the stack:

Stack methods

Scalar expression methods

The following methods return a scalar expression(RexNode).

Many of them use the contents of the stack. For example, field("DEPTNO")returns a reference to the “DEPTNO” field of the relational expression justadded to the stack.

Pattern methods

The following methods return patterns for use in match.

Group key methods

The following methods return aRelBuilder.GroupKey.

Aggregate call methods

The following methods return anRelBuilder.AggCall.

To further modify the AggCall, call its methods: