The pagination query was the kind every SaaS table eventually grows: ORDER BY tenant_id, created_at DESC, LIMIT 50, over a 300-million-row events table. The plan was a full sort — Sort Method: external merge, Disk: 1,700,000kB — and the query took fourteen seconds, of which roughly zero were spent reading rows anyone wanted. There was a btree on tenant_id already. PostgreSQL 13's incremental sort turned that exact combination — an index that pre-sorts a prefix, plus a sort key that extends it — into a plan that peaked at three megabytes of memory and answered in 180 ms. Same table, same index, same SQL.
What problem does Incremental Sort solve?
It solves the waste of re-sorting data that is already mostly sorted: when the input stream arrives ordered by a prefix of the sort keys, incremental sort only sorts within each prefix group by the remaining keys, so memory stays proportional to the largest group rather than the whole result. A full sort of ten million rows is one ten-million-row problem, spilling to disk the moment it outgrows work_mem. Incremental sort over thousand-row groups is ten thousand small problems, each a quicksort that fits in memory trivially. The prefix order comes from somewhere real — usually an index scan on the leading columns, occasionally the sorted output of a merge join — so the classic unlock is ORDER BY a, b with a btree on (a). The feature landed in PostgreSQL 13, needs no enabling, and shows up in plans whether or not you know to look for it, which is why so many people got the win silently and so few can explain the regressions when they happen.
How do you read an Incremental Sort plan node?
Find the Presorted Key line — it names the prefix columns the input is already ordered by — and then, under EXPLAIN ANALYZE, the Full-sort Groups lines, which report how many groups were actually sorted and their average and peak memory. A healthy node reads as: Sort Key: tenant_id, created_at; Presorted Key: tenant_id; Full-sort Groups: 40, Sort Method: quicksort, Average Memory: 74kB, Peak Memory: 81kB — all of it fed by an index scan that supplies the tenant order. Compare with the full-sort alternative on the same query: one group, Sort Method: external merge, and a Disk figure that tells you the peak temp space the sort needed — the real I/O volume is larger, since an external merge can read and rewrite its runs across passes, and the temp block counters in the Buffers output carry that number. Either way it is the honest comparison metric; the temp-file accounting behind it is covered in the work_mem spill notes. Run it yourself:
EXPLAIN (ANALYZE, BUFFERS)
SELECT tenant_id, created_at, event_type, payload
FROM events
ORDER BY tenant_id, created_at DESC
LIMIT 50;With LIMIT in play, read the rows counter on the index scan too: incremental sort lets execution stop once the first groups satisfy the limit, so the scan may report a few thousand rows actually returned out of hundreds of millions available. That early-stop behavior, not the sort algorithm itself, is where most of my fourteen seconds went.
When does it beat a full sort dramatically?
When groups are numerous, small, and capped by a LIMIT — then the sort touches a handful of in-memory groups, peak memory is one group's worth, and a query that would have spilled gigabytes finishes in single-digit megabytes. Pagination over tenant-, user-, or time-bucketed data is the canonical shape, and it is everywhere in production schemas. Even without LIMIT the win is real: sorting group by group keeps every sort in fast memory instead of one external merge pass, so a large ORDER BY feeding an export or a merge join stops writing temp files at all. The requirement that makes or breaks it is group size relative to work_mem: groups that individually overflow still spill, just in slices. If your largest group is fifty thousand rows and work_mem is 64 MB, incremental sort is comfortable; if one group is forty million rows, keep reading — that case has its own failure mode.
When does Incremental Sort regress, and why?
When the planner gambles on many small groups and the data holds few huge ones — the incremental machinery then degenerates into sorting one giant group, paying per-group overhead on top of a sort the plain node would have done once. The gamble lives in the group-count estimate, which comes from ndistinct statistics on the presorted columns. If the estimate says ten thousand groups and reality is twelve, the plan was chosen on a fiction — and even when the count is right, the costing assumes the groups are roughly equal in size. I hit this on a skewed table where one tenant owned eighty-five percent of the rows: incremental sort ran 2.1 seconds, the full sort it replaced ran 1.4, and the fix was not statistics and not disabling anything — it was a better index. Skew that extreme is a modeling limit, not something extended statistics can price away, so when one group can hold most of the table, a composite index that removes the sort entirely is the only honest answer. For diagnosis, there is a purpose-built GUC:
SET enable_incremental_sort = off;
EXPLAIN (ANALYZE, BUFFERS)
SELECT tenant_id, created_at FROM events
ORDER BY tenant_id, created_at DESC
LIMIT 50;
RESET enable_incremental_sort;Compare actual times, not estimated costs — the estimated cost is what the gamble already believes. Treat enable_incremental_sort strictly as a session-level diagnostic; shipping it off in production is hiding the estimate problem rather than fixing it.
Which indexes unlock it — and which remove the sort entirely?
An index on the leading columns supplies the presorted prefix and unlocks incremental sort; a composite index matching the full ORDER BY removes the sort node altogether, and the choice between them is write cost against read shape. Single-column on tenant_id: cheap to maintain, sorts each tenant's rows at query time. Composite on (tenant_id, created_at DESC): no sort at all, a plain index scan walks rows out in final order, and LIMIT stops it after fifty — the fastest possible plan for the hot pagination query, paid for with a wider index, more WAL, and slower writes on every insert.
CREATE INDEX events_tenant_idx ON events (tenant_id);
CREATE INDEX events_tenant_created_idx ON events (tenant_id, created_at DESC);My rule after a few rounds of this: composite indexes for the two or three pagination queries that carry your traffic, single-column indexes plus incremental sort for the long tail, and no index at all for sorts that run twice a night where the full sort is honestly fine. Also mind direction: for incremental sort the prefix is all that must be presorted, and the group sort handles either direction on the remaining keys — but a composite index meant to eliminate the sort entirely must match the ORDER BY directions or their exact mirror image — a btree walks backward as happily as forward, reversing every column's direction at once.
Watching sort behavior with MonPG
Sort health surfaces in two counters before it surfaces in complaints: the temp_bytes growth rate in pg_stat_database, which flatlines when spills stop, and per-statement latency in pg_stat_statements, which is where a plan flip to or from incremental sort announces itself. MonPG graphs both as part of its PostgreSQL monitoring, and the fourteen-second pagination query from the opening was found exactly that way — temp I/O pinned against statement latency, one glance. After the index change, temp_bytes kept counting up — it is a cumulative counter — but the rate for that workload dropped ninety-eight percent. That number, not the plan text, is what I put in the pull request.