本文介绍PolarDB-X如何优化和执行排序计算,达到减少数据传输量和提高执行效率的效果。

基本概念

排序操作(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层的计算能力。