Query optimisation
The optimiser searches among many equivalent plans for the cheapest. It relies on algebraic rewrite rules, statistics about data, and a cost model.
Why optimisation matters
Equivalent plans can differ in cost by factors of thousands or millions. A three-table join can be performed in several orders, each with several algorithms per join, and for ten tables there are millions of join orders. Choosing well is what lets declarative SQL be fast without programmers specifying how to execute queries.
Rewrite rules
Relational algebra identities transform plans without changing results. Selections can be pushed down below joins so fewer rows are joined; projections can be pushed down so less data flows; joins are commutative and associative, so they can be reordered; and subqueries can be flattened into joins. Rule-based rewrites apply transformations that are almost always beneficial.
Cost-based optimisation
Pioneered by IBM's System R in the late 1970s, notably in Patricia Selinger's 1979 paper, cost-based optimisers estimate each plan's cost, mainly page reads and CPU work, and pick the cheapest. System R's dynamic programming approach builds the best plans for small sets of tables and combines them into plans for larger sets, often restricting the search to left-deep trees.
Statistics
Cost estimates depend on statistics: table row counts and sizes, the number of distinct values per column, minimum and maximum values, histograms describing value distributions, and lists of the most common values. Commands such as ANALYZE in PostgreSQL refresh them. Outdated statistics, for example after a large data load, are a leading cause of bad plans.
Cardinality estimation
The optimiser estimates how many rows each operator produces. For WHERE city = 'Lima' it might use the most-common-values list or assume a uniform spread across distinct values. For combined conditions, it often assumes independence and multiplies selectivities, which fails for correlated columns, such as city and country. Errors multiply through joins, making estimation the hardest part of optimisation.
Join ordering
Join order often dominates cost: joining two small, filtered tables first and then the large one keeps intermediate results small. Exhaustive search is feasible for perhaps a dozen tables; beyond that, optimisers use heuristics or randomised searches, such as PostgreSQL's genetic query optimiser, which is used when a query joins many tables.
Helping the optimiser
Developers can help by keeping statistics current, creating appropriate indexes, writing predicates the optimiser can use (for example, avoiding functions on indexed columns unless an expression index exists), declaring constraints such as foreign keys and NOT NULL, and avoiding SELECT * when only a few columns are needed. Many systems also allow hints or extended statistics for correlated columns.
Worked example
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id WHERE c.country = 'NZ'. If 1% of 100,000 customers are in New Zealand, pushing the filter down leaves 1,000 customers. The optimiser can then use those 1,000 to drive an index lookup into orders, or build a small hash table on them and probe with orders, rather than joining all 10,000,000 orders to all customers and filtering afterwards.
Key takeaways
Equivalent plans can differ in cost by orders of magnitude. Rewrite rules push selections and projections down, reorder joins, and flatten subqueries. Cost-based optimisation, from System R and Selinger's 1979 work, uses dynamic programming over join orders and a cost model. Statistics such as row counts, distinct values, histograms, and common values feed estimates; refresh them with ANALYZE. Cardinality estimation, often assuming independence, is the hardest part and errors compound. Join order matters greatly; many-table queries use heuristics such as genetic optimisation. Indexes, constraints, current statistics, and sargable predicates help the optimiser.
Flashcard
Chooses an efficient execution plan
Check your understanding
Why does WHERE YEAR(order_date) = 2026 often prevent use of an index on order_date?