Relational Operators in Apache Calcite

When a consumer submits a question to a database, the optimizer interprets the question string to an intermediate illustration (IR) and applies numerous transformations to seek out the optimum execution plan.

Apache Calcite makes use of relational operators because the intermediate illustration. On this weblog submit, we talk about the design of frequent relational operators in Apache Calcite.

Syntax Tree

Question optimization begins with parsing when a question string is translated right into a syntax tree, which defines the syntactic construction of the question.

Since each database has a parser, the syntax tree would possibly seem like a very good candidate for the intermediate illustration as a result of it’s available to the database.

There are two vital issues with syntax tree as question’s IR:

1. AST has a extremely sophisticated construction, because of the concerned ANSI SQL syntax. For instance, a `SELECT` node might have devoted baby nodes for `FROM`, `WHERE`, `ORDER BY`, `GROUP BY`, and many others.
2. AST fashions the syntactic construction however not relational semantics. It might be problematic to map some legitimate relational transformations to the syntax tree. For instance, a semi-join can’t be expressed simply with ANSI SQL syntax.

Mixed, this makes question optimization over syntax timber difficult and never versatile.

Relational Tree

Another IR is a relational operator tree. We might outline frequent relational operators, akin to `Challenge`, `Filter`, `Be a part of`, `Combination`. The question represented in such a approach is way less complicated to optimize as a result of relational operators have a well-defined scope and often have just one enter (aside from joins and set operators). This dramatically simplifies frequent relational optimizations, akin to operator transposition. Additionally, it provides implementors flexibility to mannequin operators independently of the database syntax guidelines.

The principle drawback is the necessity to translate the syntax tree right into a relational tree, which is usually non-trivial, particularly with advanced syntax constructs like subqueries or frequent desk expressions. Nonetheless, the simplicity and adaptability of relational operators often outweigh by a excessive margin the extra efforts on translation.

Apache Calcite parses the question right into a syntax tree. Then it performs the semantic validation of the syntax tree utilizing the SqlValidatorImpl class, resolving concerned information varieties alongside the best way. Lastly, the validated syntax tree is transformed right into a tree or relational operators utilizing the SqlToRelConverter class. The following optimizations are carried out on the relational tree.

On this part, we talk about the design of Apache Calcite relational operators.

Terminology

We begin with a number of simplified definitions, which aren’t exact however ample for this weblog submit.

An attribute is a pair of a reputation and a knowledge kind. An attribute worth is outlined by an attribute title and worth from the attribute kind area. A tuple is an unordered set of attribute values. No two attribute values within the tuple might have the identical attribute title. A relation is a set of tuples. Each tuple inside the relation has the identical set of attributes. Relational operators take zero, one, or extra enter relations and produce an output relation.

Operators

To assemble a tree of relational operators, we want the flexibility to outline operator inputs. Many operators want entry to attributes of the enter relations. Subsequently we additionally want the flexibility to reference enter attributes. These are two key necessities for the relational operator interface.

In Apache Calcite, the relational operator is represented by the RelNode interface. The operator might have zero, one, or extra enter operators. For instance, `TableScan` is an 0-ary operator, `Filter` is a unary operator, and `Union` is an N-ary operator. Each operator exposes the `RelDataType`, which is an ordered checklist of operator attributes. That is ample to assemble arbitrarily advanced relational timber.

Row Expressions

Operators describe numerous transformations to tuples. A RexNode interface defines an operation that applies to some attribute values of a tuple and produces one other worth. Frequent `RexNode` varieties:

1. `RexLiteral` – a relentless.
2. `RexInputRef` – a reference to operator’s enter attribute.
3. `RexCall` – a perform name.

For instance, the expression `title = “John”` can be represented as follows.

Discover that `RexInputRef` references the enter’s attribute by index, which signifies that attribute order is vital in Apache Calcite. On the intense facet, it simplifies the design, as you do not want to care about attribute names and potential naming conflicts (consider a be part of of two tables, which have an attribute with the identical title). However, it has a detrimental impact on be part of order planning, as we will see beneath.

Now, as we perceive the fundamentals, let’s talk about the commonest Apache Calcite operators: `TableScan`, `Challenge`, `Filter`, `Calc`, `Combination`, and `Be a part of`.

