Incremental Sort

An Incremental Sort exploits input that's already sorted on a prefix of the desired keys. It sorts within each group of equal prefix values, so it only ever holds a small batch in memory.

When an index provides part of the ORDER BY (e.g. ordered by a, but you want a, b) — PostgreSQL sorts just the leftover keys per prefix group.

A win: lower memory and the ability to return early rows quickly, especially with LIMIT. Available since PostgreSQL 13.

Sorting in batches

An Incremental Sort exploits input that is already sorted on a prefix of the desired keys. Rows arrive grouped by the leading column(s); within each group, the node sorts only the remaining keys.

Take ORDER BY a, b over a table with an index on a:

• Plain Sort would buffer every row and sort the whole set by (a, b).
• Incremental Sort reads rows already ordered by a, sorts each run of equal a by b, emits, and starts the next run — so it only ever holds one group in memory.

Why LIMIT loves it

Because it emits ordered rows incrementally, a downstream LIMIT lets the whole plan stop after the requested rows. A regular Sort over the full input would have to finish first.

The plan reports both group counts and disk methods per chunk:

Incremental Sort  (actual rows=20 loops=1)
  Sort Key: a, b
  Presorted Key: a
  Full-sort Groups: 5   Sort Method: quicksort  Average Memory: 27kB

Presorted Key is the prefix the input was already on; Full-sort Groups is how many sub-sorts ran.

When the planner picks it

Available since PostgreSQL 13 and tightened in later versions. The planner uses it when a useful index supplies the prefix and a Sort node would be expensive. If you don't see it where you expect, check that the index leads with the same column order as your ORDER BY.

work_memenable_incremental_sort

How we tune these →

• Sort
• Limit