Join algorithms (nested loop, hash, merge) in PostgreSQL - Time & Space Complexity

Time Complexity: Join algorithms (nested loop, hash, merge)

O(n x m) for nested loop, O(n + m) for hash and merge joins

Understanding Time Complexity

When databases combine tables using joins, the way they do it affects how long it takes. We want to understand how the time needed grows as the tables get bigger.

How does the choice of join method change the work done as data grows?

Scenario Under Consideration

Analyze the time complexity of these three join methods in PostgreSQL.

-- Nested Loop Join
SELECT * FROM tableA a
JOIN tableB b ON a.id = b.a_id;

-- Hash Join
SELECT * FROM tableA a
JOIN tableB b ON a.id = b.a_id;

-- Merge Join
SELECT * FROM tableA a
JOIN tableB b ON a.id = b.a_id
ORDER BY a.id, b.a_id;
    

These queries join two tables on matching IDs using different join algorithms.

Identify Repeating Operations

Each join method repeats operations differently:

• Nested Loop Join: For each row in tableA, it scans all rows in tableB.
• Hash Join: Builds a hash table for one table, then looks up matches for each row in the other.
• Merge Join: Both tables are sorted, then scanned once together to find matches.
• Primary operation: Comparing rows between tables to find matches.
• How many times: Nested loop does this many times (rows in A x rows in B), hash join once per row after hashing, merge join once per row in sorted order.

How Execution Grows With Input

Imagine tableA and tableB grow in size:

Input Size (rows in each table)	Nested Loop Ops	Hash Join Ops	Merge Join Ops
10	100 (10x10)	~20 (build + probe)	~20 (sorted scan)
100	10,000 (100x100)	~200 (build + probe)	~200 (sorted scan)
1000	1,000,000 (1000x1000)	~2000 (build + probe)	~2000 (sorted scan)

Nested loop grows very fast as tables get bigger, while hash and merge join grow more slowly, roughly proportional to the total rows.

Final Time Complexity

Time Complexity: O(n x m) for nested loop, O(n + m) for hash and merge joins

This means nested loop work grows by multiplying table sizes, but hash and merge join work grows by adding sizes, making them faster for big tables.

Common Mistake

[X] Wrong: "All join methods take the same time no matter table size."

[OK] Correct: Nested loop joins check every pair, so time grows fast with size. Hash and merge join use smarter ways to avoid checking all pairs, so they scale better.

Interview Connect

Understanding how join methods scale helps you explain database performance clearly. This skill shows you know how data size affects query speed, a key part of working with databases.

Self-Check

"What if one table is much smaller than the other? How would that affect the time complexity of each join method?"