基本概念
聚合操作（Aggregate，简称Agg）语义为按照GROUP BY指定列对输入数据进行聚合的计算，或者不分组、对所有数据进行聚合的计算。PolarDB-X支持如下聚合函数：
COUNTSUMAVGMAXMINBIT_ORBIT_XORGROUP_CONCAT
排序操作（Sort）语义为按照指定的ORDER BY列对输入进行排序。
本文介绍均为不下推的Agg或Sort的算子的实现。如果已被下推到LogicalView中，则由存储层MySQL来选择执行方式。
聚合（Agg）
聚合（Agg）由两种主要的算子HashAgg和SortAgg实现。
HashAgg
HashAgg利用哈希表实现聚合：
- 根据输入行的分组列的值，通过Hash找到对应的分组。
- 按照指定的聚合函数，对该行进行聚合计算。
- 重复以上步骤直到处理完所有的输入行，最后输出聚合结果。
> explain select count(*) from t1 join t2 on t1.id = t2.id group by t1.name,t2.name; Project(count(*)="count(*)") HashAgg(group="name,name0", count(*)="COUNT()") 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 ('?'))")
Explain结果中，HashAgg算子还包含以下关键信息：
- group：表示GROUP BY字段，示例中为
name,name0分别引用t1,t2表的name列，当存在相同别名会通过后缀数字区分 。 - 聚合函数：等号（=） 前为聚合函数对应的输出列名，其后为对应的计算方法。示例中
count(*)="COUNT()"，第一个count(*)对应输出的列名，随后的COUNT()表示对其输入数据进行计数。
HashAgg对应可以通过Hint来关闭：/*+TDDL:cmd_extra(ENABLE_HASH_AGG=false)*/。
SortAgg
SortAgg在输入数据已按分组列排序的情况，对各个分组依次完成聚合。
- 保证输入按指定的分组列排序（例如，可能会看到 MergeSort 或 MemSort）。
- 逐行读入输入数据，如果分组与当前分组相同，则对其进行聚合计算。
- 否则，如果分组与当前分组不同，则输出当前分组上的聚合结果。
相比 HashAgg，SortAgg 每次只要处理一个分组，内存消耗很小；相对的，HashAgg 需要把所有分组存储在内存中，需要消耗较多的内存。
> explain select count(*) from t1 join t2 on t1.id = t2.id group by t1.name,t2.name order by t1.name, t2.name; Project(count(*)="count(*)") MemSort(sort="name ASC,name0 ASC") HashAgg(group="name,name0", count(*)="COUNT()") 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 ('?'))")
SortAgg对应可以通过Hint来关闭：/*+TDDL:cmd_extra(ENABLE_SORT_AGG=false)*/。
两阶段聚合优化
两阶段聚合，即通过将Agg拆分为部分聚合（Partial Agg）和最终聚合（Final Agg）的两个阶段，先对部分结果集做聚合，然后将这些部分聚合结果汇总，得到整体聚合的结果。
例如下面的 SQL 中，HashAgg 中拆分出的部分聚合（PartialAgg）会被下推至MySQL上的各个分表，而其中的AVG函数也被拆分成 SUM和 COUNT 以实现两阶段的计算：
> explain select avg(age) from t2 group by name Project(avg(age)="sum_pushed_sum / sum_pushed_count") HashAgg(group="name", sum_pushed_sum="SUM(pushed_sum)", sum_pushed_count="SUM(pushed_count)") Gather(concurrent=true) LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `name`, SUM(`age`) AS `pushed_sum`, COUNT(`age`) AS `pushed_count` FROM `t2` AS `t2` GROUP BY `name`")
两阶段聚合的优化能大大减少数据传输量、提高执行效率。
排序（Sort）
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个）就是需要的结果。
下面是一个用到 TopN 算子的例子：
> 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 层的计算能力。
优化组合的例子
下面是一个组合优化的例子，在这个例子中，用到了以下优化规则：
- Agg下推穿过Join
- Join算法选择为SortMergeJoin
- Agg算法选择为SortAgg
- SortMergeJoin中需要的排序利用了SortAgg输出的有序
- 两阶段Agg
- Agg下推
- Sort下推
> explain select count(*) from t1 join t2 on t1.name = t2.name group by t1.name; Project(count(*)="count(*) * count(*)0") SortMergeJoin(condition="name = name", type="inner") SortAgg(group="name", count(*)="SUM(count(*))") MergeSort(sort="name ASC") LogicalView(tables="t1", shardCount=2, sql="SELECT `name`, COUNT(*) AS `count(*)` FROM `t1` AS `t1` GROUP BY `name` ORDER BY `name`") SortAgg(group="name", count(*)="SUM(count(*))") MergeSort(sort="name ASC") LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `name`, COUNT(*) AS `count(*)` FROM `t2` AS `t2` GROUP BY `name` ORDER BY `n
