HIVE TopN shuffle 原理

  1. 云栖社区>
  2. Apache Spark中国技术社区>
  3. 博客>
  4. 正文

HIVE TopN shuffle 原理

xy_xin 2019-03-21 23:44:02 浏览652
展开阅读全文

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

网友评论

登录后评论
0/500
评论
xy_xin
+ 关注
所属云栖号: Apache Spark中国技术社区