What are the Limitations of a Cost-Based Query Optimizer?
Understand why cost-based optimizers misjudge plans: stale statistics, correlated columns, and bounded join search explained.
Expected Interview Answer
A cost-based optimizer’s limitations stem from the fact that it estimates a query’s cheapest plan using statistics and heuristics rather than executing anything, so any inaccuracy in those estimates — stale histograms, correlated columns, or complex predicates — can lead it to choose a plan that is far from actually optimal.
The optimizer relies on cardinality estimates, which assume column independence unless multi-column statistics exist, so filters on correlated columns (like city and zip code) are frequently mis-estimated, cascading errors through every join above them. Statistics also go stale after bulk loads or skewed updates, and complex expressions, user-defined functions, or subqueries can be effectively invisible to the estimator, forcing it to guess. Because plan search space grows combinatorially with join count, optimizers also use heuristics and timeouts rather than exhaustively evaluating every plan, so a good-enough plan is chosen over a guaranteed-best one for large queries.
- Understanding limitations tells you when to trust EXPLAIN output
- Explains why rewriting a query can outperform tuning
- Justifies keeping statistics current as routine maintenance
- Helps decide when a manual hint is genuinely warranted
AI Mentor Explanation
A team selector estimates a player’s likely performance from last season’s average, but that average hides how the player performs specifically against left-arm spin, which is the exact matchup coming up. Because the selector only has the aggregate number and not the detailed breakdown, the prediction can be badly wrong for this particular match. A cost-based optimizer has this same blind spot: it estimates from summary statistics that miss correlations between conditions, producing a plan that looks good on paper but performs badly in practice.
Step-by-Step Explanation
Step 1
Estimate cardinality from statistics
The optimizer reads column histograms and distinct-value counts to estimate how many rows each predicate matches.
Step 2
Assume independence by default
Without extended statistics, the optimizer multiplies individual selectivities, assuming filter conditions are uncorrelated.
Step 3
Search a bounded plan space
For queries with many joins, the optimizer uses heuristics or timeouts rather than exhaustively evaluating every join order.
Step 4
Produce a plan that may be wrong
Stale statistics, correlated columns, or opaque expressions can all push the chosen plan far from the true optimum.
What Interviewer Expects
- Clear explanation of the independence assumption and why it fails on correlated columns
- Awareness that plan search is heuristic, not exhaustive, for complex queries
- Knowledge that stale statistics degrade estimate quality over time
- A practical takeaway, such as building extended statistics or refreshing stats regularly
Common Mistakes
- Believing the optimizer always finds the mathematically optimal plan
- Not knowing correlated columns break the independence assumption
- Ignoring that user-defined functions and complex expressions are often unestimable
- Assuming bigger data automatically means worse estimates rather than staler statistics
Best Answer (HR Friendly)
“A cost-based optimizer estimates the cheapest plan using statistics instead of actually running the query, so it can get things wrong when those statistics are stale, when columns are correlated in ways it does not know about, or when the query is too complex to fully evaluate every plan. Knowing these limitations helps me decide when to update statistics, rewrite a query, or add extended statistics instead of just tuning blindly.”
Code Example
-- Optimizer assumes city and zip_code are independent by default,
-- multiplying their individual selectivities and under- or over-estimating rows.
EXPLAIN ANALYZE
SELECT * FROM Customers
WHERE city = 'Chicago' AND zip_code = '60601';
-- Extended statistics teach the optimizer the real correlation (PostgreSQL example)
CREATE STATISTICS stats_city_zip (dependencies)
ON city, zip_code FROM Customers;
ANALYZE Customers;Follow-up Questions
- What are extended or multi-column statistics and when should you create them?
- How does a stale statistics table lead to a bad execution plan?
- Why do optimizers avoid exhaustively searching every join order?
- How would you detect a cardinality estimation error using EXPLAIN ANALYZE?
MCQ Practice
1. By default, how does a cost-based optimizer typically treat two separate filter conditions?
Without extended statistics, optimizers multiply individual column selectivities, assuming independence, which breaks down for correlated columns.
2. Why do optimizers use heuristics for queries with many joins?
Plan search space grows combinatorially with join count, so optimizers bound the search with heuristics or timeouts rather than checking every order.
3. What commonly causes cardinality estimates to go wrong over time?
Statistics reflect data at the time they were last gathered, so heavy inserts, deletes, or skewed updates without a refresh make estimates stale and wrong.
Flash Cards
What does a cost-based optimizer estimate from? — Statistics like histograms and distinct-value counts, not actual execution.
What is the independence assumption? — The default assumption that filter conditions on different columns are uncorrelated, which fails for correlated data.
Why is plan search bounded? — Because join order possibilities grow combinatorially, so optimizers use heuristics instead of exhaustive search.
What fixes correlated-column estimation errors? — Creating extended or multi-column statistics that capture the real correlation.