Why work_mem changes the algorithm, not just the speed

What work_mem actually does

work_mem looks like a speed dial. Give a query more memory and it runs a bit faster, give it less and it runs a bit slower. That's not what it does, though.

work_mem feeds into plan selection. The planner prices a hash join partly on whether the hash table will fit in it. When it won't fit, the cost of that plan goes up to include spilling to temporary files and re-scanning the probe side once per batch. Past a certain point that cost is higher than a nested loop, and the planner stops choosing the hash join at all.

So a memory setting that's slightly too small doesn't make a query slightly slower. It makes the database pick a different, much worse algorithm.

I learned that while tuning anti-joins on a data platform I built for a client. Three separate things were going on in those counts, and none of them produced an error.

The first problem was stale statistics

The planner's decisions are only as good as its idea of how big each table is. Those figures come from ANALYZE, which autovacuum runs for you when enough rows have changed. But "enough rows have changed" is just a counter. Autovacuum compares a running tally of inserts, updates and deletes against a threshold based on the table's recorded size.

The host this runs on suspends compute when the database is idle, which is what makes it affordable. On resume, the statistics counters reset. The two churny tables the anti-joins depend on never went long enough between suspensions for the tally to cross the threshold, so autoanalyze never fired on them at all.

The drift was about twentyfold. The planner believed one table held around 858,000 rows, and it held around eighteen million. A planner working from a figure that low will happily choose a nested loop (on 858,000 rows a nested loop is a reasonable idea), and it'll size the hash for a table that doesn't exist.

The fix is a three-hourly scheduled ANALYZE on the affected tables. That was an easy call, because it takes no lock that blocks reads or writes, changes no data, and does nothing except sample rows and refresh planner statistics.

I don't think this is specific to one host. A feature that exists to save money (suspending idle compute) disabled a maintenance feature that relies on a counter surviving. Neither feature is broken. They just don't work together, and neither one reports anything, so you'll only see it if you compare the planner's idea of a table against the actual table.

The second was phones and emails in one list

The suppression list is one table holding two kinds of value, phone numbers and email addresses. One client's list had grown past 5.8 million values, and effectively all of them were one kind.

Each count runs two anti-joins, one testing a record's phone against the list and one testing its email, and both matched on value alone. A phone number can't equal an email address, because ten digits will never compare equal to a string containing an @. Postgres had no way to work that out, so the phone anti-join was building a hash over the client's entire list, including 5.8 million email values that could never match.

One redundant predicate tells it.

AND NOT EXISTS (
  SELECT 1 FROM suppression e
  WHERE e.client = $1
    AND e.kind = 'PHONE'     -- changes no rows; changes the plan
    AND e.value = r.phone
)

The result set is identical. I checked that, because a faster count that's wrong is no use. What changes is the size of each hash, and so which plan wins. With the kinds separated, the planner hashed each side sensibly instead of falling into a 1.1-million-row nested loop. That took it from twenty-five seconds to eleven, warm.

The general version is the useful bit. You often know something about your data that the planner can't infer (a disjointness, a correlation, a range), and writing it in as a redundant predicate costs nothing when it's true and can move the plan a long way.

The third was a hash that spilled

EXPLAIN (ANALYZE, BUFFERS) tells you what happened to a hash, in a line that's easy to skim past.

Buckets: 131072 (originally 524288)  Batches: 8

Both halves matter. originally means the planner intended 524,288 buckets, found at run time it couldn't afford them, and rebuilt the table smaller. Batches: 8 means the hash was split eight ways, with the probe side written out to temporary files and read back once per batch.

The default work_mem is 4MB, which is nowhere near this workload. I'd raised it to 64MB, which really was the knee in the curve when the lists were around a million values. Then the lists grew, and the email hash with them, to roughly 400MB.

At 64MB that hash spills to four batches, and this is the part I wanted to write down. The planner prices the spill, finds a nested loop cheaper, and drops the hash plan entirely, so a four-batch hash join never runs at all.

At 512MB the hash is one batch and the hash plan wins.

Between "enough memory" and "not quite enough" it's a decision boundary instead of a gentle slope, and the two sides run different algorithms. So I think the way to tune this is to read Batches: out of a real plan and size for one batch.

Setting it without leaking it

512MB is a big allocation, and work_mem is granted per sort or hash node per connection, so one query can take it more than once. It's only safe here because SET LOCAL inside the count's transaction makes it last only as long as that one statement, so it can't leak onto a pooled connection that later serves something small.

SET LOCAL also can't take a bind parameter, so the value gets interpolated into the statement. That means it has to be a literal constant in the source, and never reachable from anything a caller controls.

Cold runs are a different problem

The same query measured 46 seconds cold against 3 warm.

work_mem governs what happens once pages are in memory, and it does nothing about getting them there. Raising it made a measurable difference warm and none cold. The cold figure comes down to working set size and cache residency, which the plan doesn't change, and it has its own note.

Keeping those two questions apart (is this plan good and is this data resident) is most of what made the rest of it manageable. From the outside they look the same, because both show up as "the query is slow".