排序优化和执行

基本概念

排序操作（Sort）表示按照指定的ORDER BY列对输入进行排序。本文介绍的均为不下推的排序类算子的实现。如果已被下推到LogicalView中，则由存储层MySQL来选择执行方式。

PolarDB-X中的排序算子主要包括MemSort、TopN，以及 MergeSort。

MemSort

PolarDB-X中通用的排序实现为MemSort算子，表示在内存中运行快速排序（Quick Sort）算法。如下示例使用了MemSort算子：

explain select t1.name from t1 join t2 on t1.id = t2.id order by t1.name,t2.name;

返回信息如下：

Project(name="name")
  MemSort(sort="name ASC,name0 ASC")
    Project(name="name", name0="name0")
      BKAJoin(condition="id = id", type="inner")
        Gather(concurrent=true)
          LogicalView(tables="t1", shardCount=2, sql="SELECT `id`, `name` FROM `t1` AS `t1`")
        Gather(concurrent=true)
          LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id`, `name` FROM `t2` AS `t2` WHERE (`id` IN ('?'))")

TopN

当SQL中ORDER BY和LIMIT一起出现时，Sort运算和Limit运算会合并成TopN算子。

TopN算子维护一个最大或最小堆，按照排序键的值，堆中始终保留最大或最小的N行数据。当处理完全部的输入数据时，堆中留下的N个行（或小于N个）即为需要的结果。

explain select t1.name from t1 join t2 on t1.id = t2.id order by t1.name,t2.name limit 10;

返回信息如下：

Project(name="name")
  TopN(sort="name ASC,name0 ASC", offset=0, fetch=?0)
    Project(name="name", name0="name0")
      BKAJoin(condition="id = id", type="inner")
        Gather(concurrent=true)
          LogicalView(tables="t1", shardCount=2, sql="SELECT `id`, `name` FROM `t1` AS `t1`")
        Gather(concurrent=true)
          LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id`, `name` FROM `t2` AS `t2` WHERE (`id` IN ('?'))")

MergeSort

通常，只要语义允许，SQL中的排序操作会被下推到存储层MySQL上执行，而PolarDB-X执行层只做最后的归并运算，即MergeSort。严格来说，MergeSort不仅仅是排序，更是一种数据重分布算子（类似Gather）。下面的SQL表示对t1表进行排序，经过PolarDB-X查询优化器的优化，Sort算子被下推至各个存储层MySQL分片中执行，最终只在上层做归并操作。

explain select name from t1 order by name;

返回信息如下：

MergeSort(sort="name ASC")
  LogicalView(tables="t1", shardCount=2, sql="SELECT `name` FROM `t1` AS `t1` ORDER BY `name`")

相比MemSort，MergeSort算子可以减少PolarDB-X执行层的内存消耗，并充分利用存储层MySQL层的计算能力。