PostgreSQL 13 reuses order and compresses repeated index keys

Sorting a result that already has part of the required order repeats work unless the executor can preserve that order. PostgreSQL 13 introduces incremental sorting to exploit this case. The September 24 release announcement also introduces B-tree deduplication and parallel index vacuuming. Each change takes advantage of structure that already exists in a query or index, although the relevant structure differs for each operation.

The release's practical interest is in those preconditions. Partially ordered input gives incremental sort a useful starting point. Repeated indexed keys give deduplication something to share. Several eligible indexes give parallel VACUUM independent work. Understanding the precondition explains more than an expectation that a major-version upgrade should make every query or maintenance command faster.

I default to PostgreSQL for relational work and start query tuning with EXPLAIN. These changes fit that preference because their mechanisms can be explained in terms of the plan and physical objects involved. A performance claim becomes useful when it identifies which work disappears or moves, and what shape of data permits that change.

A sorted prefix divides the problem

The incremental sort implementation describes input sorted by the first part of a multicolumn ordering. If the requested order is by account and then event time, input already ordered by account can be divided into groups with the same account. Sorting each group by event time produces the complete requested order.

This works because the account ordering establishes the relationship between groups. Every row in one account group precedes every row in the next group under the requested account ordering. Work remains within a group, but there is no reason to rediscover the ordering between groups. The equal-prefix boundaries identify which rows must participate in each local sorting problem.

The executor uses a hybrid strategy because starting a fresh sort for every tiny group also has overhead. It initially collects a minimum batch and sorts on all keys. A heuristic can switch to processing a single prefix group and sorting only the remaining keys when that is beneficial. The implementation therefore adapts the basic idea to the cost of managing many small sorts.

The opportunity is particularly relevant when a query needs early output. Once a group has been processed, incremental sort can return its rows before sorting the entire input. That does not say it can return a correctly ordered row before considering the rest of that row's group. The group still defines the outstanding ordering work.

Existing index order is useful input

The index ordering documentation explains that B-tree scans can deliver sorted output. The planner can choose between using such an index and scanning the table followed by an explicit sort. For a large fraction of a table, sequential access with a sort can still be preferable to following an index.

An illustrative query requests an order with two keys. The limit asks for the first fifty rows in that order.

SELECT account_id, occurred_at
FROM account_events
ORDER BY account_id, occurred_at
LIMIT 50;

An index on account_id offers a potentially useful prefix. An index matching both order keys offers a different possibility, satisfying the requested order directly. Incremental sorting expands the choices between a fully matching index and a complete explicit sort. This example does not assert that the planner will select a particular plan without knowing the table and its statistics.

LIMIT makes the distinction consequential. A fully matching index can obtain early ordered rows directly. Partially ordered input requires the remaining sorting work, while unordered input must be examined sufficiently to establish which rows belong first. These alternatives explain why the presence of LIMIT alone cannot identify which access method will be fastest for a particular table.

Repeated keys share one physical representation

The B-tree implementation documentation defines a duplicate in terms of matching indexed key columns. Deduplication combines duplicate leaf tuples into a posting-list tuple. The key appears once, followed by an ordered array of tuple identifiers pointing to table rows. The logical contents remain the same while the physical index representation becomes smaller.

This is different from deleting duplicate rows in an application table. Every referenced row still needs its own identity. Sharing the key removes repeated index storage without merging the corresponding database rows. An index on a status column can therefore contain many rows with one status value while retaining references to each row independently.

Deduplication occurs lazily when an insertion cannot fit on an existing leaf page. It can postpone a page split by making repeated keys take less room. Index creation and rebuilding also form posting lists from sorted duplicate input. The documentation makes clear that this is an alternative representation of the same leaf contents, not an application-visible change in the meaning of an indexed equality comparison.

The amount of repeated key data matters. An index with little repetition offers little key storage to eliminate. A claim about the space saved therefore needs to identify the indexed columns and their values. Repetition in some unrelated table column does not establish that a particular index will benefit.

Deduplication has eligibility rules

The B-tree documentation lists restrictions where equal values can carry representation differences that must survive. It also excludes INCLUDE indexes. These restrictions matter when evaluating a covering index or a data type with multiple significant representations. Equality for searching does not always authorize discarding the distinct physical value representations in an index.

The CREATE INDEX reference exposes the deduplicate_items storage parameter, enabled by default. Disabling it controls future deduplication, and changing it off with ALTER INDEX does not expand existing posting lists back into ordinary tuples. That distinction separates a policy for future insertions from rewriting the physical representation already present.

I favour keeping that distinction explicit during index administration. A configuration change can alter how an operation behaves next without rewriting everything it previously produced. Looking at the parameter value alone cannot establish the current index's complete physical history. The documented behaviour gives an administrator a concrete explanation for existing posting lists after the setting changes.

Parallel VACUUM distributes work among indexes

The VACUUM reference shipped with PostgreSQL 13 limits the new parallel work to index vacuum and index cleanup phases. Only one worker can work on an index, and workers launch only when the table has at least two indexes. An eligible index must also exceed the configured minimum parallel index scan size.

An explicit request can bound the worker count. This command requests at most two parallel workers for the table.

VACUUM (PARALLEL 2) account_events;

The requested number is not a promise that all workers will run. Fewer workers, or none, may be available. Workers start before each relevant phase and exit at its end. The option cannot be combined with FULL. These limits explain why parallel VACUUM should be understood as parallel index maintenance within a vacuum operation.

For a table dominated by one large index, adding workers does not split that index's work across them. A table with several eligible indexes presents a different opportunity. The number and size of indexes therefore belong in an explanation of maintenance duration, alongside the requested worker limit. A worker setting without that context gives an incomplete account of the work available to distribute.

The routine vacuuming documentation explains the underlying reason maintenance remains necessary. Updates and deletes leave old row versions until they no longer need to remain visible. Standard vacuum makes their space available for reuse, while VACUUM FULL rewrites the table and takes an exclusive lock. Parallel index work belongs within that existing distinction between maintenance operations.

This is particularly relevant when the operational goal is described as reclaiming space. Reusable space inside a relation and a smaller file returned to the operating system are different outcomes. Choosing the maintenance operation requires knowing which outcome is intended. Parallel workers change how part of the selected operation runs, rather than redefining the result that operation is meant to produce.

The release consequently expands several independent planning and maintenance choices. An installation can examine each opportunity through the particular query and index involved, with no requirement that all of them apply to the same table.