Scans, Seeks, Join Strategies and Sorting

Access methods

Sequential reads are far cheaper per row than random ones. That is exactly why a full scan can beat an index: 100,000 random lookups may cost more than reading a million rows in order. The optimiser weighs precisely this.

Join strategies

Nested loop join

-- For each row of the outer table, look up matches in the inner table
FOR each row in customers:
    FIND matching rows in orders WHERE customer_id = customers.id

Excellent when the outer side is small and the inner side has an index on the join column - each lookup is a seek. Terrible without that index: the inner table is scanned once per outer row. MySQL uses this strategy almost exclusively, in its block nested loop and (from 8.0.18) hash join forms.

Hash join

-- Build a hash table on the smaller side, then probe it once per row of the larger
BUILD hash of customers keyed on id
FOR each row in orders:
    PROBE the hash with orders.customer_id

The best choice for large-to-large joins with no useful index, because each side is read once. Available in MySQL 8.0.18+, PostgreSQL, SQL Server and Oracle.

Merge join

Both inputs are already sorted on the join key, so they are walked in parallel. Very efficient when the sort comes free from an index; expensive if the engine has to sort first. PostgreSQL, SQL Server and Oracle use it; MySQL does not.

Why a sort appears

-- Sort needed: no index provides this order
EXPLAIN SELECT id, order_date FROM orders ORDER BY total DESC;
-- Extra: Using filesort

-- Sort removed: the index is already in the requested order
CREATE INDEX idx_orders_total ON orders (total DESC);
EXPLAIN SELECT id, total FROM orders ORDER BY total DESC;

Using filesort does not mean a file on disk - small sorts happen in memory. It becomes a problem when the result exceeds sort_buffer_size and genuinely spills, which is common on unpaginated reports.

Why a temporary table appears

-- GROUP BY on a column with no usable index builds a temporary table
EXPLAIN SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id;
-- Extra: Using temporary; Using filesort

-- An index on the grouping column can remove both
CREATE INDEX idx_orders_customer ON orders (customer_id);

DISTINCT, UNION, GROUP BY and derived tables can all materialise a temporary table. In memory it is cheap; once it exceeds tmp_table_size it spills to disk and gets much slower.

Reading the whole picture

EXPLAIN FORMAT=JSON
SELECT c.name, SUM(o.total) AS revenue
FROM   customers c
JOIN   orders o ON o.customer_id = c.id
WHERE  o.order_date >= '2024-01-01'
GROUP BY c.name
ORDER BY revenue DESC;

Work through it in order: which table is read first, how each subsequent table is reached, whether a sort or temporary table is needed, and where the estimated row counts jump. The place where rows multiplies unexpectedly is nearly always the problem.

Important rules

• Nested loop joins need an index on the inner table's join column, or they degrade badly.
• MySQL joins one table at a time; there is no merge join, and hash join is recent.
• The optimiser reorders inner joins freely - written order does not determine execution order.
• Sorts and temporary tables are fine when small and expensive when they spill.
• LIMIT can stop a sort early, but only when the sort itself can be avoided or streamed.

Common mistakes

• Joining on unindexed columns and getting Using join buffer.
• Assuming reordering the FROM clause changes the plan.
• Treating every Using filesort as a bug.
• Sorting a huge result and paginating in the application instead of in the query.
• Grouping by an expression that no index can support.

Best practices

• Index every join column on the side being looked up.
• Filter before joining - reduce rows as early as the logic allows.
• Match index order to ORDER BY and GROUP BY to eliminate sorts.
• Watch for row count explosions between plan steps.
• Prefer a covering index for hot, narrow queries.

Practice

1. Create a join with no index on the inner side, read the plan, add the index and compare.
2. Remove a Using filesort from an ORDER BY query with an index.
3. Explain why a full scan can be faster than an index seek returning half the table.