PPT《论文阅读成果和创新点》

论文阅读成果和创新点 厦门大学数据库实验室 罗道文 2015-03-07 SAND_JOIN algorithm 目录基于Locality-Aware的reduce任务调度 SAND_JOIN算法不足之处 SAND_JOIN算法改进 SAND_JOIN algoririthm 简单的范围分区 思想:在执行reduce-join连接之前,先运行一个job,统计键值的分布情况,即抽样思想,接着利用样本的键值分布情况,对所有数据进行分区.

分为:简单范围分区和虚拟处理器范围分区. 思想:Map端采样:每个Mapper随机选取X个样本,有n个Mapper.Reduce端统计分布:只需要一个Reducer对样本所有key值统计分析,构造出分区序列. SAND_JOIN algoririthm 若执行的Join连接有N个Reduce,则可以根据步长n*x/N获得一个分区序列.例如: Sample:[1,3,3,4,5,5,6,6,6,6,8,9,9,10,10],5个Reducer,步长为3, 分区序列为:[3,5,6,9] Join Partition: key≤3 3