Skew Join相关论文 报告人：蔡珉星 厦大数据库实验室 2014-08-30

论文：Efficient outer join data skew handling in parallel DBMS 目录 遇到的问题 论文：Efficient outer join data skew handling in parallel DBMS 其他论文

论文：Efficient outer join data skew handling in parallel DBMS Part 1

背景知识 Inner join 和 Outer join： inner join (等价于 join) 是求两个集合的交集 Left outer join: 返回左表中的所有结果，若右表有匹配项，则返回结果，否则返回NULL。 Right outer join: 返回的是右表中的所有结果…… Full outer join: 返回的是左右表中的所有结果……

Outer join 实例 考虑如下Outer join实例 R(x, a) S(y, b) T(z, d)

Outer join 实例 假设先进行 R left outer join S，再进行left outer join T

Outer join 实例 假设先进行 R left outer join S，再进行left outer join T

Outer join 实例 假设先进行 R left outer join S，再进行left outer join T J.c left outer join T.d J.c的部分数据为NULL， 需要单独进行分区处理。 常规情况： H(null) = 1 导致大量含NULL的数据聚集在1号Reducer上

Outer join 实例

问题分析 Outer join 存在的问题： 由于outer join操作本身的特性，结果中的某些列会出现NULL值，如果这包含NULL值的列再参与其他的join操作（多表连接），在常规的解决方法中，是将含NULL值数据都划分到某个节点上（H(NULL) = x），从而导致在原始数据不倾斜的情况下，join操作过程却出现了倾斜情况。

若中间结果为NULL的行，最终结果中新字段也为NULL 问题分析 解决 Outer join 存在的问题： 随机分配含NULL值的数据，而不是聚集在某一个节点上。 H(NULL) = random(1, n) 分析一下上述方法的执行结果 R left outer join S T 节点的最终结果 x a y c z 2 9 1 3 N 6 x a y c 2 9 1 3 N 6 z d 3 1 4 5 7 left outer join 若中间结果为NULL的行，最终结果中新字段也为NULL

问题解决 解决Outer join（该实例）存在的问题的最佳方法： 直接将新字段填充为NULL，输出即可，无需重新分配来进行剩下的join操作。 R left outer join S的结果

问题解决 解决 Outer join 存在的问题的最佳方法： 结果分成两部分：是否包含NULL值，不包含NULL的数据继续参与后续join

包含NULL的数据直接填充新字段为NULL。 问题解决 解决 Outer join 存在的问题的最佳方法： 包含NULL的数据直接填充新字段为NULL。 最后将两部分合并即为最终结果。

其他论文 Part 3

+ A New Framework for Join Product Skew 解决问题 核心思想 解决Join操作中的数据倾斜问题 统计出每个join key的频次； 根据节点处理该join key的代价（数据量），判断是否会出现倾斜情况； 如果会出现倾斜，比较两个表中该join key的频次： 例如Fr > Fs，则将R表中的该join key的数据均分到多个Reducer，将S 表中该join key的数据广播到这些Reducer上。 1000个A + 500个A

Advanced Join Strategies for Large-Scale Distributed Computation 主要内容 分析了常见的Join操作，讨论如何实现有效、健壮的join算法。 如何解决倾斜问题 核心想法：区别处理高频次的join key数据和低频次的join key数据 低频次的join key采用hash partition即可，高频次的join key依情况选择广播join或重分区join，或两者结合。 判断是否是会出现倾斜的高频次join key （根据节点处理代价） 对高频次、低频次join key的处理不同

MapReduce上基于抽样的数据划分最优化研究 主要内容 基于抽样的划分是一种比较有效的数据划分方法，为了使得抽样方法发挥最大程度的效益，研究了抽样效果与其重要影响因素之间的定量关系，从而可通过尽可能小的抽样代价来得到满足要求的数据划分。 重要结论 采样（分块随机采样）准确率的影响因素： 准确率随样本规模的增加而增大，但在一个不大的阈值N后增长缓慢； 在相同的准确率要求下，不过规模的数据集所需的样本规模相同； 准确率随着节点个数的增加而减少。 所以不管数据集有多大，都可以只取少量的样本数。并且随着节点个数的增加，需要更多的样本数量来维持原有的准确率。

Implementation and Analysis of Join Algorithms to handle skew for the Hadoop Map/Reduce Framework 主要内容 学位论文，较为详细的介绍了Hadoop中Join算法的实现和分析。 创新点 提出了Hybrid Join：结合Map-side join和Reduce-side join。

Implementation and Analysis of Join Algorithms to handle skew for the Hadoop Map/Reduce Framework 主要内容 学位论文，较为详细的介绍了Hadoop中Join算法的实现和分析。 创新点 提出了Hybrid Join：结合Map-side join和Reduce-side join。

Implementation and Analysis of Join Algorithms to handle skew for the Hadoop Map/Reduce Framework 主要内容 学位论文，较为详细的介绍了Hadoop中Join算法的实现和分析。 创新点 提出了Hybrid Join：结合Map-side join和Reduce-side join。

Implementation and Analysis of Join Algorithms to handle skew for the Hadoop Map/Reduce Framework 主要内容 学位论文，较为详细的介绍了Hadoop中Join算法的实现和分析。 创新点 提出了Hybrid Join：结合Map-side join和Reduce-side join。 处理数据倾斜： 简单范围分区算法 虚拟范围分区算法

遇到的问题 Thanks. 23