github-fill

排序算子的生成与优化

更新时间：2026-04-16 00:11:36

查询中包含 limit 子句时，生成的执行计划中是否包含阻塞性算子对执行性能影响很大。排序作为常见的阻塞性算子，在查询中包含 ORDER BY 子句或生成的计划需要分配基于排序算法的算子时(如 MERGE DISTINCT/MERGE GROUP BY/MERGE JOIN等)，就需要尝试分配排序算子，以获取按指定 sort key 有序的(中间)结果集。为了避免产生不必要的排序算子，同时充分利用已经有序的中间结果集，优化器维护了一些序相关的信息并在尝试分配排序算子时进行了一些优化。

计划树中的序

在执行计划中，算子的输入序可能是有序的，对于基表扫描这个序来自于表结构索引产生的序，对于其它算子这个序可能来自排序算子的输出序。不同于 order by 明确要求的输出序，但大部分使用排序算法的算子需要输入的序是可以调整的，并且这个序可以保留继承到算子输出序。通过优化选择排序型算子使用的序，可以避免进行多次排序。

优化器在确定排序型算子使用的序时，会通过已有输入序和之后可能需要的序得到需要最终使用的序，以下方查询为例，group by 使用 merge group by 算子时，是可以任意调整算子输入序中 c1, c2 的前后位置及排序方向的：

Q2_1_1 中选择索引 idx 产生了 c1, c2 的序避免产生排序算子，并避免了 order by c1, c2 需要分配的排序算子。
Q2_1_2 中相对 Q2_1_1 调整了 order by，并指定使用主键，merge group by 直接使用 order by c2, c1 需要的序作为算子聚合的输入序，并在 group by 下方分配排序算子。
Q2_1_3 相比 Q2_1_2 没有指定使用主键，按照代价生成了 merge group by 可直接使用 idx 产生的 c1, c2 的序，并在聚合后为 order by c2, c1 分配排序算子。

create table t1(c1 int, c2 int, c3 int, c4 int, pk int primary key);
create index idx on t1(c1, c2, c3);

Q2_1_1:
select /*+no_use_hash_aggregation*/ c1, c2, sum(c3)
from t1 t
group by c2, c1
order by c1, c2;
==========================================
|ID|OPERATOR      |NAME  |EST. ROWS|COST |
------------------------------------------
|0 |MERGE GROUP BY|      |7072     |10965|
|1 | TABLE SCAN   |t(idx)|78858    |8124 |
==========================================

Outputs & filters:
-------------------------------------
  0 - output([t.c1], [t.c2], [T_FUN_SUM(t.c3)]), filter(nil), rowset=256,
      group([t.c1], [t.c2]), agg_func([T_FUN_SUM(t.c3)])
  1 - output([t.c1], [t.c2], [t.c3]), filter(nil), rowset=256,
      access([t.c1], [t.c2], [t.c3]), partitions(p0)

Q2_1_2:
select /*+no_use_hash_aggregation full(t)*/ c1, c2, sum(c3)
from t1 t
group by c1, c2
order by c2, c1;
========================================
|ID|OPERATOR      |NAME|EST. ROWS|COST |
----------------------------------------
|0 |MERGE GROUP BY|    |7072     |41410|
|1 | SORT         |    |100000   |37988|
|2 |  TABLE SCAN  |t   |100000   |8026 |
========================================

Outputs & filters:
-------------------------------------
  0 - output([t.c1], [t.c2], [T_FUN_SUM(t.c3)]), filter(nil), rowset=256,
      group([t.c2], [t.c1]), agg_func([T_FUN_SUM(t.c3)])
  1 - output([t.c2], [t.c1], [t.c3]), filter(nil), rowset=256,
			sort_keys([t.c2, ASC], [t.c1, ASC])
  2 - output([t.c1], [t.c2], [t.c3]), filter(nil), rowset=256,
      access([t.c1], [t.c2], [t.c3]), partitions(p0)

