Cost Model and Cardinality Estimation Error Analysis and Tuning in Database Query Execution Plans

Cost Model and Cardinality Estimation Error Analysis and Tuning in Database Query Execution Plans

Description
In a database query optimizer, the Cost Model is a mathematical model used to evaluate the relative cost of different execution plans, while Cardinality Estimation is a key technique for predicting the number of rows in intermediate result sets of query operations (such as table scans, joins, aggregations, etc.). The accuracy of the cost model heavily depends on the precision of cardinality estimation. This topic delves into the root causes of cardinality estimation errors, their catastrophic impact on execution plan selection, and targeted monitoring, diagnosis, and tuning strategies. This is not only core optimizer theory but also crucial for performance tuning engineers to solve the "optimizer chooses the wrong plan" problem.

Problem Solving / Explanation Process

Let's start from basic concepts and gradually move into error analysis and tuning.

Step 1: Clarify Core Concepts

  1. Cardinality Estimation: Refers to the optimizer's prediction of how many rows an operation (e.g., WHERE department_id = 10) will output. For example, the employees table has 1000 rows, and the optimizer predicts 50 rows for department_id=10 based on statistical information; this "50" is the estimated cardinality.
  2. Cost Model: A function Cost = f(cardinality, I/O cost, CPU cost, memory cost, ...). The optimizer calculates the total cost for each candidate execution plan and selects the one with the lowest cost. If the cardinality is estimated incorrectly (e.g., actual is 500 rows, but estimated is 50), the predictions for I/O and CPU costs will severely deviate, causing the model to select a "poor plan" that runs slowly in reality.

Step 2: Main Sources of Cardinality Estimation Error
Errors are not random; they have systematic roots:

  1. Data Correlation / Predicate Correlation:

    • Problem: Statistical information (e.g., histograms, NDV) typically assumes data independence between columns. But in reality, data is highly correlated. For example, country='China' AND city='Shanghai'. If the independent selectivities of country and city are simply multiplied, the cardinality is severely underestimated (since Shanghai is necessarily in China).
    • Example: country has 100 countries, city has 1000 cities. Under the independence assumption, selectivity = (1/100) * (1/1000) = 1/100,000. If the table has 100 million rows, estimated cardinality = 100 rows. But if "Shanghai" only appears in "China" in the data, the actual number of rows satisfying the condition might be as high as 1 million rows. Estimated value (100) vs. actual value (1,000,000) differs by a factor of 10,000.

  2. Lack of Multi-Column Joint Statistics:

    • To solve the above problem, extended statistics (Extended Statistics) or column group statistics need to be created to capture multi-column correlations. But administrators might not create them, or there are too many column combinations to cover all.

  3. Predicates Using Complex Expressions or Functions:

    • Problem: WHERE YEAR(create_time) = 2023 or WHERE amount * tax_rate > 100. It's difficult for the optimizer to accurately estimate the selectivity of such expression results; it usually uses an empirical default selectivity (e.g., 1%), which is often inaccurate.

  4. Data Skew (High Data Skew):

    • Problem: Histograms (frequency/height balanced) aim to capture data distribution. But for extremely skewed data, when the number of histogram buckets is insufficient, the estimation for high-frequency values and low-frequency values can still be imprecise. For example, 99% of the status column is 'A', and 1% is 'B'. If histogram information is inaccurate, queries for status='B' might be overestimated or underestimated.

  5. Cascading Error in Join Cardinality Estimation:

    • Problem: This is the most dangerous area for error amplification. For a multi-table join query, the optimizer estimates sequentially. If the cardinality of the first step A JOIN B is estimated incorrectly (e.g., it should produce 1 million intermediate rows but only estimates 10,000), this erroneous result is passed as input to the next step (A⋈B) JOIN C, causing all subsequent cost calculations to be distorted. Ultimately, the model might think a "Hash Join" plan requiring a huge intermediate result has a low cost, while in actual execution, it suffers from memory overflow to disk and performs poorly.

