Incremental Sort

Description

Extends an existing ordering by sorting groups that share the presorted key prefix.

Core node tag

T_IncrementalSort

Structured EXPLAIN Node Type

Incremental Sort

Inputs

One partly ordered child plan

Output

Tuples ordered by the full sort key

Executor initializer

ExecInitIncrementalSort

Memory mechanism

tuplesort

EXPLAIN names and attributes

Structured formats use the Node Type above. Text-format spellings can also include operation, strategy, join type, scan direction or aggregation-stage attributes.

Text names recorded by this source: Incremental Sort.

Parallel-aware and parallel-safe are different plan properties. A node running inside a parallel worker is not necessarily a parallel-aware node.

Memory and temporary storage

The node passes work_mem to tuplesort. Sorting can use memory or temporary files; the actual method and space use depend on the input and plan.

Incremental sort may be more efficient than plain sort, particularly on large datasets, as it reduces the amount of data to sort at once, making it more likely it fits into work_mem (eliminating the need to spill to disk). But the main advantage of incremental sort is that it can start producing rows early, before sorting the whole dataset, which is a significant benefit especially for queries with LIMIT.

Because incremental sort processes (potentially many) sort batches, we need to capture tuplesort stats each time we finalize a sort state. This summary data is later used for EXPLAIN ANALYZE output.

Parallel execution and instrumentation

The source callbacks below can coordinate execution or collect worker instrumentation. Their presence is not a blanket claim that this node supports a shared parallel scan or shared state.

Callbacks in this build: ExecIncrementalSortEstimate, ExecIncrementalSortInitializeDSM, ExecIncrementalSortInitializeWorker, ExecIncrementalSortRetrieveInstrumentation.

Same-version manual discussion

If a part of the plan guarantees an ordering on a prefix of the required sort keys, then the planner may instead decide to use an Incremental Sort step:

Examples from this manual build

Example copied from the PostgreSQL 18.6 manual; it was not executed for this collection.

If a part of the plan guarantees an ordering on a prefix of the required sort keys, then the planner may instead decide to use an Incremental Sort step:

EXPLAIN SELECT * FROM tenk1 ORDER BY hundred, ten LIMIT 100;

                                              QUERY PLAN
------------------------------------------------------------------------------------------------
 Limit  (cost=19.35..39.49 rows=100 width=244)
   ->  Incremental Sort  (cost=19.35..2033.39 rows=10000 width=244)
         Sort Key: hundred, ten
         Presorted Key: hundred
         ->  Index Scan using tenk1_hundred on tenk1  (cost=0.29..1574.20 rows=10000 width=244)

Executor implementation notes

nodeIncrementalSort.c Routines to handle incremental sorting of relations.

Incremental sort is an optimized variant of multikey sort for cases when the input is already sorted by a prefix of the sort keys. For example when a sort by (key1, key2 ... keyN) is requested, and the input is already sorted by (key1, key2 ... keyM), M < N, we can divide the input into groups where keys (key1, ... keyM) are equal, and only sort on the remaining columns.

Consider the following example. We have input tuples consisting of two integers (X, Y) already presorted by X, while it's required to sort them by both X and Y. Let input tuples be following.

An incremental sort algorithm would split the input into the following groups, which have equal X, and then sort them by Y individually:

After sorting these groups and putting them altogether, we would get the following result which is sorted by X and Y, as requested:

EXPLAIN identity in core source

case T_IncrementalSort:
			pname = sname = "Incremental Sort";
			break;

Related entries

• EXPLAIN
• Using EXPLAIN
• Parallel plans
• enable_incremental_sort
• work_mem

Documentation and source

• src/backend/commands/explain.c:1525
• src/backend/executor/execProcnode.c:325
• src/backend/executor/nodeIncrementalSort.c
• src/include/nodes/plannodes.h
• src/backend/utils/sort/tuplesort.c
• PostgreSQL 18.6 · using-explain

Compare versions

PostgreSQL 17 → 18: unchanged.

Compares recorded interfaces and attributes. Source fingerprints and build metadata are excluded; an absent sample is not proof of the introduction or removal release.

Related entries

• SortSort