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