Step 3: How Errors Lead to Catastrophic Execution Plan Selection
Illustrated by a classic scenario:

  • Query: SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id WHERE c.region = 'Asia' AND o.year = 2023
  • Real Situation: Very few rows in the customers table have region='Asia' (1%), but once joined with orders, the join result is huge due to many orders from Asian customers.
  • Wrong Estimate: The optimizer might severely underestimate the cardinality after joining customers and orders (due to not considering the distribution correlation of cust_id among Asian customers).
  • Wrong Choice: The optimizer thinks the intermediate result set is small, so it chooses a Nested Loop Join, performing an indexed loop on the orders table for each Asian customer. This is fast if the estimate is correct.
  • Actual Disaster: The actual intermediate result is huge, causing the nested loop to perform millions of index lookups, making it extremely slow. In reality, a Hash Join, although requiring more memory, is much more efficient for handling such a large result set.

Step 4: Error Diagnosis and Monitoring Methods
When a query slows down, diagnose step by step:

  1. Obtain the Execution Plan: Use EXPLAIN ANALYZE (or similar commands). Key columns to look at:
    • rows: The number of rows the optimizer estimated for each operation to output.
    • actual rows: The number of rows the operation actually output during query execution.
  2. Locate the Error Point: Starting from the bottom of the execution plan tree (table scan), compare rows and actual rows level by level going upward. Find the first operation node where there is an order of magnitude difference (e.g., 10x, 100x or more). This is the source of the error.
  3. Analyze the Predicates at That Node: Examine the filter conditions (WHERE) or join conditions (ON) on this operation node. They likely involve data correlation, complex expressions, or data skew.

Step 5: Tuning Strategies and Solutions
Take targeted measures based on the diagnosis results:

  1. Update Statistical Information:
    • Command: Execute a full statistical information collection command on the relevant tables (e.g., ANALYZE TABLE or DBMS_STATS.GATHER_TABLE_STATS).
    • Increase Precision: Increase the number of histogram buckets (SIZE) for a finer description of data distribution.
  2. Create Extended Statistics:
    • Solve Correlation: Create extended statistics for column combinations with strong correlation (e.g., Oracle's (country, city) column group, MySQL's COLUMN_STATISTICS).
    • Effect: Allows the optimizer to directly obtain the selectivity for composite predicates like (country='China' AND city='Shanghai'), instead of simple multiplication.
  3. Use Dynamic Sampling or Feedback Mechanisms:
    • Dynamic Sampling: During compilation, performs a quick scan of a small portion of data blocks to obtain more real-time and accurate selectivity for single-table predicates. Suitable for temporary tables or outdated statistics.
    • Adaptive Query Optimization: Such as Oracle's Adaptive Plans, SQL Server's Cardinality Estimation Feedback. They compare estimated vs. actual values during the initial execution of a query. If the error is too large, they automatically adjust the plan or record feedback for future optimization.
  4. Query Rewriting:
    • Avoid Optimizer Weaknesses: Rewrite complex expressions. For example, change YEAR(create_time)=2023 to create_time BETWEEN '2023-01-01' AND '2023-12-31'. The latter is easier to utilize column statistics.
    • Use Hints: When certain the optimizer chose the wrong plan and you know a better one, use optimizer hints (e.g., /*+ HASH_JOIN(o c) */) to force a specific join algorithm or order. This is a last resort and must be used cautiously, as hints may become ineffective after data changes.
  5. Use SQL Profile or Plan Baselines:
    • More advanced techniques. Capture a known good execution plan and "fix" it to prevent the optimizer from choosing inferior plans in the future due to statistical fluctuations. This shifts from "treatment" to "prevention".

Summary:
Cardinality estimation is the link in query optimization where "a tiny error leads to a huge mistake". Understand that errors stem from data correlation, incomplete/outdated statistical information, complex predicates, and data skew. Use EXPLAIN ANALYZE to compare estimated and actual rows to precisely locate the error point. Tuning is a systematic engineering task. Apply strategies from updating statistics, creating extended statistics, leveraging adaptive mechanisms, to the final query rewriting or plan fixing, progressing from simple to deep, to effectively tame the optimizer and ensure it consistently generates efficient execution plans.