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.

Practice

1. Which join algorithm in PostgreSQL is best suited for small tables or when one table is very small compared to the other?

easy

A. Index Join

B. Hash Join

C. Nested Loop Join

D. Merge Join

Solution

1. Step 1: Understand Nested Loop Join usage

   Nested Loop Join works by scanning one table and for each row scanning the other table. It is efficient when one table is small.

2. Step 2: Compare with other joins

   Hash Join is better for large unsorted tables, Merge Join requires sorted inputs. Nested Loop is simplest and best for small tables.

3. Final Answer:

   Nested Loop Join -> Option C

4. Quick Check:

   Small table + Nested Loop Join = best [OK]

Hint: Small table joins usually use Nested Loop Join [OK]

Common Mistakes:

• Confusing Hash Join as best for small tables
• Thinking Merge Join works well without sorted data
• Assuming Index Join is a separate join algorithm

2. Which of the following is the correct syntax to hint PostgreSQL to use a Hash Join in a query?

easy

A. SELECT /*+ HashJoin */ * FROM table1 JOIN table2 ON table1.id = table2.id;

B. SET enable_hashjoin = on; SELECT * FROM table1 JOIN table2 ON table1.id = table2.id;

C. SELECT * FROM table1 HASH JOIN table2 ON table1.id = table2.id;

D. SELECT * FROM table1 JOIN table2 USING HASH(id);

Solution

1. Step 1: Understand PostgreSQL join hints

   PostgreSQL does not support inline join hints like /*+ HashJoin */ or HASH JOIN syntax.

2. Step 2: Use configuration to enable Hash Join

   We can enable or disable join types using SET commands, e.g., SET enable_hashjoin = on; before the query.

3. Final Answer:

   SET enable_hashjoin = on; SELECT ... -> Option B

4. Quick Check:

   PostgreSQL uses SET to enable join types [OK]

Hint: Use SET enable_hashjoin to control hash join usage [OK]

Common Mistakes:

• Using Oracle-style hints like /*+ HashJoin */
• Trying to write HASH JOIN in SQL syntax
• Using USING HASH() which is invalid

3. Given two tables employees(emp_id, dept_id) and departments(dept_id, name), what join algorithm will PostgreSQL most likely use for this query?

EXPLAIN SELECT * FROM employees JOIN departments ON employees.dept_id = departments.dept_id;

Assuming both tables are large and departments.dept_id is indexed.

medium

A. Nested Loop Join

B. Merge Join

C. Cross Join

D. Hash Join

Solution

1. Step 1: Analyze table sizes and indexes

   Both tables are large, so Nested Loop is inefficient. Departments has an index on dept_id.

2. Step 2: Determine join algorithm choice

   Hash Join is preferred for large tables without sorted data. Merge Join requires sorted inputs, which is not guaranteed here.

3. Final Answer:

   Hash Join -> Option D

4. Quick Check:

   Large tables + no sorted data = Hash Join [OK]

Hint: Large tables with join keys use Hash Join by default [OK]

Common Mistakes:

• Assuming index forces Nested Loop Join
• Thinking Merge Join is automatic without sorting
• Confusing Cross Join with inner join

4. You wrote this query:

SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id;

But PostgreSQL is using a Nested Loop Join causing slow performance. Which fix will most likely improve performance by enabling a better join algorithm?

medium

A. Disable Nested Loop Join with SET enable_nestloop = off;

B. Create an index on orders.customer_id

C. Rewrite query using LEFT JOIN instead of JOIN

D. Add ORDER BY on customer_id in the query

Solution

1. Step 1: Identify why Nested Loop is slow

   Nested Loop is slow on large tables without indexes or when better joins exist but are not chosen.

2. Step 2: Force PostgreSQL to avoid Nested Loop

   Disabling Nested Loop join with SET enable_nestloop = off forces PostgreSQL to pick Hash or Merge Join, improving performance.

3. Final Answer:

   Disable Nested Loop Join with SET enable_nestloop = off; -> Option A

4. Quick Check:

   Disable Nested Loop to force better join [OK]

Hint: Disable nested loop join to force hash or merge join [OK]

Common Mistakes:

• Assuming adding index always fixes join choice
• Changing JOIN type without understanding join algorithms
• Adding ORDER BY does not affect join algorithm

5. You have two large sorted tables sales(date, product_id, amount) and products(product_id, name). You want to join them on product_id efficiently. Which join algorithm should you prefer and why?

hard

A. Merge Join, because it exploits sorted order for fast merging

B. Hash Join, because it hashes the smaller table for fast lookup

C. Nested Loop Join, because it works well with sorted data

D. Cross Join, because it combines all rows

Solution

1. Step 1: Identify join algorithm suited for sorted tables

   Merge Join is designed to efficiently join two sorted inputs by merging them in order.

2. Step 2: Compare with other join algorithms

   Nested Loop is inefficient for large tables, Hash Join ignores sorting, Cross Join produces Cartesian product.

3. Final Answer:

   Merge Join, because it exploits sorted order for fast merging -> Option A

4. Quick Check:

   Sorted tables + Merge Join = efficient join [OK]

Hint: Use Merge Join when both tables are sorted on join keys [OK]

Common Mistakes:

• Choosing Nested Loop for large sorted tables
• Ignoring sorting and picking Hash Join
• Confusing Cross Join with inner join