SQL · Advanced

Hash join vs nested loop vs merge join

23 min read

Why it matters

Hash join vs nested loop vs merge join is the choice the database makes every time your query has a JOIN, and it is often the single biggest factor in how long the query takes. The same join on the same data ran in 100 ms with a hash join and 341 ms with a nested loop in this lesson, only because the planner misjudged one row count. You do not pick the algorithm in SQL, but you cause the planner's choice through your filters, indexes and statistics, and you need to recognise a bad choice in a plan. SQL appears in 88% of Data Analyst and 80% of Data Engineer job descriptions we studied, and "what join algorithms does a database use and when is each chosen?" is a standard data engineering and backend interview question.

You will force each algorithm on the same Olist join and time it, watch a hash join spill to disk when memory is short, see where a nested loop wins by a factor of 12, and trigger a slow nested loop with a single function call in the WHERE.

The concept

Three ways to join

Every join pairs rows from two inputs. Databases have three basic algorithms:

Nested loop: for each row of the outer input, find the matching rows of the inner input.

text

for each order in orders:            -- outer
    look up its items in order_items -- inner, ideally through an index

Cost grows with outer rows x cost of one inner lookup. With an index on the inner side, each lookup is a few page reads, so a nested loop is the fastest choice when the outer side is small. With many outer rows it does many thousands of index lookups. It is also the only algorithm that handles any join condition (<, BETWEEN, LIKE).

Hash join: read the smaller input once and build a hash table on the join key (the build side), then stream the other input through it and look up each row (the probe side). One pass over each input, so it is the workhorse for large, unsorted, equality joins (= only). The hash table must fit in memory (work_mem in PostgreSQL); if it does not, it is split into batches written to disk, which is slower.

Merge join: read both inputs sorted by the join key and walk them together like a zip. Ideal when both sides are already sorted (an index on the key, or a previous sort); otherwise it pays for sorting first. Good for very large joins on sorted data and for range-friendly conditions.

	Nested loop	Hash join	Merge join
Best when	Outer side small, inner side indexed	Large inputs, no useful order	Both inputs already sorted on the key
Join conditions	Any	Equality only	Equality (and some ranges)
Memory	Little	Hash table of the build side	Little, unless it must sort
Startup	Instant first row	Must build the hash table first	Must sort unless pre-sorted
Failure mode	Millions of index lookups when the outer side is larger than estimated	Spills to disk when the build side does not fit	Expensive sorts

Estimates drive the choice

The planner picks the algorithm with the lowest estimated cost, and the cost depends on how many rows it expects from each side. If it expects 500 rows from the outer side, a nested loop with 500 index lookups looks cheap; if 96,000 rows actually arrive, it does 96,000 lookups. Most "the database chose a terrible join" incidents are row-estimate errors, caused by stale statistics, functions on columns, correlated filters, or complex expressions.

Join order

For three or more tables, the planner also chooses the order: which tables to join first. It considers many orders and ignores the order you wrote, so FROM a JOIN b JOIN c and FROM c JOIN b JOIN a normally produce the same plan (in PostgreSQL, up to join_collapse_limit, 8 tables by default). For a hash join it also picks which input to build the hash table from, usually the smaller one.

Skew

A hash join assumes keys are spread evenly. If one key value is extremely common (one giant customer, a default "unknown" ID, NULL-like placeholders), its bucket holds a huge share of rows. On a single machine this mainly costs memory; in distributed engines like Spark, one worker gets most of the work and the whole job waits for it. Spark covers distributed joins, broadcast joins and skew handling in depth.

Settings for experiments, not production

PostgreSQL lets you switch algorithms off for a session: SET enable_hashjoin = off, enable_mergejoin, enable_nestloop. They do not forbid an algorithm absolutely; they make it look very expensive. Use them to compare plans, never as a permanent fix. The permanent fixes are better statistics, sargable filters, indexes, and sometimes rewriting the query.

Worked example: orders and items on Olist

PostgreSQL 16 on the Olist e-commerce data (CC BY-NC-SA 4.0): 99,441 orders and 112,650 order items. Every output is from a real run; your times will differ. We turn off parallel query for the session so each plan runs in one process and is easier to read.

Set up the data

Download the two CSVs (link in Further reading), start psql in the same folder, and run:

