Cost-Based Query Optimization

4
0

Introduction

A database can often execute the same SQL query in several ways. It might scan a table, use an index, change the order of joins, or choose a different algorithm for combining records.

Cost-based query optimization compares these alternatives using estimated work. Its goal is to select an efficient execution plan without actually running every candidate plan.

What Does “Cost” Mean?

An optimizer’s cost is a model-based estimate used to compare execution plans.

Depending on the database, the model may account for:

  • Reading pages from storage or memory.

  • Processing records and evaluating expressions.

  • Performing index lookups.

  • Sorting or building hash tables.

  • Moving data between parallel workers.

Cost values are generally expressed in internal units. A cost of 200 does not automatically mean 200 milliseconds.

The optimizer chooses among the alternatives it considers. It does not guarantee the fastest possible plan under every runtime condition.

One Query, Different Access Paths

Consider:

SELECT order_id, total
FROM orders
WHERE customer_id = 101;

Suppose the table has an index on customer_id.

The database could choose:

Candidate

Main work

Table scan

Read table pages and test the condition

Index access

Find matching index entries and retrieve required row values

If customer 101 has only a few orders, index access may avoid substantial scanning.

If that customer owns a large proportion of the table’s orders, many additional row lookups could make a scan cheaper.

The choice depends on the estimated number of matches, index coverage, storage organization, and other factors. The existence of an index does not require the optimizer to use it.

Statistics Describe the Data

The optimizer relies on statistics rather than inspecting every record during planning.

Statistics can describe:

Information

Why it helps

Table size

Estimates the amount of input

Number of distinct values

Helps estimate equality matches

Common values and their frequencies

Identifies uneven distributions

Value distributions or histograms

Helps estimate ranges

Relationships between columns, where supported

Improves estimates for combined conditions

Suppose an orders table contains one million records and 10,000 customers.

Under a simplified uniform-distribution assumption, an equality filter would match:

1,000,000 ÷ 10,000 = 100 orders per customer

But real customers may have very different order counts. One might have two orders while another has 100,000.

Statistics that capture this imbalance can support better estimates. Stale or insufficient statistics can misrepresent the current data.

Cardinality Drives Later Decisions

Cardinality means the number of records produced by an operation.

For a filtered table, the optimizer estimates how many records remain. For a join, it estimates how many combinations will match.

These estimates influence later choices:

  • A small outer input may favor indexed nested-loop lookups.

  • A larger equality join may favor hashing.

  • An expected small sort may appear inexpensive.

  • A larger intermediate result may need more memory or temporary storage.

An estimation error can therefore spread through the plan.

If an operation is expected to return 100 records but actually returns 100,000, later joins and memory allocations may be based on a misleading picture.

Cardinality Drives Later Decisions

Cardinality Drives Later Decisions

Join Order Can Change the Amount of Work

Consider a query involving customers, orders, and order items, with a condition restricting customers to one region.

One candidate might filter customers first and then join their matching orders and items.

Another might create a large orders-and-items intermediate result before applying the customer restriction.

If the region filter is highly selective, applying it early can reduce subsequent work. If it matches nearly every customer, the advantage may be smaller.

The optimizer evaluates legal alternatives while preserving the query’s meaning. Outer joins and other SQL features can restrict which reorderings are valid.

For queries involving many tables, exploring every possible combination would itself be expensive. Optimizers use search strategies and limits to keep planning practical.

Comparing Estimated Plan Costs

A simplified comparison might look like this:

Candidate plan

Illustrative estimated cost

Table scan and filter

420

Index lookup with row retrieval

75

Alternative index access

130

Under this model, the optimizer prefers the plan estimated at 75.

These numbers are teaching examples, not benchmark results or execution times. Different databases calculate and display costs differently.

Real estimates also depend on how much input operators are expected to consume. For example, a LIMIT can make early output valuable when the access path can stop before processing all records.

Comparing Estimated Plan Costs.

Comparing Estimated Plan Costs.

Why the Chosen Plan Can Be Poor

A cost-based decision can be reasonable according to its inputs and still perform badly.

Common causes include:

  • Stale statistics: The data has changed since statistics were collected.

  • Skewed values: Some values occur much more often than others.

  • Correlated conditions: Columns are related, making independent estimates inaccurate.

  • Runtime pressure: Memory, caching, or concurrent activity differs from expectations.

  • Different parameter values: One plan may not suit both rare and very common values.

For example, filtering by both city and postal code does not necessarily reduce the result as much as treating those conditions as independent would suggest.

Adding another index does not automatically correct these estimation problems.

Investigating an Unexpected Plan

Start with the execution plan and, where available, actual runtime measurements.

Compare estimated and actual record counts at important operators. Look for the earliest substantial mismatch, because later errors may follow from it.

Then investigate the relevant statistics, predicates, indexes, and data distribution. Check whether sorting or hashing spills to temporary storage, or whether repeated lookups process far more records than expected.

Make targeted changes and measure the result using representative workloads. A plan that helps one parameter value may hurt another.

Summary

Cost-based optimization compares candidate execution plans using estimated resource requirements. Statistics and cardinality estimates help determine access paths, join order, and physical algorithms.

The selected plan is only as reliable as the model and information behind it. Comparing estimates with actual execution behavior helps reveal why a decision performed poorly and what should be improved.

CS Core

Read Similar Blogs

Comments0