增量排序

本文介绍 YMatrix 的增量排序能力，包括它的使用条件、配置方式、执行计划识别方法，以及不生效时如何排查。

适用版本：YMatrix 6.8.6 及以上

什么是增量排序

普通排序需要读取全部输入后再排序。当输入本身已经按查询需要的部分排序键有序时，增量排序会把输入按这个已排序前缀切成若干组，只对组内剩余键排序，从而减少比较次数和排序需要占用的内存。

YMatrix 的增量排序由两层配合完成：

层次	作用
PostgreSQL Planner	判断输入是否提供了可用的排序前缀，决定是否生成 `Incremental Sort` 节点
向量化执行器	把满足条件的增量排序转换为 `MxVSort` 的 SubKeySorter 实现，按批次处理数据

Planner 决定"要不要用增量排序"，向量化执行器决定"用哪种实现"。两者都通过，才会得到向量增量排序。

使用条件

增量排序要生效，需要同时满足：

查询带 ORDER BY，且排序键中至少有一个键已经被输入计划保证有序。
该前缀的顺序满足查询要求，包括排序方向、NULLS FIRST / NULLS LAST 以及 collation。
使用 PostgreSQL Planner。ORCA 优化器下请以实际计划为准。
相关开关已打开，且成本估算认为增量排序比普通排序更划算。

有序前缀的常见来源有：索引顺序、MARS3 表的物理排序键，以及下层排序节点输出的顺序。表上建有索引不等于上层排序一定会用到该索引的顺序，必须以实际执行计划为准。

配置

增量排序由两个参数控制，默认都开启：

参数	默认值	作用
`enable_incremental_sort`	`on`	是否允许 Planner 生成 `Incremental Sort` 计划
`matrix.enable_mxv_subkey_sort`	`on`	是否允许 `MxVSort` 使用 SubKeySorter，以及原生增量排序是否允许转换为向量增量排序

matrix.enable_mxv_subkey_sort 在 6.8 中已存在并默认开启；6.8.6 新增的是 Planner 生成增量排序计划的能力（enable_incremental_sort），以及把生成的原生增量排序转换为向量增量排序。

常用组合如下（组合前三项已假设向量化执行与向量排序已开启）：

使用目的	`enable_incremental_sort`	`matrix.enable_mxv_subkey_sort`	预期行为
允许向量增量排序	`on`	`on`	条件满足时使用向量增量排序；无法向量化时保留原生增量排序
使用原生增量排序，仍允许向量扫描	`on`	`off`	排序节点保留原生 `Incremental Sort`，下层扫描仍可向量化
关闭增量排序	`off`	`off`	不生成 `Incremental Sort`，普通排序仍可向量化

日常使用前，先确认使用 PostgreSQL Planner 并开启向量化：

SET optimizer = off;
SET matrix.enable_mxvector = on;
SET matrix.enable_mxv_sort = on;

再按需选择上表中的一组配置。也可以使用 SET LOCAL，在事务结束时自动恢复。

注意！
enable_incremental_sort=off 不能单独用于关闭所有向量增量排序。普通 MxVSort 在特定输入下仍会识别下层提供的排序前缀，详见限制与注意事项。

示例

以下示例创建一个 MARS3 表，用 mars3_btree 索引提供一个排序前缀，然后比较不同配置下的执行计划。示例使用事务包裹，结束时 ROLLBACK 即可撤销对象和设置。

BEGIN;
CREATE SCHEMA incremental_sort_demo;
SET LOCAL search_path = incremental_sort_demo, public;
SET LOCAL optimizer = off;
SET LOCAL matrix.enable_mxvector = on;
SET LOCAL matrix.enable_mxv_sort = on;
SET LOCAL statement_timeout = '60s';

CREATE TABLE events(id int, a int, b int) USING mars3
WITH (compress_threshold=65535, mars3options='prefer_load_mode=normal')
DISTRIBUTED BY(id);

INSERT INTO events
SELECT g, (g-1)/100, 12001-g FROM generate_series(1,12000) g;
CREATE INDEX events_a ON events USING mars3_btree(a);
ANALYZE events;

a 每 100 行取一个新值，共 120 个取值；b 随 id 增大而减小。索引提供 a 的顺序，而查询要求 ORDER BY a, b, id，因此 a 可以作为前缀。

mars3.enable_btree_inorderscan 控制 mars3_btree 是否提供有序索引路径，默认关闭；不开启时，索引扫描不会带上排序信息，增量排序也就无从利用。为便于观察，示例中临时压低其他路径的竞争力。这些设置不属于日常配置：

SET LOCAL enable_seqscan = off;
SET LOCAL enable_bitmapscan = off;
SET LOCAL enable_sort = off;
SET LOCAL mars3.enable_btree_inorderscan = on;

向量增量排序

SET LOCAL enable_incremental_sort = on;
SET LOCAL matrix.enable_mxv_subkey_sort = on;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;

Custom Scan (MxVLimit)
  ->  Custom Scan (MxVMotion) Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Custom Scan (MxVLimit)
              ->  Custom Scan (MxVSort)
                    Sort Key: a, b, id
                    Common Prefix Order Key: a
                    Sort Method: subkey sort
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

