Every JOIN in a PostgreSQL query gets executed as one of exactly three physical operations, and the planner picks which one without asking you. Get it right and the query comes back in milliseconds. Get it wrong and the same logical join burns minutes of CPU or spills batch after batch of hash table to temp files under pgsql_tmp. This post walks through how Nested Loop, Hash Join, and Merge Join actually work, with EXPLAIN output from a real dataset you can build yourself, so the next time you read a plan you know why the planner did what it did instead of just trusting it.
The Setup
Two tables: customers, around 200,000 rows, and orders, around 9 million rows, linked by orders.customer_id. Small dimension table, large fact table - a shape that shows up constantly, and exactly where join algorithm choice matters most.
CREATE TABLE customers (
customer_id BIGINT PRIMARY KEY,
email TEXT NOT NULL,
signup_date DATE NOT NULL
);
CREATE TABLE orders (
order_id BIGINT PRIMARY KEY,
customer_id BIGINT NOT NULL REFERENCES customers(customer_id),
order_date DATE NOT NULL,
amount NUMERIC(10,2) NOT NULL
);
CREATE INDEX idx_customers_signup_date ON customers (signup_date);
customers.customer_id gets a B-tree automatically from the primary key. orders.customer_id does not - PostgreSQL never indexes a foreign key column for you just because a REFERENCES clause points at one. That gap is deliberate here, because it changes which algorithm the planner reaches for later in this post.
One more thing before running anything: pin down parallel workers so the plans below stay simple.
SET max_parallel_workers_per_gather = 0;
Parallelism doesn't change which join algorithm gets chosen, only how many worker processes execute it. Turning it off keeps Gather and Parallel Hash nodes out of the plans so the shapes are easier to read.
Nested Loop: The Only One That Isn't Picky
The idea is about as simple as query execution gets: for every row on the outer side, scan the inner side and keep whatever matches. No sort, no hash table, just a loop inside a loop. Run that against two full tables and it's O(N × M) - quadratic, and it falls over fast at any real size. Put an index on the inner side's join column and each outer row turns into a cheap index probe instead of a full inner scan, which is the difference between Nested Loop being the worst option and the best one.
Nested Loop is also the only algorithm PostgreSQL has for a join condition that isn't equality. Hash Join needs = to build a lookup table; Merge Join needs a consistent sort order to walk in lockstep. Neither can evaluate <, >, BETWEEN, or a range overlap. Nested Loop can, because it just checks the condition row by row.
Here's a query that needs one: a data-integrity check for orders recorded before the customer's account even existed.
EXPLAIN
SELECT o.order_id, c.customer_id
FROM orders o
JOIN customers c ON c.signup_date > o.order_date;
Nested Loop (cost=0.29..7620552000.29 rows=600000000000 width=16)
-> Seq Scan on orders o (cost=0.00..162000.00 rows=9000000 width=8)
-> Index Scan using idx_customers_signup_date on customers c (cost=0.29..846.71 rows=66667 width=8)
Index Cond: (signup_date > o.order_date)
Note the plain EXPLAIN, not EXPLAIN ANALYZE - actually running this means materializing an estimated 600 billion rows, and nobody has that kind of afternoon. The planner still did the right thing with what it was given: it used the only algorithm available for > and picked the cheapest access path for the inner side, an index scan on signup_date. What it can't fix is the query itself. Every order gets compared against roughly half the customer table on average, because on any given day about half of all customers signed up later than that day. The fix here isn't a different join algorithm, it's a tighter query - a NOT EXISTS correlated subquery, or bounding the date range - that stops asking the planner to compare every order to every later signup in the first place. The PostgreSQL join strategies reference has more on reading a Nested Loop's row estimate against what you'd expect from the data, which is usually the fastest way to catch a runaway join like this one before it ships.
Hash Join: Build Once, Probe Many
Hash Join runs in two phases. First it scans one side - the "build" side, normally whichever input is smaller - and loads it into an in-memory hash table keyed on the join column. Then it scans the other side, the "probe" side, and looks each row up in that hash table. With a reasonable hash function that's O(N + M) time, a big improvement over Nested Loop's O(N × M) when neither side has a useful index. Memory cost is proportional to the build side, which is exactly why the planner tries to pick the smaller one.
EXPLAIN ANALYZE
SELECT COUNT(*)
FROM orders o
JOIN customers c ON c.customer_id = o.customer_id;
Aggregate (cost=282500.00..282500.01 rows=1 width=8) (actual time=1180.470..1180.471 rows=1 loops=1)
-> Hash Join (cost=5200.00..282500.00 rows=9000000 width=0) (actual time=16.100..1180.450 rows=9000000 loops=1)
Hash Cond: (o.customer_id = c.customer_id)
-> Seq Scan on orders o (cost=0.00..162000.00 rows=9000000 width=8) (actual time=0.015..380.220 rows=9000000 loops=1)
-> Hash (cost=3200.00..3200.00 rows=200000 width=8) (actual time=15.980..15.981 rows=200000 loops=1)
Buckets: 262144 Batches: 1 Memory Usage: 7123kB
-> Seq Scan on customers c (cost=0.00..3200.00 rows=200000 width=8) (actual time=0.010..15.203 rows=200000 loops=1)
Planning Time: 0.298 ms
Execution Time: 1180.520 ms
customers is the build side, loaded into a 7 MB hash table in a single batch. orders is the probe side. Only an equality condition works here - Hash Cond is always = - and it doesn't matter which table you write first in the FROM clause. SQL describes the result, not the execution order, so FROM customers c JOIN orders o ON ... produces the identical plan; the planner is free to pick build and probe sides on its own regardless of how the query is written.
The build side has to fit in memory or the hash table gets partitioned into batches that spill to temp files, one batch processed at a time. The budget is work_mem multiplied by hash_mem_multiplier, which defaults to 2.0 as of PostgreSQL 15 and is unchanged in 18. With the default work_mem of 4MB, that's roughly 8MB before spilling starts - our 7MB hash table above just clears it. Watch Batches in the plan output: Batches: 1 means everything stayed in memory, anything higher means temp-file I/O got added to the join.
Merge Join: Free If Sorted, Expensive If Not
Merge Join needs both inputs sorted on the join key, then walks the two sorted streams together, advancing whichever side is behind - the same core idea as the merge step in merge sort. If both sides already arrive in order, typically because a B-tree index scan produces that order for free, the merge itself is O(N + M) with almost no extra memory. If either side needs sorting first, that sort costs O(N log N) and can be the most expensive part of the whole query.
customers.customer_id is already sorted, courtesy of its primary key index. orders.customer_id has no index, so it has nothing to sort by for free. To see the algorithm anyway, force it by turning off Hash Join for the session:
SET enable_hashjoin = off;
EXPLAIN ANALYZE
SELECT o.order_id, c.email
FROM orders o
JOIN customers c ON c.customer_id = o.customer_id;
Merge Join (cost=9832.58..1650000.00 rows=9000000 width=24) (actual time=25.360..1980.090 rows=9000000 loops=1)
Merge Cond: (c.customer_id = o.customer_id)
-> Index Scan using customers_pkey on customers c (cost=0.29..9832.29 rows=200000 width=16) (actual time=0.020..25.331 rows=200000 loops=1)
-> Materialize (cost=1583200.00..1628200.00 rows=9000000 width=16) (actual time=1005.230..1855.204 rows=9000000 loops=1)
-> Sort (cost=1583200.00..1605700.00 rows=9000000 width=16) (actual time=1005.220..1520.900 rows=9000000 loops=1)
Sort Key: o.customer_id
Sort Method: external merge Disk: 245000kB
-> Seq Scan on orders o (cost=0.00..162000.00 rows=9000000 width=16) (actual time=0.012..320.556 rows=9000000 loops=1)
Planning Time: 0.245 ms
Execution Time: 1980.112 ms
RESET enable_hashjoin;
customers streams straight off its primary key index, already in order. orders has to be sorted from scratch, and 9 million rows of sort key doesn't fit in the default 4MB work_mem, so it spills - the Sort Method: external merge Disk: 245000kB line is PostgreSQL telling you it wrote the intermediate sort to disk. That sort is also why this plan takes longer than the Hash Join above: 1.98 seconds against 1.18. This is the normal case, not an edge case. Merge Join wins when the sort is nearly free - an index already provides the order, or the query needed that ORDER BY anyway - and loses when it has to build the order from nothing. That's exactly why the planner defaults to Hash Join here once you let it choose freely again.
How the Planner Actually Decides
None of this is rule-based. PostgreSQL estimates the total cost of each candidate plan - Nested Loop with this index, Hash Join with that build side, Merge Join with or without a sort - and picks the cheapest one it can find. Those estimates come from table and column statistics that ANALYZE collects: row counts, most-common values, distinct-value counts, correlation between physical row order and column values. Autovacuum keeps that current in the background, which is why a table that gets vacuumed and analyzed regularly tends to get better plans than one that doesn't.
This is also where plans go wrong. If statistics are stale - a table quadrupled in size since the last ANALYZE, or a bulk load skewed the value distribution - the cost estimates are wrong, and the planner can confidently pick the wrong algorithm: a Nested Loop that turns quadratic because the planner thought the outer side was small, or a Hash Join that spills to disk because it underestimated the build side. Comparing the rows estimate in EXPLAIN against the rows actual in EXPLAIN ANALYZE is the fastest way to spot this - a large gap there is a statistics problem before it's anything else.
The enable_nestloop, enable_hashjoin, and enable_mergejoin session settings (we used the second one above) are useful for exactly this kind of diagnosis - confirm a hypothesis, then reset them - but they're not a fix. Setting one off doesn't remove the algorithm; it marks those plans as a last resort, and the planner still falls back to one when no alternative exists. Leave one off in production and the plan you get today is wrong for whatever the data looks like in six months. The durable fixes are the boring ones: add the index the inner side needs, run ANALYZE so estimates track reality, or raise work_mem for the session doing the heavy lifting.
Watching for the Drift
A join algorithm rarely breaks all at once. It's usually a slow drift - orders grows past the point where a Nested Loop stays cheap, a nightly batch job that used to insert thousands of rows starts inserting millions, autovacuum falls behind on a busy table and statistics go stale for a week before anyone notices. None of that shows up as a single alert. It shows up as a query that was fine last month and is timing out now, with nobody sure which of a dozen recent changes is the cause.
That's the gap between running EXPLAIN ANALYZE once and actually watching plan behavior over time. NeverBlink tracks query plans and execution stats across PostgreSQL, Elasticsearch, OpenSearch, and ClickHouse continuously, and when a join flips from Hash to Nested Loop or a sort starts spilling that never used to, it surfaces the specific statistics or index gap behind the change - as a recommendation to review, not a plan it silently rewrites for you.
The three algorithms aren't competing for the same job. Nested Loop is unavoidable for inequalities and cheap when the inner side is small and indexed. Hash Join is the default workhorse for equality joins with no useful sort order lying around. Merge Join wins the moment sorted input is nearly free and loses badly the moment it isn't. Reading the plan the planner actually chose, and checking its row estimates against what came back, tells you which of those situations you're in - which matters more than memorizing which algorithm is supposed to be fastest.
