排序算子 (SORT 算子) 的作用是将下层算子计算的结果进行排序。因为必须要拿到完整的数据后才能进行排序，所以该算子为阻塞性算子。

SORT 的算法

SORT 逻辑算子主要有三种，分别是普通排序，前缀排序和 top-n 排序。生成逻辑计划时，优化器会对 SORT 选择最优的算法。选择的依据是：

  • 下层算子的结果的序和 SORT 算子的排序表达式的关系；

  • 上层算子的类型。

普通排序

当下层算子的结果是无序的，或者下层算子的结果有序但是与 SORT 算子的排序键无关时，使用普通的排序算法。

如下例所示，T2 表的主键是 (a, b)，而 SORT 算子的排序键是 b，所以不能直接使用。

  1. obclient> explain extended_noaddr select * from t2 order by b\G
  2. *************************** 1. row ***************************
  3. Query Plan: 
  4. ====================================
  5. |ID|OPERATOR   |NAME|EST. ROWS|COST|
  6. ------------------------------------
  7. |0 |SORT       |    |1000     |2198|
  8. |1 | TABLE SCAN|t2  |1000     |455 |
  9. ====================================
  11. Outputs & filters:
  12. -------------------------------------
  13.   0 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.b, ASC])
  14.   1 - output([t2.a], [t2.b], [t2.c]), filter(nil),
  15.       access([t2.a], [t2.b], [t2.c]), partitions(p0),
  16.       is_index_back=false,
  17.       range_key([t2.a], [t2.b]), range(MIN,MIN ; MAX,MAX)always true

前缀排序

当下层算子结果是有序的，且与 SORT 算子的排序键存在公共前缀，使用前缀排序。

如下例所示，T2 的主键为 (a, b)，SORT 算子排序键为 (a, c)，那么公共前缀就是 a。优化器会认为可以利用 a 的序，所以选择前缀排序。其中 prefix_pos(1) 表示前 1 个列已经有序，不再需要比较。

  1. obclient> explain extended_noaddr select * from t1 order by a, c\G
  2. *************************** 1. row ***************************
  3. Query Plan:
  4.  ====================================
  5. |ID|OPERATOR   |NAME|EST. ROWS|COST|
  6. ------------------------------------
  7. |0 |SORT       |    |1000     |1531|
  8. |1 | TABLE SCAN|t1  |1000     |455 |
  9. ====================================
  11. Outputs & filters:
  12. -------------------------------------
  13.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), prefix_pos(1)
  14.   1 - output([t1.a], [t1.b], [t1.c]), filter(nil),
  15.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
  16.       is_index_back=false,
  17.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
  19. 1 row in set (0.01 sec)

TOP-N 排序

TOP-N 排序表示上层只要求取最大或最小的前 N 个结果。当 SORT 的上层为 LIMIT 时，优化器认为该 SORT 不需要所有结果，标记该 SORT 为 TOP-N SORT。

如下例所示，SORT 算子上层为 LIMIT 算子，只要求 5 行数据，所以下层 SORT 采用 TOP-N 排序算法，cost 比常规排序要小。需要注意的是 TOP-N 算法与前缀排序算法可以同时作为 SORT 算子的优化算法存在。

  1. obclient> explain extended_noaddr select * from t1 order by a, c limit 5\G
  2. *************************** 1. row ***************************
  3. Query Plan: 
  4. =====================================
  5. |ID|OPERATOR    |NAME|EST. ROWS|COST|
  6. -------------------------------------
  7. |0 |LIMIT       |    |5        |1065|
  8. |1 | TOP-N SORT |    |5        |1065|
  9. |2 |  TABLE SCAN|t1  |1000     |455 |
  10. =====================================
  12. Outputs & filters:
  13. -------------------------------------
  14.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil), limit(5), offset(nil)
  15.   1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), topn(5), prefix_pos(1)
  16.   2 - output([t1.a], [t1.b], [t1.c]), filter(nil),
  17.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
  18.       is_index_back=false,
  19.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
  21. 1 row in set (0.01 sec)

其他

SORT 算子的消除

当下层算子的序与 SORT 算子的序相同的时候，SORT 算子可以消除。

如下例所示，T2 的主键为 (a, b)，SORT 算子排序键也为 (a, b)。上层不需要排序，所以消除该 SORT。下层序能否被利用这个特性在选择访问路径的时候也会考虑。

  1. obclient> explain extended_noaddr select * from t1 order by a, b\G
  2. *************************** 1. row ***************************
  3. Query Plan: 
  4. ===================================
  5. |ID|OPERATOR  |NAME|EST. ROWS|COST|
  6. -----------------------------------
  7. |0 |TABLE SCAN|t1  |1000     |455 |
  8. ===================================
  10. Outputs & filters:
  11. -------------------------------------
  12.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil),
  13.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
  14.       is_index_back=false,
  15.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
  17. 1 row in set (0.01 sec)

SORT 算子落盘

当 SORT 算子在执行的过程中，如果检测到当前算子使用的内存超过限制(目前为 128 M)或者当前租户的 ob_sql_work_area_percentage 所表示的内存被占满时，当前 SORT 所使用的内存将会落盘，并执行外排。因为该操作是在执行时判断的，所以对于用户来说并不可见，但是对于实际性能是有影响的。