How SQL Optimizers Actually Work

Why you need an optimizer at all

SQL is declarative. When you write SELECT c.name, o.total FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.region = 'West', you never said whether to scan the orders table first or the customers table first, whether to use an index, or which join algorithm to run. You just described the result. Something has to turn that description into an actual sequence of steps the storage engine can execute — that something is the optimizer, and the plan it produces is called an execution plan.

This matters because the same query can be executed a dozen logically equivalent ways, and their real-world costs can differ by orders of magnitude. Picking well is the entire job.

Stage 1: Parse and validate

Before any optimization happens, the database parses your SQL text into a tree structure, checks that the tables and columns exist, resolves data types, and confirms you have permission to read them. The output of this stage is a logical plan — an abstract description of what the query needs to do (scan customers, filter by region, join to orders, project two columns) with no decisions yet about how.

Stage 2: Logical rewrite

Next, the optimizer applies rewrite rules that produce a logically equivalent query, but one that's often much cheaper to execute. These rewrites happen regardless of your table sizes — they're safe transformations, not cost-based guesses. The most important one is predicate pushdown: moving a WHERE filter as close to the data source as possible, instead of applying it only after everything is joined.

SELECT c.name, o.total
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.region = 'West';

Read literally, this looks like "join every customer to every order, then throw away the rows where region isn't West." No real database executes it that way. The rewrite stage recognizes that the region filter only touches customers, and applies it before the join — filtering customers down to just the West region rows, then joining only those against orders. Same result, far less work, and it happens before the optimizer even starts thinking about statistics or costs.

Stage 3: Cost-based physical planning

This is where the optimizer earns its name. For each step in the logical plan, it considers several possible physical implementations, estimates the cost of each using table statistics, and picks the cheapest. The key input is cardinality estimation — predicting how many rows each step will produce.

Say customers has 100 rows and, from stored statistics, the optimizer knows region has 10 distinct values spread roughly evenly. It estimates WHERE region = 'West' will match about 10 rows — 10% selectivity. That single estimate cascades through the rest of the plan: with only ~10 customer rows to join, a plan that loops over those 10 and does an indexed lookup into orders for each one is far cheaper than a plan that builds a hash table out of a million-row order table.

Join order and join algorithms

With more than two tables, the optimizer also has to decide which table to join first — join order changes the size of every intermediate result, and a bad order can make a query orders of magnitude slower even though the final output is identical. For each pair of tables being joined, it also picks a join algorithm:

None of these is universally "best" — each wins under different conditions, which is exactly why the optimizer needs cost estimates to choose rather than a fixed rule.

How an index changes the plan

Indexes don't just make lookups faster — they change which plan is even worth considering. Without an index on orders.customer_id, looking up one customer's orders means scanning the whole orders table. Doing that 10 times, once per West-region customer, would be worse than scanning it once. So the optimizer correctly avoids a nested loop and instead picks a hash join: one full scan of orders, building a hash table on customer_id, then probing it with the 10 filtered customers.

Add an index on orders.customer_id, and the calculus flips. Now each of the 10 customer lookups is a cheap indexed seek instead of a full scan, and the nested loop plan becomes far cheaper than building a hash table out of a million rows it will mostly never use. Same query, same data, different plan — because the available access paths changed.

Reading an EXPLAIN plan

EXPLAIN (or EXPLAIN ANALYZE to also run the query and show real numbers) prints the plan the optimizer chose. A representative plan for the indexed version of our query looks like this:

Nested Loop  (rows=10)
  -> Seq Scan on customers c  (rows=10)
       Filter: region = 'West'
  -> Index Scan using orders_customer_id_idx on orders o  (rows=1)
       Index Cond: customer_id = c.id

Read it from the innermost, most indented node outward — that's execution order, not the order the lines appear in your query. Here, the customers scan runs first and produces 10 rows; for each one, an index lookup into orders runs and typically returns about 1 matching row; the nested loop combines them. Each node's row count is what the optimizer estimated — with EXPLAIN ANALYZE you'd also see the actual count, and a big gap between estimated and actual is usually the first sign something's wrong.

When optimizers get it wrong

• Stale statistics. If a table has grown from 1,000 rows to 10 million since statistics were last gathered, every cardinality estimate built on it is wrong, and the chosen plan can be badly suited to the real data.
• Non-sargable predicates. Wrapping an indexed column in a function, like WHERE YEAR(order_date) = 2026, usually stops the optimizer from using an index on order_date at all, because it can no longer reason about the filter directly against the stored values.
• Data skew. Statistics often summarize a column with an average — but if 90% of orders belong to one customer, an estimate based on the average selectivity across all customers will be wrong for that one.
• Search space limits. With enough joined tables, evaluating every possible join order becomes computationally infeasible, so optimizers fall back to heuristics or randomized search past a certain threshold — still good, but no longer guaranteed optimal.