How Database Query Optimizers Work

Problem Description
The database query optimizer is the core component of a relational database management system, responsible for translating user-submitted SQL queries into efficient and executable query plans. Its primary task is to select the lowest-cost execution strategy from numerous possible alternatives while guaranteeing the correctness of the results. Understanding how the optimizer works helps in writing high-performance SQL statements and designing efficient database structures.

Solution Process

1. Parsing and Syntax Tree Generation

   • Step Description: The optimizer first receives an SQL string, which is processed by the parser for lexical analysis (identifying keywords, table names, etc.) and syntactic analysis (checking grammar structure).
   • Key Details: After parsing, an initial syntax tree is generated. For example, for the query SELECT * FROM users WHERE age > 25, the tree structure will contain nodes for the FROM clause (data source), WHERE clause (filter condition), etc. This stage only verifies syntactic correctness and does not involve logical optimization.

2. Logical Optimization (Query Rewriting)

   • Step Description: Performs equivalent transformations on the syntax tree based on relational algebra rules to eliminate redundant or inefficient structures.
   • Common Operations:
     • Predicate Pushdown: Moves filter conditions as close to the data source as possible to reduce the amount of data processed later. For example, executing WHERE conditions before JOINs.
     • Constant Folding: Directly computes constants in expressions (e.g., simplifying WHERE age > 2023-1990 to age > 33).
     • Subquery Optimization: Converts certain subqueries into JOIN operations (e.g., transforming IN subqueries into semi-joins).
   • Output: A more concise logical query plan is generated, describing only the logical order of operations.

3. Physical Optimization (Plan Generation and Cost Estimation)

   • Step Description: Selects specific physical implementation algorithms for each operation in the logical plan and estimates execution costs.
   • Cost Model Components:
     • I/O Cost: Number of disk data reads (primary influencing factor).
     • CPU Cost: Consumption from operations like condition evaluation and sorting.
     • Memory Cost: Memory space occupied by intermediate results.
   • Algorithm Selection Examples:
     • JOIN Algorithms: Nested Loop Join (for small driving tables), Hash Join (for large unindexed tables), Sort-Merge Join (for already sorted data).
     • Index Selection: Decides whether to use indexes based on the selectivity of WHERE conditions and index coverage.
   • Cost Estimation Basis: Relies on statistics (such as table size, number of distinct column values, data distribution histograms). Outdated statistics can lead to optimizer misjudgments.

4. Plan Selection and Execution

   • Step Description: Compares the costs of different physical plans using dynamic programming or heuristic algorithms and selects the plan with the lowest total cost.
   • Dynamic Programming Example: For multi-table JOINs, the optimal way to join two tables is calculated first, then gradually extended to multiple tables, avoiding exhaustive enumeration of all permutations.
   • Final Output: Generates an executable query plan tree (e.g., the result displayed by the EXPLAIN command), which is then processed by the execution engine.

Summary
The optimizer reduces computational load through logical optimization and matches efficient algorithms through physical optimization. Its accuracy highly depends on the quality of statistics. In practice, you can assist the optimizer's decision-making by analyzing query plans, updating statistics, or using optimizer hints (e.g., HINTs).