排序算子介绍

    排序算子(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. ====================================
    10. Outputs & filters:
    11. -------------------------------------
    12.   0 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.b, ASC])
    13.   1 - output([t2.a], [t2.b], [t2.c]), filter(nil),
    14.       access([t2.a], [t2.b], [t2.c]), partitions(p0),
    15.       is_index_back=false,
    16.       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. ====================================
    10. Outputs & filters:
    11. -------------------------------------
    12.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), prefix_pos(1)
    13.   1 - output([t1.a], [t1.b], [t1.c]), filter(nil),
    14.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
    15.       is_index_back=false,
    16.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
    18. 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. =====================================
    11. Outputs & filters:
    12. -------------------------------------
    13.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil), limit(5), offset(nil)
    14.   1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.a, ASC], [t1.c, ASC]), topn(5), prefix_pos(1)
    15.   2 - output([t1.a], [t1.b], [t1.c]), filter(nil),
    16.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
    17.       is_index_back=false,
    18.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
    20. 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. ===================================
    9. Outputs & filters:
    10. -------------------------------------
    11.   0 - output([t1.a], [t1.b], [t1.c]), filter(nil),
    12.       access([t1.a], [t1.b], [t1.c]), partitions(p0),
    13.       is_index_back=false,
    14.       range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true
    16. 1 row in set (0.01 sec)
    • SORT算子落盘

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