Query optimization series: 1. How SQL runs and reading execution plans · 2. PostgreSQL index lab on an airline dataset · 3. Join algorithms and partitioning
You write JOIN; the database decides how to combine the two tables: for the same bookings JOIN tickets, a nested loop takes 3.7 seconds and a hash join 0.7. After this post you’ll recognize the three join algorithms in a plan, avoid the traps in writing joins, and know when to partition (split a big table into pieces) rather than shard.
Read first: join syntax in ERD, JOIN, GROUP BY, indexes in Indexes, EXPLAIN, N+1 and pagination, and reading plans in part 1. The PostgreSQL 16 and MySQL 8.4 plans below are real output from my runs on the dataset from part 2 (2.1 million bookings, 3.1 million tickets).
1. Nested loop join
Key idea: for each row of the outer table, find the matching rows in the inner table. Cost ≈ outer rows × the cost of one inner lookup, so the inner table needs an index on the join column.
for each row b in bookings where <conditions on b>: -- outer
for each row t in tickets where t.book_ref = b.book_ref: -- inner: index lookup if available
emit (b, t)
- With an index, each lookup is a few pages. Without one, every outer row means a full scan of the inner table.
- Works with any join condition (
<,BETWEEN,LIKE). - Returns its first row almost immediately, which suits
LIMITwell.
Forcing PostgreSQL into a nested loop for the 132,789 bookings with total_amount >= 500000:
Nested Loop (actual time=1.378..428.104 rows=196171 loops=1)
-> Seq Scan on bookings b (actual time=1.360..104.560 rows=132789 loops=1)
Filter: (total_amount >= '500000'::numeric)
-> Index Only Scan using tickets_book_ref_idx on tickets t (actual time=0.002..0.002 rows=1 loops=132789)
Index Cond: (book_ref = b.book_ref)
Each lookup takes only 0.002 ms, but multiplied by loops=132789 that’s about 270 ms. MySQL’s block nested loop variant from before 8.0.20 has since been replaced by hash join (section 2).
2. Hash join
Key idea: the build phase reads the smaller input into a hash table keyed on the join column; the probe phase streams the larger input and looks each row up. Cost ≈ O(n + m), no index needed, but it needs memory.
flowchart LR
subgraph Build["1. Build: smaller input"]
C["filtered bookings<br/>132,789 rows"] --> H["Hash table<br/>key = book_ref"]
end
subgraph Probe["2. Probe: stream the larger input"]
T["tickets<br/>3.1 million rows"] --> L{"hash(book_ref)<br/>in the table?"}
end
H -.-> L
L -->|yes| O["Emit joined row"]
L -->|no| X["Discard"]
Limits: equality conditions only (in PostgreSQL), and no row comes out until the build is finished.
Hash Join (actual time=148.566..728.749 rows=196171 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
-> Seq Scan on tickets t (actual time=0.084..267.757 rows=3100000 loops=1)
-> Hash (actual time=147.911..147.912 rows=132789 loops=1)
Buckets: 262144 Batches: 1 Memory Usage: 7106kB
-> Seq Scan on bookings b (actual time=4.577..128.159 rows=132789 loops=1)
Filter: (total_amount >= '500000'::numeric)
The Hash node is the build phase: 7 MB, and Batches: 1 means it fit in memory. Lower work_mem (PostgreSQL’s memory for each sort/hash step) to 1 MB and it becomes Batches: 4 Memory Usage: 1772kB with temp written=327: it spilled to disk.
Spilling to disk (Grace hash join), early filtering, the old block nested loop and MySQL’s benchmark
Block nested loop (BNL). When the inner table has no index, MySQL before 8.0.20 collects outer rows in a join buffer (join_buffer_size) and scans the inner table once per full buffer, comparing in memory. If t1 JOIN t2 yields 10 rows, a plain nested loop typically scans t3 10 times; with a join buffer holding all 10 rows, it scans once.
Since MySQL 8.0.20, BNL has been replaced entirely by hash join. Seeing Using join buffer (Block Nested Loop) means an old MySQL version.
Spilling to disk (Grace hash join). When the build input doesn’t fit in memory, both inputs are split into N partitions by a second hash function on the join key, written to temp files, and then each pair of partitions i is joined. A row can only match rows in the same partition, so the result is still correct, at the cost of an extra round of disk reads and writes. MySQL does the same with “chunk files” once join_buffer_size (256 KB by default) is exceeded. PostgreSQL 11+ adds Parallel Hash: several workers build one shared hash table.
Early filtering. For t1 JOIN t2 ON t1.a = t2.a WHERE t1.b > 3 AND t2.c < 4, MySQL 8.4’s EXPLAIN FORMAT=TREE shows Filter: (t1.b > 3) under the Hash node and Filter: (t2.c < 4) under the probe side: the hash join filters both inputs before combining them.
Benchmark. The MySQL team’s TPC-H-style benchmark for the hash join launch (8.0.18) showed queries going from over 400 seconds with BNL down to around 2.5 seconds.
3. Merge join
Key idea: sort both inputs by the join key, then walk them side by side with two pointers. If both already come sorted from an index there’s no sort, and PostgreSQL picks it when ORDER BY matches the join key.
The two pointers: advance whichever side has the smaller key, emit a joined row when they’re equal.
SELECT b.book_ref, t.ticket_no
FROM bookings b JOIN tickets t ON t.book_ref = b.book_ref
ORDER BY b.book_ref LIMIT 100000;
Limit (actual time=0.014..61.773 rows=100000 loops=1)
-> Merge Join (actual time=0.013..58.510 rows=100000 loops=1)
Merge Cond: (b.book_ref = t.book_ref)
-> Index Only Scan using bookings_pkey on bookings b (actual time=0.003..21.098 rows=67745 loops=1)
-> Index Scan using tickets_book_ref_idx on tickets t (actual time=0.008..20.103 rows=100000 loops=1)
No Sort, no hash table, and it stops after 100,000 rows. Drop the ORDER BY ... LIMIT (count everything) and the planner goes back to a hash join.
4. Comparison and a Java simulation
Key idea: no algorithm always wins. Joining all of two large tables, the hash join is far faster; once the filter leaves few rows, it’s practically a tie.
Measured with \timing on PostgreSQL (warm cache, no parallelism):
| Query | Hash join | Nested loop + index |
|---|---|---|
6% of bookings (total_amount >= 500000), ~196,000 result rows |
300–390 ms | ~395 ms |
| All 2.1 million bookings × 3.1 million tickets | 685 ms | 3,750 ms |
In-memory simulation in Java 21
A simulation with 200,000 persons and 2,000 countries makes the complexity visible. A nested loop without an index is two nested for loops, O(n × m); an index nested loop replaces the inner loop with a TreeMap.get, O(n log m). The merge join is two pointers over two sorted lists as in section 3 (the full version handles duplicate keys on both sides). The hash join:
record Country(int id, String name) {}
record Person(int id, int countryId) {}
record Row(Person p, Country c) {}
// Hash join: build on the smaller input, probe with the larger one -> O(n + m)
static List<Row> hashJoin(List<Country> build, List<Person> probe) {
var table = new HashMap<Integer, List<Country>>();
for (var c : build) table.computeIfAbsent(c.id(), k -> new ArrayList<>()).add(c);
var out = new ArrayList<Row>();
for (var p : probe)
for (var c : table.getOrDefault(p.countryId(), List.of())) out.add(new Row(p, c));
return out;
}
nested loop 808.8 ms 160033 rows
index nested loop 10.3 ms 160033 rows
hash join 3.1 ms 160033 rows
merge join 21.9 ms 160033 rows
Inside a database the gaps are smaller, because the dominant cost is reading pages (see the \timing table above).
5. Writing joins that are correct and fast
Key idea: the optimizer orders the tables itself, so your job is to index the columns in ON and put conditions in the right place (ON or WHERE) for a LEFT JOIN.
ON vs WHERE. With an INNER JOIN, both give the same result. With a LEFT JOIN it’s a different story:
-- customers: An, Binh, Chi. orders: An has 1 PAID + 1 CANCELLED, Binh has 1 CANCELLED.
SELECT c.name, o.id FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id AND o.status = 'PAID';
-- An | 10 Binh | NULL Chi | NULL → every customer, with a PAID order if there is one
SELECT c.name, o.id FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id
WHERE o.status = 'PAID';
-- An | 10 → only customers with a PAID order
The tell in a PostgreSQL plan: the second query shows a plain Hash Join, not a Hash Left Join, because the planner sees that WHERE removes every NULL row and downgrades it to an INNER JOIN.
Join order, hints and filtering by another table
Join order. PostgreSQL tries every order up to join_collapse_limit = 8 tables; from 12 tables it switches to GEQO (an approximate search algorithm), which can choose poorly. The advice “join the big table to the small table” is vague: the planner picks the build/outer side from the row counts after filtering. Hints (MySQL /*+ JOIN_ORDER(...) */, PostgreSQL pg_hint_plan) are a last resort.
6. Case study: join decomposition
Key idea: join decomposition splits one JOIN into several single-table queries combined in the application. It trades one round-trip and a consistent snapshot for per-entity caching and the freedom to split services; only worth it when a service or cache boundary forces it.
The tag/post case study: the split queries and their cost versus one JOIN
Context. The “posts by tag” page runs tag JOIN tag_post JOIN post WHERE tag.name = 'mysql'; post is about to get its own database and is read very heavily. The split:
SELECT id FROM tag WHERE name = 'mysql'; -- 1 row, cacheable for a long time
SELECT post_id FROM tag_post WHERE tag_id = 1234; -- list of ids
SELECT * FROM post WHERE id = ANY(:ids); -- MySQL: WHERE id IN (...)
7. Partitioning a table
Key idea: partitioning splits one table’s data into separate physical pieces that are still queried as a single table. It lets you read less and drop old data cheaply, but only when queries filter on the partition key.
Vertical partitioning splits columns (moving a long, rarely read description into a side table); horizontal partitioning splits rows by a partition key, e.g. bookings by month of book_date. This post is about the latter. Pruning is the planner skipping partitions that can’t contain the rows you want.
| Partitioning | Sharding | |
|---|---|---|
| Scope | Pieces inside one server | Pieces across many servers |
| Application | Doesn’t need to know | Must know (or go through middleware such as Vitess or Citus) |
| Main purpose | Read less (pruning), cheap removal of old data, per-piece maintenance | Spread write load and storage beyond one machine |
| When the server dies | Every partition is gone | Only the shards on that server |
An experiment on PostgreSQL with bookings_p partitioned by month (15 partitions):
CREATE TABLE bookings_p (
book_ref char(6) NOT NULL,
book_date timestamptz NOT NULL,
total_amount numeric(10,2) NOT NULL,
PRIMARY KEY (book_ref, book_date) -- must include the partition key
) PARTITION BY RANGE (book_date);
CREATE TABLE bookings_p_201703 PARTITION OF bookings_p FOR VALUES FROM ('2017-03-01') TO ('2017-04-01');
-- ... one partition per month (a DO loop or the pg_partman extension), plus a DEFAULT partition
CREATE INDEX ON bookings_p (book_date); -- created on every partition
| Experiment | Plain bookings |
bookings_p |
|---|---|---|
count(*) for one month |
Seq Scan of the whole table, 13,376 pages, 188 ms | Scans only bookings_p_201703, 1,064 pages, 11.6 ms |
WHERE book_ref = '00A1B2' (no partition key) |
1 Index Scan | 15 Index Scans, one per partition |
| Removing July 2016 (64,981 rows) | DELETE 316 ms, generates WAL and dead tuples |
DETACH PARTITION 2 ms |
Choose a partition key by distribution (roughly even partitions, no “hot” partition) and access pattern (do the main queries filter on it?):
- RANGE on time for data with a lifecycle. The same idea in NoSQL: a composite partition key
(channel_id, bucket)where the bucket is a time window, so a busy channel’s partition doesn’t grow forever; see Designing a Discord-style chat system. - LIST on tenant when queries always stay within one tenant.
- HASH for even spread when there’s no natural range.
MySQL partitioning limits, and Redis Cluster as a sharding example
MySQL partitioning supports RANGE, LIST, HASH, KEY and RANGE/LIST COLUMNS. Limits:
- At most 8,192 partitions per table since 5.6.7 (the often-quoted 1,024 is from older versions).
- PK/unique keys must include every column in the partitioning expression:
PRIMARY KEY (id)withPARTITION BY RANGE (YEAR(created_at))fails with error 1503. - No foreign keys and no FULLTEXT.
That’s why many teams only use it for time-based log/event tables, to drop old data.
Redis Cluster is a small, easy-to-observe example of sharding: keys hash into 16,384 slots split across the masters, clients get redirected with MOVED/ASK, and multi-key commands only work when the keys share a slot (hash tags); see Redis: persistence, replication, Sentinel and Cluster.
Choosing a shard key, four case studies and resharding without downtime are in Sharding: choosing a shard key and resharding; when to switch to NoSQL, NewSQL or columnar storage altogether is in Choosing a database: SQL, NoSQL, NewSQL.
8. Case study: what to do with a table that’s too big
Key idea: measure first, then climb one step at a time, moving up only when the current step isn’t enough. Each step is more expensive and harder to undo than the one before.
| Step | Solves | Cost |
|---|---|---|
| 1. Rewrite the query | Non-sargable predicates (conditions that can’t use an index), SELECT *, deep OFFSET, N+1 |
Next to nothing |
| 2. Index | Missing index, wrong column order, missing covering index | Slower writes, more storage |
| 3. Archive | 90% of the data nobody reads, bloating indexes and hurting the cache | An archive job, rules for accessing old data |
| 4. Cache | Repeated reads of the same data | Invalidation, stale data |
| 5. Read replicas | Read load beyond one node | Replication lag, read-after-write issues |
| 6. Partition / shard | Data lifecycle, pruning / write load beyond one node | Unique-key constraints, queries without the key; sharding loses joins/transactions |
| 7. A different database | Analytics over the whole history | Another system, data sync (CDC: reading changes from the database’s log and pushing them to another system) |
Example (an illustrative scenario): bookings at 800 million rows and 600 GB, the “booking history” API’s p95 up from 50 ms to 900 ms, the nightly report overrunning, and someone proposing to shard. The culprits were a deep OFFSET and a missing (passenger_id, book_date) index: steps 1–2 brought p95 back to 60 ms. 85% of the data was older than 18 months and only read by reports: monthly partitions to detach, reports moved to an analytics database. No sharding needed.
Exercises
Exercise 1: An effective strategy for archiving old data
Task (the course homework, paraphrased): design a strategy for archiving old data in the bookings table, keeping the latest 18 months in the main table.
Solution to exercise 1: partition + detach, batched deletes, summary tables
Ask first: does old data still need to be queried, how long must it be kept by law, do you have to erase personal data on request? Three approaches:
- Monthly partitions + detach/drop: each month,
ALTER TABLE bookings DETACH PARTITION bookings_2024_05 CONCURRENTLY(PostgreSQL 14+, doesn’t block queries), export the detached table to Parquet on object storage, thenDROP TABLE. Almost no I/O on the main table; requires partitioning from the start or a big migration. - Batched deletes when partitioning isn’t possible:
DELETE ... WHERE id IN (SELECT id ... WHERE book_date < ? ORDER BY id LIMIT 5000), commit per batch, pause between batches, watch replication lag, copy to an archive table before deleting (MySQL haspt-archiver). Slow, lots of WAL/binlog, needsVACUUMafterwards. - Summary tables by day/month for reporting, with the detail archived.
Safe batched deletion is covered in depth in Deleting old data safely.
Remember
- Explain why a nested loop needs an index while a hash join needs memory, and read
Batches: 4. - Know when PostgreSQL picks a merge join, and why that doesn’t carry over to MySQL.
- Write a
LEFT JOINwith a filter on the right-hand table correctly. - Name the two costs of partitioning and how it differs from sharding.
- Answer “what do you do with a huge table” with the ladder, starting by asking for numbers.
Interview questions
Junior
What join algorithms do databases use?
Three: nested loop, hash join and merge join.
Nested loop: for each outer row, find matching inner rows; good with an index on the join column. Hash join: build a hash table from the smaller input and probe it with the larger one; good for large equality joins. Merge join: sort both inputs and walk them in step; PostgreSQL has it, MySQL doesn’t.
Does it matter whether a condition goes in ON or WHERE?
Not for an INNER JOIN; for a LEFT JOIN it does.
A condition on the right-hand table in WHERE removes the NULL rows and effectively turns it into an INNER JOIN. To keep every row of the left table, put the condition in ON.
Mid
When is a hash join better than a nested loop?
When joining most of two large tables on an equality, especially without a suitable index on the join column.
A nested loop wins when the outer side is small and the inner side is indexed, or when you need the first rows fast with LIMIT. In the lab, joining all 2.1 million × 3.1 million rows took 0.7 seconds with a hash join and 3.7 with a nested loop.
In a PostgreSQL plan, what does Batches: 4 on a Hash node mean?
The build input didn’t fit in work_mem, so the hash join spilled to disk in 4 parts.
Both inputs were split into 4 partitions by a hash of the key, the ones not yet processed were written to temp files, and they were joined pair by pair; you’ll see temp read/written with it. Options: raise work_mem for that session, shrink the build input’s rows or columns, or accept it if the query isn’t hot.
Senior
You partition an orders table by created_at. What can break?
Table-wide uniqueness, foreign keys, queries without created_at, creating new partitions, and planning time.
- PK/unique constraints must include
created_at, soorder_idis no longer guaranteed unique across the table; foreign keys pointing at the table have to change. - Queries by
order_idorcustomer_idwithoutcreated_atscan every partition. - You need a job that creates next month’s partition in advance (or a default partition), or inserts fail.
- Many partitions increase planning time.
What you gain is time-based pruning and removing old data by detaching.
The main table has reached a few hundred million rows and is getting slow. How do you approach it?
Measure first, then climb from cheap to expensive, moving up only when the numbers show the previous step isn’t enough.
Measure: size, top queries by total time, read/write ratio, how much of the data is hot. The steps: rewrite queries, add indexes, archive, cache, read replicas, partition/shard, a different database. Each step is more expensive and harder to undo than the previous one.
Useful phrases for interviews
- “The planner chose a nested loop because it expected only a handful of outer rows.”
- “A hash join doesn’t need an index, but it does need enough work_mem, otherwise it spills to disk in batches.”
- “MySQL doesn’t have a merge join, so I wouldn’t carry that intuition over from Postgres.”
- “That filter belongs in the ON clause; in WHERE it silently turns the left join into an inner join.”
- “I’d use EXISTS here; joining and then adding DISTINCT just to remove duplicates is wasted work.”
- “Partitioning helps us read less and drop old data cheaply, but it doesn’t give us more write capacity.”
- “Before partitioning, I’d check that the main queries actually filter on the partition key.”
- “Let’s go up the ladder one step at a time: query, index, archive, cache, replicas, and only then partitioning or sharding.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.