How Database Query Optimizers Work

A query optimizer is the component of a database engine that takes a declarative SQL query — which describes what result you want, not how to get it — and picks a concrete execution strategy to produce that result as cheaply as possible. The same query can usually be satisfied by several different physical strategies (scan this table first or that one, use an index or don’t, join in this order or the reverse), and the optimizer’s job is to estimate the cost of each candidate plan and choose the cheapest one it can find.

Declarative queries, procedural plans

SQL is declarative: SELECT * FROM orders WHERE customer_id = 42 says nothing about how to find those rows. The database could scan every row in orders and check each one, or it could jump straight to the matching rows using an index. Both produce the same result set; only their cost differs. Converting the declarative query into a procedural plan — an ordered sequence of concrete steps like “index scan orders on customer_id, then filter” — is exactly what the optimizer does, and it does it fresh for most queries, since the best plan depends on the current data, not just the query text.

Statistics: what the optimizer bases estimates on

The optimizer can’t try every possible plan against the real data and time it — that would be slower than just running the query. Instead, it estimates cost using statistics the database maintains about each table: row counts, the distribution of distinct values in a column (a histogram), the size of the average row, and which indexes exist. From those statistics it estimates, for instance, that customer_id = 42 will match roughly 12 rows out of 2 million, which makes an index scan far cheaper than reading the whole table.

These statistics go stale as data changes, which is why databases periodically recompute them (commands like ANALYZE in PostgreSQL) — an optimizer working from outdated statistics can pick a badly wrong plan even though the query itself never changed.

Join order and join strategy

For queries touching multiple tables, the optimizer also has to decide the order tables are joined in and which join algorithm to use for each pair — a nested-loop join, a hash join, or a merge join, depending on table sizes and whether the join columns are already sorted or indexed. Join order matters more than it might seem: joining a small filtered table first, then joining the result against a large table, can be orders of magnitude cheaper than joining the two large tables first and filtering afterward. With more than a handful of tables, the number of possible join orders grows combinatorially, so optimizers use heuristics and dynamic-programming-style search to prune the space rather than exhaustively evaluating every ordering.

Reading an execution plan

Every major database exposes a way to see the plan it chose — EXPLAIN in PostgreSQL and MySQL, execution plans in SQL Server. A plan typically shows, for each step: which table or index is accessed, the access method (sequential scan vs index scan vs index-only scan), the estimated number of rows, and the estimated cost. Running the ANALYZE variant (EXPLAIN ANALYZE in PostgreSQL) actually executes the query and reports the real row counts alongside the estimates, which is the fastest way to spot a bad estimate: a step estimated to return 10 rows that actually returns 2 million is a strong signal that the optimizer’s statistics are stale or that the query is structured in a way the optimizer can’t reason about accurately.

Why the same query can suddenly get slow

A query that ran fast for months can suddenly get slow with no code change, and the query optimizer is a common reason why. As a table grows or its data distribution shifts, the optimizer’s cost estimates for the same query change too, and past a certain threshold it may flip to a different plan — for example switching from an index scan to a full table scan once it estimates that more than some fraction of the table will match the filter, at which point scanning sequentially is genuinely cheaper than the overhead of random index lookups. This is one reason database indexing strategy needs to be revisited as data grows rather than set once and forgotten, and why understanding OLTP vs OLAP workload patterns matters — the two put very different pressure on an optimizer’s assumptions.

Where indexes and structure come in

The optimizer can only choose from the physical structures actually available — it can’t use an index that doesn’t exist, or benefit from column order in a composite B-tree index that doesn’t match the query’s filter order. Table layout matters too: whether a table is stored row-oriented or columnar fundamentally changes which scan strategies are cheap. Writing SQL well — filtering early, avoiding functions wrapped around indexed columns, and structuring joins so the optimizer can push filters down — gives the optimizer more good options to choose between; a poorly structured query can prevent even a well-indexed table from being used efficiently.

The takeaway

A query optimizer bridges the gap between declarative SQL and an actual sequence of physical operations, using table statistics to estimate the cost of alternative scan strategies, join orders, and join algorithms before picking the cheapest plan it can find. Reading EXPLAIN output — especially the ANALYZE variant that compares estimated to actual row counts — is the most direct way to understand why a query is slow, and refreshing table statistics or adding a supporting index is often a faster fix than rewriting the query itself.