通过Map-Reduce实现Join系列之四

在本系列的前面几篇文章中，主要介绍了利用Map-Reduce任务来完成两个或者多个文件的Join操作的一些算法和思路。基于的前提是对这些文件在相同的列上进行Join，本文将要讨论如何通过Map-Reduce任务来完成对多个文件在不同列上进行Join。由于需要在不同的列上进行Join，涉及到的文件个数至少会是三个，比如有三个文件T1(A,B)、T2(B,C)、T3(C,D)，T1和T2基于B列进行Join，而T2和T3则需要基于C列进行Join。本系列的第二和第三篇中提到的针对两个文件和多个文件进行Join的相关算法和思路稍加扩展就可以用到对多个文件在不同列上进行Join的情况中，另外，文本还将介绍一种通过一个Map-Reduce任务完成多个文件在不同列上进行Join操作的算法。
1.通过多个Map-Reduce任务来完成Join
对于本文开头的例子，如果要对T1、T2和T3进行Join，我们可以通过两个Map-Reduce任务来完成，第一个任务将T1和T2在B列上进行Join，然后将结果与T3在C列上执行Join，这样就可以得到最终的结果。本系列第二篇中对如何执行两个文件的Join有更详细的描述。
扩展多跟一般的情况，有n个数据文件，需要在m个列上进行Join。在第一个阶段，我们需要根据Join条件对n个数据文件进行分类，然后对每个分类执行Join操作。对于包含两个文件的分类，可以通过第二篇介绍的方式来完成Join，对于包含多个文件的分类，则可以实用第三篇中介绍的方法来完成Join，对于只包含一个数据文件的分类，则可以跳过这个阶段。
第二个阶段则需要对第一个阶段产生的结果进行两两join操作，这个阶段执行完成之后，就可以得到最终的结果。
可以看到，这种方式需要执行多个Map-Reduce任务，从而会占用比较多的计算和存储资源。
2.通过一个Map-Reduce任务来完成Join
对于文章开头提到的T1、T2、T3进行Join的问题，可以通过一个Map-Reduce过程来完成，在Map阶段，我们将T1和T3文件中的所有记录复制给所有的Reducer，而T2中的记录则按照Reducer进行切分，每个Reducer只处理T2中的一部分数据。这样每个Reducer各自完成一部分数据的Join，所有Reducer所产生的结果加到一起，就可以形成完成的结果。虽然，数据的复制到只了存储和Map阶段数据通信的成本，但是整个Join过程被放到了一个Map-Reduce任务中，执行效率被提高了，我们可以更快速的得到结果。

算法的优化

这个算法可以被进行优化，这里对优化的方法进行一个大概的介绍。首先，假设我们将会实用k=m2个Reducer来完成T1、T2和T3三个文件的Join，其中m是一个任意的数字。B列和C列上的值通过一个哈希函数之后，可以被映射到[1, m]之间的一个值上，这个哈希函数我们命名为h。这样一来，这m2个Reducer就会形成一个矩阵，如下图所示：

(i,j)表示矩阵中的某个位置，其中i和j的取值在[1,m]之间。这样对于每个B和C的哈希值对(h(B),h(C))，都能够被映射到Reducer矩阵中的某个Reducer上，也就是说T2文件中的记录能够被分配到不同的Reducer中，而且每个Reducer上的记录不会重复。而对于T1文件，由于它只包含了B列，因此我们只能够得到(h(B),y)形式的映射结果，也就是在y轴上的值是未知的，因此对于T1文件中的每条数据，需要被复制到m个Reducer上。同样的，对于T3数据文件来说，我们能够得到(x,h(C))这样的映射结果，也就是在x轴上的值是未知的，因此T3文件中的每条数据也同样需要被复制到m个Reducer上。通过这个优化，矩阵中的每个Reducer将会得到1/m2条T2文件中的记录，1/m条T1和T3中的数据，这样以来，就不需要把T1和T3文件完整复制给所有的Reducer了，而只需要复制其中的一部分。
通过上面的描述，我们可以看到，对这个算法的优化，主要集中在如何减少需要复制给每个Reducer的数据量上。关于这个问题，本文不打算详细展开，更具体的内容可以在后面给出的参考文献中找到。
3.参考文献
Join Algorithms using Map/Reduce
Optimizing Joins in a Map-Reduce Environment