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, totalFROM ordersWHERE 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
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.
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.
Be the first to add a comment.