sql

CREATE TABLE orders (
  order_id text PRIMARY KEY,
  customer_id text,
  order_status text,
  order_purchase_timestamp timestamp,
  order_approved_at timestamp,
  order_delivered_carrier_date timestamp,
  order_delivered_customer_date timestamp,
  order_estimated_delivery_date timestamp
);
\copy orders FROM 'olist_orders_dataset.csv' WITH (FORMAT csv, HEADER true)

CREATE TABLE order_items (
  order_id text,
  order_item_id int,
  product_id text,
  seller_id text,
  shipping_limit_date timestamp,
  price numeric(10,2),
  freight_value numeric(10,2),
  PRIMARY KEY (order_id, order_item_id)
);
\copy order_items FROM 'olist_order_items_dataset.csv' WITH (FORMAT csv, HEADER true)
VACUUM ANALYZE;

-- from the composite index lesson
CREATE INDEX order_items_seller_ship_idx
  ON order_items (seller_id, shipping_limit_date) INCLUDE (price);

Output

CREATE TABLE
COPY 99441
CREATE TABLE
COPY 112650
VACUUM
CREATE INDEX

Step 1: one join, three algorithms

Revenue by order status joins every order to its items. Let the planner choose, then take its favourite away twice:

sql

SET max_parallel_workers_per_gather = 0;  -- one process, so plans are easier to read

-- the planner's choice
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status;

-- forbid hash joins: the planner falls back to a merge join
SET enable_hashjoin = off;
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status;

-- forbid merge joins too: only nested loop is left
SET enable_mergejoin = off;
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status;

RESET enable_hashjoin;
RESET enable_mergejoin;

Output

SET
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 HashAggregate (actual time=135.638..135.647 rows=7 loops=1)
   Group Key: o.order_status
   Batches: 1  Memory Usage: 24kB
   ->  Hash Join (actual time=42.204..115.602 rows=112650 loops=1)
         Hash Cond: (i.order_id = o.order_id)
         ->  Seq Scan on order_items i (actual time=0.007..16.582 rows=112650 loops=1)
         ->  Hash (actual time=41.512..41.514 rows=99441 loops=1)
               Buckets: 131072  Batches: 2  Memory Usage: 4668kB
               ->  Seq Scan on orders o (actual time=0.011..12.770 rows=99441 loops=1)
 Planning Time: 0.836 ms
 Execution Time: 135.916 ms
(11 rows)
 
SET
                                                   QUERY PLAN                                                   
----------------------------------------------------------------------------------------------------------------
 HashAggregate (actual time=132.943..132.947 rows=7 loops=1)
   Group Key: o.order_status
   Batches: 1  Memory Usage: 24kB
   ->  Merge Join (actual time=0.014..110.700 rows=112650 loops=1)
         Merge Cond: (o.order_id = i.order_id)
         ->  Index Scan using orders_pkey on orders o (actual time=0.005..52.597 rows=99441 loops=1)
         ->  Index Scan using order_items_pkey on order_items i (actual time=0.003..17.695 rows=112650 loops=1)
 Planning Time: 0.232 ms
 Execution Time: 133.017 ms
(9 rows)
 
SET
                                                  QUERY PLAN                                                  
--------------------------------------------------------------------------------------------------------------
 HashAggregate (actual time=314.350..314.355 rows=7 loops=1)
   Group Key: o.order_status
   Batches: 1  Memory Usage: 24kB
   ->  Nested Loop (actual time=0.020..291.599 rows=112650 loops=1)
         ->  Seq Scan on orders o (actual time=0.005..7.391 rows=99441 loops=1)
         ->  Index Scan using order_items_pkey on order_items i (actual time=0.002..0.002 rows=1 loops=99441)
               Index Cond: (order_id = o.order_id)
 Planning Time: 0.135 ms
 Execution Time: 314.405 ms
(9 rows)
 
RESET
RESET

How to read each join:

