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

Presentation on theme: "Skew Join相关论文 报告人：蔡珉星 厦大数据库实验室 2014-08-30."— Presentation transcript:

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

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

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

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

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

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

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

8 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上

9 Outer join 实例

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

11 若中间结果为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

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

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

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

15 其他论文 Part 3

16 + 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

17 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的处理不同

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

19 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。

20 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。

21 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。

22 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。 处理数据倾斜： 简单范围分区算法 虚拟范围分区算法

23 遇到的问题 Thanks. 23