The Hash Join Gets a Spillway

The tiny hash-join story fits on one napkin:

build a hash table from the smaller input
scan the larger input
probe the table for matching keys

That is the pleasant case. It is also the case that hides the interesting engineering.

The executor does not always receive a build side that fits in memory. Cardinality estimates are wrong. Tuple widths are larger than expected. A key distribution is not uniform. Several queries are competing for memory. At that point the hash join needs a spillway: a way to turn one too-large join into many smaller joins without changing the answer.

The trick is to partition both relations by the join key.

If a build tuple r and a probe tuple s can join, then their join keys are equal, so a deterministic partition hash sends them to the same batch:

\[h(r.key)=h(s.key).\]

Therefore:

join(R, S)
=
union over batches i of join(R_i, S_i)

The hash table only has to hold one build batch at a time.

Two Hashes, Two Jobs

It helps to separate two hashes that are often blurred together.

The partition hash decides which batch a tuple belongs to. It is the spillway contract. Corresponding build and probe tuples must go to the same batch.

The lookup hash is used inside one resident batch to find matching build tuples quickly.

These are conceptually different jobs. The first bounds memory by cutting the problem into files. The second avoids comparing every tuple inside a file.

Shapiro’s 1986 paper describes three hash-based join strategies: simple hash, GRACE hash, and hybrid hash.¹ The shared idea is partitioning. If the smaller relation cannot fit in memory, partition both inputs into corresponding subsets, then join matching subsets. The hybrid algorithm keeps one partition resident while spilling the rest, so it degrades from an in-memory hash join toward GRACE-style partitioning as memory becomes scarce.

That is the shape modern systems still expose. PostgreSQL’s EXPLAIN ANALYZE shows Buckets, Batches, and hash memory usage on hash nodes; its docs note that more than one batch implies disk space is involved even when the display does not show the disk amount.² PostgreSQL also makes the memory budget for hash operations depend on work_mem * hash_mem_multiplier.³

So the line:

Buckets: 65536  Batches: 8  Memory Usage: 4096kB

is not decoration. It is a field report from the spillway.

Lab: Batches Are a Memory Promise

The lab below builds deterministic synthetic key-count tables for a build input and a probe input. It estimates the batch count from the build-side memory budget, partitions both sides by the same hash, then doubles the batch count until every build batch fits or a single key is too large to split.

It does not simulate PostgreSQL tuple headers, cache misses, executor state machines, parallel barriers, filesystem behavior, or output materialization. The purpose is narrower:

show why build and probe sides must be partitioned together;
show why Batches > 1 means extra temporary writes and reads;
show why skew can make the original batch estimate grow;
show the degenerate case where one hot key is larger than memory.

Key profile Build rows 240,000 Probe rows 620,000 Distinct keys 12,000 Memory rows 42,000 Skew exponent 0.95 Seed 29

Build rows Probe rows / GRACE comparison Memory or write/read boundary Overflow Batch growth

Long-tail keys: 240,000 build rows, 620,000 probe rows, memory for 42,000 build rows. The planner-sized 8 batches become 16; all build batches fit.

The Default Run

The default run has:

240,000 build rows;
620,000 probe rows;
12,000 distinct keys;
memory for 42,000 build rows;
a long-tail key distribution with skew exponent 0.95.

The initial estimate is:

\[\left\lceil {240000\over 42000} \right\rceil = 6\]

rounded up to 8 power-of-two batches. Under the actual key distribution, one of those batches is too large, so the executor model doubles to 16 batches. The largest build batch then has 35,434 rows, below the 42,000 row memory budget.

The hybrid spill ledger reports:

Quantity	Value
Original batches	`8`
Actual batches	`16`
Largest build batch	`35,434` rows
Build rows kept in resident batch 0	`11,523`
Temporary rows written plus read	`1,638,784`
Top build key	`14,233` rows
Estimated output pairs	`1.05B`

The last number is a separate warning. A spill strategy controls memory. It does not make a high-multiplicity join small. If many build and probe tuples share a key, the output can still be enormous.

The exported audit grid is reproducible from Node:

