Query Optimizer: Building Execution from Lego Blocks

Concept. The query optimizer transforms a SQL query into an executable plan by enumerating possible join orders and access paths, estimating each one's IO cost, and picking the cheapest.

Intuition. For a 3-table join (Users, Listens, Songs) there are six possible join orders and dozens of access paths (full scan vs index scan, hash join vs nested loop). The optimizer asks "what does each cost?" using statistics, then runs the winning plan. A 100× speedup over the naive ordering is normal.

The Journey: SQL to Execution

Query optimizer pipeline: SQL is parsed into a parse tree, lowered to a logical plan, then expanded into multiple physical plans (each with a cost estimate). The cheapest plan is picked and executed.

Figure: SQL is parsed into a parse tree, lowered to a logical plan, then expanded into multiple physical plans, each with a cost estimate. The cheapest plan is the one that gets executed.

Algorithm Lego Blocks

The optimizer's job is to pick from a catalog of algorithm "blocks" and assemble them into a physical plan. Four families:

Algorithm 'lego blocks' the optimizer can mix and match into physical plans. Four columns: Access Methods (sequential, index, bitmap scans), Partition/Sort (Hash Partition, BigSort), Aggregation (Hash Aggregate, Sort Aggregate), Join Algorithms (Hash Join, Sort-Merge Join, Block Nested Loop).

Figure: the four families of algorithm blocks the optimizer mixes and matches. Access methods, partition and sort, aggregation, and join algorithms.

Cost mechanics (how the optimizer picks among these) live in Selectivity & Statistics and IO Cost Summary.

Query Parsing: SQL → Tree

Your SQL query starts its life as a parse tree, a structured representation that sets the stage for optimization.

SELECT * FROM users WHERE age > 21

Becomes:

        SELECT
           |
        PROJECT(*)
           |
        FILTER(age > 21)
           |
        SCAN(users)

Logical Planning: Tree → Algebra

The parse tree morphs into relational algebra operations:

  • Selection (σ): Filters rows

  • Projection (π): Chooses columns

  • Join (⋈): Merges tables

  • Aggregation (γ): Groups data

Optimization rules kick in:

  • Push filters down to process them early

  • Cut out unnecessary projections

  • Simplify expressions

The Search Space Problem

3 tables to join = 3! = 6 possible join orders
4 tables = 4! = 24 orders
5 tables = 5! = 120 orders
10 tables = 10! = 3,628,800 orders!

Solution: Use dynamic programming to discard inefficient plans early.

When the optimizer is wrong: stale statistics. If pg_class.reltuples says Listens has 1,000 rows when it actually has a billion, the optimizer picks a plan tuned for small data, runs it on big data, and your query takes hours. The fix in production is almost always ANALYZE, which refreshes the statistics. Most slow queries in the world come down to stale stats, not bad SQL.

Key Takeaways

  1. SQL is declarative - You define the result, the optimizer handles the method.

  2. Algorithms are lego blocks - Combine them for optimal performance.

  3. Cost-based decisions - Statistics guide which algorithms to use.

  4. Exponential search space - Efficient pruning is crucial.

  5. 10-100x performance difference - Between well-optimized and poor plans.

The query optimizer is your silent partner, transforming simple SQL into lightning-fast execution.

Next: Selectivity & Statistics covers how the optimizer estimates the cost of each plan it considers.