天行自息

    连接(Join)是关系运算，可以用于合并关系(relation)。对于数据库中的表连接操作，可能已经广为人知了。在 MapReduce 中，连接可以用于合并两个或多个数据集。例如，用户基本信息和用户活动详情信息。用户基本信息来自于 OLTP 数据库。用户活动详情信息来自于日志文件。

    MapReduce 的连接操作可以用于以下场景:

• 用户的人口统计信息的聚合操作(例如:青少年和中年人的习惯差异)。

• 当用户超过一定时间没有使用网站后，发邮件提醒他们。(这个一定时间的阈值是用户自己预定义的)

• 分析用户的浏览习惯。让系统可以基于这个分析提示用户有哪些网站特性还没有使用到。进而形成一个反馈循环。

• 所有这些场景都要求将多个数据集连接起来。   

• 
  

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

    为了实现内连接和外连接，MapReduce 中有三种连接策略，如下所示。这三种连接策略有的在 map阶段，有的在 reduce 阶段。它们都针对 MapReduce 的排序-合并的架构进行了优化。

•     重分区连接(Repartition join)— reduce 端连接。使用场景:连接两        个或多个大型数据集。 

•     复制连接(Replication join)— map 端连接。使用场景:待连接的数        据集中有一个数据集足够

•     半连接(Semi-join)— 另一个 map 端连接。使用场景:待连接的数据        集中有一个数据集非常    

2,选择最佳连接策略

    要选择连接数据的最优方法，我们这里使用数据驱动的决策树来选择最佳连接策略。

    
这个决策树可以总结以下三点：

1. 如果其中有一个数据集小到足够放入到一个 mapper 的内存，则 map only 复制连接最有效。

2. 如果两个数据集都很大，其中一个数据集可通过预过滤(与其它数据集数据不匹配的)元素而大大减少体积，则 semi-join(半连接)最合适。

3. 如果不能对数据进行预处理，并且数据体积太大而不能被缓存—这意味着我们不得不在 reducer端执行 join 连接—需要使用重分区连接(repartition join)

4. 不管应用哪种策略，我们在 join 中应该执行的最基本的活动是使用过滤和投影。 

3，过滤和投影

    使用过滤和投影减少处理的数据量，使用下推优化技术来改善数据管道。过滤和投影工作原理如下图所示:

    应该尽可能地靠近数据源执行过滤和投影;在 MapReduce 中，最好是在 mapper 中执行这个工作。例如下面的代码执行过滤:

    投影和谓词下推进一步将过滤推进到存储格式。这甚至更高效，特别是使用基于下推可以 skip 过记录或 blocks 的存储格式时。