Query Planning & Optimization I: SqlNode, RelNode and RexNode

• Query String <-> SqlNode <-> RelNode -- RexNode

SqlNode - Node in the SQL parse tree

SqlNode forms the abstract syntax tree (AST)/ SQL parse tree that represents the actual structure of the query a user input. When a query is first parsed, it's parsed into a SqlNode. For instance, by calling Planner.parse(), a SELECT query will be parsed into a SqlSelect object (example). SqlNode can also be translated into a query string by calling toSqlString().

SqlNode can be a call (SqlCall) which is the non-leaf node in the parse tree and instantiates an operator (SqlOperator), an immutable literal (SqlLiteral), an identifier (SqlIdentifier), and so forth.

RelNode - Node used in the optimizer

RelNode represents a relational expression. After being parsed into SqlNode, a query is then converted to RelNode (by Planner.rel(SqlNode)) for use in the optimizer to decide how to execute a query.

Relational expressions process data, so their names are typically verbs: Sort, Join, Project, Filter, Scan, Sample.

When a query is first converted to RelNode, there will be logical nodes like LogicalProject, LogicalFilter, LogicalTableScan (see the output of the example SimpleQueryPlanner.java), etc. If a RelNode has some particular planner rules, it should implement the public static method AbstractRelNode.register(). The rules are triggered by the planner and convert the logical nodes to physical ones (☞ TODO: example and more detailed study in optimizers). The physical RelNodes could have specific user implementations to represent the execution of some expression in a third system (TODO: details about plugin implementations of RelNodes).

(｡ʘ‿ʘ｡ this is how we can use Calcite to support SQL processing in Husky)

Every relational expression must derive from AbstractRelNode. (Why have the RelNode interface, then? We need a root interface, because an interface can only derive from an interface.)

RexNode - A row expression

RexNode represents a row expression that is typically contained within a RelNode. The row expression contains operations performed on a single row.

Every row-expression has a type. (Compare with SqlNode, which is created before validation, and therefore types may not be available.)

A RexNode might be a reference to a field from an input to the RelNode (RexFieldAccess), a function call (RexCall), a window aggregation call (RexOver, a subclass of RexCall), etc. The operator within the RexCall defines what the node does, and operands define arguments to the operator.

What RelNode and RexNode together give you is a way to plan and implement a query. Systems typically use VolcanoPlanner (cost-based) or HepPlanner (heuristic) to convert the logical plan (RelNode) into a physical plan and then implement the plan by converting each RelNode and RexNode into optimized query strings or executable codes.

Reference

Difference between sqlnode and relnode and rexnode by Jordan Halter