Skip to content

Query Optimizer

1. What is it? (2-3 lines)

The Query Optimizer is the internal database engine component that parses declarative SQL queries, evaluates candidate physical execution plans, and selects the lowest-cost plan (minimizing estimated disk I/O, CPU, and memory) for execution.

2. Why does it exist?

SQL is a declarative language: the user specifies what data they want, not how to physically retrieve it. The Query Optimizer bridges this gap by automatically choosing access paths (Index Scan vs Sequential Scan), join algorithms (Nested Loop, Hash Join, Sort-Merge Join), and execution order across millions of candidate execution trees.

3. Where is it used?

  • Cost-Based Optimizers (CBO): PostgreSQL, MySQL (InnoDB), Oracle, SQL Server, Snowflake, BigQuery.
  • Rule-Based Optimizers (RBO): Legacy database engines (largely obsolete).

4. How does it work? (simple flow)

  1. Parser & Lexer: Converts raw SQL text into an Abstract Syntax Tree (AST).
  2. Query Rewriter / Analyzer: Normalizes AST, expands views, simplifies expressions, and applies semantic checks.
  3. Plan Generator: Generates physical execution tree alternatives (Access paths, Join orders, Aggregations).
  4. Cost Estimation: Estimates CPU and Disk I/O costs using database statistics (table row counts, page counts, column histograms, MCVs - Most Common Values).
  5. Plan Selection: Chooses the physical plan tree with the lowest total estimated cost and hands it to the Query Executor (EXPLAIN ANALYZE).

5. Advantages

  • Decouples application SQL code from physical database physical storage structures.
  • Automatically leverages newly created indexes without requiring code changes.
  • Optimizes join order dynamically based on real-time data volume statistics.

6. Limitations

  • Stale Statistics: Outdated table statistics (ANALYZE missing) cause catastrophic plan selection mistakes (e.g., picking Sequential Scan over Index Scan).
  • Parameter Blindness: Prepared statements with dynamic bind parameters can force generic, sub-optimal execution plans.
  • High planning time overhead for complex multi-table queries (requires genetic algorithm plan generation in Postgres).

7. Common interview questions (10)

  1. What is the difference between a Cost-Based Optimizer (CBO) and a Rule-Based Optimizer (RBO)?
  2. How do Nested Loop Join, Hash Join, and Sort-Merge Join differ in performance and memory usage?
  3. What causes a Query Optimizer to choose a Full Table Scan over an existing Index Scan?
  4. How do column histograms and Most Common Values (MCVs) assist in query cardinality estimation?
  5. What is EXPLAIN ANALYZE and how does actual time differ from cost estimates?
  6. What is Parameter Sniffing in database query optimization?
  7. How does PostgreSQL handle plan generation for complex queries with \(>12\) joins (GEQO - Genetic Query Optimizer)?
  8. How do Optimizer Hints (e.g. MySQL FORCE INDEX) override default CBO plan selection?
  9. Why do STALE database statistics lead to massive production latency spikes?
  10. How does Index Condition Pushdown (ICP) optimize data filtering at the storage engine level?

8. Common misconceptions

  • Misconception: The optimizer always picks the fastest execution plan. Fact: The optimizer picks the lowest-cost plan based on estimated statistics, which can be flat-out wrong if statistics are stale.
  • Misconception: SQL query order in WHERE clauses dictates join execution order. Fact: The optimizer completely reorders joins and predicates to minimize intermediate result set sizes.

10. 30-second cheat sheet

  • Function: Converts declarative SQL into the lowest-cost physical execution plan tree.
  • Cost Formula: \(\text{Total Cost} = (\text{Disk Pages Read} \times \text{seq\_page\_cost}) + (\text{CPU Tuples Checked} \times \text{cpu\_tuple\_cost})\).
  • Join Trio:
  • Nested Loop: Small outer table + Indexed inner table.
  • Hash Join: Large un-indexed equality joins (builds RAM hash table).
  • Sort-Merge Join: Pre-sorted data or range joins.
  • Top Production Fix: Run ANALYZE <table> when optimizer makes poor plan choices due to stale stats!