Sort in PostgreSQL EXPLAIN

What it does

Sort reads every row from its child, sorts them by the Sort Key, then returns them in order. It can’t return its first row until it has read its last input row, so its startup time is close to its total time, and everything above it waits.

If the rows fit in work_mem (4 MB by default), it sorts in memory. If they don’t, it sorts chunks that fit, writes each to a temporary file, and merges the files. With a LIMIT above it, it only needs the top n rows and keeps them in a small heap instead of sorting everything.

When the planner picks it

• ORDER BY with no index that returns rows in that order (or one that would cost more to use).
• Under a GroupAggregate, Unique or WindowAgg, which need sorted input.
• Under a Merge Join, for an input that isn’t already sorted on the join key.
• In each process of a parallel plan, under a Gather Merge.

If the input is already sorted on the first columns of the sort key, you’ll see an Incremental Sort instead, which sorts one group at a time.

Reading its numbers

Sort  (cost=4770.41..4895.41 rows=50000 width=29) (actual time=130.235..131.875 rows=50000.00 loops=1)
  Sort Key: name
  Sort Method: quicksort  Memory: 3710kB
  Buffers: shared hit=368

• Sort Key: the columns or expressions, with DESC, NULLS FIRST or COLLATE where used.
• Sort Method:
  • quicksort Memory: …: sorted in memory; the number is the memory used.
  • top-N heapsort Memory: …: a LIMIT above needed only the first rows, so only those were kept.
  • external merge Disk: …: didn’t fit in work_mem; sorted runs were written to temporary files and merged. The number is the temporary file space.
  • external sort Disk: …: also on disk; you’ll see it when the node above needs to read the sorted rows more than once, as a merge join can.
• Buffers: temp read=… written=…: temporary file pages, when it spilled.
• actual time=130.235..131.875: the first number is when the first sorted row came out, so it covers reading the input and sorting it; the gap to the second is the time spent handing rows out.
• Worker N: Sort Method …: in a parallel plan, each process sorts its share and reports its own method and memory.

The disk figure is usually smaller than the memory the same sort would need, because rows are stored more compactly in the files. In the example below, 50,000 rows took 3,710 kB in memory and 2,064 kB on disk.

When it’s a problem

1. It spills (external merge). Extra writes and reads of temporary files. On our test machine, with the files in the operating system’s cache, a 3 MB spill cost little (54 ms against 49 ms in memory for 131,000 rows); on large sorts, or many sessions spilling at once, it’s the slow part. Raise work_mem for the query or session, not the whole server: SET LOCAL work_mem = '64MB' inside a transaction. Every sort and hash in every session can use up to work_mem, so a large global value can exhaust memory under load.
2. An index could provide the order. For ORDER BY created_at DESC LIMIT 10, an index on created_at means reading 10 index entries instead of sorting the table (see Limit). For WHERE status = 'x' ORDER BY total, an index on (status, total) does the same.
3. Text sorts under a linguistic collation are slow. Sorting 50,000 names under en_US.utf8 took 130 ms; with COLLATE "C" (plain byte order) it took 31 ms even though that version spilled to disk. If byte order is acceptable (codes, identifiers, hashes), declare the column or the sort with COLLATE "C". For human-readable names, it usually isn’t.
4. It sorts far more rows than the query returns. A sort below a filter, join or LIMIT that discards most rows suggests the filter could run first, or an index could replace the sort.

Example

PostgreSQL 18.6, default settings (work_mem 4 MB), database collation en_US.utf8:

CREATE SCHEMA seo_explain;
SET search_path = seo_explain;

CREATE TABLE customers (
  id         int PRIMARY KEY,
  name       text NOT NULL,
  country    text NOT NULL,
  created_at timestamptz NOT NULL
);
INSERT INTO customers
SELECT i, 'Customer ' || i,
       (ARRAY['GB','US','DE','FR','NL','IE','ES','IT','SE','NO',
              'DK','FI','PL','PT','BE','AT','CH','CA','AU','NZ'])[1 + (i * 7) % 20],
       timestamptz '2023-01-01' + i * interval '20 minutes'
FROM generate_series(1, 50000) AS i;
VACUUM ANALYZE customers;

All customers by name, in memory:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM customers ORDER BY name;

Sort  (cost=4770.41..4895.41 rows=50000 width=29) (actual time=130.235..131.875 rows=50000.00 loops=1)
  Sort Key: name
  Sort Method: quicksort  Memory: 3710kB
  Buffers: shared hit=368
  ->  Seq Scan on customers  (cost=0.00..868.00 rows=50000 width=29) (actual time=0.008..1.883 rows=50000.00 loops=1)
        Buffers: shared hit=368
Planning Time: 0.045 ms
Execution Time: 133.495 ms

The scan took 2 ms; comparing 50,000 strings under the language’s collation rules took the rest.

With SET work_mem = '1MB', the same sort spills:

Sort  (cost=5967.41..6092.41 rows=50000 width=29) (actual time=45.781..60.745 rows=50000.00 loops=1)
  Sort Key: name
  Sort Method: external merge  Disk: 2064kB
  Buffers: shared hit=368, temp read=258 written=261

The ten first names only, with LIMIT 10:

Limit  (cost=1948.48..1948.51 rows=10 width=29) (actual time=11.908..11.910 rows=10.00 loops=1)
  Buffers: shared hit=368
  ->  Sort  (cost=1948.48..2073.48 rows=50000 width=29) (actual time=11.907..11.907 rows=10.00 loops=1)
        Sort Key: name
        Sort Method: top-N heapsort  Memory: 26kB
        Buffers: shared hit=368
        ->  Seq Scan on customers  (cost=0.00..868.00 rows=50000 width=29) (actual time=0.005..2.065 rows=50000.00 loops=1)
              Buffers: shared hit=368
Planning Time: 0.053 ms
Execution Time: 11.927 ms

26 kB instead of 3.7 MB, and 12 ms instead of 133: a heap of ten names only needs comparing against the current tenth.

Byte order instead of the language’s collation:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM customers ORDER BY name COLLATE "C";

Sort  (cost=6653.41..6778.41 rows=50000 width=61) (actual time=25.300..29.004 rows=50000.00 loops=1)
  Sort Key: name COLLATE "C"
  Sort Method: external merge  Disk: 2784kB
  Buffers: shared hit=371, temp read=348 written=349

31 ms in total, despite spilling (the extra sort-key column made each row wider).

Across versions

The same ORDER BY name with default settings:

Newer versions need less memory for the same rows, so sorts that spilled on 14 and 15 fit in memory on 16 and later. If you upgrade and a sort stops spilling, that’s why. (PostgreSQL 15’s release notes describe its in-memory sort improvements; the memory figures above are from our runs.)

In Inlet

Inlet draws EXPLAIN ANALYZE as a tree and highlights the slowest step and badly misestimated row counts, so a Sort that holds up everything above it is easy to find.