Different vital operators are `Window` and `Union`. We omit them on this weblog submit as a result of they comply with the identical design rules because the beforehand talked about operators.

TableScan

`TableScan` is a leaf 0-ary operator that defines a scan of some information supply.

The operator incorporates the `org.apache.calcite.schema.Desk` occasion, which describes a knowledge supply that produces tuples. It might characterize a relational desk, an index, a view, a CSV file, a community connection, or the rest. As an implementor, you present the schema of your database that incorporates some `Desk` cases. Apache Calcite will create a `TableScan` operator with the referenced `Desk` inside while you discuss with that desk within the question. The `Desk` should expose the row kind in order that the dad or mum operators know which attributes can be found from the `TableScan`.

Challenge

The `Challenge` operator defines row expressions that must be utilized to enter tuples to supply new tuples. The operator produces one output tuple for each enter tuple. Expressions are organized in an inventory.

As a result of Apache Calcite makes use of native indexes to reference enter attributes, the `Challenge` operator can also be injected each time we have to change the attribute’s order. For instance, if there’s a desk with attributes `[a, b]` in that order and we execute `SELECT b, a FROM t`, the `Challenge` operator will probably be added on prime of the `TableScan` to reorder attributes as required by the question. This complicates question planning as a result of the optimizer spends time making use of transformation guidelines to in any other case ineffective operators that do a trivial reorder.

Bodily implementations of the `Challenge` operator should modify the enter traits. E.g., if the `TableScan` produces tuples ordered by `[b]` however the `Challenge` operator would not challenge that column, the order will probably be misplaced.

The relational tree of the question `SELECT a, a+b FROM t`  would possibly seem like this:

Filter

The `Filter` operator returns tuples that fulfill a predicate. A predicate is a row expression. The `Filter` output row kind is just like the enter’s row kind. Bodily implementations of the `Filter` operator often do not change enter traits.

The question `SELECT a, a+b FROM t WHERE a+b>5` might be represented as:

Calc

The `Calc` is a particular operator that mixes the performance of `Challenge` and `Filter` operators and performs the frequent sub-expression elimination. Internally, it splits all composite row expressions into primitive expressions. Expressions are organized in an inventory. The particular `RexLocalRef` node is used to hyperlink siblings. `Challenge` turns into an inventory of expression indexes that must be uncovered from the operator. `Filter` turns into an non-obligatory expression index that filters enter tuples.

Apache Calcite gives a variety of optimization guidelines for `Challenge` and `Filter` operators. These similar optimizations are typically not applied for the `Calc` operator as a result of it might basically require duplication of guidelines logic. As an alternative, chances are you’ll do the cost-based optimization with `Challenge` and `Filter` operations solely after which convert `Challenge` and `Filter` operators into `Calc` in a separate heuristic part. Apache Calcite gives dedicated rules for that. We touched on the multi-phase optimization in our earlier blog post.

Combination

The `Combination` operator fashions the appliance of mixture capabilities to the enter. The operator consists of two components – the group keys and mixture capabilities.

The group keys outline which enter attributes to make use of to assemble the teams. The assertion `GROUP BY a, b` yields the grouping key `[0, 1]` if `a` and `b` are positioned on enter positions 0 and 1, respectively. If there isn’t a `GROUP BY` clause, the group key can be empty.

There will probably be a number of group keys if there’s a `ROLLUP` or `CUBE` clause. For instance, `GROUP BY ROLLUP a, b` would yield the grouping keys `[0,1], [0], []`, which signifies that we wish to output teams for `[a, b]`, teams for `[a]`, and world aggregates with none grouping.

If there may be an expression within the `GROUP BY` assertion, it might be moved to a separate `Challenge` operator beneath `Combination`. Because of this it’s ample to outline enter attribute indexes for the group keys as a substitute of defining row expressions. Separation of projections and aggregations is important to maintain the complexity of optimization guidelines underneath management. In any other case, we must repeat logic from the `Challenge` optimization guidelines within the `Combination` optimization guidelines.

