How a database turns your SQL into the fastest possible plan

1 Why optimization matters

In SQL you write what you want, not how to get it. SQL is a declarative language — you describe the result ("give me all customers in London who spent over $1000"), and the database decides the actual steps. This is different from a language like Python, where you'd write the exact loops and lookups yourself (that style is called imperative).

The catch: there are usually many different step-by-step procedures that all produce the exact same answer. We call each one a plan (or query plan / execution plan). Two plans can return identical rows yet differ in speed by factors of thousands or millions. The piece of the database that picks a good plan is the query optimizer.

Logical plans vs physical plans

Optimization happens in two layers. First the database figures out what operations to do; then it figures out how to do each one. These are two different kinds of plan:

A logical operation like "join" can be carried out by several physical operators — a nested-loop join, a hash join, or a sort-merge join (you met these in Session 10: Query Execution — Joins & Sorting). The optimizer's job is to start from the logical plan and choose the best physical operators and the best order, guided by cost estimates.

SELECT c.name, o.total
FROM Orders o
JOIN Customers c ON o.customer_id = c.id
WHERE c.city = 'London';

2 Cost estimation & selectivity

To compare plans without running them, the optimizer assigns each one a cost — a single number estimating how much work it'll take (CPU + disk reads, roughly). The plan with the lowest estimated cost wins. The hardest, most important input to that cost is: how many rows will each step produce? Get the row counts right and the cost is usually right; get them wrong and the optimizer can pick a disastrous plan.

Statistics — what the database remembers about your data

The database keeps statistics about each table, gathered by periodically scanning (or sampling) it. The optimizer never looks at the actual data while planning — only these summaries. Common statistics:

Selectivity — what fraction survives a filter

The selectivity of a predicate (a condition in a WHERE clause) is the fraction of rows that pass it — a number between 0 and 1. Multiply selectivity by the table's row count and you get the estimated rows out. This estimated row count is called the cardinality estimate.

Rules of thumb the optimizer uses (when it has no better information):

SELECT * FROM Customers
WHERE city = 'London' AND country = 'UK';

3 Join ordering

Most real queries join several tables. A join combines rows from two tables on a matching condition. When you join three or more tables, you must pick an order — and because joins produce intermediate results that feed the next join, the order massively changes how much work happens. Join ordering is the single most important decision the optimizer makes, because the intermediate result sizes can blow up.

The combinatorial explosion

How many orders are there? For n tables, the number of possible join orderings grows terrifyingly fast — far faster than even factorial when you also count the different tree shapes:

You can't enumerate all of these for a 15-table query. So the optimizer needs both a way to limit the shapes it considers, and a clever search that avoids brute force.

Left-deep trees — taming the shapes

A join tree can be shaped many ways. The classic restriction is the left-deep tree: every join takes the running result so far on the left and joins in one base table on the right. It looks like a staircase.

Left-deep (preferred):        Bushy (more shapes, rarely needed):

        ⋈                              ⋈
       / \                           /   \
      ⋈   D                        ⋈     ⋈
     / \                          / \   / \
    ⋈   C                        A   B C   D
   / \
  A   B

Why left-deep? Because it lets the optimizer pipeline nicely (feed one join's output straight into the next without materializing huge tables) and it keeps the search space at n! instead of the astronomically larger set of all "bushy" trees. System R, the original optimizer, restricted itself to left-deep trees for exactly this reason.

Dynamic programming — the System R approach

The breakthrough from the 1979 System R paper (Selinger et al.) was to find the best order without trying every order, using dynamic programming (DP). The trick: the best way to join a big set of tables is built from the best ways to join its smaller subsets. So compute and remember the best plan for every subset, building up from small to large.

DP vs heuristics — when each is used

DP gives the provably best order it considers, but its cost grows like 2ⁿ, so it becomes too slow past roughly 10–15 tables. Beyond that, optimizers fall back to heuristics — fast rules of thumb that find a "good enough" order without guaranteeing the best:

4 Rule-based transformations

Before (and during) cost-based search, the optimizer applies transformation rules: rewrites that change a plan's shape while guaranteeing the result stays identical. These come from the algebra of relations — operations that are provably equivalent. Unlike join ordering (which needs cost estimates), many of these are almost always good, so they're applied as rules. Here are the classics:

Predicate pushdown (filter early)

Predicate pushdown moves WHERE filters as close to the raw tables as possible — before joins instead of after. Filtering first shrinks the data that the expensive joins have to chew through. This is the LEGO trick, and it's exactly the "Plan A vs Plan B" from Topic 1.

Projection pushdown (drop columns early)

Projection pushdown moves column-trimming (the SELECT list) down so the database stops carrying columns it doesn't need. Narrower rows mean less memory and less data shuffled between operators. If you only need name and total, there's no reason to drag along 30 other columns through a join.

Constant folding (do the arithmetic once)

Constant folding evaluates constant expressions at planning time instead of once per row. WHERE price > 10 * 100 becomes WHERE price > 1000 — computed once, not a million times. Related simplifications drop always-true conditions like 1 = 1 and short-circuit always-false ones.

Using indexes (the right access path)

An index (covered in earlier sessions) is a sorted lookup structure, like a book's index. Instead of a full sequential scan (reading every row), the optimizer can choose an index scan to jump straight to matching rows — but only when the filter is selective enough to be worth it. Choosing between a sequential scan and an index scan for each table is the access-path selection that the System R paper is literally named after.

Before / after — a worked transformation

SELECT c.name, o.total
FROM Orders o
JOIN Customers c ON o.customer_id = c.id
WHERE c.city = 'London';

π (name, total)              -- project: keep 2 columns  (LAST)
  └─ σ (city = 'London')     -- filter                   (MIDDLE)
       └─ Orders ⋈ Customers -- join ALL rows first      (FIRST, huge!)

π (name, total)
  └─ ( Orders )  ⋈  ( σ city='London' (Customers) )
                          ↑ filter applied BEFORE the join

Reading EXPLAIN — seeing the chosen plan

You don't have to guess what the optimizer picked. The EXPLAIN command prints the chosen physical plan as an indented tree. In PostgreSQL:

EXPLAIN SELECT c.name, o.total
FROM Orders o
JOIN Customers c ON o.customer_id = c.id
WHERE c.city = 'London';

A typical output looks like this (read it inside-out: the most indented nodes run first, feeding their parents):

Hash Join  (cost=15.50..320.75 rows=50 width=40)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o  (cost=0.00..250.00 rows=10000 width=12)
  ->  Hash  (cost=15.00..15.00 rows=50 width=36)
        ->  Index Scan using customers_city_idx on customers c
              (cost=0.42..15.00 rows=50 Filter: (city = 'London'))

How to read each node:

★ Putting it all together

You just learned how a database secretly transforms your tidy little SQL query into a fast, concrete execution plan. Here's the one-paragraph story connecting all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• 📘 DBMS Session 11 — Query Optimization (class handout).

Papers, docs & deep dives

• CMU 15-445 — Database Systems — the gold-standard free course; its query-planning and optimization lectures cover everything here in depth.
• Selinger et al., "Access Path Selection in a Relational Database Management System" (1979) — the foundational System R paper that introduced cost-based optimization and dynamic-programming join ordering.
• PostgreSQL Documentation — Using EXPLAIN — the official guide to reading query plans, costs, and row estimates in a real, widely-used database.
• PostgreSQL Documentation — Statistics Used by the Planner — how a production optimizer stores and uses statistics, histograms, and distinct-value counts.
• Use The Index, Luke! — a friendly, practical explainer on indexing and how the optimizer decides between index scans and full scans.