Incremental Sort in PostgreSQL EXPLAIN

What it does

Say you ask for ORDER BY customer_id, created_at and there’s an index on customer_id. The index already returns rows sorted by customer_id; only the order within each customer is missing. An Incremental Sort reads rows from the index, collects a group with the same customer_id, sorts that group by created_at, returns it, and moves on.

Each sort is small, so it uses little memory, and the first rows come out almost immediately. With a LIMIT above it, it stops as soon as it has enough rows, without reading the rest of the input.

It was added in PostgreSQL 13. Since 16 it’s also used for DISTINCT, and since 18 under merge joins. enable_incremental_sort (on by default) switches it off for testing.

When the planner picks it

• ORDER BY a, b where an index or an earlier step already provides order on a.
• Especially with LIMIT: a full Sort would have to read every row first.
• Under window functions (PARTITION BY a ORDER BY b) and aggregates when the input is sorted on the leading column.

Reading its numbers

Incremental Sort  (cost=1.89..87206.24 rows=1000000 width=34) (actual time=0.665..1.355 rows=100.00 loops=1)
  Sort Key: customer_id, created_at
  Presorted Key: customer_id
  Full-sort Groups: 3  Sort Method: quicksort  Average Memory: 27kB  Peak Memory: 27kB

• Sort Key: the full order requested.
• Presorted Key: the leading columns that arrive already sorted.
• Full-sort Groups: batches it sorted on the whole sort key. When groups are small, it gathers rows from several groups into one batch (here three batches covered the 101 rows it read) and sorts them together.
• Pre-sorted Groups: when one group turns out to be large, it switches to sorting that group on the remaining columns only. This line appears only if that happened, for example: Pre-sorted Groups: 2 Sort Methods: top-N heapsort, quicksort Average Memory: 189kB Peak Memory: 189kB.
• Sort Method, Average Memory, Peak Memory: per batch. If a batch spills you’ll see Disk figures too.
• The child’s rows: how much input it actually read. rows=101.00 under a LIMIT 100 means it read one row past the limit to be sure the last group was complete.

When it’s a problem

It helps when groups are small. It doesn’t when the presorted column has few distinct values:

• Huge groups. With ORDER BY status, created_at and an index on status alone, each status is one group of hundreds of thousands of rows. To return the first rows of a group, it must read and sort the whole group. In the example below, LIMIT 2100 read all 500,000 rows. Fix: an index on the full sort key, (status, created_at), so no sort is needed at all.
• Bad estimates of group size. The planner chooses it based on the estimated number of distinct values in the presorted column. If those statistics are stale, run ANALYZE.
• To compare plans, SET enable_incremental_sort = off in your session shows the cost of a full sort instead.

Example

PostgreSQL 18.6, default settings:

CREATE SCHEMA seo_explain;
SET search_path = seo_explain;

CREATE TABLE orders (
  id          bigint PRIMARY KEY,
  customer_id int NOT NULL,
  status      text NOT NULL,
  total       numeric(10,2) NOT NULL,
  created_at  timestamptz NOT NULL
);
INSERT INTO orders
SELECT i,
       1 + (i::bigint * 7919) % 50000,
       CASE WHEN i % 100 < 90 THEN 'shipped'
            WHEN i % 100 < 97 THEN 'pending'
            ELSE 'refunded' END,
       round(((i * 37) % 100000) / 100.0, 2),
       timestamptz '2024-01-01' + i * interval '1 minute'
FROM generate_series(1, 1000000) AS i;
CREATE INDEX orders_customer_id_idx ON orders (customer_id);
CREATE INDEX orders_created_at_idx ON orders (created_at);
VACUUM ANALYZE orders;

(Our test table also had a foreign key to customers; it doesn’t change these plans.)

Orders by customer, oldest first within each customer, first 100:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders ORDER BY customer_id, created_at LIMIT 100;

Limit  (cost=1.89..10.61 rows=100 width=34) (actual time=0.665..1.361 rows=100.00 loops=1)
  Buffers: shared hit=83 read=27
  ->  Incremental Sort  (cost=1.89..87206.24 rows=1000000 width=34) (actual time=0.665..1.355 rows=100.00 loops=1)
        Sort Key: customer_id, created_at
        Presorted Key: customer_id
        Full-sort Groups: 3  Sort Method: quicksort  Average Memory: 27kB  Peak Memory: 27kB
        Buffers: shared hit=83 read=27
        ->  Index Scan using orders_customer_id_idx on orders  (cost=0.42..52136.34 rows=1000000 width=34) (actual time=0.036..1.322 rows=101.00 loops=1)
              Index Searches: 1
              Buffers: shared hit=77 read=27
Planning:
  Buffers: shared hit=4
Planning Time: 0.026 ms
Execution Time: 1.369 ms

101 rows read out of a million, 1.4 ms. A full sort would have read and sorted all 1,000,000 rows to return the first 100. PostgreSQL 14 produced the same plan (Full-sort Groups: 3, 28 kB).

When groups are large

A tickets table where only two status values exist, and an index on (status, id):

CREATE TABLE tickets (
  id         bigint PRIMARY KEY,
  status     text NOT NULL,
  subject    text NOT NULL,
  created_at timestamptz NOT NULL
);
INSERT INTO tickets
SELECT i, CASE WHEN i <= 2000 THEN 'open' ELSE 'closed' END, 'Ticket ' || i,
       timestamptz '2025-01-01' + i * interval '2 minutes'
FROM generate_series(1, 500000) AS i;
CREATE INDEX tickets_status_id_idx ON tickets (status, id);
VACUUM ANALYZE tickets;

SET max_parallel_workers_per_gather = 0;  -- keeps the plan short
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM tickets WHERE status IN ('open', 'closed')
ORDER BY status DESC, created_at DESC LIMIT 2100;

Limit  (cost=26892.30..27031.96 rows=2100 width=35) (actual time=0.594..101.317 rows=2100.00 loops=1)
  Buffers: shared hit=4969 read=1122
  ->  Incremental Sort  (cost=26892.30..60008.27 rows=497925 width=35) (actual time=0.593..101.190 rows=2100.00 loops=1)
        Sort Key: status DESC, created_at DESC
        Presorted Key: status
        Full-sort Groups: 2  Sort Method: quicksort  Average Memory: 29kB  Peak Memory: 29kB
        Pre-sorted Groups: 2  Sort Methods: top-N heapsort, quicksort  Average Memory: 189kB  Peak Memory: 189kB
        Buffers: shared hit=4969 read=1122
        ->  Index Scan Backward using tickets_status_id_idx on tickets  (cost=0.42..23818.61 rows=497925 width=35) (actual time=0.040..50.358 rows=500000.00 loops=1)
              Index Cond: (status = ANY ('{open,closed}'::text[]))
              Index Searches: 1
              Buffers: shared hit=4963 read=1122
Planning:
  Buffers: shared hit=118 read=3
Planning Time: 0.296 ms
Execution Time: 101.397 ms

The 2,000 open tickets weren’t enough for LIMIT 2100, so it had to take 100 rows from the closed group, and to know which 100 are newest it read and sorted all 498,000 of them. An index on (status, created_at) would return the rows in the final order with no sort.

In Inlet

Inlet draws EXPLAIN ANALYZE as a tree and highlights the slowest step and badly misestimated row counts, so a scan that reads half a million rows under a LIMIT stands out.