如何在Spark中实现Count Distinct重聚合

背景

Count Distinct是SQL查询中经常使用的聚合统计方式，用于计算非重复结果的数目。由于需要去除重复结果，Count Distinct的计算通常非常耗时。

以如下查询为例，Count Distinct的实现方式主要有两种：

SELECT region, COUNT(DISTINCT userId) FROM orders GROUP BY region

1. 对订单表的数据按照region进行shuffle分区，在每个分区中使用一个类似HashTable的数据结构，存储所有的非重复userId的值，最后统计所有key的数量。
2. 对表t的数据按照（region, userId）进行shuffle分区，第一步的结果即为非重复的（region, userId）对，对于第一步的结果再按照region分区，统计每个分区中的Row数量。

第一种方式