基本概念

排序操作（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層的計算能力。