The optimizer

Cost is a unitless number. Historically it was "how many random page reads would this take", and the constants still carry that flavour. They live in two tables you can actually edit.

Notice io_block_read_cost is only 4× memory_block_read_cost. On real hardware a disk read is orders of magnitude slower than a memory read — so the model systematically underestimates the penalty of a plan that misses the buffer pool. That is one structural reason MySQL sometimes prefers a scan you would not have chosen.

From chapter 34: index statistics are sampled from innodb_stats_persistent_sample_pages pages (default 20). They give the optimizer cardinality — how many distinct values an index has — from which it infers selectivity by assuming uniform distribution.

That assumption is the problem. Real data is skewed. A status column with 99% 'active' and 1% spread across four other values has cardinality 5, so the optimizer estimates every value matches 20% of the table. It is catastrophically wrong in both directions at once.

Histograms fix exactly this

8.0 added histograms: an actual distribution of values, stored in the data dictionary, for columns you nominate. Two kinds, chosen automatically:

• Singleton — when distinct values ≤ bucket count, it stores the exact frequency of each value. Perfect accuracy.
• Equi-height — otherwise, buckets each holding roughly the same number of rows, so dense regions get finer resolution.

-- 1. See the misestimate on a skewed column.
EXPLAIN SELECT * FROM orders WHERE status = 'cancelled';
SELECT COUNT(*) FROM orders WHERE status = 'cancelled';
--    compare "rows" to the real count. often 100x out.

-- 2. Build a histogram.
ANALYZE TABLE orders UPDATE HISTOGRAM ON status, amount WITH 64 BUCKETS;

-- 3. Re-EXPLAIN. The estimate should now be close.
EXPLAIN SELECT * FROM orders WHERE status = 'cancelled';

-- 4. Inspect what it stored.
SELECT JSON_PRETTY(histogram) FROM information_schema.column_statistics
WHERE table_name = 'orders' AND column_name = 'status'\G

-- 5. Refresh it on a schedule, or drop it.
-- ANALYZE TABLE orders DROP HISTOGRAM ON status;

MySQL has three, and notably lacks a fourth that Postgres has.

For N tables there are N! possible join orders. Ten tables is 3.6 million orderings, each needing cost evaluation. Exhaustive search is infeasible, so MySQL uses a greedy search with a configurable lookahead: optimizer_search_depth (default 62, meaning "decide automatically").

The chosen order matters enormously, because the optimizer wants the most selective table first — filtering early means fewer rows flow through every subsequent join.

A semijoin answers "does a match exist?" without duplicating rows — WHERE x IN (SELECT ...) and WHERE EXISTS (...). MySQL has five execution strategies and picks by cost.

A subquery in FROM is a derived table. The optimizer either merges it into the outer query — so conditions push down and indexes work — or materializes it into a temporary table.

-- merged: becomes a plain indexed lookup
SELECT * FROM (SELECT * FROM users WHERE active=1) d WHERE d.id = 42;

-- cannot merge: aggregation forces materialization
SELECT * FROM (SELECT user_id, COUNT(*) c FROM orders
          GROUP BY user_id) d WHERE d.user_id = 42;
--   the ENTIRE aggregate is computed, then one row selected.

Merging is blocked by aggregation, DISTINCT, LIMIT, UNION and window functions. When it is blocked, the filter cannot push down and you may compute a million groups to read one.

derived_merge in optimizer_switch controls this, and 8.0 adds automatic indexes on materialized derived tables (<auto_key0> in EXPLAIN) which softens the cost considerably.

When no single index serves a query, MySQL can use several and combine the results. Three variants:

• Union — for OR conditions. Scan each index, union the primary keys.
• Intersection — for AND. Scan each, keep keys appearing in all.
• Sort-union — union where results need sorting first.

"Filesort" is a misleading name — it often happens entirely in memory. It means "sorting without using an index's ordering", nothing more.

Two algorithms

• Single-pass — read all selected columns into the sort buffer, sort, output. Fewer IO operations, but wide rows fill the buffer fast. Preferred when the row fits.
• Two-pass — sort only the sort key plus the row id, then fetch rows in sorted order. Handles wide rows but re-reads them randomly.

If the data exceeds sort_buffer_size, it is sorted in chunks written to disk and merged — each merge pass increments Sort_merge_passes. That counter rising is the signal that sorts are spilling.

