Join algorithms (nested loop, hash, merge) in PostgreSQL - Step-by-Step Execution

Concept Flow - Join algorithms (nested loop, hash, merge)

Start Join Operation

↓

Choose Join Algorithm

↓

Nested Loop

↓

Scan Outer

↓

Scan Inner

↓

Output Matches

↓

End

The join operation starts by choosing one of three algorithms: nested loop, hash join, or merge join. Each algorithm follows its own steps to find matching rows and produce the joined result.

Execution Sample

PostgreSQL

SELECT * FROM A JOIN B ON A.id = B.id;
-- Using Nested Loop Join
-- Outer table: A
-- Inner table: B
-- For each row in A, scan B for matches

This query joins tables A and B on the id column using a nested loop join, scanning B for each row in A.

Execution Table

Step	Outer Row (A.id)	Inner Scan Position (B.id)	Match Found?	Action	Output Rows
1	A.id=1	B.id=1	Yes	Output row (1,1)	1
2	A.id=1	B.id=2	No	Continue scanning B	1
3	A.id=2	B.id=1	No	Continue scanning B	1
4	A.id=2	B.id=2	Yes	Output row (2,2)	2
5	A.id=3	B.id=1	No	Continue scanning B	2
6	A.id=3	B.id=2	No	Continue scanning B	2
7	A.id=3	B.id=3	Yes	Output row (3,3)	3
8	-	-	-	No more outer rows	3

💡 All outer rows scanned; join complete with 3 matching output rows.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	Final
Outer Row (A.id)	None	1	2	3	End
Inner Scan Position (B.id)	None	1-2	1-2	1-3	End
Output Rows Count	0	1	2	3	3

Key Moments - 3 Insights

Why does the inner scan restart for each outer row in nested loop join?

Because nested loop join scans the entire inner table for each outer row to find matches, as shown in execution_table rows 1-7 where inner scan position resets for each outer row.

How does hash join avoid scanning the inner table multiple times?

Hash join builds a hash table from the inner table once, then probes it for each outer row, avoiding repeated scans. This differs from nested loop join's repeated scanning.

Why must both tables be sorted in merge join?

Merge join requires both tables sorted on join keys to efficiently merge rows by advancing pointers, unlike nested loop or hash join.

Visual Quiz - 3 Questions

Look at the execution_table, what is the Output Rows count after step 4?

A 1

B 2

C 3

D 0

💡 Hint

Check the Output Rows column at step 4 in the execution_table.

At which step does the nested loop join finish scanning all outer rows?

A Step 8

B Step 5

C Step 7

D Step 3

💡 Hint

Look for the step where the action says 'No more outer rows' in the execution_table.

If the inner table B had no matching rows, how would the Output Rows column change in the execution_table?

A It would increase by one each step

B It would show random values

C It would remain zero throughout

D It would be negative

💡 Hint

Refer to the Output Rows column and consider what happens when no matches are found.

Concept Snapshot

Join algorithms combine rows from two tables based on a condition.
Nested Loop: For each row in outer table, scan inner table.
Hash Join: Build hash on inner table, probe with outer rows.
Merge Join: Sort both tables, merge by advancing pointers.
Choose algorithm based on data size and indexes for best performance.

Full Transcript

This visual execution shows how join algorithms work in PostgreSQL. The join starts by choosing an algorithm: nested loop, hash join, or merge join. Nested loop join scans the inner table for each outer row, outputting matches. The execution table traces each step scanning rows from tables A and B, showing when matches are found and output rows increase. Variable tracker shows how outer row, inner scan position, and output count change. Key moments clarify why inner scans restart in nested loops, how hash join avoids repeated scans, and why merge join needs sorted tables. The quiz tests understanding of output counts and termination steps. The snapshot summarizes join algorithms and their behavior for quick reference.