Hash Join (136 ms). The child under Hash is the build side: all 99,441 orders went into a hash table. Then Seq Scan on order_items streamed 112,650 items through it. Notice the planner built from orders even though we wrote orders first in FROM: it picks the sides itself. Batches: 2 means the table did not fit in memory and was split; more on that in step 2.
Merge Join (133 ms). Both primary keys start with order_id, so two index scans deliver both inputs already sorted and the join walks them together with no sort step. Here it is as fast as the hash join, which is why it was the planner's second choice.
Nested Loop (314 ms). For each of the 99,441 orders, one index lookup into order_items (loops=99441). Each lookup is fast (0.002 ms), but 99,441 of them add up to more than twice the time.

For a join of two whole tables, nested loop is the wrong tool. The planner knew that, which is why it never chose it on its own.

Step 2: a hash join that does not fit in memory

The hash table above needed more than the default work_mem (4 MB), so it ran in 2 batches. Shrink and grow the budget:

sql

SET max_parallel_workers_per_gather = 0;

-- hash table size vs work_mem
SET work_mem = '256kB';
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status;

SET work_mem = '32MB';
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status;
RESET work_mem;

Output

SET
SET
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 HashAggregate (actual time=222.545..222.550 rows=7 loops=1)
   Group Key: o.order_status
   Batches: 1  Memory Usage: 24kB
   ->  Hash Join (actual time=94.397..202.661 rows=112650 loops=1)
         Hash Cond: (i.order_id = o.order_id)
         ->  Seq Scan on order_items i (actual time=0.012..17.279 rows=112650 loops=1)
         ->  Hash (actual time=93.962..93.963 rows=99441 loops=1)
               Buckets: 8192  Batches: 32  Memory Usage: 286kB
               ->  Seq Scan on orders o (actual time=0.010..21.203 rows=99441 loops=1)
 Planning Time: 1.057 ms
 Execution Time: 222.636 ms
(11 rows)
 
SET
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 HashAggregate (actual time=145.411..145.418 rows=7 loops=1)
   Group Key: o.order_status
   Batches: 1  Memory Usage: 24kB
   ->  Hash Join (actual time=70.054..125.900 rows=112650 loops=1)
         Hash Cond: (i.order_id = o.order_id)
         ->  Seq Scan on order_items i (actual time=0.004..8.749 rows=112650 loops=1)
         ->  Hash (actual time=69.464..69.466 rows=99441 loops=1)
               Buckets: 131072  Batches: 1  Memory Usage: 8306kB
               ->  Seq Scan on orders o (actual time=0.053..13.254 rows=99441 loops=1)
 Planning Time: 0.250 ms
 Execution Time: 146.874 ms
(11 rows)

With 256 kB the hash table was cut into 32 batches: each batch of orders, and the matching share of items, was written to temporary files and joined one at a time. The query took 223 ms instead of about 140. With 32 MB, the whole 8,306 kB table fit in 1 batch.

Batches above 1 on a Hash node is the sign of a spill. The fixes, in order: make the build side smaller (select fewer columns, filter earlier), raise work_mem for that session or job (SET work_mem = '64MB' before a heavy report), and only then raise it globally. work_mem applies per sort or hash node, per process, so a server-wide 1 GB with 100 connections running multi-join queries can run out of memory.

Step 3: where a nested loop wins

Now a small outer side: one seller's 297 items in the first quarter of 2018, with their order status.

sql

SET max_parallel_workers_per_gather = 0;

-- one seller's orders in Q1 2018: a small outer side
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items
FROM order_items AS i
JOIN orders AS o ON o.order_id = i.order_id
WHERE i.seller_id = '6560211a19b47992c3666cc44a7e94c0'
  AND i.shipping_limit_date >= '2018-01-01' AND i.shipping_limit_date < '2018-04-01'
GROUP BY o.order_status;

SET enable_nestloop = off;
EXPLAIN (ANALYZE, COSTS OFF)
SELECT o.order_status, count(*) AS items
FROM order_items AS i
JOIN orders AS o ON o.order_id = i.order_id
WHERE i.seller_id = '6560211a19b47992c3666cc44a7e94c0'
  AND i.shipping_limit_date >= '2018-01-01' AND i.shipping_limit_date < '2018-04-01'
GROUP BY o.order_status;
RESET enable_nestloop;

Output

