How Database Query Optimizers Work

Description
The query optimizer is the core component of a database management system, responsible for transforming user-submitted SQL queries into efficient executable plans. By evaluating multiple possible execution strategies, it selects the plan with the lowest cost to minimize query response time and system resource consumption. Understanding how the optimizer works helps in writing high-performance SQL statements and performing targeted tuning.

Knowledge Point Explanation

1. Query Processing Stages

   • Parsing and Syntax Checking: The database first checks if the SQL syntax is correct and generates an initial parse tree.
   • Logical Optimization: Rewrites the query tree, for example, by merging subqueries, eliminating redundant conditions, and applying algebraic laws (such as predicate pushdown).
   • Physical Optimization: Generates multiple physical execution plans (such as choosing between index scans or full table scans) based on the logical plan and selects the optimal one through a cost model.

2. Core Operations of Logical Optimization

   • Predicate Pushdown: Filters data as early as possible to reduce the amount of data processed in subsequent steps.
     Example: For the query SELECT * FROM A JOIN B ON A.id=B.id WHERE A.age>30, the optimizer pushes A.age>30 down to be executed before the join operation.
   • Projection Pruning: Reads only the columns required by the query, avoiding the transfer of unnecessary data.
   • Query Rewriting: Transforms IN subqueries into JOINs or merges multiple adjacent WHERE conditions.

3. Cost Estimation in Physical Optimization

   • Cost Model: Estimates the cost of each operation based on statistical data (such as table size, index selectivity, data distribution).
     • I/O Cost: The cost of reading data from disk.
     • CPU Cost: The computational cost of data comparison, sorting, etc.
   • Cardinality Estimation: A key challenge! The optimizer estimates the number of rows output by each operator using information like histograms.
     Example: If the filter selectivity for WHERE age>30 is estimated at 20%, but in reality 50% of the data meets the condition, it may lead to the selection of an inefficient plan.

4. Search Algorithms and Plan Selection

   • Dynamic Programming: Used to search for the optimal join order (e.g., avoiding Cartesian products in multi-table JOINs).
   • Heuristic Rules: Such as "prefer index scans" or "use smaller tables as the outer table in joins."
   • Common Execution Plan Types:
     • Table Scan
     • Index Scan
     • Nested Loop Join
     • Hash Join
     • Sort-Merge Join

5. Influencing Factors and Limitations of Optimizers

   • Outdated Statistics: If data has changed but statistics have not been updated, cost estimates may be significantly inaccurate.
   • Invalid Assumptions: Optimizers assume uniform data distribution, but actual data may be skewed (e.g., 90% of data concentrated in a certain range).
   • Limitations with Complex Queries: For multi-table joins, it may not be possible to enumerate all plans, leading to suboptimal choices.

Practical Recommendations

• Use the EXPLAIN command to analyze execution plans, paying attention to differences between actual and estimated row counts.
• Regularly update statistics (e.g., ANALYZE TABLE).
• Avoid using functions or expressions on indexed columns in WHERE clauses to prevent index invalidation.

By understanding the decision-making logic of the optimizer, you can more effectively optimize query design, for example, by adjusting join order or using hints to guide the optimizer toward a better plan.