In this lesson, you will learn how the PostgreSQL query optimizer selects between Nested Loop, Hash, and Merge joins based on data distribution and available access paths.
Nested Loop Join: The Iterative Approach
The Nested Loop is the simplest algorithm: for every row in the outer table, the database scans the inner table to find matches. This is highly efficient when the outer set is very small and the inner set has a high-quality index (like a B-tree). If you are joining a user (1 row) to orders (1,000,000 rows) via an indexed user_id, a Nested Loop is unbeatable because it performs a simple index lookup. However, if both tables are large and unindexed, performance collapses into a quadratic nightmare.
Hash Join: The Memory-Heavy Workhorse
When joining two large, unsorted datasets, PostgreSQL often chooses a Hash Join. The optimizer builds an in-memory hash table for the smaller table (the "build" side) and then probes it while scanning the larger table (the "probe" side).
-- Hash Join is often preferred for large, unindexed joins
SELECT * FROM orders o JOIN line_items l ON o.id = l.order_id;
This is ideal when data distribution is uniform and you have enough work_mem to hold the hash table. If the data exceeds work_mem, PostgreSQL will spill to disk (using temporary files), which significantly degrades performance.
Merge Join: The Ordered Alternative
A Merge Join requires both inputs to be sorted by the join key. If the inputs are already indexed or sorted by a previous operation, the algorithm simply "merges" the two streams like a zipper. It is extremely fast for large, sorted datasets because it performs a single sequential scan of each side.
Choosing the Strategy
The cost model weighs these factors:
- Nested Loop: Best for small inputs or highly selective index lookups.
- Hash Join: Excellent for large, unsorted data where memory is sufficient.
- Merge Join: The winner when data is already sorted (e.g., via a B-Tree index or
ORDER BY) or when the join operator is an inequality (like<or>), which Hash Joins cannot handle.
Key Takeaway: The optimizer chooses the join strategy by estimating the cost of scanning, sorting, and memory availability; ensure your join columns are indexed to enable Merge Joins or efficient Nested Loops.