MySQL Join Algorithms and Optimization Techniques

When optimizing MySQL queries, single‑table cases often focus on indexes, but most production workloads involve multi‑table joins that can severely degrade performance; this article demonstrates how to analyze and improve such joins.

Preparation

All examples use MySQL 5.7 (with occasional references to MySQL 8.0). Two identical tables, t1 and t2 , are created and populated via stored procedures:

# create two identical tables t1, t2
create table t1(
  id int not null auto_increment,
  a int,
  b int,
  c int,
  primary key(id),
  key idx_a(a)
);
create table t2 like t1;

# procedure to fill t1 with numbers divisible by 3 (1000 rows)
delimiter //
create procedure t1_proc()
begin
  declare i int default 1;
  while (i<=3000) do
    if (i%3)=0 then
      insert into t1(a,b,c) values(i,i,i);
    end if;
    set i=i+1;
  end while;
end //
delimiter ;

# procedure to fill t2 with numbers divisible by 2 (100000 rows)
delimiter //
create procedure t2_proc()
begin
  declare i int default 1;
  while (i<=200000) do
    if (i%2)=0 then
      insert into t2(a,b,c) values(i,i,i);
    end if;
    set i=i+1;
  end while;
end //
delimiter ;

call t1_proc();
call t2_proc();

drop procedure t1_proc;
drop procedure t2_proc;

Sample data from each table confirms the expected rows.

MySQL Join Algorithms

1. Simple Nested‑Loop Join : For each row in the driving table ( t1 ), the entire t2 table is scanned, leading to rows(t1) × rows(t2) comparisons (e.g., 1 000 × 100 000 = 100 million). This causes massive I/O and CPU usage.

2. Block Nested‑Loop Join : MySQL stores a block of rows from the driving table in the join buffer (size controlled by join_buffer_size , default 256 KB). The buffered rows are compared against the whole inner table in one pass, reducing the number of full scans of the inner table. If the buffer fills, the process repeats, scanning the inner table only a few times.

3. Hash Join (available from MySQL 8.0): MySQL builds a hash table on the join column of the driving side and probes it with rows from the inner side, dramatically cutting the number of comparisons. Execution plans show Using join buffer (hash join) and performance improves from ~5 seconds to ~0.02 seconds in the demo.

4. Index Nested‑Loop Join : When the join column on the inner table has an index, MySQL can perform an index lookup for each driving‑row value, eliminating the need for a full scan or join buffer. This is similar to single‑table index optimization.

Optimization Steps

Initial multi‑table query:

select *
from t1 join t2 on t1.b = t2.b
where t1.c in (6,12,18,24,30)
  and t2.c in (6,12,18,24,30);

Explain shows both tables scanned ( type: ALL ). By replacing t1.c with the indexed column t1.a , the plan for t1 changes to type: range using idx_a , reducing estimated rows from 1 000 to 5.

Further, swapping the join condition to use the indexed column on t2 ( t2.a ) changes t2 from a full scan to an index range scan, still using Block Nested‑Loop but with far fewer rows to compare.

When both join and filter columns are indexed (adding idx_c on t2.c ), the optimizer may still choose Block Nested‑Loop if it estimates lower cost, but the overall cost is reduced.

These examples illustrate that the best algorithm depends on data distribution, index availability, and join buffer size; the optimizer selects the cheapest plan.

Conclusion

Understanding MySQL’s join algorithms and how indexes affect them enables developers to transform slow multi‑table joins into fast, resource‑efficient queries. Readers are encouraged to experiment with their own schemas, comment with questions, and share the article.