Join Algorithm Selections

Differentiate between Nested Loop, Hash, and Merge join performance profiles.

In this lesson, you will learn how the MySQL/MariaDB query optimizer chooses between Nested Loop, Hash, and Merge join strategies to execute your SQL queries efficiently.

When you execute a query involving multiple tables, the optimizer must decide how to pair the data together. While standard MySQL (InnoDB) relies heavily on Nested Loop Joins, understanding these three fundamental strategies explains why performance shifts based on your indexing strategy.

1. Nested Loop Join (NLJ)

This is the "workhorse" of MySQL. For every row in the outer table, the engine scans the inner table to find matches.

Performance Profile: It is extremely fast if the join column on the inner table is indexed. If there is no index, the engine must perform a full table scan for every single row of the outer table, leading to exponential performance degradation.
Ideal for: Small-to-medium datasets where indices are present.

2. Hash Join

Introduced more broadly in MySQL 8.0.18+, this algorithm builds a hash table in memory for the smaller table. It then scans the larger table once, probing the hash table to find matches instantly.

Performance Profile: It is often faster than nested loops for large, unsorted datasets because it avoids repeated index lookups. However, it is memory-intensive; if the hash table exceeds join_buffer_size, it may spill to disk.
Ideal for: Large-scale equi-joins (=) where no useful index exists.

3. Merge (Sort-Merge) Join

Though less common as a direct choice in standard MySQL compared to Hash Joins, it functions by sorting both input tables on the join key and then merging the two streams.

Performance Profile: It excels when data is already sorted or when you have high-volume joins that don't fit into a hash table. The downside is the heavy I/O cost of the initial sort phase.
Ideal for: Large join operations where sorted order is beneficial for subsequent operations like GROUP BY or ORDER BY.

-- The optimizer chooses the algorithm based on available indexes
EXPLAIN SELECT * FROM orders o 
JOIN customers c ON o.customer_id = c.id;

If you look at the Extra column in your EXPLAIN output, you will see Using join buffer (hash join) or simply reliance on index lookups for Nested Loops.

Key Takeaway: Nested Loop Joins thrive on indexed columns, Hash Joins dominate large unsorted joins by trading memory for speed, and Merge Joins are your go-to for sorted, massive datasets.