From a plan to rows

After parsing, the MySQL optimizer turns a query into a tree of iterators, which EXPLAIN FORMAT=TREE prints (and EXPLAIN ANALYZE runs, adding the real row counts and times). Each iterator asks its children for rows and hands rows to its parent. Some pass each row on at once (a table scan, a filter, a nested-loop join, a limit); others must see their whole input first (building a hash table, filling a temporary table, sorting). The animation draws that tree top left, highlights the iterator at work, and counts the rows each one returns.

Iterator tree for the All three query: Sort total DESC (2 rows) over Table scan on temporary (2) over Aggregate using temporary table (2) over Nested loop inner join (8), whose children are Table scan on c (5) and Covering index lookup on o using idx_cust_amt (8). Sort and the aggregate must read all their input first; the others pass rows on at once.
A plan is a tree of iterators: rows flow up from the table scans, and blocking iterators such as the temporary table and the sort hold them until their input is done.

The data is tiny so every step fits on screen, but the plans are the ones MySQL picks when the tables are large:

CREATE TABLE customers (id INT PRIMARY KEY, name VARCHAR(20), city CHAR(2));    -- 5 rows
CREATE TABLE orders    (id INT PRIMARY KEY, cust_id INT, amount INT,
                        KEY idx_cust_amt (cust_id, amount));                   -- 8 rows

In InnoDB every secondary index entry also stores the primary key, so an entry of idx_cust_amt is (cust_id, amount, id). A query that needs only those columns is answered from the index alone: a covering index (EXPLAIN: Using index). Use the idx_cust_amt control to drop the index and see which plans change; use sort / join buffer to make the buffers hold just 3 rows.

JOIN

MySQL joins tables one at a time, in the order the optimizer finds cheapest. Two algorithms are used:

  • Nested-loop join. For each row of the outer (first) table, look up the matching rows in the inner table. With an index on the join column (o.cust_id) each lookup is one B-tree descent (type = ref, or eq_ref on a unique key). Cost: outer rows × one index lookup. This is by far the most common MySQL join.
  • Hash join (8.0.18 and later). When the join is an equality and no index can be used, MySQL reads the smaller input (the build input) into a hash table in the join buffer, then reads the other input (the probe input) once and looks up each row's key. Cost: one pass over each table. It replaced the older block nested loop (EXPLAIN: Using join buffer (hash join)).
Left: nested loop: for Ann (id 1) the idx_cust_amt lookup finds orders 102 and 106, for Cid (id 3) it finds 104, 101 and 107. Right: hash join: the HN customers 1 and 3 go into a hash table in the join buffer, then all 8 orders are read once and probed; 5 match.
A nested loop does one index lookup per outer row; a hash join builds a table from the small side and reads the big side once.

If the build input does not fit in join_buffer_size, the hash join writes rows to chunk files on disk, partitioned by a hash of the join key so that matching rows of both inputs land in the same pair of chunks, and then joins each pair in memory. Run All three tab, Demo: hash join spills to see it with two halves.

MySQL has no sort-merge join. The WHERE condition c.city = 'HN' is checked as early as possible (the Filter iterator above the table scan), so only the matching customers drive the join.

GROUP BY

  • Over an ordered index (tight index scan). If an index returns rows already sorted by the group columns, the aggregate only has to watch for the key to change: it keeps one group in memory and returns it the moment the next group starts. No temporary table, no sort.
  • Loose index scan (Using index for group-by). For MIN() or MAX() of the column after the group columns in an index, MySQL jumps straight to the first or last entry of each group and skips the rest. With many rows per group this reads a tiny fraction of the index.
  • Temporary table (Using temporary). Otherwise MySQL creates an internal temporary table with one row per group and a unique hash index on the group key (TempTable engine in memory; converted to an on-disk InnoDB table if it grows past tmp_table_size). Each input row finds its group and updates the aggregates; at the end the table is scanned.
Left: orders read from idx_cust_amt in cust_id order; each run of equal cust_id becomes a group (1: 2 rows 55, 2: 1 row 60, 3: 3 rows 110, 5: 2 rows 90) that is output as soon as the key changes. Right: orders in table order are added to a temporary table of groups, in first-seen order 3, 1, 5, 2, output only after all input is read.
An index in group order lets GROUP BY stream one group at a time; otherwise every group sits in a temporary table until the input ends.

Since MySQL 8.0, GROUP BY does not sort its result any more (5.7 did, implicitly). If you need an order, write ORDER BY. Watch the output order of Demo: temporary table on the GROUP BY: COUNT, SUM tab: it is the order in which groups were first seen.

ORDER BY

  • An index in the right order makes sorting unnecessary: the rows are read in order (ORDER BY cust_id, amount with idx_cust_amt). This also lets LIMIT stop after the first rows.
  • Filesort (Using filesort) otherwise. Despite the name it sorts in memory when it can: rows (the sort key plus the selected columns, packed) go into the sort buffer (sort_buffer_size) and are sorted there.
  • When the buffer fills, the sorted contents are written to a temporary file as a chunk (run), the buffer is reused, and at the end the chunks are merged. The status counter Sort_merge_passes counts these merges; if it keeps growing, the sort buffer is too small for your sorts.
  • With LIMIT n and small n, filesort keeps a priority queue of the best n rows instead: every other row is compared with the worst of the kept rows and dropped. Memory stays at n rows and nothing spills.

All three in one query

In SELECT c.city, COUNT(*), SUM(o.amount) AS total … GROUP BY c.city ORDER BY total DESC the stages stack: joined rows stream into the temporary table as they are produced, and only after the join has finished can the groups be sorted. Using temporary; Using filesort on the first table in classic EXPLAIN means exactly this.

Reading EXPLAIN

You seeIt means
type = ref / eq_ref on the inner tablenested-loop join with an index lookup per outer row
Using join buffer (hash join)no usable index for the join: a hash join
Using indexcovering index: the table itself is not read
Using index for group-byloose index scan: one or two entries per group
Using temporaryan internal temporary table (GROUP BY, DISTINCT, UNION …)
Using filesorta sort, in the sort buffer and maybe temporary files

What the animation leaves out

  • Cost estimates and index statistics: the plans are fixed per query and setting, as the optimizer would choose them for large tables.
  • Batched Key Access and Multi-Range Read, index condition pushdown, semi-joins and derived tables, and the hash-join details (MySQL sizes the number of chunk files so that each fits in the join buffer, and also uses the in-memory part of the build input).
  • Real B+ tree descents: a lookup is drawn as landing on its first entry.

Practical consequences

  • Index the join column of the inner table (usually the foreign key). Without one, a large join becomes a hash join at best.
  • A composite index in (group or order columns, other needed columns) order can remove the temporary table, the filesort, and the table lookups, all at once.
  • ORDER BY … LIMIT n is cheap either way: an index in the right order, or a priority queue.
  • Raise sort_buffer_size and join_buffer_size per session for the big reporting query that needs it, not globally: they are allocated per sort or join, per connection.