Lesson 5.9 · Reading time: ~9 min

SQL join algorithms are the methods a database uses to execute a join: nested loop join, hash join and merge join. In this lesson you'll learn how each algorithm works, when the query planner chooses it, which databases support which algorithms, and how to see the chosen one with EXPLAIN.

SQL Join Algorithms: How the Database Executes Joins

In the previous lessons you wrote joins and focused on which rows they return. The same join can be executed in very different ways, and on large tables the difference between them is seconds versus hours. You don't choose the algorithm in SQL; the query planner does. But knowing how the algorithms work explains why indexes on join columns matter and how to read execution plans.

Nested Loop Join

How It Works

The database takes one table as the outer (driving) table and, for each of its rows, searches the inner table for matches: two nested loops.

for each row R1 in outer_table:
    for each row R2 in inner_table:
        if R1.key = R2.key:
            output(R1, R2)

Without an index, the inner table is scanned completely for every outer row: N × M comparisons. With an index on the inner table's join column, each search becomes a fast index lookup. This index nested loop join is one of the most efficient plans when the outer side is small.

When the Planner Uses It

• The outer table, or the outer side after filtering, is small.
• The inner table has an index on the join column.
• The join condition is not an equality (<, >, BETWEEN): the classic hash and merge joins work only with equality.

Hash Join

How It Works

A hash join has two phases:

1. Build: the database reads the smaller input and builds an in-memory hash table keyed by the join column.
2. Probe: it reads the larger input and looks up each row's key in the hash table.

-- build
for each row R1 in smaller_input:
    hash_table[hash(R1.key)].append(R1)

-- probe
for each row R2 in larger_input:
    for each R1 in hash_table[hash(R2.key)]:
        if R1.key = R2.key:
            output(R1, R2)

Each input is read once, so the cost is about N + M: much better than a nested loop without indexes.

When the Planner Uses It

• Two large inputs joined by equality.
• No useful index on the join columns.
• Enough memory for the hash table (work_mem in PostgreSQL, join_buffer_size in MySQL).

Merge Join

How It Works

A merge join (sort-merge join) needs both inputs sorted by the join column. It then walks through both sorted lists at the same time, like the merge step of merge sort:

sort outer by key   -- skipped if read through an ordered index
sort inner by key   -- skipped if read through an ordered index

while neither input is exhausted:
    if outer.key = inner.key: output matches, advance
    elif outer.key < inner.key: advance outer
    else: advance inner

If both inputs can be read in order through indexes, the sort is free and the merge is very fast.

When the Planner Uses It

• Large inputs joined by equality.
• Both inputs are already sorted or can be read through ordered indexes.
• The query sorts by the join column anyway (ORDER BY, GROUP BY, DISTINCT).

Which Database Uses Which Algorithm

In MySQL, the hash join is also used for joins without an equality condition and for Cartesian products, so the "equality only" rule applies to the classic algorithm rather than to every implementation.

Seeing the Algorithm in EXPLAIN

EXPLAIN shows the plan the database chose; EXPLAIN ANALYZE (MySQL 8.0.18+, PostgreSQL) also runs the query and reports the real time of each step:

EXPLAIN ANALYZE
SELECT a.first_name, a.last_name, f.title
FROM actor AS a
INNER JOIN film_actor AS fa ON fa.actor_id = a.actor_id
INNER JOIN film AS f ON f.film_id = fa.film_id;

Result: the execution plan as a tree. In MySQL, look for Nested loop inner join or Inner hash join; in PostgreSQL, for Nested Loop, Hash Join or Merge Join.

Here MySQL uses nested loops: film_actor and film have indexes on the join columns, so each lookup is an index search.

How to Help the Planner

• Index foreign key columns that are used in joins: this enables index nested loops.
• Filter early: a selective WHERE makes the outer side small.
• Keep statistics up to date (ANALYZE TABLE in MySQL, ANALYZE in PostgreSQL): the planner chooses by estimated row counts.
• Check memory settings if a hash join spills to disk on large data.

Key Takeaways:

• Nested loop join searches the inner table for each outer row; fast with a small outer side and an index, and works with any condition.
• Hash join builds a hash table from the smaller input and probes it; efficient for large unindexed equality joins, but uses memory.
• Merge join merges two sorted inputs; ideal when data is already ordered by an index.
• MySQL and MariaDB have no merge join; PostgreSQL, SQL Server and Oracle have all three.
• You influence the choice with indexes, filters, statistics and memory settings, and check it with EXPLAIN ANALYZE.

Frequently Asked Questions

What is the difference between a nested loop join and a hash join?

A nested loop join looks up matches in the inner table for every outer row, which is fast when there is an index and the outer side is small. A hash join reads each input once and matches rows through an in-memory hash table, which is faster for two large inputs without useful indexes.

Does MySQL support hash join?

Yes, since MySQL 8.0.18. Since 8.0.20 it replaces the block nested loop algorithm for joins that can't use an index. MySQL doesn't have a merge join.

Can I force a specific join algorithm?

Not in standard SQL. Some databases offer hints: MySQL optimizer hints such as HASH_JOIN / NO_HASH_JOIN (version-dependent), SQL Server OPTION (HASH JOIN), PostgreSQL settings like enable_hashjoin. Use them for diagnosis; for production queries, better indexes and statistics are usually the right fix.