Q2_1_3:
select /*+no_use_hash_aggregation index(t idx)*/ c1, c2, sum(c3)
from t1 t
group by c1, c2
order by c2, c1;
===========================================
|ID|OPERATOR       |NAME  |EST. ROWS|COST |
-------------------------------------------
|0 |SORT           |      |7072     |12771|
|1 | MERGE GROUP BY|      |7072     |10965|
|2 |  TABLE SCAN   |t(idx)|78858    |8124 |
===========================================

Outputs & filters:
-------------------------------------
  0 - output([t.c1], [t.c2], [T_FUN_SUM(t.c3)]), filter(nil), rowset=256,
			sort_keys([t.c2, ASC], [t.c1, ASC])
  1 - output([t.c2], [t.c1], [T_FUN_SUM(t.c3)]), filter(nil), rowset=256,
      group([t.c1], [t.c2]), agg_func([T_FUN_SUM(t.c3)])
  2 - output([t.c1], [t.c2], [t.c3]), filter(nil), rowset=256,
      access([t.c1], [t.c2], [t.c3]), partitions(p0)

排序算子的分配与优化

尝试分配排序算子以获得期望排序时，排序算子的输出可能是有序的，首先根据输入序和其它信息进行检查，判断输入序能否满足期望的输出序。对于下方的三个查询，包含 order by 子句需要最终结果有序，由于匹配了索引或主键提供的序，最终不需要分配排序算子：

Q2_2_1: idx 索引可以提供 (c1, c2, c3) 的序，输出序匹配 order by c1, c2。
Q2_2_2: idx 索引可以提供 (c1, c2, c3) 的序, 由于包含 c1 = 4 谓词，输出序匹配 order by c2。
Q2_2_3: 主键提供 (pk) 的序，由于主键唯一性，输出序匹配 order by pk, c3, c2, c1。

create table t1(c1 int, c2 int, c3 int, c4 int, pk int primary key);
create index idx on t1(c1, c2, c3);

Q2_2_1: select /*+index(t idx)*/ * from t1 t order by c1, c2;
Q2_2_2: select /*+index(t idx)*/ * from t1 t where c1 = 4 order by c2;
Q2_2_3: select /*+index(t primary)*/ * from t1 t order by pk, c3, c2, c1;

Q2_2_1执行计划:
=======================================
|ID|OPERATOR  |NAME  |EST. ROWS|COST  |
---------------------------------------
|0 |TABLE SCAN|t(idx)|76557    |216994|
=======================================

Outputs & filters:
-------------------------------------
  0 - output([t.c1], [t.c2], [t.c3], [t.c4], [t.pk]), filter(nil), rowset=256,
      access([t.pk], [t.c1], [t.c2], [t.c3], [t.c4]), partitions(p0)

对于无法消除的排序，优化器分配排序算子前会对需要排序的列进行一定的优化。

前缀排序

需要分配排序算子时，如果算子输入序能够匹配部分期望的序，使用前缀排序利用部分输入序进行优化。

下方查询使用 idx 索引后 table scan 算子输出序为 (c1, c2, c3)，使用前缀排序后对每组 c1 仅对 pk 进行排序。

Q2_2_4:
select /*+index(t idx)*/ c1 from t1 t order by c1, pk;
=======================================
|ID|OPERATOR   |NAME  |EST. ROWS|COST |
---------------------------------------
|0 |SORT       |      |76557    |18874|
|1 | TABLE SCAN|t(idx)|76557    |5319 |
=======================================

Outputs & filters:
-------------------------------------
  0 - output([t.c1]), filter(nil), rowset=256,
			sort_keys([t.c1, ASC], [t.pk, ASC]), prefix_pos(1)
  1 - output([t.pk], [t.c1]), filter(nil), rowset=256,
      access([t.pk], [t.c1]), partitions(p0)

简化排序列

对需要排序的列进行一定的简化优化，减少需要排序列数量。化简排序列过程中主要使用以下方式:

利用等值条件关系进行化简排序列
```
select c1 from t1 t where c3 = 1 and c2 = c1 order by c3, c2, c1;
```
对于上方查询，使用 c3 = 1 及 c2 = c1 进行化简，最终按照 c2 列进行排序。
利用主键/唯一索引化简排序列
```
select c1 from t1 t order by c1, pk, c3, c2;
```
对上方查询，由于 pk 为主键，最终按照 c1, pk 两列进行排序。