Cost-Based Query Optimization

Cost-based query optimization estimates the resource cost of candidate execution plans and chooses one using database statistics and a cost model. Its choice depends on estimate quality and is not a guarantee of minimum real-world runtime.

A database query can often be executed in several equivalent ways. For example, a join may use a nested-loop, hash, or merge strategy, and filters may be applied at different points. A cost-based query optimizer evaluates candidate plans and chooses one it estimates will use fewer resources.

To estimate cost, the optimizer uses information such as table and index statistics, estimated row counts, data distributions, available indexes, and the database's cost model. It may account for work such as disk reads, CPU operations, memory use, and data transfer. The exact model and units depend on the database; an estimated cost is not a direct promise of elapsed time.

Cardinality estimates—the predicted number of rows produced by an operation—are especially influential. If those estimates are inaccurate, the optimizer may choose a poor join order, an unsuitable join algorithm, or an ineffective access path. Stale or insufficient statistics and skewed data can contribute to this problem.

The optimizer generally compares plans it can generate under its transformation rules and constraints; it does not necessarily enumerate every logically possible plan. Developers can inspect plans with database-specific tools such as `EXPLAIN` and, where supported, compare estimates with actual execution measurements. Indexes, query structure, and refreshed statistics may help, but should be evaluated against the workload rather than treated as automatic improvements.

Key points

• The optimizer estimates resource use across candidate execution plans and chooses according to its cost model.
• Cardinality estimates strongly influence operator costs and plan selection.
• Statistics, data distributions, indexes, and query predicates can affect estimates and available plans.
• Estimated cost is database-specific and should not be confused with measured elapsed time.
• Inspect plans and validate performance with representative measurements before making changes.

Interview questions

What does a cost-based query optimizer do?

A cost-based optimizer generates or considers alternative plans that preserve the query's result. It estimates resource use for those plans and chooses one according to its cost model. Inputs can include row-count estimates, table and index statistics, available access paths, and expected operation costs. The chosen plan is an estimate-driven decision, not a guarantee that it will be fastest for every data distribution or runtime condition.

Why are cardinality estimates important to query optimization?

Cardinality is the estimated number of rows produced by a table access or an intermediate operation. It influences estimated costs for scans, joins, and other operators, so an inaccurate estimate can make an otherwise reasonable cost comparison misleading. For example, underestimating rows from a filter may make a nested-loop join appear cheaper than a hash join. Statistics and assumptions about data distributions help the optimizer form these estimates.

A query is unexpectedly slow in production. How would you investigate whether the optimizer chose a poor plan?

I would inspect the database's execution plan and identify where estimated row counts diverge from actual counts, if the system can report both. Then I would check relevant table and index statistics, filter selectivity, data skew, and whether the query's predicates match available indexes. I would also review the expensive operators and measure execution under representative data and load. Any change should be validated with both plan inspection and runtime measurements because an index or rewrite can help one query while harming other workload patterns.

Why might a cost-based optimizer choose a table scan instead of using an available index?

An index can provide a cheaper access path when its structure and selectivity fit the query, but using it is not always cheaper than scanning. The optimizer estimates the work for each available plan and may prefer a sequential scan when many rows qualify or when index lookups would cause substantial I/O. Indexes also consume storage and add work to inserts, updates, and deletes. I would consider the workload and confirm the effect with plans and measurements rather than assuming every useful-looking index should be added.

Does a cost-based optimizer necessarily find the globally cheapest possible plan?

A query optimizer searches a constrained plan space shaped by the database's transformations, operator support, and semantic constraints; it need not enumerate every logically equivalent plan. As the number of joins grows, the number of possible orders can grow rapidly, so implementations use search strategies and pruning to manage planning effort. Cost estimates then help rank the plans that are considered. This means a selected plan is best according to the optimizer's search and estimates, not necessarily a global optimum over every imaginable plan.