query-execution • Advanced

SQL Joins & Execution Algorithms (Nested Loop, Hash, Merge)

The query optimizer selects between three physical join strategies: Nested Loop Join (small/indexed), Hash Join (large unsorted equi-joins), and Merge Join (pre-sorted streams).

Intuitive Mental Model

Finding Pairs at a Party: Nested Loop is asking every guest one-by-one; Hash Join is putting names into a hash bucket first then checking matches; Merge Join is lining up both groups alphabetically and stepping together.

SQL DDL / DML QueryPostgreSQL / MySQL

-- 1. Nested Loop Join: Ideal when outer set is small and inner table has an index.
-- Complexity: O(N * log M)

-- 2. Hash Join: Builds in-memory hash table of smaller table, probes with larger.
-- Complexity: O(N + M)

-- 3. Merge Join: Steps through two sorted inputs in lockstep.
-- Complexity: O(N + M) if pre-sorted, or O(N log N + M log M) with sort step.

Key Architectural Takeaways

•Nested Loop Join is preferred when joining a small dataset with a table that has an index on the join key.
•Hash Join excels at large ad-hoc joins without indexes (build phase creates hash table in work_mem, probe phase scans matching rows).
•Merge Join is fastest when both inputs are already sorted by indexes or ORDER BY clauses.

Common Production Mistake

Joining on columns with mismatched data types (e.g. VARCHAR id joining INT id), preventing index usage and forcing slow Nested Loops.