蔡珉星-skew-join相关论文-厦门大学数据库室.ppt

Skew Join相关论文 报告人：蔡珉星 厦大数据库实验室 2014-08-30 遇到的问题 目录 论文：Efficient outer join data skew handling in parallel DBMS 其他论文 Part 1 论文：Efficient outer join data skew handling in parallel DBMS Inner join 和 Outer join： inner join (等价于 join) 是求两个集合的交集 outer join: Left outer join: 返回左表中的所有结果，若右表有匹配项，则返回结果，否则返回NULL。 Right outer join: 返回的是右表中的所有结果…… Full outer join: 返回的是左右表中的所有结果…… 背景知识 考虑如下Outer join实例 Outer join 实例 R(x, a) S(y, b) T(z, d) 假设先进行 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 Outer join 实例 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操作过程却出现了倾斜情况。 问题分析 解决 Outer join 存在的问题： 随机分配含NULL值的数据，而不是聚集在某一个节点上。 H(NULL) = random(1, n) 问题分析 分析一下上述方法的执行结果 z d 3 1 4 4 5 7 x a y c 2 9 2 1 3 3 N N 6 2 N N R left outer join S T x a y c z 2 9 2 1 3 3 3 N N N 6 2 N N N 节点的最终结果 若中间结果为NULL的行，最终结果中新字段也为NULL left outer join 解决Outer join（该实例）存在的问题的最佳方法： 直接将新字段填充为NULL，输出即可，无需重新分配来进行剩下的join操作。 问题解决 R left outer join S的结果 解决 Outer join 存在的问题的最佳方法： 问题解决 结果分成两部分：是否包含NULL值，不包含NULL的数据继续参与后续join 解决 Outer join 存在的问题的最佳方法： 问题解决 包含NULL的数据直接填充新字段为NULL。 最后将两部分合并即为最终结果。 Part 3 其他论文 解决问题 解决Join操作中的数据倾斜问题 核心思想 统计出每个join key的频次； 根据节点处理该join key的代价（数据量），判断是否会出现倾斜情况； 如果会出现倾斜，比较两个表中该join key的频次： 例如Fr Fs，则将R表中的该join key的数据均分到多个Reducer，将S 表中该join key的数据广播到这些Reducer上。 A New Framework for Join Product Skew 1000个A + 500个A 500个A 主要内容 分析了常见的Join操作，讨论如何实现有效、健壮的join算法。 如何解决倾斜问题 核心想法：区别处理高频次的join key数据和低频次的join key数据 低频次的join key采用hash partition即可，高频次的join key依情况选择广播join或重分区join，或两者结合。 Advanced Join Strategies for Large-Scale Distributed Computation 判断是否是会出现倾斜的高频次join key