SET
                                                                                                                          QUERY PLAN                                                                                                                           
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 GroupAggregate (actual time=3.515..3.571 rows=3 loops=1)
   Group Key: o.order_status
   ->  Sort (actual time=3.506..3.521 rows=297 loops=1)
         Sort Key: o.order_status
         Sort Method: quicksort  Memory: 31kB
         ->  Nested Loop (actual time=0.144..3.422 rows=297 loops=1)
               ->  Bitmap Heap Scan on order_items i (actual time=0.125..1.097 rows=297 loops=1)
                     Recheck Cond: ((seller_id = '6560211a19b47992c3666cc44a7e94c0'::text) AND (shipping_limit_date >= '2018-01-01 00:00:00'::timestamp without time zone) AND (shipping_limit_date < '2018-04-01 00:00:00'::timestamp without time zone))
                     Heap Blocks: exact=263
                     ->  Bitmap Index Scan on order_items_seller_ship_idx (actual time=0.085..0.086 rows=297 loops=1)
                           Index Cond: ((seller_id = '6560211a19b47992c3666cc44a7e94c0'::text) AND (shipping_limit_date >= '2018-01-01 00:00:00'::timestamp without time zone) AND (shipping_limit_date < '2018-04-01 00:00:00'::timestamp without time zone))
               ->  Index Scan using orders_pkey on orders o (actual time=0.007..0.007 rows=1 loops=297)
                     Index Cond: (order_id = i.order_id)
 Planning Time: 0.844 ms
 Execution Time: 3.643 ms
(15 rows)
 
SET
                                                                                                                          QUERY PLAN                                                                                                                           
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 GroupAggregate (actual time=44.468..44.506 rows=3 loops=1)
   Group Key: o.order_status
   ->  Sort (actual time=44.458..44.476 rows=297 loops=1)
         Sort Key: o.order_status
         Sort Method: quicksort  Memory: 31kB
         ->  Hash Join (actual time=39.807..44.417 rows=297 loops=1)
               Hash Cond: (i.order_id = o.order_id)
               ->  Bitmap Heap Scan on order_items i (actual time=0.132..0.494 rows=297 loops=1)
                     Recheck Cond: ((seller_id = '6560211a19b47992c3666cc44a7e94c0'::text) AND (shipping_limit_date >= '2018-01-01 00:00:00'::timestamp without time zone) AND (shipping_limit_date < '2018-04-01 00:00:00'::timestamp without time zone))
                     Heap Blocks: exact=263
                     ->  Bitmap Index Scan on order_items_seller_ship_idx (actual time=0.090..0.091 rows=297 loops=1)
                           Index Cond: ((seller_id = '6560211a19b47992c3666cc44a7e94c0'::text) AND (shipping_limit_date >= '2018-01-01 00:00:00'::timestamp without time zone) AND (shipping_limit_date < '2018-04-01 00:00:00'::timestamp without time zone))
               ->  Hash (actual time=39.057..39.058 rows=99441 loops=1)
                     Buckets: 131072  Batches: 2  Memory Usage: 4668kB
                     ->  Seq Scan on orders o (actual time=0.010..11.919 rows=99441 loops=1)
 Planning Time: 0.222 ms
 Execution Time: 44.562 ms
(17 rows)

The nested loop did 297 primary-key lookups into orders (loops=297) and finished in 3.6 ms. Forced into a hash join, the database had to read all 99,441 orders to build a hash table it then probed only 297 times: 44.6 ms, 12 times slower. Same tables, same join; the size of the outer side flips the right answer. This is the typical OLTP pattern (one customer, one seller, one order), and why foreign key columns used in joins usually deserve an index.

Step 4: a bad estimate picks the wrong algorithm

The same "all delivered orders" join, written two ways. The only difference is upper() around the status:

sql

SET max_parallel_workers_per_gather = 0;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT sum(i.price)
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
WHERE upper(o.order_status) = 'DELIVERED';

EXPLAIN (ANALYZE)
SELECT sum(i.price)
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
WHERE upper(o.order_status) = 'DELIVERED';

EXPLAIN (ANALYZE, COSTS OFF)
SELECT sum(i.price)
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
WHERE o.order_status = 'delivered';

Output

SET
                                                  QUERY PLAN                                                  
