Cost-Based Optimizer: What It Is and How It Works
A cost-based optimizer (CBO) is the component of a relational database responsible for selecting the most efficient way to execute a SQL query. Rather than applying fixed rules, it evaluates multiple possible execution strategies and picks the one with the lowest estimated cost.
In distributed SQL databases, where data spans multiple nodes, that decision has a direct impact on query performance at scale.
What Does a Cost-Based Optimizer Do?
A cost-based optimizer evaluates candidate query execution plans and selects the one with the lowest estimated resource cost, weighing CPU, I/O, and memory usage.
This is the key difference from a rule-based optimizer (RBO). An RBO applies fixed heuristics regardless of data characteristics, while a CBO adapts its decisions to the actual shape of the data.
If a table has 10 rows, the optimizer may skip an index entirely; if it has 10 billion rows, that same index becomes critical. The CBO makes that distinction; an RBO cannot.
What Inputs Does a Cost-Based Optimizer Use?
To estimate the cost of each candidate plan, the CBO draws on four main inputs:
- Table and column statistics: Row counts, column cardinality, null value ratios, and value distribution histograms
- Index availability and selectivity: Which indexes exist, and how selective each is for a given predicate
- Join type options: Nested-loop joins, hash joins, and merge joins each carry different cost profiles, depending on data volume
- Join ordering: The sequence in which tables are joined, which affects intermediate row counts at every step
In a distributed database like YugabyteDB, a fifth input matters: network latency.
Moving data between nodes carries real cost, and a CBO that doesn’t account for network round trips will routinely pick plans that are optimal on paper but slow in practice.
What Are Cardinality Estimates and Why Do They Matter?
Cardinality estimation is the optimizer’s prediction of how many rows each step in a query plan will return. These estimates drive index selection and join ordering.
If the optimizer predicts that a filter will return 100 rows when it actually returns 10 million, it may choose a nested-loop join that performs acceptably at small scale but becomes catastrophically slow at real volume. Inaccurate cardinality estimates are the most common root cause of bad query plans, and they almost always trace back to stale or missing statistics.
How Does a Cost-Based Optimizer Choose an Execution Plan?
The plan selection process works in three steps: generate candidate plans, assign each a cost estimate, and then execute the lowest-cost plan. “Cost” is an abstract unit that combines I/O, CPU, and memory trade-offs, not wall-clock time, but it correlates with it when statistics are accurate.
YugabyteDB’s CBO was built specifically for a distributed storage layer, accounting for factors the standard PostgreSQL query planner cannot see: tablet-level data distribution, replication topology, and cross-node data movement costs.
That architecture-aware planning translates to better index selection and join ordering for workloads spanning multiple nodes. For a detailed look at how we built and validated the YugabyteDB CBO, explore our CBO engineering deep-dive.
What Happens When a Cost-Based Optimizer Gets It Wrong?
The most common failure mode is stale or missing statistics. Without accurate data, cardinality estimates break down, leading to suboptimal plans: the wrong index gets chosen, joins are processed in the wrong order, or a full table scan replaces a selective index lookup.
The fix is straightforward: refresh statistics regularly, especially after bulk writes or significant data distribution changes.
In PostgreSQL-compatible databases, ANALYZE is the standard mechanism. Treating statistics maintenance as a routine operational task, rather than a one-time setup step, is the most reliable way to avoid plan regressions in production.
How Does a Cost-Based Optimizer Handle Large Numbers of Joins?
The number of possible join orderings grows factorially with the table count. To keep planning time reasonable, most CBOs limit the search space using heuristics, reordering joins only up to a threshold count. This is a deliberate trade-off, not a limitation, and it holds for most production query patterns.
How Does the Cost-Based Optimizer Work in a Distributed SQL Database?
In a single-node database, query planning focuses on local I/O and CPU cost. In a distributed system, data lives across multiple nodes, and joining it involves network round trips, replication overhead, and tablet-level distribution patterns.
YugabyteDB’s CBO was designed natively for this architecture. It understands how data is distributed across tablets, accurately models cross-node movement costs, and selects join strategies and index paths that minimize network overhead.
Databases that bolt a distribution layer onto a single-node planner optimize for local cost models that don’t hold in a multi-node topology, producing plans that underperform under real distributed workloads.
For more on ACID transactions and consistency across distributed query execution, see our ACID transactions key concept. We also published a broader look at enhanced PostgreSQL compatibility, covering how the CBO fits into our performance parity effort.
Query planner quality determines whether a distributed database delivers on its scale promise or resorts to brute-force scans. A CBO that understands the distributed storage layer is the difference between theoretical performance and real-world throughput.
Try YugabyteDB Aeon for free, or book a demo to see how our cost-based optimizer handles your workloads.