MapReduce连接运算

在实际中,有很多场景都要求将多个数据集连接起来。

连接(Join)是关系运算,可以用于合并关系(relation)。对于数据库中的表连接操作,可能已经广为人知了。在MapReduce中,连接可以用于合并两个或多个数据集。

最常用的两个连接类型是内连接(inner join)和外连接(outer join)。 如下图所示,内连接比较两个关系中所有的元组,判断是否满足连接条件,然后生成一个满足连接条件的结果集。 与内连接相反的是,外连接并不需要两个关系的元组都满足连接条件。 在连接条件不满足的时候,外连接可以将其中一方的数据保留在结果集中。

为了实现内连接和外连接,MapReduce中有两种连接策略,如下所示。

  • map端连接。使用场景:待连接的数据集中有一个数据集足够小到可以完全放在缓存中。 在这种类型中,连接是在map函数实际使用数据之前执行的。 每个map的输入必须以分区的形式并按顺序排列。 此外,必须有相同数量的分区,并且必须按连接key进行排序。 也就是说,要连接的数据集已经按相同的键进行排序,并且拥有相同数量的分区。
  • reduce端连接。使用场景:连接两个或多个大型数据集。 当连接由reducer执行时,它被称为reduce-side联接。 在此连接中,没有必要使用结构化形式(或分区形式)的数据集。

连接选择策略

MapReduce连接策略可被总结以下三点:

  • 1) 如果其中有一个数据集小到足够放入到一个mapper的内存,则map only复制连接最有效。
  • 2) 如果两个数据集都很大,其中一个数据集可通过预过滤(与其它数据集数据不匹配的)元素而大大减少体积,则semi-join(半连接)最合适。
  • 3) 如果不能对数据进行预处理,并且数据体积太大而不能被缓存—这意味着我们不得不在reducer端执行join连接—需要使用重分区连接(repartition join)。

《Spark原理深入与编程实战》