{"Entry":{"collection":"plan","key":"incremental-sort","name":"Incremental Sort","aliases":["Incremental Sort","IncrementalSort","T_IncrementalSort"],"metadata":{"aliases":["Incremental Sort","IncrementalSort","T_IncrementalSort"],"category":"Ordering","content_hash":"db16888ef5f851a3f09b3750ff12727ff7020771907c13664945478dfc3ccae0","derived_content_hash":"a48915536e90f0d170e86b2a60243a369bc52e16ec777f55bf1c029012ef3fe5","imported_at":"2026-09-30T00:40:44.174939+08:00","name":"Incremental Sort","name_zh":"IncrementalSort","slug":"incremental-sort","summary":"Extends an existing ordering by sorting groups that share the presorted key prefix."}},"Definition":{"Collection":"plan","Key":"incremental-sort","SourceDatabase":"center","Version":"18","SourceTable":"plan_node","SourceKey":"incremental-sort","SourceRevision":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","Facts":{"comparison_data":{"initializer":"ExecInitIncrementalSort","memory_mechanism":"tuplesort","node_tag":"T_IncrementalSort","parallel_callbacks":["ExecIncrementalSortEstimate","ExecIncrementalSortInitializeDSM","ExecIncrementalSortInitializeWorker","ExecIncrementalSortRetrieveInstrumentation"],"partial_modes":[],"strategies":[],"text_names":["Incremental Sort"]},"comparison_hash":"28d8e33452af10dcac50fa98fa4c5c6f639be663ae15b475f003e7c287e678f4","description":["Extends an existing ordering by sorting groups that share the presorted key prefix."],"description_zh":"对具有相同预排序键前缀的行组排序，以扩展已有顺序。","description_zh_html":"\u003cp\u003e对具有相同预排序键前缀的行组排序，以扩展已有顺序。\u003c/p\u003e\u003cp\u003e核心节点标识：\u003ccode\u003eT_IncrementalSort\u003c/code\u003e；EXPLAIN 名称：\u003ccode\u003eIncremental Sort\u003c/code\u003e。\u003c/p\u003e\u003cp\u003e本版本源码中的并行执行或观测回调：\u003ccode\u003eExecIncrementalSortEstimate, ExecIncrementalSortInitializeDSM, ExecIncrementalSortInitializeWorker, ExecIncrementalSortRetrieveInstrumentation\u003c/code\u003e。回调的存在不表示该节点必然支持共享并行扫描；在并行工作进程中执行也不等于具有并行感知能力。\u003c/p\u003e\u003ch3\u003e同版本中文手册节选\u003c/h3\u003e\u003cp\u003e\n    查询计划的结构是一棵由\u003cem class=\"firstterm\"\u003e计划节点\u003c/em\u003e组成的树。树的最底层是扫描节点，它们从表中返回原始行。不同的表访问方法对应不同类型的扫描节点，例如顺序扫描、索引扫描和位图索引扫描。也有一些并非表的行来源，例如 \u003ccode class=\"literal\"\u003eVALUES\u003c/code\u003e 子句和 \u003ccode class=\"literal\"\u003eFROM\u003c/code\u003e 中的返回集合函数，它们也各自有对应的扫描节点类型。如果查询需要对原始行执行连接、聚合、排序或其他操作，那么扫描节点之上还会出现额外的节点来完成这些操作。同样，这些操作通常不止一种实现方式，因此这里也会出现不同的节点类型。\u003ccode class=\"command\"\u003eEXPLAIN\u003c/code\u003e 会为计划树中的每个节点输出一行，显示基本节点类型以及规划器对该计划节点执行代价的估计值。还可能出现相对节点摘要行缩进的附加行，用来显示该节点的更多属性。第一行，也就是最顶层节点的摘要行，给出了整个计划的估计总执行代价；规划器力图最小化的正是这个数字。\n   \u003c/p\u003e\u003cp\u003e\n    下面是一个简单的示例，仅用于展示输出的样子：\n\n\u003c/p\u003e\u003cp\u003e\n    由于这个查询没有 \u003ccode class=\"literal\"\u003eWHERE\u003c/code\u003e 子句，它必须扫描表中的所有行，因此规划器选择了一个简单的顺序扫描计划。圆括号中的数字从左到右依次表示：\n\n    \u003c/p\u003e\u003cp\u003e\n    这些代价使用由规划器代价参数决定的任意单位来衡量（见\u003ca class=\"xref\" href=\"/zh/docs/18/runtime-config-query.html#RUNTIME-CONFIG-QUERY-CONSTANTS\"\u003e第 19.7.2 节\u003c/a\u003e）。传统上通常以磁盘页读取作为代价单位；也就是说，惯例上将 \u003ca class=\"xref\" href=\"/zh/docs/18/runtime-config-query.html#GUC-SEQ-PAGE-COST\"\u003eseq_page_cost\u003c/a\u003e 设为 \u003ccode class=\"literal\"\u003e1.0\u003c/code\u003e，其他代价参数都相对它来设定。本节中的示例都使用默认代价参数。\n   \u003c/p\u003e\u003cp\u003e\u003ca href=\"/zh/docs/18/using-explain.html#USING-EXPLAIN-BASICS\"\u003e查看完整中文手册与上下文\u003c/a\u003e。\u003c/p\u003e\u003cp\u003e本页开头的中文说明为 PG.CENTER 对编辑说明的翻译；手册节选保留对应版本中文文档原文。源码信息及手册示例不代表重新进行过运行测试。\u003c/p\u003e","evidence_kind":"source and documentation","explain_names":["Incremental Sort"],"explain_prefixes":["Parallel","Async"],"facts":[{"label":"Core node tag","value":"T_IncrementalSort"},{"label":"Structured EXPLAIN Node Type","value":"Incremental Sort"},{"label":"Inputs","value":"One partly ordered child plan"},{"label":"Output","value":"Tuples ordered by the full sort key"},{"label":"Executor initializer","value":"ExecInitIncrementalSort"},{"label":"Memory mechanism","value":"tuplesort"}],"facts_zh":[{"label":"核心节点标签","value":"T_IncrementalSort"},{"label":"结构化 EXPLAIN 节点类型","value":"Incremental Sort"},{"label":"输入","value":"一个部分有序的子计划"},{"label":"输出","value":"按完整排序键排序的元组"},{"label":"执行器初始化函数","value":"ExecInitIncrementalSort"},{"label":"内存机制","value":"tuplesort"}],"memory":{"description":"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.","evidence":[{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/executor/nodeIncrementalSort.c","path":"src/backend/executor/nodeIncrementalSort.c","sha256":"9fd15ce79cd3dd5c131c5bfb322039213cba9232fdfaa5b53e5f40e7d17195cf","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/utils/sort/tuplesort.c","path":"src/backend/utils/sort/tuplesort.c","sha256":"509d4cef598613bbf0725f697e1e1e33f3dfc8debed20169a6c4bf1ac9e5c2e3","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"}],"mechanism":"tuplesort","source_notes":["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."]},"node_tag":"T_IncrementalSort","parallel_callbacks":["ExecIncrementalSortEstimate","ExecIncrementalSortInitializeDSM","ExecIncrementalSortInitializeWorker","ExecIncrementalSortRetrieveInstrumentation"],"partial_modes":[],"related":[{"label":"EXPLAIN","url":"/wiki/sql/explain/?v=18"},{"label":"Using EXPLAIN","url":"/docs/18/using-explain.html"},{"label":"Parallel plans","url":"/docs/18/parallel-plans.html"},{"label":"enable_incremental_sort","url":"/wiki/guc/enable_incremental_sort/?v=18"},{"label":"work_mem","url":"/wiki/guc/work_mem/?v=18"}],"release":{"channel":"stable","label":"18.6","major":"18","ref":"PostgreSQL 18.6 source archive","revision":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","source_snapshot_utc":"","source_url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},"runtime_verified":false,"sections":[{"paragraphs":["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."],"title":"EXPLAIN names and attributes"},{"paragraphs":["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."],"title":"Memory and temporary storage"},{"paragraphs":["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."],"title":"Parallel execution and instrumentation"},{"paragraphs":["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:"],"title":"Same-version manual discussion"},{"blocks":[{"code":"EXPLAIN SELECT * FROM tenk1 ORDER BY hundred, ten LIMIT 100;\n\n                                              QUERY PLAN\n------------------------------------------------------------------------------------------------\n Limit  (cost=19.35..39.49 rows=100 width=244)\n   -\u003e  Incremental Sort  (cost=19.35..2033.39 rows=10000 width=244)\n         Sort Key: hundred, ten\n         Presorted Key: hundred\n         -\u003e  Index Scan using tenk1_hundred on tenk1  (cost=0.29..1574.20 rows=10000 width=244)","paragraphs":["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:"],"source":{"label":"PostgreSQL 18.6 · using-explain","path":"using-explain.html","sha256":"60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed","url":"/docs/18/using-explain.html#USING-EXPLAIN-BASICS"}}],"title":"Examples from this manual build"},{"paragraphs":["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 \u003c 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:"],"title":"Executor implementation notes"},{"code":"case T_IncrementalSort:\n\t\t\tpname = sname = \"Incremental Sort\";\n\t\t\tbreak;","title":"EXPLAIN identity in core source"}],"sections_zh":[{"paragraphs":["结构化格式使用上述 Node Type。文本格式名称还可能包含操作、策略、连接类型、扫描方向或聚合阶段属性。","此源码记录的文本名称：Incremental Sort.","并行感知与并行安全是不同的计划属性。在并行工作进程内运行的节点不一定是并行感知节点。"],"title":"EXPLAIN 名称与属性"},{"paragraphs":["此节点将 work_mem 传给 tuplesort。排序可使用内存或临时文件；实际方法和空间用量取决于输入及计划。","增量排序可能比普通排序更高效，尤其对于大型数据集，因为它减少了每次排序的数据量，更可能放入 work_mem，从而避免落盘。但其主要优势是在整个数据集排序完成之前就能开始输出行，这对带 LIMIT 的查询尤其有利。","增量排序可能处理许多排序批次，因此每次结束一个排序状态时都要记录 tuplesort 统计信息。这些汇总数据随后用于 EXPLAIN ANALYZE 输出。"],"title":"内存与临时存储"},{"paragraphs":["以下源码回调可以协调执行或收集工作进程的测量数据。回调存在不代表该节点普遍支持共享并行扫描或共享状态。","此构建的回调：ExecIncrementalSortEstimate, ExecIncrementalSortInitializeDSM, ExecIncrementalSortInitializeWorker, ExecIncrementalSortRetrieveInstrumentation."],"title":"并行执行与运行信息采集"},{"paragraphs":["如果计划中的某一部分已经保证了所需排序键前缀的顺序，规划器也可能改用 Incremental Sort 步骤："],"title":"同版本手册说明"},{"blocks":[{"code":"EXPLAIN SELECT * FROM tenk1 ORDER BY hundred, ten LIMIT 100;\n\n                                              QUERY PLAN\n------------------------------------------------------------------------------------------------\n Limit  (cost=19.35..39.49 rows=100 width=244)\n   -\u003e  Incremental Sort  (cost=19.35..2033.39 rows=10000 width=244)\n         Sort Key: hundred, ten\n         Presorted Key: hundred\n         -\u003e  Index Scan using tenk1_hundred on tenk1  (cost=0.29..1574.20 rows=10000 width=244)","paragraphs":["示例摘自 PostgreSQL 18.6 手册；本百科未实际执行此示例。","如果计划中的某一部分已经保证了所需排序键前缀的顺序，规划器也可能改用 Incremental Sort 步骤："],"source":{"label":"PostgreSQL 18.6 · using-explain","path":"using-explain.html","sha256":"60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed","url":"/docs/18/using-explain.html#USING-EXPLAIN-BASICS"}}],"title":"本版手册中的示例"},{"paragraphs":["nodeIncrementalSort.c：处理关系增量排序的例程。","增量排序是多键排序的一种优化形式，适用于输入已按排序键前缀排好序的情况。例如，要求按 (key1, key2 ... keyN) 排序，而输入已按 (key1, key2 ... keyM) 排序，且 M \u003c N，则可将输入划分为 (key1, ... keyM) 相等的分组，只对剩余列排序。","考虑以下示例：输入元组由两个整数 (X, Y) 组成，已经按 X 预排序，而现在需要同时按 X 和 Y 排序。输入元组如下。","增量排序算法会按 X 相等将输入拆分为以下各组，再分别按 Y 排序：","对这些分组分别排序后，将其拼接起来，即可得到下面按要求同时按 X 和 Y 排序的结果："],"title":"执行器实现说明"},{"code":"case T_IncrementalSort:\n\t\t\tpname = sname = \"Incremental Sort\";\n\t\t\tbreak;","title":"核心源码中的 EXPLAIN 标识"}],"source_inventory":{"executor":"src/backend/executor/execProcnode.c","explain":"src/backend/commands/explain.c","implementation":"src/backend/executor/nodeIncrementalSort.c"},"sources":[{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/commands/explain.c:1525","line":1525,"path":"src/backend/commands/explain.c","sha256":"34c86d6070224a0e981efef51f79101d6d505e5874f1684ace183034bab14bb4","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/executor/execProcnode.c:325","line":325,"path":"src/backend/executor/execProcnode.c","sha256":"f8a06a3f539077249b20664b2812433db6d7bd12b2c0ca633525db43d06f112a","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/executor/nodeIncrementalSort.c","path":"src/backend/executor/nodeIncrementalSort.c","sha256":"9fd15ce79cd3dd5c131c5bfb322039213cba9232fdfaa5b53e5f40e7d17195cf","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/include/nodes/plannodes.h","path":"src/include/nodes/plannodes.h","sha256":"52422b327a8049fbbb20d8b96008a0fc0a6fafa60f7eff3c695d5b2e83830120","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/utils/sort/tuplesort.c","path":"src/backend/utils/sort/tuplesort.c","sha256":"509d4cef598613bbf0725f697e1e1e33f3dfc8debed20169a6c4bf1ac9e5c2e3","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"label":"PostgreSQL 18.6 · using-explain","path":"using-explain.html","sha256":"60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed","url":"/docs/18/using-explain.html#USING-EXPLAIN-BASICS"}],"strategies":[],"tables":[{"columns":[{"key":"label","label":"Text-format label"},{"key":"identity","label":"Structured node identity"}],"key":"explain-labels","rows":[{"identity":"Incremental Sort","label":"Incremental Sort"}],"title":"EXPLAIN labels in this source build"}],"tables_zh":[{"columns":[{"key":"label","label":"文本格式标签"},{"key":"identity","label":"结构化节点标识"}],"key":"explain-labels","rows":[{"identity":"Incremental Sort","label":"Incremental Sort"}],"title":"本构建中的 EXPLAIN 标签"}],"zh_from":{"authored_translation":"authored-translation-of-reviewed-guidance","body_sha256":"504920ce098796e7e5ad828aff39a1cad3565ca4784ddabfbf4e240df374dfa4","kind":"same-version-chinese-manual-with-authored-translation-of-reviewed-guidance","manual":{"anchor":"USING-EXPLAIN-BASICS","build_id":107,"extraction":"concept-introduction","fragment_sha256":"bc79b6f9c70f2b56968e08ea26d2c9ec3d395e425aca0594e227203daa0ad29b","locale":"zh-Hans","page_key":"using-explain.html","source_hash":"d2f749744b3ac5aa2eb0154f295e8163903cd20fcc130c74c6172cdf2ae3a9df","source_revision":"unknown:rendered-translation-baseline","translated_from_revision":null,"translation_revision":"git:b1b500221dbe5437cfca004d6b04d3f6e422765d;html-sha256:08e987a66af27b98444a8057c256314eafa13611a3fb9e888214fc436824244b","url":"/zh/docs/18/using-explain.html#USING-EXPLAIN-BASICS","version":"18"},"runtime_rerun":false,"source_facts_revision":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f"}},"ManualEvidence":{"release":{"channel":"stable","label":"18.6","major":"18","ref":"PostgreSQL 18.6 source archive","revision":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","source_snapshot_utc":"","source_url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},"sources":[{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/commands/explain.c:1525","line":1525,"path":"src/backend/commands/explain.c","sha256":"34c86d6070224a0e981efef51f79101d6d505e5874f1684ace183034bab14bb4","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/executor/execProcnode.c:325","line":325,"path":"src/backend/executor/execProcnode.c","sha256":"f8a06a3f539077249b20664b2812433db6d7bd12b2c0ca633525db43d06f112a","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/executor/nodeIncrementalSort.c","path":"src/backend/executor/nodeIncrementalSort.c","sha256":"9fd15ce79cd3dd5c131c5bfb322039213cba9232fdfaa5b53e5f40e7d17195cf","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/include/nodes/plannodes.h","path":"src/include/nodes/plannodes.h","sha256":"52422b327a8049fbbb20d8b96008a0fc0a6fafa60f7eff3c695d5b2e83830120","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"archive_sha256":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","label":"src/backend/utils/sort/tuplesort.c","path":"src/backend/utils/sort/tuplesort.c","sha256":"509d4cef598613bbf0725f697e1e1e33f3dfc8debed20169a6c4bf1ac9e5c2e3","url":"https://ftp.postgresql.org/pub/source/v18.6/postgresql-18.6.tar.bz2"},{"label":"PostgreSQL 18.6 · using-explain","path":"using-explain.html","sha256":"60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed","url":"/docs/18/using-explain.html#USING-EXPLAIN-BASICS"}]},"MeasuredEvidence":{"runtime_verified":false}},"Text":{"Collection":"plan","Key":"incremental-sort","SourceDatabase":"center","Version":"18","Locale":"en","Title":"Incremental Sort","Summary":"Extends an existing ordering by sorting groups that share the presorted key prefix.","BodyHTML":"\u003cp\u003eExtends an existing ordering by sorting groups that share the presorted key prefix.\u003c/p\u003e","SourceRevision":"555610c24d53e4316da5b7d3fc25c279d96856d5e0e23ee308c328c5fa881d9f","ContentHash":"2dd941f9c6d30ee3447e3d28b8db4d3441339836f45b0c60293719522d65d899","Payload":{"description":["Extends an existing ordering by sorting groups that share the presorted key prefix."],"related":[{"label":"EXPLAIN","url":"/wiki/sql/explain/?v=18"},{"label":"Using EXPLAIN","url":"/docs/18/using-explain.html"},{"label":"Parallel plans","url":"/docs/18/parallel-plans.html"},{"label":"enable_incremental_sort","url":"/wiki/guc/enable_incremental_sort/?v=18"},{"label":"work_mem","url":"/wiki/guc/work_mem/?v=18"}],"sections":[{"paragraphs":["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."],"title":"EXPLAIN names and attributes"},{"paragraphs":["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."],"title":"Memory and temporary storage"},{"paragraphs":["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."],"title":"Parallel execution and instrumentation"},{"paragraphs":["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:"],"title":"Same-version manual discussion"},{"blocks":[{"code":"EXPLAIN SELECT * FROM tenk1 ORDER BY hundred, ten LIMIT 100;\n\n                                              QUERY PLAN\n------------------------------------------------------------------------------------------------\n Limit  (cost=19.35..39.49 rows=100 width=244)\n   -\u003e  Incremental Sort  (cost=19.35..2033.39 rows=10000 width=244)\n         Sort Key: hundred, ten\n         Presorted Key: hundred\n         -\u003e  Index Scan using tenk1_hundred on tenk1  (cost=0.29..1574.20 rows=10000 width=244)","paragraphs":["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:"],"source":{"label":"PostgreSQL 18.6 · using-explain","path":"using-explain.html","sha256":"60040c30180093418a0affe56dd27dff9df2504b705b38039589e458bf5c31ed","url":"/docs/18/using-explain.html#USING-EXPLAIN-BASICS"}}],"title":"Examples from this manual build"},{"paragraphs":["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 \u003c 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:"],"title":"Executor implementation notes"},{"code":"case T_IncrementalSort:\n\t\t\tpname = sname = \"Incremental Sort\";\n\t\t\tbreak;","title":"EXPLAIN identity in core source"}],"tables":[{"columns":[{"key":"label","label":"Text-format label"},{"key":"identity","label":"Structured node identity"}],"key":"explain-labels","rows":[{"identity":"Incremental Sort","label":"Incremental Sort"}],"title":"EXPLAIN labels in this source build"}]}},"RequestedLocale":"en","Fallback":false,"Versions":["13","14","15","16","17","18","19","20"],"Locales":["en","zh-Hans"],"Signatures":null,"Spellings":null,"SQLState":null,"Evidence":null}