简介

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

SORT 的算法

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

  • 下层算子的结果的序和 SORT 算子的排序表达式的关系;
  • 上层算子的类型。

普通排序

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

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

  1. OceanBase_114 (root@test)> explain extended_noaddr select * from t2 order by b\G
  2. *************************** 1. row ***************************
  3. Query Plan: ====================================
  4. |ID|OPERATOR |NAME|EST. ROWS|COST|
  5. ------------------------------------
  6. |0 |SORT | |1000 |2198|
  7. |1 | TABLE SCAN|t2 |1000 |455 |
  8. ====================================
  9. Outputs & filters:
  10. -------------------------------------
  11. 0 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.b, ASC])
  12. 1 - output([t2.a], [t2.b], [t2.c]), filter(nil),
  13. access([t2.a], [t2.b], [t2.c]), partitions(p0),
  14. is_index_back=false,
  15. 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. OceanBase_114 (root@test)> explain extended_noaddr select * from t1 order by a, c\G
  2. *************************** 1. row ***************************
  3. Query Plan: ====================================
  4. |ID|OPERATOR |NAME|EST. ROWS|COST|
  5. ------------------------------------
  6. |0 |SORT | |1000 |1531|
  7. |1 | TABLE SCAN|t1 |1000 |455 |
  8. ====================================
  9. Outputs & filters:
  10. -------------------------------------
  11. 0 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), prefix_pos(1)
  12. 1 - 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
  16. 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. OceanBase_114 (root@test)> explain extended_noaddr select * from t1 order by a, c limit 5\G
  2. *************************** 1. row ***************************
  3. Query Plan: =====================================
  4. |ID|OPERATOR |NAME|EST. ROWS|COST|
  5. -------------------------------------
  6. |0 |LIMIT | |5 |1065|
  7. |1 | TOP-N SORT | |5 |1065|
  8. |2 | TABLE SCAN|t1 |1000 |455 |
  9. =====================================
  10. Outputs & filters:
  11. -------------------------------------
  12. 0 - output([t1.a], [t1.b], [t1.c]), filter(nil), limit(5), offset(nil)
  13. 1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), topn(5), prefix_pos(1)
  14. 2 - 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
  18. 1 row in set (0.01 sec)

其他

SORT 算子的消除

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

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

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

SORT 算子落盘

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