Query optimizer

What is a query optimizer?

A query optimizer is the part of a database that decides how a query actually runs. You write SQL that says what data you want. The optimizer works out how to get it: which table to read first, whether to use an index or scan, which join method to apply, and in what order.

This works because SQL is declarative. A SELECT statement describes the result, not the steps. As Microsoft's SQL Server documentation puts it, the statement "doesn't state the exact steps that the database server should use to retrieve the requested data," so the engine has to find the most efficient way itself.

Take a query that joins orders, customers, and products with a filter on the customer. The database could filter customers first, read all the orders first, seek an index, scan a table, or pick a different join order. Every route returns the same rows, but not in the same time. The optimizer's job is to pick the route it estimates will be cheapest.

How the optimizer chooses a plan

Most relational databases use a cost-based optimizer. It generates candidate plans, gives each an estimated cost in CPU, disk, memory, and temporary storage, and keeps the cheapest. SQL Server says it plainly: "Each possible execution plan has an associated cost... the Query Optimizer must analyze the possible plans and choose the one with the lowest estimated cost." MySQL does the same against a configurable cost model.

Part of that cost is the join strategy. For each join the optimizer weighs a nested loop, a hash join, or a merge join, and it also weighs the order in which tables are joined. Join order matters a lot: filtering a table down to 50 rows before joining is far cheaper than joining two large tables and filtering afterwards.

The number of candidate plans explodes with every extra table. SQL Server notes that some queries have "thousands of possible execution plans," so it does not try them all; it uses algorithms to find a plan "reasonably close to the minimum possible cost." PostgreSQL runs a near-exhaustive search for a handful of tables, then switches to a heuristic search (its genetic optimizer) once the join count grows. Good enough quickly beats perfect but too late.

Statistics and cardinality estimation

A cost estimate is only as good as the row counts behind it. Working out how many rows each step will produce is called cardinality estimation, and it runs on statistics the database keeps about your data: table row counts, the number of distinct values in a column, histograms of how values are spread, and lists of the most common values. PostgreSQL refreshes these with ANALYZE; MySQL builds column histograms with ANALYZE TABLE.

Selectivity is the fraction of rows a condition keeps, and it decides whether a database index earns its place. A filter on country = 'BE' helps almost nothing if 95% of your customers are Belgian, because the index would point at nearly every row anyway and a plain scan is cheaper. A filter on a unique customer_id that matches 30 rows out of five million is a clear win for an index seek. The optimizer only tells the two cases apart because the statistics tell it. It can also rewrite the query to drop rows earlier, for example pushing a filter below a join, an optimization called predicate pushdown.

The optimizer versus the execution plan

These two terms get used interchangeably, but they are not the same thing. The query optimizer is the component that does the choosing. The execution plan is the artefact it produces: the concrete list of steps (scans, seeks, joins, sorts, aggregations) that the engine then runs. You inspect the plan with EXPLAIN to see what the optimizer decided.

It is worth separating from query folding as well. Folding, in tools like Power Query, decides whether a transformation step is translated back into SQL and pushed to the source database at all. Once folding has handed that SQL over, the database's optimizer decides how to run it. Folding sets where the work happens; the optimizer sets how.

Why the optimizer gets it wrong

The optimizer estimates, and estimates can miss. Three causes explain most bad plans.

Stale statistics. If the data has grown or shifted since the last ANALYZE, the optimizer plans against a picture that no longer matches reality. A table it thinks holds a thousand rows might hold ten million. Refreshing the statistics is usually the first thing to try.

Correlated predicates. By default the optimizer assumes conditions are independent and multiplies their selectivities. When columns move together, that assumption breaks. PostgreSQL's own example filters on city = 'Washington' AND state = 'DC': the two are correlated, so the real match rate is about a hundred times higher than the independent estimate. A count that low can steer the optimizer into a nested loop that is fine for three rows and painful for thousands. Extended statistics (CREATE STATISTICS) let it learn the correlation.

Parameter sniffing. SQL Server compiles a plan using the parameter values from the first run and caches it. If that first call was for a small customer with 20 orders, the cached plan can crawl when the next call asks for a customer with two million. The plan fit the value it was built for, not the one you are running now. OPTION (RECOMPILE) forces a fresh plan each run when that trade-off is worth it.