SQL Parsing Framework - Calcite

Calcite: A General-Purpose SQL Parsing Framework

While studying Flink, I encountered Calcite in flink-table. When I first entered big data a year ago, Hive SQL made me curious about SQL parsing, but the many unfamiliar concepts overwhelmed me and I abandoned Calcite. It now seems time for a proper review.

Background

Anyone working with data processing is familiar with SQL. Calcite is a widely used SQL processor in major open-source projects including Hive, Flink, and Beam.
Many posts about SQL parsing, such as Spark Catalyst, describe this process: The same process applies to Calcite. Read on.

Quick Overview

First, complete SQL execution code in four steps:

1. Parse SQL
2. Convert SqlNodes
3. Optimize
4. Execute

1
// Convert query to SqlNode
2
String sql = "select price from transactions";
3
Config config = SqlParser.configBuilder().build();
4
SqlParser parser = SqlParser.create(sql, config);
5
SqlNode node = parser.parseQuery();

SqlParser turns a SQL statement into a tree of SqlNodes. JavaCC implements this from the Parser.jj template, so there is little handwritten code. See JavaCC Help.

1
// Convert SqlNode to RelNode
2
VolcanoPlanner planner = new VolcanoPlanner();
3
RexBuilder rexBuilder = createRexBuilder();
4
RelOptCluster cluster = RelOptCluster.create(planner, rexBuilder);
5
SqlToRelConverter converter = new SqlToRelConverter(...);
6
RelRoot root = converter.convertQuery(node, false, true);

SqlToRelConverter converts the SQL tree into Calcite RelNodes. Both are tree structures but have different meanings. SqlNodes include expressions such as MIN/MAX and relational constructs such as SELECT/JOIN. Conversion separates these into relational RelNodes and expression RexNodes.

1
// Optimize RelNode
2
RelNode optimized = planner.findBestExp();

Rules optimize RelNodes. Calcite planners can be rule-based or cost-based; the more complex cost-based implementation is discussed below.

1
// Execute
2
Interpreter interpreter = new Interpreter(dataContext, optimized);
3
interpreter.enumerator();

The optimized plan executes code according to each RelNode type. TableScan, for example, runs table-scanning code.

SqlNode Conversion

In SqlToRelConverter, the entry point is convertQuery.

1
public RelRoot convertQuery(SqlNode query, final boolean needsValidation, final boolean top) {
2
    if (needsValidation) {
3
      query = validator.validate(query);
4
    }
5
    RelNode result = convertQueryRecursive(query, top, null).rel;
6
    ....
7
}

convertQueryRecursive traverses the query. A series of visit methods converts SqlNodes directly into RexNodes, as shown: visit(SqlLiteral), for example, creates different RexNodes depending on the type: RexNodes are then assembled into RelNodes according to SqlNode.getKind(), for example Select -> Project.

Optimization

Planner.findBestExp() performs optimization using customizable strategies. Calcite provides two planners:

• HepPlanner: repeatedly applies rules to the RelNode tree until no optimization remains.
• VolcanoPlanner: uses rules and costs with stochastic gradient descent until each improvement becomes small.

For example, VolcanoPlanner follows this logic:

1. Register RelNodes. When a node matches a rule, create a RuleCall and add it to ruleQueue for later optimization.
2. Check whether cost dropped by 10 percent from the previous optimization; continue if so, otherwise exit.
3. Retrieve a RuleCall from ruleQueue and optimize.
4. Rebuild RelRoot and update its cost.
5. Repeat from step 2.
6. Exit.

VolcanoPlanner is relatively cumbersome because cost calculations must be implemented for different stores, so most big-data frameworks use rule-based planning. Optimization involves many details, including stochastic-gradient-descent controls, iteration limits, and internal RelNode replacement. One section cannot explain it fully; interested readers can inspect VolcanoPlanner.

Execution

Execution defines code implementations for different node types and proceeds upward from the lowest RelNodes, receiving data through sources and sending it through sinks. Flink’s translate functions provide a similar mechanism.

Calcite Source Terminology

Related Reading

• Analyzing Calcite Optimizer Code in Drill
• Deep Dive into Spark SQL’s Catalyst Optimizer
• Compiler principles