MySQL Join Performance: Index on Join Columns, Hash Join

A join is only as fast as MySQL’s way of finding the matching rows. This lesson shows how it works and how to read it.

How a join runs: nested loops

The classic algorithm is the nested-loop join. For each row of the first table, MySQL looks for matching rows in the second table. If the second table has an index on the join column, each lookup is fast. If not, each lookup scans the whole table, which is very slow.

query.sql

SQL

SET SESSION cte_max_recursion_depth = 20000;

CREATE TABLE customers (id INT PRIMARY KEY, name VARCHAR(30) NOT NULL);
CREATE TABLE orders (id INT AUTO_INCREMENT PRIMARY KEY, customer_id INT NOT NULL, total DECIMAL(8,2) NOT NULL);

INSERT INTO customers
WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i + 1 FROM n WHERE i < 1000)
SELECT i, CONCAT('Customer ', i) FROM n;

INSERT INTO orders (customer_id, total)
WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i + 1 FROM n WHERE i < 10000)
SELECT 1 + MOD(i * 7, 1000), 10 + MOD(i, 500) FROM n;

ANALYZE TABLE customers, orders;

Without an index on the join column

query.sql

SQL

EXPLAIN FORMAT=TRADITIONAL SELECT c.name, o.total FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.id <= 10;

Output

OUTPUT

+----+-------------+-------+------------+--------+---------------+---------+---------+---------------------+-------+----------+-------------+
| id | select_type | table | partitions | type   | possible_keys | key     | key_len | ref                 | rows  | filtered | Extra       |
+----+-------------+-------+------------+--------+---------------+---------+---------+---------------------+-------+----------+-------------+
|  1 | SIMPLE      | o     | NULL       | ALL    | NULL          | NULL    | NULL    | NULL                | 10195 |   100.00 | Using where |
|  1 | SIMPLE      | c     | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | learn.o.customer_id |     1 |   100.00 | NULL        |
+----+-------------+-------+------------+--------+---------------+---------+---------+---------------------+-------+----------+-------------+
2 rows in set

(The rows numbers are estimates and vary between runs and versions, so this block is not compared.) With no index on orders.customer_id, MySQL cannot start from the customers and find their orders quickly. It chooses a different route: it reads the whole orders table (type: ALL, about 10,000 rows) and, for each order, looks up the customer through the primary key (eq_ref). That is acceptable for one small query, and a full scan every time for a big one.

When both sides lack an index: the hash join

If you join two big tables on columns without any index, MySQL 8.0.18 and later can use a hash join: it builds an in-memory hash table from one input and probes it with the rows of the other. It is far better than the old “block nested loop”, but it still reads both tables completely.

query.sql

SQL

EXPLAIN FORMAT=TREE SELECT COUNT(*) FROM orders a JOIN orders b ON a.total = b.total AND a.id < 100;

Output

OUTPUT

+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                  |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Aggregate: count(0)  (cost=108436 rows=1)
    -> Inner hash join (b.total = a.total)  (cost=98580 rows=98555)
        -> Table scan on b  (cost=1.06 rows=9955)
        -> Hash
            -> Filter: (a.id < 100)  (cost=20.1 rows=99)
                -> Index range scan on a using PRIMARY over (id < 100)  (cost=20.1 rows=99)
 |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set

Inner hash join in the plan is the sign. The plan text includes cost numbers that differ by version, so this block is not compared. Hash joins are a safety net, and the real fix for a frequent join is an index.

Add the index

query.sql

SQL

1
2

CREATE INDEX idx_orders_customer ON orders (customer_id);
EXPLAIN FORMAT=TRADITIONAL SELECT c.name, o.total FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.id <= 10;

Output

OUTPUT

+----+-------------+-------+------------+-------+---------------------+---------------------+---------+------------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys       | key                 | key_len | ref        | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------------+---------------------+---------+------------+------+----------+-------------+
|  1 | SIMPLE      | c     | NULL       | range | PRIMARY             | PRIMARY             | 4       | NULL       |   10 |   100.00 | Using where |
|  1 | SIMPLE      | o     | NULL       | ref   | idx_orders_customer | idx_orders_customer | 4       | learn.c.id |   10 |   100.00 | NULL        |
+----+-------------+-------+------------+-------+---------------------+---------------------+---------+------------+------+----------+-------------+
2 rows in set

Now orders is accessed with type: ref and ref: learn.c.id: for each of the 10 customers, MySQL jumps straight to their orders through the index. About 100 rows are read in total instead of 10,000.

Rule 1: index the foreign key column (the column in the child table that holds the parent’s id). InnoDB creates an index automatically when you declare a foreign key. Without a foreign key, you must create it yourself.

What to check in EXPLAIN for a join

Column	Good	Bad
`type`	`const`, `eq_ref`, `ref`, `range`	`ALL` on a big table
`key`	An index name	`NULL`
`rows`	Small numbers (the product of the rows of all tables is the work)	Large numbers on the second table
`Extra`	`Using index`	`Using join buffer`, `Using temporary`, `Using filesort` on big sets

eq_ref is the best join access: exactly one row for each row of the previous table, through a primary key or a unique index.

Join order

For inner joins, MySQL chooses the order. It tends to start with the table that has the fewest rows after filtering and then look up the others through indexes. You help it by:

Writing selective WHERE conditions, on indexed columns.
Keeping statistics fresh (ANALYZE TABLE).
Using the same data type and collation for joined columns. A join on INT against BIGINT, or utf8mb4 against latin1 text, may prevent index use or force conversions.

If the optimizer chooses badly, STRAIGHT_JOIN forces the order of the tables as you wrote them:

query.sql

SQL

SELECT STRAIGHT_JOIN c.name, o.total FROM customers c JOIN orders o ON o.customer_id = c.id WHERE c.id <= 3 ORDER BY o.id LIMIT 3;

Output

OUTPUT

+------------+--------+
| name       | total  |
+------------+--------+
| Customer 2 | 153.00 |
| Customer 3 | 296.00 |
| Customer 1 |  10.00 |
+------------+--------+
3 rows in set

Use it as a last resort and document why. Data changes, and a forced order that was right last year may be wrong now.

EXPLAIN ANALYZE

EXPLAIN ANALYZE (MySQL 8.0.18 and later) runs the query and shows the real time and the real row counts next to the estimates. It is the best tool for finding where a join spends its time (EXPLAIN ANALYZE).

Common join problems

No index on the join column: full scans.
Different types on the two sides (INT vs VARCHAR): no index, or wrong matches.
A function on the join column (ON LOWER(a.email) = LOWER(b.email)): no index.
Too many rows from a one-to-many join, then aggregated: filter and aggregate before joining.
Joining to a huge table just to check existence: use EXISTS.
**SELECT *** across many tables: more data to move.

lightbulb

Index first, then measure

For a slow join: (1) check that both sides have a suitable index and the same type, (2) read EXPLAIN, (3) only then think about rewriting.