In this article, I will introduce the join algorithms MySQL/InnoDB uses, and two gotchas about how MySQL can choose a slower join algorithm and give us a bad result.
I assume you have a basic understanding of how a database works in general, and you know how to write a basic join query.
Note that this article is based on MySQL 8.0.20 and later (including 8.4). The join behavior changed a lot in 8.0.18 and 8.0.20, so if you're on an older version, some of the things below won't apply.
Why This Matters: The Index That Made a Join Slower
We'll use the following tables as the example throughout this article.
| Table | Rows | Columns | Indexes |
|---|---|---|---|
accounts |
100,000 |
id, plan, notes
|
PRIMARY (id) |
orders |
2,000,000 |
id, account_id, product_id, amount, status, created_at
|
PRIMARY (id), idx_account_id (account_id)
|
One point about the data:
- 20,000 accounts (20%) are on the
enterpriseplan. There's no index onplan
Let's see this simple join query. It sums up the order amount for all enterprise accounts.
SELECT COUNT(*), SUM(o.amount)
FROM accounts a
JOIN orders o ON o.account_id = a.id
WHERE a.plan = 'enterprise';
We might have two assumptions:
- We have an index on
orders(account_id), so the query must be faster than without it - MySQL will choose the plan that runs faster
Surprisingly, both assumptions are wrong for this query. The plan MySQL chose took 2.36 s. When I forced MySQL to ignore the indexes, the same query took 0.47 s. So having the index made this join about 5x slower, and MySQL picked the slower plan because of that index.
This article explains why this happens, and what we can do about it as engineers
Basic Join Algorithm Introduction
Before explaining the reason, we should first understand what join algorithms MySQL has.
Block Nested Loop Join
The idea of block nested loop join is very straightforward:
- Choose one table as the outer table, and the other one as the inner table
- Read the outer table's rows into memory. This memory is called the join buffer
- Scan the inner table page by page, and compare every inner row with every outer row in memory
// read the outer table's rows into the join buffer
for each row o in the inner table:
for each row a in the join buffer:
if a.id == o.account_id:
emit (a, o)
The problem is that every inner row is compared with every outer row, so the cost is basically the two table sizes multiplied together. (And the join buffer is small, so for a big outer table, MySQL has to fill it many times and scan the whole inner table again each time.)
Index Nested Loop Join
The idea is very similar, but now we use an index (B+Tree) on the inner table to find the matched rows, instead of scanning the whole inner table.
- Choose one table as the outer table, and the other one as the inner table
- Take one row from the outer table
- Use the index on the inner table's join column to find the matched rows. This is one B+Tree walk
- Repeat for the next outer row
for each row a in the outer table:
matches = lookup a.id in the index on orders(account_id) # one B+Tree walk
for each row o in matches:
emit (a, o)
Note two things here:
- The index has to be on the inner table's join column
- The cost grows with the number of outer rows. One lookup is cheap, but 20 lookups and 20,000 lookups are very different. And each lookup jumps to a different place on disk (random reads)
Hash Join
The idea of hash join is that there are two phases:
- Build phase
- Choose one table (usually the smaller one, after the
WHEREfilter) to build the hash table - Read all its rows once, and build the hash table in memory
- The key is the join column, and the value is the columns the query needs from that row
- Choose one table (usually the smaller one, after the
- Probe phase
- Scan all the rows from the other table once
- For each row, look up its join key in the hash table in O(1)
# build
for each row a in accounts:
hash_table[a.id] = a
# probe
for each row o in orders:
if o.account_id in hash_table:
emit (hash_table[o.account_id], o)
So each table is read only once, and the matching happens in memory. The cost is basically the two table sizes added together, instead of multiplied.
Note that a hash table can only answer "give me the entry with exactly this key", so hash join needs an equality (=) in the join condition.
What MySQL actually runs
This part is a bit confusing, because MySQL changed it in two releases:
- 8.0.18: hash join was added, but only for some joins. Others still ran as block nested loop join
- 8.0.20: block nested loop join was removed. Everywhere MySQL used to run block nested loop join, it now runs hash join
So since 8.0.20, MySQL only runs two join algorithms:
- Index nested loop join, when there's a usable index on the inner table's join column
- Hash join, otherwise
Block nested loop join never runs anymore. But as we'll see next, it still lives somewhere, and that's where the problem comes from.
The Nested Loop Bias
Now that we understand the basics of the three join algorithms, it's time to see where MySQL goes wrong.
First, there are two important components in MySQL:
-
Query optimizer
- Its job is to choose the plan (join order and join algorithm) before running the query
- It can only estimate the cost, based on the statistics it has, like how many rows a table has and how many distinct values an index has
-
Query executor
- Its job is to actually run the query, based on the plan from the optimizer
So the optimizer chooses the join algorithm, and the executor just runs it.
For each table in the join, the optimizer asks one question: "for each row I already have, how do I read this table?" There are only two answers:
- Index lookup on the join column. This is index nested loop join
- Full scan of the table. The optimizer prices this as block nested loop join
The problem isn't that the optimizer always estimates the wrong cost. The problem is that when the optimizer chooses the full scan option, it prices it as block nested loop join, but the executor actually runs it as hash join.
flowchart LR
Q[Join query] --> O[Optimizer: for each table in the join order]
O -->|usable index on join column| I[Index lookup<br/>priced as index nested loop join]
O -->|no usable index| S[Scan + buffer<br/>priced as block nested loop join<br/>every pair compared]
I --> E1[Runs as index nested loop join]
S --> E2[Runs as hash join<br/>each table read once]So when deciding, the optimizer compares index nested loop join against block nested loop join. When running, it uses index nested loop join or hash join. Hash join is never priced as itself. Block nested loop join looks very expensive (two table sizes multiplied), so the index lookup wins far more often than it should.
Real Example
Let's go back to the query from the beginning.
EXPLAIN ANALYZE
SELECT COUNT(*), SUM(o.amount)
FROM accounts a
JOIN orders o ON o.account_id = a.id
WHERE a.plan = 'enterprise';
-> Aggregate: count(0), sum(o.amount)
(cost=221653 rows=1) (actual time=2338..2338 rows=1 loops=1)
-> Nested loop inner join <- index nested loop join
-> Filter: (a.plan = 'enterprise') <- outer: 20,000 enterprise accounts
-> Table scan on a
-> Index lookup on o using idx_account_id <- inner: one lookup per account
(actual time=0.115..0.115 rows=20 loops=20000)
1 row in set (2.36 sec)
From the output, we can focus on a few things:
-
Nested loop inner joinwithIndex lookup on o using idx_account_idmeans it's using index nested loop join.accountsis the outer table, andordersis the inner table, because the index is onorders.account_id -
loops=20000means the index lookup ran 20,000 times, once per enterprise account. Each lookup took about 0.115 ms, so 0.115 ms × 20,000 ≈ 2.3 s. That's almost the whole query - The estimated cost is
cost=221653. Remember this number - The total execution time is 2.36 s
Now let's force MySQL to not use the index. Instead of dropping the index, we can use the NO_JOIN_INDEX hint, which tells MySQL not to use that index for the join in this query only.
If we hide only idx_account_id, MySQL doesn't switch to hash join. It flips the join order instead: orders becomes the outer table, and it does 2,000,000 primary key lookups into accounts (about 2.0 s). Even with one index gone, it goes looking for another index. So we have to hide both indexes.
EXPLAIN ANALYZE
SELECT /*+ NO_JOIN_INDEX(o idx_account_id) NO_JOIN_INDEX(a PRIMARY) */
COUNT(*), SUM(o.amount)
FROM accounts a
JOIN orders o ON o.account_id = a.id
WHERE a.plan = 'enterprise';
-> Aggregate: count(0), sum(o.amount)
(cost=1.94e+9 rows=1) (actual time=453..453 rows=1 loops=1)
-> Inner hash join (o.account_id = a.id) <- hash join
-> Table scan on o <- probe: all 2,000,000 orders, read once
(actual time=0.907..205 rows=2e+6 loops=1)
-> Hash
-> Filter: (a.plan = 'enterprise') <- build: 20,000 enterprise accounts
-> Table scan on a
1 row in set (0.47 sec)
From the output, we can focus on a few things:
-
Inner hash join (o.account_id = a.id)means it's now using hash join - The table under
-> Hashis the build side. Here it's the 20,000 enterprise accounts. The other table,orders, is the probe side, and it's scanned only once - The total execution time is 0.47 s, about 5x faster
- But look at the estimated cost:
cost=1.94e+9
Put the two runs side by side:
| Plan | Estimated cost | Actual time |
|---|---|---|
| Index nested loop join | 221,653 | 2.36 s |
| Hash join | 1,940,000,000 | 0.47 s |
The optimizer thought the hash join was about 9,000x more expensive, but it was actually 5x faster. That's the nested loop bias: the optimizer priced the scan option as block nested loop join (re-reading orders again and again), but the executor ran it as a hash join that read orders only once.
InnoDB's Double Lookup
(Highly recommend checking out A Straightforward Guide for Database Index (B+Tree) first if you don't understand B+Tree)
There's another reason the first query was slow, and it's about how InnoDB stores data.
In InnoDB, the table itself is stored as a B+Tree on the primary key, called the clustered index. Its leaf nodes store the full rows. A secondary index like idx_account_id is another B+Tree, and its leaf nodes only store the index column and the primary key, (account_id, id).
So when a query reads a table through a secondary index and needs a column the index doesn't have, it needs a second walk on the clustered index to get that column.
In our query, we select o.amount, and idx_account_id doesn't have amount. So for each enterprise account:
- Walk
idx_account_idindex B+Tree to find that account's orders - Then walk the clustered index to get
amount
That's 20,000 secondary index walks, plus 20,000 × 20 = 400,000 clustered index walks, all random reads.
Note that this only happens when the table is read through a secondary index. A primary key lookup lands on the full row in one walk, and a full table scan reads the clustered index leaf nodes directly, so neither of them pays the second walk.
Let's add an index that has every column the query needs from orders:
CREATE INDEX idx_account_amount ON orders (account_id, amount);
DROP INDEX idx_account_id ON orders;
We don't need to add id to the index, because every secondary index leaf already has the primary key. And we can drop idx_account_id, because (account_id, amount) still works for any lookup on account_id alone (it's the leftmost column).
Run the same query again, without any hint:
-> Aggregate: count(0), sum(o.amount)
(cost=59421 rows=1) (actual time=103..103 rows=1 loops=1)
-> Nested loop inner join
-> Filter: (a.plan = 'enterprise')
-> Table scan on a
-> Covering index lookup on o using idx_account_amount <- no second walk
(actual time=0.00171..0.00236 rows=20 loops=20000)
1 row in set (0.10 sec)
From the output, we can focus on a few things:
- It's still index nested loop join, with the same 20,000 lookups.
- But now it says
Covering index lookup. This means the index alone answered the lookup, so there's no walk on the clustered index. - One lookup went from about 0.1 ms to about 0.002 ms.
- The total execution time is 0.10 s. (I re-ran the original query in the same session for comparison, and it took 2.03 s.)
Note that this is even faster than the forced hash join (0.47 s), and we didn't need any hint.
But this is fragile. If I add one more column the index doesn't have, like MAX(o.status), the plan goes back to Index lookup, all 400,000 clustered index walks come back, and the query takes 1.61 s. There's no error and no warning. Only the plan shows it.
What This Means as an Engineer
We've seen which join algorithms MySQL uses (both in the optimizer and the executor), why MySQL chooses the slower plan, and how the double lookup slows down the lookups.
Nested loop bias
In MySQL, adding an index on a join column is also choosing the join algorithm. Once that index exists, index nested loop join almost always wins in the optimizer, even for big joins where a hash join would be much faster. It's a strong bias, not a strict rule, because the optimizer still looks at other factors.
Also, don't expect MySQL to switch to hash join when the data grows. A join that reaches 50 outer rows today and 500,000 next year usually stays index nested loop join, and its cost grows with the number of outer rows.
How to spot it: a slow big join, where EXPLAIN ANALYZE shows Index lookup on the inner table with a huge loops.
When this join becomes a bottleneck, try the fixes in this order:
Cover the query first. Select only the columns you need, and add an index that has all of them. In our example this took the query from 2.03 s to 0.10 s without fighting the optimizer.
Use a hint. Give MySQL a hint to not use the index for this query, instead of dropping the index (other queries like "this account's orders" still need it).
SELECT /*+ NO_JOIN_INDEX(o idx_account_id) NO_JOIN_INDEX(a PRIMARY) */
COUNT(*), SUM(o.amount)
FROM accounts a
JOIN orders o ON o.account_id = a.id
WHERE a.plan = 'enterprise';
- One hint may not be enough. As we saw, hiding idx_account_id alone just made MySQL use the accounts primary key. Always check the plan with EXPLAIN after adding a hint
- Note that a hint locks the plan. It protects us when the optimizer chooses badly, but it also stops MySQL from adapting when the data changes
Double lookup
When a table is read through a secondary index, every column that isn't in the index costs one more clustered index walk per matched row.
Avoiding SELECT * is the first step, but it's not enough by itself. Our query only selected amount, and it still paid 400,000 extra walks. The fix is a covering index, and selecting fewer columns is what makes a covering index possible.
But covering indexes are easy to break. One new column in the query silently brings the double lookup back, and every extra column in the index makes writes slower. So it's worth it for a few hot and stable queries, not as a general fix.
Summary
- Since 8.0.20, MySQL runs only index nested loop join and hash join. Block nested loop join only exists in the optimizer's cost model
- The optimizer prices the scan option as block nested loop join, but runs it as hash join. So an index on a join column almost always locks in index nested loop join, even when hash join is much faster (2.36 s vs 0.47 s in our example)
- In InnoDB, a secondary index lookup needs a second walk on the clustered index for every column the index doesn't have. A covering index removes it (2.03 s to 0.10 s), but one extra column brings it back
Reference
I'm not a database engineer—just a software engineer who loves learning and sharing what I've figured out. If you spot any mistakes or have suggestions, please let me know in the comments. I genuinely appreciate the feedback and want to make sure this is as accurate and helpful as possible.
Top comments (1)
the nested loop bias part is the one to remember. an index quietly picking the join algorithm is a nasty surprise when the data grows.