--------------------------------------------------------------------------------------------------------------
 Aggregate (actual time=340.977..340.979 rows=1 loops=1)
   ->  Nested Loop (actual time=0.060..329.074 rows=110197 loops=1)
         ->  Seq Scan on orders o (actual time=0.042..40.670 rows=96478 loops=1)
               Filter: (upper(order_status) = 'DELIVERED'::text)
               Rows Removed by Filter: 2963
         ->  Index Scan using order_items_pkey on order_items i (actual time=0.002..0.002 rows=1 loops=96478)
               Index Cond: (order_id = o.order_id)
 Planning Time: 1.117 ms
 Execution Time: 341.080 ms
(9 rows)
 
                                                                   QUERY PLAN                                                                    
-------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=6843.19..6843.20 rows=1 width=32) (actual time=351.846..351.848 rows=1 loops=1)
   ->  Nested Loop  (cost=0.42..6841.78 rows=563 width=6) (actual time=0.016..339.896 rows=110197 loops=1)
         ->  Seq Scan on orders o  (cost=0.00..3300.61 rows=497 width=33) (actual time=0.007..42.374 rows=96478 loops=1)
               Filter: (upper(order_status) = 'DELIVERED'::text)
               Rows Removed by Filter: 2963
         ->  Index Scan using order_items_pkey on order_items i  (cost=0.42..7.12 rows=1 width=39) (actual time=0.002..0.003 rows=1 loops=96478)
               Index Cond: (order_id = o.order_id)
 Planning Time: 0.217 ms
 Execution Time: 351.880 ms
(9 rows)
 
                                      QUERY PLAN                                       
---------------------------------------------------------------------------------------
 Aggregate (actual time=98.518..98.522 rows=1 loops=1)
   ->  Hash Join (actual time=35.124..88.287 rows=110197 loops=1)
         Hash Cond: (i.order_id = o.order_id)
         ->  Seq Scan on order_items i (actual time=0.003..8.623 rows=112650 loops=1)
         ->  Hash (actual time=34.557..34.559 rows=96478 loops=1)
               Buckets: 131072  Batches: 1  Memory Usage: 7149kB
               ->  Seq Scan on orders o (actual time=0.007..13.959 rows=96478 loops=1)
                     Filter: (order_status = 'delivered'::text)
                     Rows Removed by Filter: 2963
 Planning Time: 0.267 ms
 Execution Time: 100.008 ms
(11 rows)

The second plan, with costs shown, explains the first. PostgreSQL has statistics on order_status but none on upper(order_status), so for the filter it fell back to a default guess of 0.5% of the table: 497 orders. With 497 outer rows, a nested loop with index lookups really is the cheapest plan. But 96,478 orders matched, 194 times more, so it ran 96,478 index lookups: 341 ms.

The plain order_status = 'delivered' uses real statistics, estimates correctly, and gets a hash join: 100 ms, 3.4 times faster, for the same 110,197 joined rows.

The fix is not enable_nestloop = off. It is to make the estimate right: filter on the raw column (store values in one case), or, if you must filter on an expression, create an expression index on it and run ANALYZE, which gives PostgreSQL statistics for the expression. On a join that runs for minutes, this pattern (estimated rows tiny, loops= huge on the inner side of a Nested Loop) is the first thing to look for.

Step 5: the same join in DuckDB

Columnar engines show the same algorithms with different drawings. DuckDB's EXPLAIN for the step 1 query, on the same two CSV files:

python

import duckdb
c = duckdb.connect()
c.sql("CREATE TABLE orders AS SELECT * FROM read_csv_auto('olist_orders_dataset.csv')")
c.sql("CREATE TABLE order_items AS SELECT * FROM read_csv_auto('olist_order_items_dataset.csv')")
r = c.sql("""EXPLAIN
SELECT o.order_status, count(*) AS items, sum(i.price) AS revenue
FROM orders AS o
JOIN order_items AS i ON i.order_id = o.order_id
GROUP BY o.order_status""").fetchall()
print(r[0][1])