The mixture capabilities are the checklist of aggregates that must be computed for the teams. The mixture capabilities don’t use the `RexNode` interface as a result of they function on a number of tuples versus row expressions which are utilized to a single tuple. Just like group keys, mixture capabilities discuss with enter columns by indexes. For instance, the perform `SUM(a)` is transformed to `SUM(0)` if the enter attribute `a` is positioned at place 0. Likewise, advanced expressions are moved to a `Challenge` operator beneath the `Combination`. Combination capabilities may have superior properties, such because the `DISTINCT` flag or an non-obligatory filter. We are going to talk about these options intimately in future weblog posts.

The `Combination` operator outputs group keys adopted by mixture capabilities. For the question `SELECT SUM(a), b GROUP BY b`, the related `Combination` operator would output `[0:b, 1:SUM(a)]`.

Contemplate the plan for the question `SELECT SUM(a+b), c FROM t GROUP BY c` beneath. Discover two `Challenge` operators: one to calculate `a+b` and one other to output `SUM` earlier than the attribute `c`.

Be a part of

The `Be a part of` operator joins two inputs. The operator defines the be part of kind (inside, left/proper/full outer, semi, and many others.) and the non-obligatory predicate.

The `Be a part of` operator outputs all columns from the left enter adopted by all columns from the appropriate enter. There’s the conference: given the left enter with `L` attributes and the appropriate enter with `R` attributes:

• If the referenced column index `I` is between zero and `L` unique, we should always use the left enter’s attribute at place `I`.
• In any other case, we should always use the appropriate enter’s attribute at place `I – L`.

In our earlier blog post, we mentioned that cost-based optimizers depend on the equivalence property of operators to encode different plans effectively within the MEMO information construction. In Apache Calcite, `Be a part of(AxB)` and `Be a part of(BxA)` aren’t semantically equal as a result of Apache Calcite depends on attribute indexes within the `RexInputRef` class. Guardian operators of `Be a part of(AxB)` and `Be a part of(BxA)` should use completely different indexes when referring to the identical be part of attribute. Inside be part of predicates may also reference attributes at completely different indexes.

Contemplate the `JoinCommute` rule that modifications the order of inputs. To use this rule, we have to (a) rewrite the interior predicate and (b) add the `Challenge` on prime of the brand new `Be a part of` to revive the unique order of attributes.

This extra `Challenge` prevents the execution of different guidelines. For instance, the `JoinAssociate` rule tries to reorder `(A be part of B) be part of C` to `A be part of (B be part of C)`. The rule appears for a sample “Be a part of on prime of the Be a part of”. However with the extra `Challenge`, we have now solely “Be a part of on prime of the Challenge”. To mitigate this, we might use the `JoinProjectTransposeRule` that transposes `Be a part of` and `Challenge`, however this dramatically decreases planner’s efficiency to the extent that Apache Calcite can not do the exhaustive cost-based be part of planning on greater than 5-6 tables in an affordable time.

The choice resolution can be to function on distinctive column names somewhat than indexes. Spark Catalyst and CockroachDB comply with this strategy. However this is able to require introducing some distinctive identifier to each equivalence group, which can also be a problem by itself.

Apache Calcite parses the question string right into a syntax tree. The syntax tree is then translated right into a tree of relational operators, which have a less complicated inner construction and are extra appropriate for the next optimizations.

We mentioned a number of frequent relational operators in Apache Calcite. `Challenge` transforms each tuple from the enter into one other tuple. `Filter` operator returns enter tuples that cross the predicate. `Calc` combines `Challenge` and `Filter` performance and eliminates the frequent sub-expressions. `Combination` operator performs the grouping and applies mixture capabilities. `Be a part of` operator combines tuples two inputs and applies the predicate.

Designing relational operators is difficult. Each choice might open alternatives for brand new optimizations however block others. The index-based enter attribute references in Apache Calcite are a very good instance of such a trade-off when a simplification helpful for a lot of optimization guidelines results in extreme issues with probably the most crucial optimizer duties – be part of order planning.

In future weblog posts, we are going to dive into concrete optimizations that Apache Calcite applies to particular person operators. Keep tuned!

We’re at all times prepared that will help you together with your question optimizer design. Simply let us know.