const lab = require("./assets/js/hash-join-spill-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:uniform:120000/260000:mem=40000:4->4:growth=0:fits=true:30853:570148:12:11/11",
  "2:zipf:240000/620000:mem=42000:8->16:growth=1:fits=true:35434:1638784:14233:11/11",
  "3:hot:220000/500000:mem=35000:8->8:growth=0:fits=false:65129:1295540:42592:11/11",
  "4:burst:360000/700000:mem=56000:8->8:growth=0:fits=true:47659:1858390:148:11/11"
];
const EXPECTED_BY_PROFILE_SHAPE = [
  "uniform:4->4:fits=true:1/1:11/11",
  "zipf:8->16:fits=true:1/1:11/11",
  "hot:8->8:fits=false:1/1:11/11",
  "burst:8->8:fits=true:1/1:11/11"
];
const EXPECTED_CHECK_NAMES = [
  "build rows preserved",
  "probe rows preserved",
  "batch count power of two",
  "partition build rows preserved",
  "partition probe rows preserved",
  "temp accounting nonnegative",
  "hybrid does not spill more than grace",
  "fits or has skew explanation",
  "top key count agrees",
  "uniform case fits after batching",
  "hot key can exceed memory"
];
const EXPECTED_CHECK_ROWS = [
  "1:uniform:build rows preserved=true|probe rows preserved=true|batch count power of two=true|partition build rows preserved=true|partition probe rows preserved=true|temp accounting nonnegative=true|hybrid does not spill more than grace=true|fits or has skew explanation=true|top key count agrees=true|uniform case fits after batching=true|hot key can exceed memory=true",
  "2:zipf:build rows preserved=true|probe rows preserved=true|batch count power of two=true|partition build rows preserved=true|partition probe rows preserved=true|temp accounting nonnegative=true|hybrid does not spill more than grace=true|fits or has skew explanation=true|top key count agrees=true|uniform case fits after batching=true|hot key can exceed memory=true",
  "3:hot:build rows preserved=true|probe rows preserved=true|batch count power of two=true|partition build rows preserved=true|partition probe rows preserved=true|temp accounting nonnegative=true|hybrid does not spill more than grace=true|fits or has skew explanation=true|top key count agrees=true|uniform case fits after batching=true|hot key can exceed memory=true",
  "4:burst:build rows preserved=true|probe rows preserved=true|batch count power of two=true|partition build rows preserved=true|partition probe rows preserved=true|temp accounting nonnegative=true|hybrid does not spill more than grace=true|fits or has skew explanation=true|top key count agrees=true|uniform case fits after batching=true|hot key can exceed memory=true"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_NAMES.length;

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function caseShape(row, index) {
  return `${index + 1}:${row.profile}:${row.buildRows}/${row.probeRows}:` +
    `mem=${row.memoryRows}:${row.originalBatches}->${row.actualBatches}:` +
    `growth=${row.growthEvents}:fits=${row.fits}:` +
    `${row.maxBuildBatchRows}:${row.hybridTempRows}:${row.topBuildKeyRows}:` +
    `${row.passedChecks}/${row.totalChecks}`;
}

function byProfileShape(row) {
  return `${row.profile}:${row.batches}:fits=${row.fits}:` +
    `${row.passed}/${row.total}:${row.passedChecks}/${row.totalChecks}`;
}

function checkRow(row, index) {
  return `${index + 1}:${row.profile}:` +
    row.checks.map((check) => `${check.name}=${check.ok}`).join("|");
}

function rowDrifts(actual, expected) {
  return {
    missing: expected.filter((row) => !actual.includes(row)),
    extra: actual.filter((row) => !expected.includes(row))
  };
}

function hasRowDrift(drift) {
  return drift.missing.length > 0 || drift.extra.length > 0;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
console.table(audit.byProfile);
const shape = {
  byProfile: audit.byProfile.map(byProfileShape),
  cases: audit.cases.map(caseShape),
  checkRows: audit.cases.map(checkRow)
};
const checkRowDrifts = rowDrifts(shape.checkRows, EXPECTED_CHECK_ROWS);
const shapeErrors = [];
if (!sameList(shape.cases, EXPECTED_CASE_SHAPE)) {
  shapeErrors.push({ name: "cases", actual: shape.cases, expected: EXPECTED_CASE_SHAPE });
}
if (!sameList(shape.byProfile, EXPECTED_BY_PROFILE_SHAPE)) {
  shapeErrors.push({
    name: "byProfile",
    actual: shape.byProfile,
    expected: EXPECTED_BY_PROFILE_SHAPE
  });
}
audit.cases.forEach((row, index) => {
  const names = row.checks.map((check) => check.name);
  if (!sameList(names, EXPECTED_CHECK_NAMES)) {
    shapeErrors.push({
      name: `case ${index + 1} check names`,
      actual: names,
      expected: EXPECTED_CHECK_NAMES
    });
  }
});
if (hasRowDrift(checkRowDrifts)) {
  shapeErrors.push({ name: "check rows", drift: checkRowDrifts });
}

console.table(audit.cases.map((row) => ({
  profile: row.profile,
  batches: `${row.originalBatches}->${row.actualBatches}`,
  fits: row.fits,
  maxBuildBatch: row.maxBuildBatchRows,
  memoryRows: row.memoryRows,
  tempRows: row.hybridTempRows,
  topKeyRows: row.topBuildKeyRows,
  checks: `${row.passedChecks}/${row.totalChecks}`
})));
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  !audit.ok ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    failed,
    totals: {
      total: audit.total,
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}
console.log(summary);

The hot row is allowed to fail the fit test only because the audit also requires a skew explanation. A spill plan that silently overflows memory is not a valid plan.

The current grid covers four key profiles and 44 named checks. Those checks verify row preservation before and after partitioning, power-of-two batch counts, nonnegative temporary I/O, hybrid-vs-GRACE spill accounting, top-key bookkeeping, and the two regression cases the prose leans on: uniform data fits after batching, while a single hot key can exceed memory even after batch growth.

The Spill Invariant

Let the partition function be:

\[b(k)=h(k) \bmod B.\]

For each batch i, define:

\[R_i = \{r \in R : b(r.key)=i\}\]

and

\[S_i = \{s \in S : b(s.key)=i\}.\]

If r.key = s.key, then b(r.key) = b(s.key). Therefore every true join pair appears inside exactly one corresponding pair (R_i, S_i). No valid pair is lost by processing one batch at a time.

This is why the probe side must be spilled too. It is not enough to save the build partitions. The executor also needs the matching probe tuples waiting in the same batch files, or it would have to rescan the entire probe input for every build batch.

The simplified temporary I/O cost for a GRACE-style partitioned hash join is roughly:

\[2(|R|+|S|)\]

temporary rows: write both inputs into partitions, then read them back. A hybrid hash join saves the resident batch. In the default lab run, batch 0 keeps 11,523 build rows and its corresponding 29,085 probe rows out of temporary files, so the hybrid ledger is smaller than the all-partitioned ledger.

When Batches Explode

PostgreSQL’s executor comments describe the modern dynamic version: if the inner side does not fit, hash join can run in multiple batches; if the real hash table grows too large, the executor increases the number of batches, always by powers of two.⁴

That power-of-two detail is not cosmetic. It lets the executor add one more hash bit to split every old batch into two possible new batches:

old batch: h(key) & 0b0111
new batch: h(key) & 0b1111

Uniform data responds nicely. Long-tail data responds imperfectly. A single heavy key does not respond at all, because all rows with that key must stay in the same batch. PostgreSQL’s source comments call out this kind of best-effort edge: if doubling leaves a batch with all or none of its tuples, growth can be disabled globally, and later oversized batches may exceed the nominal budget.⁴

In the lab, switch Key profile to Single hot key and raise Skew exponent. The top-key panel eventually turns red: one key alone is larger than memory. No partition hash on the join key can split that key while preserving the join invariant.

Real engines have more choices than this toy:

skew optimization for most-common values;
recursive partitioning;
bloom filters or semijoins to reduce one side before spilling;
switching join algorithms;
increasing memory for this operator;
parallel work sharing;
pushing predicates earlier;
changing the query shape so the build side is genuinely smaller.

The invariant remains the same. If a batch is too large because many distinct keys landed there, more hash bits can help. If a batch is too large because one key is too large, batch count is the wrong lever.

Reading The Plan

For a production PostgreSQL plan, I would read a hash join spill with four questions:

Is Batches greater than 1?
Did actual batches exceed original batches?
Is the build-side row estimate or width estimate badly wrong?
Is the join key skewed enough that more batches cannot divide the problem?

The first question says whether the spillway opened. The second says whether the executor had to resize the spillway while running. The third asks whether the optimizer walked into the wrong memory budget. The fourth asks whether the data distribution violated the uniform partition fantasy.

That last phrase is the quiet contract behind hash join:

partitioning is a memory theorem only if the partitions become small enough

Hash join is fast because equality makes a partition proof possible. It is fragile because the proof says where matches go, not how evenly the data will arrive.

Sources

Leonard D. Shapiro, “Join Processing in Database Systems with Large Main Memories”, ACM Transactions on Database Systems 11(3), 239-264, 1986. Shapiro presents simple, GRACE, and hybrid hash joins, with partitioning as the shared mechanism, and discusses partition overflow. ↩
PostgreSQL documentation, “14.1. Using EXPLAIN”. The docs state that hash nodes show buckets, batches, and peak hash memory; if batches exceed one, disk usage is involved even if that disk amount is not displayed. ↩
PostgreSQL documentation, “19.4. Resource Consumption”. The docs describe work_mem, hash_mem_multiplier, and the fact that hash-based operations use the product as their memory limit. ↩
PostgreSQL source comments, nodeHashjoin.c, lines 26-56 in the generated source view. The comments describe multi-batch hash join, executor batch growth, power-of-two batch doubling, and the skew case where growth can be disabled. ↩ ↩²