Incremental Sort

说明

对具有相同预排序键前缀的行组排序，以扩展已有顺序。

核心节点标签

T_IncrementalSort

结构化 EXPLAIN 节点类型

Incremental Sort

输入

一个部分有序的子计划

输出

按完整排序键排序的元组

执行器初始化函数

ExecInitIncrementalSort

内存机制

tuplesort

EXPLAIN 名称与属性

结构化格式使用上述 Node Type。文本格式名称还可能包含操作、策略、连接类型、扫描方向或聚合阶段属性。

此源码记录的文本名称：Incremental Sort.

并行感知与并行安全是不同的计划属性。在并行工作进程内运行的节点不一定是并行感知节点。

内存与临时存储

此节点将 work_mem 传给 tuplesort。排序可使用内存或临时文件；实际方法和空间用量取决于输入及计划。

增量排序可能比普通排序更高效，尤其对于大型数据集，因为它减少了每次排序的数据量，更可能放入 work_mem，从而避免落盘。但其主要优势是在整个数据集排序完成之前就能开始输出行，这对带 LIMIT 的查询尤其有利。

增量排序可能处理许多排序批次，因此每次结束一个排序状态时都要记录 tuplesort 统计信息。这些汇总数据随后用于 EXPLAIN ANALYZE 输出。

并行执行与运行信息采集

以下源码回调可以协调执行或收集工作进程的测量数据。回调存在不代表该节点普遍支持共享并行扫描或共享状态。

此构建的回调：ExecIncrementalSortEstimate, ExecIncrementalSortInitializeDSM, ExecIncrementalSortInitializeWorker, ExecIncrementalSortRetrieveInstrumentation.

同版本手册说明

如果计划中的某一部分已经保证了所需排序键前缀的顺序，规划器也可能改用 Incremental Sort 步骤：

本版手册中的示例

示例摘自 PostgreSQL 18.6 手册；本百科未实际执行此示例。

如果计划中的某一部分已经保证了所需排序键前缀的顺序，规划器也可能改用 Incremental Sort 步骤：

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)

执行器实现说明

nodeIncrementalSort.c：处理关系增量排序的例程。

增量排序是多键排序的一种优化形式，适用于输入已按排序键前缀排好序的情况。例如，要求按 (key1, key2 ... keyN) 排序，而输入已按 (key1, key2 ... keyM) 排序，且 M < N，则可将输入划分为 (key1, ... keyM) 相等的分组，只对剩余列排序。

考虑以下示例：输入元组由两个整数 (X, Y) 组成，已经按 X 预排序，而现在需要同时按 X 和 Y 排序。输入元组如下。

增量排序算法会按 X 相等将输入拆分为以下各组，再分别按 Y 排序：

对这些分组分别排序后，将其拼接起来，即可得到下面按要求同时按 X 和 Y 排序的结果：

核心源码中的 EXPLAIN 标识

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

相关条目

• EXPLAIN
• 使用 EXPLAIN
• 并行计划
• enable_incremental_sort
• work_mem

文档与源码

• 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

版本比较

PostgreSQL 12 → 13: 新增收录。

以下差异保留原始字段名与英文源描述。

--- PostgreSQL 12
+++ PostgreSQL 13
@@ -1 +1,16 @@
-该版未收录
+{
+  "initializer": "ExecInitIncrementalSort",
+  "memory_mechanism": "tuplesort",
+  "node_tag": "T_IncrementalSort",
+  "parallel_callbacks": [
+    "ExecIncrementalSortEstimate",
+    "ExecIncrementalSortInitializeDSM",
+    "ExecIncrementalSortInitializeWorker",
+    "ExecIncrementalSortRetrieveInstrumentation"
+  ],
+  "partial_modes": [],
+  "strategies": [],
+  "text_names": [
+    "Incremental Sort"
+  ]
+}

比较已记录的接口与属性，排除来源指纹和构建元数据。某个样本中没有记录，不能据此判断实际引入或移除的版本。

相关条目

• SortSort