The priority queue optimization

For ORDER BY ... LIMIT n with small n, MySQL keeps a heap of the best n rows instead of sorting everything. Finding the top 10 of a million rows costs one pass and a tiny heap, not a full sort. This is why adding LIMIT to an ordered query can be dramatically faster than you would expect — and why removing it can be dramatically slower.

EXPLAIN shows the plan. EXPLAIN ANALYZE (8.0.18+) runs the query and annotates the iterator tree with real timings. It is strictly more useful, and this is how to read it.

The five things to look at, in order

1. actual time=A..B — A is time to the first row, B to the last. A blocking operator shows A ≈ B, because it cannot emit anything until it has consumed everything. Above, Sort shows 812..812: it is the blocker.
2. loops=N — how many times this node ran. Multiply it by the node's own time to get its true contribution. The index lookup above takes 0.06ms but runs 10,000 times: 600ms, the bulk of the query.
3. Estimated rows versus actual rows — the single most valuable comparison. rows=9891 against rows=10000 is healthy. An order-of-magnitude gap means your statistics are wrong, and every cost decision above that node was made on bad data.
4. Where the time appears — subtract a child's time from its parent's to find where it was actually spent.
5. Scan nodes on large tables — Table scan on u producing 10,000 rows to feed a join is the thing to fix first.

-- Plan only, no execution.
EXPLAIN FORMAT=TREE SELECT ...\G

-- Plan + real timings. NOTE: it EXECUTES the query.
-- Never run it on an UPDATE/DELETE you do not want applied.
EXPLAIN ANALYZE SELECT ...\G

-- Full cost numbers, including filtered % and used_key_parts.
EXPLAIN FORMAT=JSON SELECT ...\G

-- Explain a query that is running RIGHT NOW in another session:
EXPLAIN FOR CONNECTION 1234\G
--   invaluable during an incident. get the id from
--   SHOW PROCESSLIST, then see what plan it actually chose.

EXPLAIN tells you what was chosen. The trace tells you why — every alternative considered, its cost, and the reason it lost. When a plan makes no sense, this is the tool.

SET optimizer_trace = "enabled=on";
SET optimizer_trace_max_mem_size = 1048576;   -- traces get big

SELECT * FROM orders o JOIN users u ON u.id=o.user_id
 WHERE o.status='paid' ORDER BY o.created_at LIMIT 10;

SELECT JSON_PRETTY(trace) FROM information_schema.optimizer_trace\G
SET optimizer_trace = "enabled=off";

-- The sections that matter, in reading order:
--
--   rows_estimation.range_analysis
--     → every index considered, with its cost.
--       "chosen": false always carries a "cause".
--
--   considered_execution_plans
--     → each join order tried, and its cumulative cost.
--
--   attaching_conditions_to_tables
--     → which predicates were pushed to which table.
--
--   reconsidering_access_paths_for_index_ordering
--     → why it did or did not use an index to avoid the sort.

Two generations of hint syntax, and they behave differently.

Prefer the new comment-style hints: they are scoped to one query block, they are ignored rather than fatal on older servers, and they express intent more precisely.

Both arrived in 8.0 and both have execution characteristics worth knowing. The SQL module covers their semantics; here we cover how MySQL runs them.

CTEs

A non-recursive CTE is treated like a derived table: merged when possible, materialized otherwise. Crucially, a CTE referenced multiple times is materialized once and reused — unlike a repeated subquery, which is evaluated each time. That makes a CTE a genuine optimization when you need the same intermediate result twice.

Recursive CTEs execute as a fixpoint loop: evaluate the anchor, then repeatedly evaluate the recursive term against the previous iteration's rows until it produces none. cte_max_recursion_depth (default 1000) stops runaway recursion.

Window functions

Executed after WHERE, GROUP BY and HAVING, but before ORDER BY and LIMIT — which is why you cannot filter on a window function's result directly and must wrap it in a subquery or CTE.

Execution needs the rows sorted by PARTITION BY then ORDER BY. If an index provides that order, the sort is free; otherwise it is a filesort over the whole result. So a window function over a large partition set is really a sorting problem, and the index that matches the partition and order clauses is what makes it fast.

That is the single-server picture complete. Part 9 adds the second machine: binary logs, replication, GTIDs, and the failure modes that come with them.