HIVE TopN shuffle 原理

HIVE TopN Shuffle

TopN 问题是排序中的一个经典问题。对于一个长度为 m 的数组，取其最大的 n (n <= m) 条数据，可以不必对整个数组进行全排。一般的算法对 m 进行全排的复杂度大约为 mlog2(m)。假设我们只取其中最大的 n 条，那么可以把这个复杂度降低到 m * log2(n)。如果 n << m，那么收益还是很大的。

HIVE-3562 引入了一个针对 TopN 的优化，即将带有 limit 算子的 order by 推至 map 端，这样 map 不必将所有数据 shuffle 到 reduce。order by 和 limit 算子在日常使用场景中经常一起出现，因此这个优化就显得很有必要。

抛开 limit 是如何下推的不管，我们这里只关注 ReduceSinkOperator