Unit
- Parsing: The database parses SQL text into an internal parse tree. It checks syntax, validates object names, and resolves privileges. Any syntax error stops the process immediately. This phase is purely syntactic and does not consider performance.
- Binding: The parser resolves identifiers against system catalogs to determine table structures, column types, and available indexes. Binding ensures semantic correctness and produces a query graph that includes metadata for subsequent optimization.
- Optimization: The optimizer evaluates many alternative execution strategies, estimating the cost of each based on table statistics and system parameters. It selects the plan with the lowest estimated cost. This is the core of query optimization.
- Execution Plan Generation: The chosen strategy is translated into an executable plan composed of operators such as table scans, index seeks, joins, aggregations, and sorts. Each operator has input and output characteristics like row count and column set.
- Execution: The execution engine runs the plan by iterating over row sources and applying operators step by step. Results are streamed to the client or written to temporary storage as needed. Runtime conditions may cause plan changes.
- Cost Estimation Basis: Costs are measured in terms of I/O operations, CPU cycles, and memory usage. The optimizer uses these metrics to compare plans. Accurate statistics are critical: outdated or incomplete statistics lead to suboptimal plans.
- Reoptimization and Plan Caching: Many databases cache execution plans to avoid repeated optimization. However, parameterized queries may cause plan reuse that is suboptimal for different input values. Understanding when reoptimization is triggered helps maintain performance.
- Row Source Trees: The physical plan is a tree of row sources (operators). Each row source consumes rows from its children, applies its logic, and produces rows for its parent. Examples include Sequential Scan, Index Scan, and Hash Join nodes.
- Statistics and Histograms: The optimizer relies on column-level statistics such as distinct values, null fraction, and data distribution histograms. Histograms break down value ranges to estimate selectivity of filter predicates. Without accurate histograms, the optimizer may misestimate row counts, leading to poor join order or index selection. Regularly updating statistics is essential for reliable cost estimates.
- Join Algorithms: The optimizer chooses among nested loop, hash join, and merge join based on input sizes and available indexes. Nested loops work well for small outer relations with an index on the inner side. Hash joins are efficient for large unsorted inputs, while merge joins require sorted data and are ideal for large tables with matching sort orders. Understanding these choices helps diagnose plan performance.
System Architecture
Pattern: Query Compilation Pipeline
Components:
- Parser: Converts SQL text to parse tree. Validates syntax and permissions.
- Binder: Resolves symbols against system catalog. Injects type and constraint info.
- Optimizer: Explores join orders, access paths, and operator implementations. Produces costed plans.
- Executor: Interprets physical plan, fetches rows from storage, applies operations, and returns results.
Code Example
SQL
EXPLAIN ANALYZE
SELECT o.order_id, c.customer_name
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE o.order_date >= '2024-01-01';The EXPLAIN ANALYZE output shows each plan node with actual row counts and execution time. Look for nodes with a high cost or large discrepancy between estimated and actual rows. That indicates a statistics or optimization problem.
Quick Revision
- The query execution pipeline includes parsing, binding, optimization, and execution phases.
- Optimization relies on statistics and cost models to choose the best plan among many alternatives.
- The physical plan is a tree of row source operators, each responsible for a specific data transformation.
- Plan caching improves performance but can cause suboptimal plans if parameter values vary widely.