Incremental Sort Plans #

A paginated feed — ORDER BY account_id, created_at DESC LIMIT 50 — has an index on account_id but not on (account_id, created_at). Before PostgreSQL 13 the only options were to sort everything or add an index. Now the plan shows Incremental Sort with Presorted Key: account_id, reads a few hundred rows, and returns in under a millisecond. For one large account, the same plan takes six seconds.

Sort spills, work_mem sizing and unexpected sorts are covered in sort and hash node analysis. This page covers the sort node that exploits partial order.

The Algorithmic Condition #

Incremental Sort (PostgreSQL 13+, enable_incremental_sort) applies when:

Instead of buffering all input, it processes rows in runs that share prefix values. Two modes:

Benefits over a full Sort:

The planner costs it assuming groups of average size from n_distinct of the prefix column. That assumption is exactly what fails on skewed prefixes — the same class of estimate error covered in statistics and selectivity estimation. Deciding whether the planner should see presorted input at all is part of debugging unexpected sort operations.

Sorting everything versus sorting each group Top row: a full Sort buffers the entire input, one long block, before emitting any row. Bottom row: input ordered by account_id arrives in groups; Incremental Sort sorts each group by created_at as it completes and emits it, so a LIMIT can stop after the first groups. Sort buffer and sort all 4.2M rows then emit Incremental Sort acct 12acct 3 each group sorted by created_at, emitted LIMIT reached → never read memory ∝ largest group, not total input

Annotated EXPLAIN Evidence #

Typical accounts:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM activity
WHERE account_id BETWEEN 1000 AND 2000
ORDER BY account_id, created_at DESC
LIMIT 50;
Limit  (actual time=0.09..0.71 rows=50 loops=1)
  ->  Incremental Sort  (actual time=0.09..0.69 rows=50 loops=1)
        Sort Key: account_id, created_at DESC
        Presorted Key: account_id                              -- input already ordered by this
        Full-sort Groups: 2  Sort Method: quicksort  Average Memory: 30kB  Peak Memory: 30kB
        --  two small batches covered the first 50 rows
        ->  Index Scan using activity_account_id_idx on activity  (actual rows=71 loops=1)
              Index Cond: ((account_id >= 1000) AND (account_id <= 2000))
Execution Time: 0.76 ms

A skewed prefix — account 1000 is an integration account with 3.8 million rows:

Limit  (actual time=6104.2..6104.3 rows=50 loops=1)
  ->  Incremental Sort  (actual time=6104.2..6104.3 rows=50 loops=1)
        Sort Key: account_id, created_at DESC
        Presorted Key: account_id
        Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 28kB  Peak Memory: 28kB
        Pre-sorted Groups: 1  Sort Method: external merge  Average Disk: 412208kB  Peak Disk: 412208kB
        --  one pre-sorted group of 3.8M rows, sorted on disk before the first row came out
        ->  Index Scan using activity_account_id_idx on activity  (actual rows=3804211 loops=1)
Execution Time: 6110.8 ms

Fields to read: Presorted Key (which prefix is exploited), the two group counts, and Peak Memory / Peak Disk for the pre-sorted mode — a large peak there means one group dominated.

Reading the two group modes Three lines are annotated. Presorted Key names the prefix supplied by the index. Full-sort Groups with small memory are the healthy small batches. Pre-sorted Groups with 412 megabytes on disk show one huge group. Presorted Key: account_id order supplied by the index Full-sort Groups: 1 … Peak Memory: 28kB small batches: healthy Pre-sorted Groups: 1 … Peak Disk: 412208kB one giant prefix group

Step-by-Step Resolution #

  1. Find Incremental Sort and compare Sort Key with Presorted Key to see which columns remain to be sorted.

  2. Read the group statistics. Many full-sort groups with small peak memory is healthy. A pre-sorted group with large memory or disk means a skewed prefix.

  3. Check prefix skew.

    SELECT account_id, count(*) FROM activity
GROUP BY account_id ORDER BY count(*) DESC LIMIT 5;

  4. Test alternatives.

    BEGIN;
SET LOCAL enable_incremental_sort = off;
EXPLAIN (ANALYZE, BUFFERS) <query>;
ROLLBACK;

  5. Give the planner full order when the query is hot. An index matching the entire sort key removes sorting entirely and makes LIMIT stop after 50 rows regardless of skew:

    CREATE INDEX CONCURRENTLY activity_account_created_idx
  ON activity (account_id, created_at DESC);

    Column order and direction rules are in descending and NULLS ordering in B-tree indexes.

  6. Size memory for the largest group if the incremental plan is otherwise right; the pre-sorted mode obeys work_mem like any sort.

Group size decides the benefit Two bars show rows read before 50 rows are emitted. For typical accounts, 71 rows. For the skewed integration account, 3.8 million rows, because its single group must be fully sorted first. A third short bar shows 50 rows read with a full-key index. typical accounts 71 rows read skewed account 1000 3,804,211 rows read and sorted full-key index 50 rows read, no sort node rows read before the first 50 are returned

Before and After #

-- BEFORE: index on (account_id) only, skewed account
Incremental Sort  Pre-sorted Groups: 1  Sort Method: external merge  Peak Disk: 412208kB   Execution Time: 6110.8 ms

-- AFTER: index on (account_id, created_at DESC)
Limit → Index Scan using activity_account_created_idx  (actual rows=50)                    Execution Time: 0.41 ms

The full-key index is worth its write cost only for hot paginated queries; for occasional reports over typical accounts, the incremental plan on the single-column index was already fast, and the skewed account can be handled by its own query path.

Common Pitfalls #

Reading Incremental Sort as “no sort cost”. It still sorts; it just sorts in pieces. Diagnostic signal: Pre-sorted Groups with disk usage. Fix: check group sizes before assuming the node is cheap.

Average estimates on skewed prefixes. The planner’s group size assumption hides the one huge group. Diagnostic signal: fast plans for most parameter values and one pathological value. Fix: a full-key index, or split the hot value into its own query.

Disabling the feature globally. Many paginated and merge-join plans benefit. Diagnostic signal: new full Sort nodes across unrelated queries. Fix: scope enable_incremental_sort = off to the transaction.

Mismatched sort directions. An index on account_id with ORDER BY account_id DESC, created_at still provides a presorted prefix via a backward scan, but mixed directions on the remaining keys cannot come from a single-direction index. Diagnostic signal: incremental sort persisting after adding an index with the wrong direction. Fix: match the index directions to the ORDER BY.

Frequently Asked Questions #

When does PostgreSQL use Incremental Sort? When the input is already sorted by a leading prefix of the sort keys and sorting each prefix group separately is estimated cheaper than a full sort. Available from PostgreSQL 13, controlled by enable_incremental_sort.

What are Full-sort Groups and Pre-sorted Groups? Full-sort mode sorts small batches on all keys; pre-sorted mode sorts one large same-prefix group on the remaining keys. EXPLAIN reports counts and memory or disk for each.

Why is Incremental Sort sometimes slower than a full sort? The estimate assumes average group sizes. A skewed prefix value creates one huge group that is effectively a full sort, plus overhead, and the LIMIT benefit disappears.

Up: Sort and Hash Node Analysis