Cost-Based Optimizer (CBO)

Introduction to the Cost-Based Optimizer

When you submit a SQL query to a database or compute engine (like PostgreSQL, Trino, or Spark), the engine must translate your declarative text into a physical execution plan.

For a simple query like SELECT * FROM users, there is only one way to execute it: read the table. However, if you write a complex analytical query involving a 5-table JOIN, there are thousands of mathematically valid ways to retrieve the answer. The engine must decide: Which table do I read first? Should I load Table A into memory to join it with Table B, or vice-versa?

In early database systems, engineers relied on Rule-Based Optimizers (RBO), which blindly followed hard-coded rules (e.g., “Always join the smallest table first based on the syntax order”). RBOs failed at scale because they completely ignored the actual data.

The Cost-Based Optimizer (CBO) revolutionized query execution. A CBO acts like a GPS routing algorithm. Instead of blindly following a pre-set rule, it calculates the “cost” (CPU, memory, and network I/O) of every possible execution path based on the actual statistical shape of the data, and intelligently chooses the cheapest, fastest route.

How the CBO Calculates Cost

To make intelligent decisions, the CBO relies entirely on Metadata Statistics. Before executing a query, the CBO looks at the catalog (like the Hive Metastore or Apache Iceberg) to gather statistics about the involved tables.

It looks for:

1. Row Count: How many rows are in the table?
2. Column Cardinality: How many unique values exist in the state column? (e.g., 50 unique US states).
3. Data Distribution (Histograms): Is the data evenly distributed, or do 90% of the customers live in California?
4. Null Counts: How many missing values are there?

The “Cost” Formula

The CBO takes these statistics and feeds them into mathematical formulas to estimate the computational cost of different operations. If it estimates that a “Hash Join” will require 5 seconds of CPU time and 2GB of RAM, and a “Sort-Merge Join” will require 8 seconds of CPU time and 1GB of RAM, it calculates a total weighted cost score for both options.

CBO Decisions in Action

The intelligence of the CBO dictates the performance of the entire data platform. Here are the critical decisions it makes:

1. Join Ordering

The order in which tables are joined is the most critical factor in query performance. If you join a 10-billion row sales table with a 10-row regions table, and then join the result with a 100-row products table, the CBO uses statistics to determine the order. It will always choose to join the smallest tables first, creating a tiny intermediate dataset, before attempting to join the massive 10-billion row table.

2. Join Strategy Selection

• Broadcast Hash Join: If the CBO sees that Table A is massive (10TB) but Table B is tiny (10MB), it chooses a Broadcast Join. It sends a copy of Table B to every single worker node in the cluster, completely eliminating the need to shuffle the massive Table A across the network.
• Shuffle Hash Join / Sort-Merge Join: If the CBO sees that both tables are massive (10TB), it knows a Broadcast Join will crash the cluster (Out of Memory). It chooses a Shuffle Join, safely sorting and distributing the data across the nodes.

3. Predicate Pushdown Evaluation

If a query filters WHERE state = 'WY', the CBO looks at the histogram. It sees that Wyoming only accounts for 0.1% of the data. The CBO knows that pushing this filter down to the Parquet file reader will drastically reduce network I/O.

The Challenge: Stale Statistics

The CBO is a mathematical genius, but it is entirely dependent on its input data. If the statistics are wrong, the CBO will make catastrophically bad decisions.

If a table actually contains 10 billion rows, but the metadata statistics haven’t been updated in a month and currently claim the table only has 10,000 rows, the CBO will attempt a Broadcast Join. It will try to load the entire 10-billion row table into the RAM of every worker node, instantly crashing the entire cluster.

In traditional databases, Database Administrators (DBAs) had to manually run the ANALYZE command nightly to recalculate these statistics. In modern Open Lakehouses, table formats like Apache Iceberg automatically track and update these statistics (min/max bounds, null counts) internally during every single write operation. This guarantees that modern engines (like Spark or Dremio) always have perfectly fresh statistics, enabling the CBO to execute flawless query plans at petabyte scale.

Conclusion

The Cost-Based Optimizer is the invisible conductor of the analytical orchestra. By treating query planning as a mathematical routing problem rather than a set of hard-coded rules, the CBO enables business analysts to write wildly complex SQL without ever worrying about the underlying physical execution strategy. The CBO’s ability to seamlessly scale from gigabytes to petabytes is why modern data warehouses and lakehouses perform as efficiently as they do.