BodoSQL Query Optimizer Deep Dive — bodo.ai

In a previous post, we explained how BodoSQL builds on Apache Calcite, an open source framework for developing data management systems, to transform a user's SQL query into an optimized execution plan. At a high level, this process involves parsing SQL text into an abstract syntax tree (AST), validating the query against the schema, converting the validated query into relational algebra, and finally optimizing that relational plan and converting it into a physical plan. We recommend reading that post first for background on the overall BodoSQL query planning pipeline.
In this post, we focus on that final step: query optimization. We will start with an overview of the BodoSQL optimizer architecture, including its major optimization stages, metadata framework, and cost model. We will then dive deeper into several custom BodoSQL optimizations, showing how BodoSQL builds on Calcite's mature optimizer framework while extending it for large-scale, parallel query execution.
The BodoSQL optimizer transforms a logical plan describing what computation should be performed into an optimized physical plan describing how that computation should be executed by the backend.
Rather than performing this optimization in a single step, BodoSQL uses a pipeline of specialized stages. Early stages normalize and simplify the logical plan and apply rule-based transformations. The Volcano planner then explores alternative plans using cost-based optimization and converts the logical plan into a physical plan. Finally, additional physical-plan passes introduce optimizations targeted specifically at Bodo's execution backend.
Throughout this pipeline, optimizer stages can use BodoSQL's metadata framework to estimate properties of the data, such as row counts and distinct values. During cost-based optimization, these estimates feed into BodoSQL's custom cost model to compare alternative plans and select an efficient physical plan.
The following sections walk through each stage of this pipeline before describing the metadata framework and cost model in more detail.
The preprocessor normalizes and simplifies the query plan in preparation for later optimization passes. It first removes nested subqueries—expressions containing relational plans, such as IN or EXISTS—and rewrites them using relational operators such as joins. If a subquery references columns from the outer query, this rewrite may produce a Correlate node, which a subsequent decorrelation pass attempts to transform into a regular join. The preprocessor also converts Calcite's logical operators into BodoSQL's BodoLogical operator classes.
After preprocessing, BodoSQL applies a series of rule-based transformations to further simplify the plan and perform optimizations that are generally beneficial independent of the cost model. These include removing unused fields, eliminating common subexpressions, pushing filters and fields closer to their data sources, and simplifying projections. Many of these passes use Calcite's HEP planner, which repeatedly applies a specified collection of transformation rules to the plan until it converges. BodoSQL combines Calcite's core rules with custom rules that target patterns important to BodoSQL workloads. We will look at a couple examples of these custom rules in the following section.
After rule-based optimization, BodoSQL uses Calcite's Volcano planner to transform the logical plan into an efficient physical plan. Volcano uses transformation rules to explore alternative logical plans and converter rules to generate executable physical implementations. As alternatives are discovered, Volcano organizes equivalent relational expressions into sets and tracks the lowest-cost physical implementations found for each set. BodoSQL's metadata framework and cost model estimate and compare the execution costs of these alternatives, allowing Volcano to ultimately select the lowest-cost physical plan equivalent to the original logical plan.
After Volcano selects a physical plan, BodoSQL applies additional optimization passes to improve its execution on its backend. Some of these transformations use the HEP planner with custom rules. For example, one rule marks certain BodoPhysicalJoin operators for rebalancing when their output is reused by multiple non-trivial projections, helping redistribute data across parallel workers and mitigate data skew. Other optimizations are implemented as specialized passes over the physical plan, including the SubplanCachingProgram and RuntimeJoinFilterProgram, which identify opportunities for common subplan reuse and runtime join filtering respectively. These optimizations are discussed in more detail in later sections.
BodoSQL uses a custom cost model to compare plan alternatives during Volcano optimization. Each BodoPhysical operator estimates its cost using statistics from the metadata framework, such as input row counts and row sizes. For operators such as projections and aggregates, the cost model also accounts for the cost of evaluating individual expressions and aggregate functions. These cost functions have been tuned based on empirical results from customer workloads, with particular emphasis on selecting efficient join orders. As BodoSQL expands to support new workloads and execution strategies, improving the usefulness of the cost model remains an active area of development.
The effectiveness of the cost model depends heavily on accurate estimates of the data flowing through each operator. Row count is particularly important, but estimating the output size of operators such as joins and aggregates also requires statistics such as the number of distinct values (NDVs) for individual columns.
BodoSQL obtains base-table statistics from the underlying catalog. For Snowflake, BodoSQL can issue metadata queries such as COUNT(*) and APPROX_COUNT_DISTINCT to obtain row counts and approximate NDVs. For Iceberg tables, BodoSQL uses the NDV statistics stored in Iceberg Puffin files. Bodo DataFrames and Bodo