Output

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│__internal_decompress_strin│
│           g(#0)           │
│             #1            │
│             #2            │
│                           │
│          ~6 rows          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       HASH_GROUP_BY       │
│    ────────────────────   │
│         Groups: #0        │
│                           │
│        Aggregates:        │
│        count_star()       │
│          sum(#1)          │
│                           │
│          ~6 rows          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        order_status       │
│           price           │
│                           │
│       ~112,650 rows       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│    ────────────────────   │
│__internal_compress_string_│
│        uhugeint(#0)       │
│             #1            │
│                           │
│       ~112,650 rows       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         HASH_JOIN         │
│    ────────────────────   │
│      Join Type: INNER     │
│                           │
│        Conditions:        ├──────────────┐
│    order_id = order_id    │              │
│                           │              │
│       ~112,650 rows       │              │
└─────────────┬─────────────┘              │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   ││    ────────────────────   │
│           Table:          ││           Table:          │
│     memory.main.orders    ││  memory.main.order_items  │
│                           ││                           │
│   Type: Sequential Scan   ││   Type: Sequential Scan   │
│                           ││                           │
│        Projections:       ││        Projections:       │
│          order_id         ││          order_id         │
│        order_status       ││           price           │
│                           ││                           │
│        ~99,441 rows       ││       ~112,650 rows       │
└───────────────────────────┘└───────────────────────────┘

Read it top-down this time: the result is at the top and the scans at the bottom. The same pieces are there: two sequential scans, a HASH_JOIN on order_id with an estimate of about 112,650 rows, and a hash aggregate. Notice the Projections lines: the columnar scan reads only order_id and order_status from orders and order_id and price from items, not whole rows. Analytical engines lean on hash joins almost exclusively, because their inputs are large and rarely indexed.

Common mistakes

"Nested loops are bad." They are the best plan for a small outer side with an indexed inner side (3.6 ms vs 44.6 ms in step 3). They are bad only when the outer side is much bigger than estimated.
Fixing a bad plan with enable_* settings in production. They hide the real problem (a wrong estimate) and break other queries. Fix the estimate: ANALYZE, sargable filters, expression statistics.
Ignoring Batches on a hash node. More than 1 means the hash table spilled to disk. Reduce the build side or give the query more work_mem.
Setting a huge global work_mem. It is per node per process. Raise it for the session or job that needs it.
No index on foreign key columns used in joins. Without one, a small lookup join must hash or scan the whole other table.
Functions on join or filter columns. upper(), casts and date_trunc destroy estimates and indexes, as step 4 showed.
Believing the written join order matters. The planner reorders joins. Write them in the order that reads best; tune with statistics and indexes, not by shuffling FROM.
Joining before reducing. Joining two big tables and then filtering or aggregating makes every algorithm work harder. Filter and aggregate each side first when the logic allows (covered in the query optimization lesson).

Interview angle

What join algorithms does a database use and when is each one chosen?

Three. Nested loop: for each outer row, look up matches in the inner input, ideally through an index; best when the outer side is small, and the only one that supports arbitrary conditions. Hash join: build a hash table on the smaller input's join key and probe it with the other; best for large equality joins without useful ordering, but it needs memory and spills to disk when the table does not fit. Merge join: walk two inputs sorted on the key; best when both are already sorted, for example by indexes. The planner estimates the cost of each from row-count estimates, so wrong estimates lead to wrong choices.

A query that joins two tables suddenly takes minutes instead of seconds. What do you check?

Get EXPLAIN ANALYZE and compare estimated and actual rows at each node. The classic pattern is a Nested Loop whose outer side was estimated at a few hundred rows but returned hundreds of thousands, shown by a huge loops= count on the inner side. Then find why the estimate is off: stale statistics after a big load (run ANALYZE), a function or cast on a filtered column, correlated filters, or a new data distribution. Also check hash nodes for Batches above 1 (spilling) and whether an index the plan relied on was dropped.

What is a hash join spill and how do you avoid it?

When the build side's hash table does not fit in the memory allowed for that operation (work_mem in PostgreSQL), the database splits both inputs into batches, writes them to temporary files and joins batch by batch. It shows as Batches greater than 1 and makes the join noticeably slower. Avoid it by building from the smaller input, selecting only needed columns, filtering before the join, or raising work_mem for that session or job rather than globally.

Does the order of tables in the FROM clause matter?

Usually not for correctness of inner joins or for performance in PostgreSQL, SQL Server, Oracle or modern warehouses: the optimizer considers different join orders and picks the cheapest, and also chooses which side of a hash join to build from. Order does matter for outer joins' meaning, beyond the planner's search limit (join_collapse_limit, 8 tables by default in PostgreSQL), and in simpler engines or when hints force an order.

Practice task

Back to Online Retail (CC BY 4.0). Using the sales table from SQL EXPLAIN: read query plans and use indexes:

Build a customers table with one row per customer_id, their country and their first purchase time (first_seen), with customer_id as primary key, and make sure sales has an index on invoiced_at.
Write a query for November 2011 lines bought by customers whose first purchase was in December 2010, filtering customers with date_trunc('month', first_seen) = '2010-12-01'. Read the plan with EXPLAIN (ANALYZE): which join algorithm, which side is hashed, and how good is the estimate for customers?
Rewrite the customer filter so the estimate is right, and compare.
Switch off hash joins and see what the planner does instead.

Show a solution

sql

CREATE TABLE customers AS
SELECT customer_id, min(country) AS country, min(invoiced_at) AS first_seen
FROM sales WHERE customer_id IS NOT NULL GROUP BY customer_id;
ALTER TABLE customers ADD PRIMARY KEY (customer_id);
ANALYZE customers;
-- if you dropped it: CREATE INDEX sales_invoiced_at_idx ON sales (invoiced_at);

Output

SELECT 4372
ALTER TABLE
ANALYZE

The date_trunc version:

sql

SET max_parallel_workers_per_gather = 0;

-- November 2011 revenue from customers who first bought in December 2010
EXPLAIN (ANALYZE)
SELECT count(*) AS lines, sum(s.quantity * s.unit_price) AS revenue
FROM customers AS c
JOIN sales AS s ON s.customer_id = c.customer_id
WHERE date_trunc('month', c.first_seen) = '2010-12-01'
  AND s.invoiced_at >= '2011-11-01' AND s.invoiced_at < '2011-12-01';

Output

SET
                                                                               QUERY PLAN                                                                               
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=3558.07..3558.08 rows=1 width=40) (actual time=34.356..34.359 rows=1 loops=1)
   ->  Hash Join  (cost=98.28..3554.83 rows=324 width=10) (actual time=1.051..28.782 rows=23006 loops=1)
         Hash Cond: (s.customer_id = c.customer_id)
         ->  Index Scan using sales_invoiced_at_idx on sales s  (cost=0.42..3230.98 rows=86028 width=14) (actual time=0.106..18.081 rows=84711 loops=1)
               Index Cond: ((invoiced_at >= '2011-11-01 00:00:00'::timestamp without time zone) AND (invoiced_at < '2011-12-01 00:00:00'::timestamp without time zone))
         ->  Hash  (cost=97.58..97.58 rows=22 width=4) (actual time=0.910..0.912 rows=948 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 42kB
               ->  Seq Scan on customers c  (cost=0.00..97.58 rows=22 width=4) (actual time=0.020..0.782 rows=948 loops=1)
                     Filter: (date_trunc('month'::text, first_seen) = '2010-12-01 00:00:00'::timestamp without time zone)
                     Rows Removed by Filter: 3424
 Planning Time: 1.625 ms
 Execution Time: 34.435 ms
(12 rows)

A hash join, built from customers (the small side) and probed with 84,711 November lines. The customer estimate is the problem: 22 expected (the 0.5% default guess for a function), 948 actual, so the join output was estimated at 324 rows and was 23,006. Here the hash join survived because even 948 customers is a small build side, but anything stacked on top of this join (another join, a sort) would be planned for 324 rows.

The sargable rewrite, and then the same query with hash joins switched off:

sql

SET max_parallel_workers_per_gather = 0;

EXPLAIN (ANALYZE)
SELECT count(*) AS lines, sum(s.quantity * s.unit_price) AS revenue
FROM customers AS c
JOIN sales AS s ON s.customer_id = c.customer_id
WHERE c.first_seen >= '2010-12-01' AND c.first_seen < '2011-01-01'
  AND s.invoiced_at >= '2011-11-01' AND s.invoiced_at < '2011-12-01';

SET enable_hashjoin = off;
EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) AS lines, sum(s.quantity * s.unit_price) AS revenue
FROM customers AS c
JOIN sales AS s ON s.customer_id = c.customer_id
WHERE c.first_seen >= '2010-12-01' AND c.first_seen < '2011-01-01'
  AND s.invoiced_at >= '2011-11-01' AND s.invoiced_at < '2011-12-01';

Output

SET
                                                                               QUERY PLAN                                                                               
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=3706.67..3706.68 rows=1 width=40) (actual time=37.461..37.464 rows=1 loops=1)
   ->  Hash Join  (cost=109.91..3566.46 rows=14021 width=10) (actual time=0.710..30.132 rows=23006 loops=1)
         Hash Cond: (s.customer_id = c.customer_id)
         ->  Index Scan using sales_invoiced_at_idx on sales s  (cost=0.42..3230.98 rows=86028 width=14) (actual time=0.023..16.739 rows=84711 loops=1)
               Index Cond: ((invoiced_at >= '2011-11-01 00:00:00'::timestamp without time zone) AND (invoiced_at < '2011-12-01 00:00:00'::timestamp without time zone))
         ->  Hash  (cost=97.58..97.58 rows=952 width=4) (actual time=0.655..0.656 rows=948 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 42kB
               ->  Seq Scan on customers c  (cost=0.00..97.58 rows=952 width=4) (actual time=0.014..0.488 rows=948 loops=1)
                     Filter: ((first_seen >= '2010-12-01 00:00:00'::timestamp without time zone) AND (first_seen < '2011-01-01 00:00:00'::timestamp without time zone))
                     Rows Removed by Filter: 3424
 Planning Time: 1.194 ms
 Execution Time: 37.588 ms
(12 rows)
 
SET
                                                                               QUERY PLAN                                                                               
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate (actual time=42.278..42.280 rows=1 loops=1)
   ->  Nested Loop (actual time=0.110..36.771 rows=23006 loops=1)
         ->  Index Scan using sales_invoiced_at_idx on sales s (actual time=0.010..10.458 rows=84711 loops=1)
               Index Cond: ((invoiced_at >= '2011-11-01 00:00:00'::timestamp without time zone) AND (invoiced_at < '2011-12-01 00:00:00'::timestamp without time zone))
         ->  Memoize (actual time=0.000..0.000 rows=0 loops=84711)
               Cache Key: s.customer_id
               Cache Mode: logical
               Hits: 82999  Misses: 1712  Evictions: 0  Overflows: 0  Memory Usage: 131kB
               ->  Index Scan using customers_pkey on customers c (actual time=0.001..0.001 rows=0 loops=1712)
                     Index Cond: (customer_id = s.customer_id)
                     Filter: ((first_seen >= '2010-12-01 00:00:00'::timestamp without time zone) AND (first_seen < '2011-01-01 00:00:00'::timestamp without time zone))
                     Rows Removed by Filter: 1
 Planning Time: 0.234 ms
 Execution Time: 42.387 ms
(14 rows)

The range filter gives an estimate of 952 customers for an actual 948, and a join estimate of 14,021 instead of 324: much closer to the real 23,006. Same hash join, now planned on honest numbers.

Without hash joins the planner did not pick a merge join; it chose a nested loop with Memoize (PostgreSQL 14+). The 84,711 November lines are the outer side, but they come from only 1,712 different customers, so Memoize caches each customer lookup: 1,712 misses went to the primary key index, the other 82,999 lookups were answered from a 131 kB cache. That brings the nested loop to 42 ms, close to the hash join's 38 ms. Memoize is the planner's answer to a big outer side with few distinct keys.

#Why it matters

#The concept

#Three ways to join

#Estimates drive the choice

#Join order

#Skew

#Settings for experiments, not production

#Worked example: orders and items on Olist

#Step 1: one join, three algorithms

#Step 2: a hash join that does not fit in memory

#Step 3: where a nested loop wins

#Step 4: a bad estimate picks the wrong algorithm

#Step 5: the same join in DuckDB

#Common mistakes

#Interview angle

#Practice task

#Further reading

Why it matters

The concept

Three ways to join

Estimates drive the choice

Join order

Skew

Settings for experiments, not production

Worked example: orders and items on Olist

Step 1: one join, three algorithms

Step 2: a hash join that does not fit in memory

Step 3: where a nested loop wins

Step 4: a bad estimate picks the wrong algorithm

Step 5: the same join in DuckDB

Common mistakes

Interview angle

Practice task

Further reading