Common Prefix Order Key 和 Sort Method: subkey sort 是向量增量排序的标志。

原生增量排序加向量扫描

SET LOCAL enable_incremental_sort = on;
SET LOCAL matrix.enable_mxv_subkey_sort = off;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;

Limit
  ->  Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Limit
              ->  Incremental Sort
                    Sort Key: a, b, id
                    Presorted Key: a
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

排序节点保留为原生 Incremental Sort，输入仍然是向量化的索引扫描。关闭的只是向量化增量排序实现，不是向量扫描。

关闭增量排序

SET LOCAL enable_incremental_sort = off;
SET LOCAL matrix.enable_mxv_subkey_sort = off;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, a, b FROM events ORDER BY a, b, id LIMIT 50;

Custom Scan (MxVLimit)
  ->  Custom Scan (MxVMotion) Gather Motion 3:1  (slice1; segments: 3)
        Merge Key: a, b, id
        ->  Custom Scan (MxVLimit)
              ->  Custom Scan (MxVSort)
                    Sort Key: a, b, id
                    Sort Method: top-k sort
                    ->  Custom Scan (MxVIndexScan) using events_a on events
Optimizer: Postgres-based planner

MxVSort 仍会出现，但 Sort Method 为 top-k sort 或 quicksort，没有 Common Prefix Order Key，说明走的还是普通排序。扫描用了索引，不代表上层排序利用了索引顺序。

示例结束后清理：

ROLLBACK;

如何判断是否生效

在 EXPLAIN 输出中按以下特征区分：

实际实现	关键标志
原生增量排序	`Incremental Sort` 节点，带 `Presorted Key`
向量增量排序	`MxVSort` 节点，带 `Common Prefix Order Key`，且 `Sort Method: subkey sort`
普通向量排序	`MxVSort` 节点，`Sort Method` 为 `top-k sort` 或 `quicksort`

只看节点名称无法判断：MxVSort 在普通排序和向量增量排序下都会出现。

以上示例输出取自测试环境，行数会随数据分布、统计信息、成本估算和版本变化。上表是在 3 个 Segment 上分布约 12000 行，单个 Segment 的扫描行数在 4000 上下浮动属于正常现象，不要用示例里的行数推算性能倍数。

限制与注意事项

有序前缀必须来自计划节点实际报告的顺序。 当前普通 MxVSort 不会从 MxVIndexScan 直接获得索引提供的排序前缀。若要利用索引顺序，需要 Planner 生成 Incremental Sort 节点并把前缀传给向量排序。因此仅打开 SubKeySorter 而不生成增量排序计划，不会让 MxVIndexScan → MxVSort 这条路径用上索引前缀。
enable_incremental_sort=off 不等于关闭全部向量增量排序。 当下层是能够报告顺序的 MxVSort 时，上层普通 MxVSort 仍可能识别该前缀并使用 SubKeySorter。
开启开关不等于一定使用。 最终由成本估算决定，通常需要输入确实提供有序前缀，且前缀组的规模足够小。
前缀组大小直接影响收益。 如果前缀取值几乎不重复（每组只有一两行），增量排序的收益接近普通排序，额外分组开销可能使耗时更高。
分布式执行下只保证 Segment 内有序。 各 Segment 分别完成增量排序后，由带 Merge Key 的 Gather Motion 合并。Segment 节点显示的 actual rows 是单个 Segment 的量，不是全表合计。
LIMIT 不是必要条件。 它有机会让扫描提前结束，但实际读取量还受前缀组大小、过滤条件、向量批次和分布式执行影响，不保证每次都少读。
无法转换时保留原生实现。 当前向量转换要求存在对应的 DeltaFilter、使用受支持的默认排序操作符，且 collation 为确定性。不满足时不会报错，而是退回原生 Incremental Sort。

不生效时的排查顺序

EXPLAIN 中是否为 Optimizer: Postgres-based planner。
输入路径是否真的提供了查询需要的排序前缀，而不只是表上存在相关索引。
统计信息是否已更新（ANALYZE），成本估算是否倾向了其他路径。
向量化总开关、向量排序开关、SubKeySorter 开关是否都已打开，子计划是否可向量化。
前缀比较是否满足转换条件：DeltaFilter、排序操作符、collation 确定性。

比较两种实现时，请在同一查询上分别使用"向量增量排序"与"原生增量排序"两组配置，确认 Sort Method 之后再对比耗时。把"关闭增量排序"与"开启增量排序"相比，得到的是"普通排序 vs 增量排序"的差异，不是两种增量排序实现的对比。

验证清单

[ ] EXPLAIN 显示 Optimizer: Postgres-based planner
[ ] 增量排序节点带 Presorted Key 或 Common Prefix Order Key
[ ] 向量增量排序的 Sort Method 为 subkey sort
[ ] 排序键的方向、NULLS 位置与所用索引或排序键定义一致
[ ] 已执行 ANALYZE，统计信息不是陈旧值
[ ] 在真实数据量下对比过开启与关闭的实际耗时，而不是只看计划

← 上一篇

向量化最佳实践

流计算场景实践

简体中文 English Русский