The Cost-Based Optimizer: How Execution Plans Actually Come to Be

1. The core problem: many possible plans for the same query

SQL describes what result a query should produce, not how the database technically produces that result. For a query with several joins, filters, and a sort, there are often dozens to hundreds of technically equivalent ways to compute the result: different join orders, different join algorithms, different decisions on whether an index is used or a full table scan is cheaper.

A rule-based optimizer, as used in older systems, makes these decisions based on fixed priorities, for instance always preferring the most selective available index. A cost-based optimizer takes a different route: it computes an estimated cost figure for several candidate plans and picks the plan with the lowest estimated cost, regardless of which general rule might argue for something else.

2. Statistics as the foundation of every cost estimate

For the optimizer to estimate cost at all, it needs information about the actual data distribution: the total row count of a table, the number of distinct values per column, and a histogram that roughly maps the value distribution within a column. These statistics are not recomputed on every query, but updated periodically or via explicit maintenance commands and then cached.

Outdated statistics are one of the most common causes of poor execution plans: if a table has grown substantially since the last statistics update, or if a column's value distribution has changed fundamentally, the optimizer works with wrong assumptions and makes decisions that no longer fit the actual data, even if the cost calculation itself is flawless.

-- Update statistics manually (syntax varies by system)
ANALYZE TABLE orders;

-- Check current statistics
SELECT table_name, table_rows, avg_row_length
FROM information_schema.tables
WHERE table_name = 'orders';

3. Cardinality estimation: how many rows an intermediate step produces

The central figure in every cost model is cardinality, the estimated number of rows a given step of the plan produces. For a simple filter such as WHERE status = 'shipped', the optimizer estimates cardinality based on that value's selectivity, derived from the histogram of the status column: if shipped is a common value, the estimated result set is large; if it is rare, correspondingly small.

For several combined filters or joins, the optimizer typically multiplies the individual selectivities together, under the assumption of statistical independence between the involved columns. That assumption is the central starting point for many later observable misjudgments, because real-world data is often anything but independently distributed.

4. From estimated row count to a concrete cost figure

From the estimated cardinality, the optimizer computes a cost figure for each candidate plan that typically combines I/O costs, for reading data pages from disk or the buffer pool, and CPU costs for comparisons, sorts, and hash computations. These cost values are usually abstract, system-specific units, not direct time figures, but can be compared reliably within the same system.

For every join in the query, the optimizer additionally evaluates several algorithms, such as nested loop join, hash join, and merge join, and picks the cheapest one depending on the estimated size of the involved intermediate results. A nested loop join is often cheapest for small result sets, a hash join for large, unsorted sets, which is why the chosen algorithm can change with the estimated data volume, even for an identical query structure.

5. How the optimizer picks the final plan from several candidates

Because the number of theoretically possible plans grows exponentially with the number of joins, the optimizer does not exhaustively search all combinations in practice, but uses heuristics and dynamic programming to narrow the search space. Beyond a certain number of tables in a join, many systems switch to genetic or greedy algorithms that no longer guarantee finding the globally optimal plan, but a sufficiently good one within a reasonable planning time.

At the end of this process stands the plan with the lowest total cost figure among all considered candidates. This plan is compiled or executed interpretively and frequently cached in a plan cache for repeated executions of the same or similar queries, to save the optimization time on re-execution.

6. Why identical queries get different plans on different data sets

Because the entire decision process rests on statistics that reflect the actual data distribution, the same query on a small test database with a few thousand rows often produces a completely different plan than on the production database with millions of rows. An index still judged too expensive on the small table, because a full scan of few data pages barely matters, can suddenly become the clearly better choice on the large table.

Likewise, the plan for the same query on the same system can change once the value distribution shifts through new data, for instance when a status column suddenly gets many new, rare values through a batch import. That explains why a plan that ran stably and performantly for months can suddenly become slow without any code change, once the underlying statistics shift due to data growth or a new statistics refresh.

7. The central limit: correlations between columns mostly stay invisible

The assumption of statistical independence between columns is the best-known blind spot of every cost-based optimizer. If a query filters simultaneously on country = 'DE' and city = 'Berlin', the optimizer estimates combined selectivity as the product of both individual selectivities, even though both values are in reality strongly correlated: almost every row with city = 'Berlin' automatically also has country = 'DE'. The actual result set is thus often many times larger than what the optimizer estimated.

Such misjudgments lead the optimizer to choose a plan that would make sense for the estimated, far-too-small result set, but in practice has to process considerably more rows, for instance a nested loop join that is clearly inferior to a hash join at the actual data volume. Modern systems partly offer multi-column statistics or extended statistics for exactly this kind of correlation, but these have to be created explicitly and are rarely used comprehensively in practice.

-- Create multi-column statistics to make the correlation
-- between country and city visible to the optimizer
-- (syntax is illustrative, varies by database system)
CREATE STATISTICS stat_country_city
ON country, city
FROM customers;

8. Spotting faulty cardinality estimates in the execution plan

Most database systems show both the estimated and, after actual execution, the observed row count per step in the detailed execution plan. A large gap between estimated and actual row count at a particular point in the plan is the most reliable sign that the optimizer made a wrong assumption at that spot, usually due to exactly the correlation issue described above, or outdated statistics.

This diagnosis is the crucial first step before even thinking about optimization measures such as additional indexes, rewritten queries, or explicit statistics hints. Without looking at the actual execution plan with the real observed row counts, any optimization at this point remains pure speculation about a problem whose cause is not yet even known.

9. How to steer the optimizer deliberately without bypassing it

Instead of forcing the optimizer via a hint to a specific access strategy, which can quickly become the worse choice again as data grows, it is usually more sustainable to feed the optimizer better input data: more current statistics, more finely resolved histograms for heavily skewed columns, or multi-column statistics for known correlated column combinations.

Only once these measures are exhausted and the optimizer still systematically decides wrong despite correct statistics, for instance because the cost model fundamentally cannot represent a certain constellation well, is a targeted plan hint justified. Even then, such a hint should be documented and reviewed regularly, because it can easily become itself the cause of a suboptimal plan as data growth changes.

10. Summary

11. FAQ: Cost-Based Optimizer: Key Facts at a Glance