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 costs each candidate from statistics, then runs the winner. A 100× speedup over the naive ordering is normal.

The Journey: SQL to a Plan

Five-stage pipeline: SQL (declarative) to parse and bind, to a logical plan of equivalence-preserving relational-algebra rewrites that defines the result, to the physical-plan cost search (pick join order, algorithm, access path; dynamic programming reuses the best sub-plan per table subset so n! becomes about 2 to the n; cost each from statistics) where speed is decided, to executing the chosen operator tree about 100x faster than naive.

Figure 1. SQL is declarative: it states the result, not the procedure. Parsing and binding produce a validated tree; the logical plan then applies equivalence-preserving relational-algebra rewrites (predicate pushdown, projection pruning, subquery flattening). "Defines the result" means exactly this: every rewrite, and every plan the next stage considers, returns the same rows, so the answer is now pinned and only running time can still change. The physical-plan cost search decides speed: it chooses a join order, join algorithm, and access path, and because trying all n! orders is infeasible it uses dynamic programming, computing the cheapest sub-plan for each subset of tables once and reusing it (so n! work collapses to about 2ⁿ), with each candidate costed from table statistics. Only the winner executes, routinely about 100 times faster than the naive ordering.

Algorithm Lego Blocks

The optimizer picks from a catalog of algorithm "blocks" and assembles 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 2. The optimizer assembles a physical plan from four families of interchangeable blocks: access methods (sequential, index, and bitmap scans), partition and sort (Hash Partition, BigSort), aggregation (Hash Aggregate, Sort Aggregate), and join algorithms (Hash Join, Sort-Merge Join, Block Nested Loop). Any plan is one choice from each family wired together, so plan selection is a cost comparison across those combinations. Each block is a primitive with its own page.

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

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. Many slow queries come down to stale stats rather than the SQL.

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