(1)基于原始MapReduce的连接算法
　　这类算法通过设计Map函数、Reduce函数和数据流来完成连接，涉及到的连接方式包括两表等值连接[9,25,28-29]、两表0连接[3°]、多表等值连接[1-32]和两表集合相似性连接[3°]3种类型.如表3所示，我们首先对两表等值连接的算法进行分析比较.设参加连接的两个表分别为只和S，并且只为其中数据量较小的表.?
　　标准重分区算法[9'25'28_29].该算法类似于〇8皿3中的排序^合并算法，由一个MapReduce作业构成.Mapper读入两个表的数据文件，并根据查询条件对数据进行过滤.输出的键值对中，键值是连接的列值，数值部分包括记录值和标签两部分，标签用于标识该记录来自哪个表.在reduce的混洗（shuffle)过程中，具有相同连接值的记录被分区到同一个reducer上.针对每一个连接值，reducer根据标签把记录分成两个集合，然后计算两个集合元素的向量积从而完成连接.标准重分区算法在现有云数据管理系统比较常见，Pig、Hive和Jaql均实现了这种算法[8,5,8].该算法的一个潜在问题是针对某个连接键值计算向量积时，两个表的相关数据都要放入内存进行缓存.当连接键值基数比较少或者出现数据倾斜时，会导致某个连接键值对应的数据量较大，一方面可能会造成内存溢出，另一方面造成计算资源分布不均匀.
　　改进的重分区算法[29].为了解决标准重分区算法的内存缓存问题，该算法从两个方面进行了改进：首先，map阶段输出的键值由连接的列值和表名的标签值混合构成，标签值放到键值中可以保证在reduce阶段进行排序时，来自其中一个表的数据总是排在另一个表的前面.其次，在计算卡氏积时，内存中只缓存较小表的数据，而另一个大表的数据以数据流的方式读入内存.这样，算法对内存大小的要求大大降低.
　　广播算法['25'28%].该算法将两个表中较小的一个以广播的形式传输到另一个表数据所在的节点上，然后在每个节点上直接进行连接.算法由一个只有map函数而reduce函数为空的MapReduce作业完成.作业初始化阶段对小表只进行数据广播，然后在Map阶段直接对数据进行Hash连接.由于广播算法没有reduce操作，因此避免了混洗过程中的数据传输和排序.当进行连接的两个表数据量相差很大时，广播小表的数据传输代价将会大大小于混洗过程中的数据传输代价，从而提高连接效率.
　　半连接算法[29].半连接算法基于广播算法进行改进，旨在减少广播过程中的数据传输量.广播的表只中并不是所有的数据都会参与连接，因此在传输数据之前通过半连接操作去除部分数据.该算法由3个MapReduce作业构成.第1个作业主要扫描S表并生成其连接键值文件S.M^.第2个作业根据文件S.M中的键值过滤只中每个子表的数据，生成一系列的数据文件第3个作业依据过滤后的只表数据执行广播算法.尽管半连接算法减少了广播过程中的数据传输量，但增加了对表S和只的扫描.因此具体选择哪种算法要根据连接表的大小以及连接键值的分布情况决定.
　　分片半连接算法[29].该算法将半连接的粒度缩小到S的每个分片子表&'，它同样由3个MapReduce作业构成.第1个作业生成S的链接键值文件，与前一个算法不同的是这个作业只有map操作，针对每个子表没生成连接键值文件Sz.k第2个作业执行半连接，针对每个没，根据只的匹配记录文件和标记生成与子表没相对应的广播数据文件只s,.第3个作业只有map操作，每个mapper读入对应的数据文件并直接进行连接操作.与普通的半连接算法相比，分片半连接算法在广播过程中数据传输量较少，但是需要为每个子表Sz过滤一次只.
　　冗余重分区算法[30].该算法使用一个二维矩阵表示两表的笛卡尔积，通过将满足连接条件的元素设定为"真"表示各种不同连接类型的结果.所有的连接均由一个MapReduce作业完成，通过均衡每个reducer任务输入和输出的数据量来达到减少查询执行时间的目的.算法根据reducer任务的个数r将二维矩阵分成r个大小均衡的区域，每个reducer负责产生相应区域的连接结果，其输入的数据量则等于区域矩形的周长之半.与以往的连接算法不同，在冗余重分区算法中，一个记录可能被重定向到多个reducer任务的区域中.算法正是通过这种冗余重定向实现了非等值连接，并减轻了数据倾斜的影响，但增加了混洗过程中的数据传输量
　　除了两表等值连接，多表等值连接在数据分析和决策支持中的应用也非常广泛，星形连接和链式连接是主要的两种连接形式.文献[31]提出了一种基于"数据冗余传输"的算法.该算法只包含一个MapReduce作业，数据的冗余传输在map之后的混洗过程中进行，冗余传输的次数和方式则由"mapkey"决定.Map键值是多个连接属性的集合，其中每个连接属性对应着一个共享值（share)，表示该属性Hash后的桶数.Mapper输出的每个键值对可能传输到多个reducer，其个数由Map键值中没有被该表覆盖的连接属性共享值的乘积决定.在reduce阶段，直接对传输到本地的数据进行连接.这种算法比较适合星形连接或者表数不多的链式连接，随着链式连接的表数不断增多，传输代价也成倍增加.文献[32]提出了一种利用二部图进行连接的算法，该算法主要应用在链式连接上设参加链式连接表的个数为w,首先使用w个MapReduce作业为每个表生成一个二部图，然后执行2("-1)个作业根据二部图按照和链式连接相反的顺序减少每个表参与连接的记录数，最后利用浓密树提高连接的并行度，这样最少再执行W-1)个作业执行连接.该算法从最大程度上减少了连接过程中的数据传输量，但是需要的MapReduce作业个数较多.
　　与等值连接不同，集合相似性连接要求计算两个表（或者集合）中所有元素的相似度，因此减少数据传输的方法比等值连接复杂.文献[33]提出了一种使用MapReduce实现集合相似性连接的算法，利用"前缀过滤"[36]原则减少参加连接的候选数据对.该算法包括3个步骤：第1步计算用于前缀过滤的全局词项排序，包括两个MapReduce作业，分别用于统计和排序，第2步利用词项排序执行前缀过滤并生成连接结果的行键值对（row-IDpar)，第3步根据行键值对取得实际的连接结果，这两步各使用一个MapReduce作业.该算法通过前缀过滤减少了连接过程中的数据传输代价，但其应用范围比较固定，适用于字符串类型的相似连接.
　　(2)基于调整后MapReduce的连接算法
　　原始的MapReduce框架是一个"过滤-聚集"的过程，这对处理同构的数据源比较有效[37]，然而在处理多表连接时会遇到两方面的问题.一方面，参加连接的数据源往往是异构的，因此在连接处理过程中需要对不同数据源的数据进行同构化处理，例如增加数据源标记等.同构化处理过程不但需要额外的存储开销，而且增加了数据传输量.另一方面，原始的MapReduce框架在处理多表连接时会产生大量中间结果和检查点，这也增加了数据传输量.
　　文献[34]针对异构数据源问题对MapReduce框架进行了扩展，在reduce步骤结束后增加了一个merge的步骤，形成Map-Reduce-Merge框架.Merge的输入数据可以来自不同reducer的输出，这样在一个MapReduce作业里可以处理多个数据源.实现连接的过程类似于传统MapReduce上的重分区连接，不过在map阶段不需要为不同表的数据登记标签，merge阶段可以将两个表对应reduer输出的排序数据进行合并连接.新加坡国立大学的研究人员提出了Map^Join-Reduce框架[35]，并对原始MapReduce的处理过程进行了两方面的扩展.针对第1个问题，文献[35]提出了"过滤-连接^聚集"的编程框架，连接函数可从多个数据源读入数据进行处理，连接函数内容和连接顺序由用户定义.针对第2个问题，Map-Join-Reduce对Map完成后的混洗过程进行了扩展，将原来的"一对一"模式扩展成"一对多"模式，Map函数输出的中间结果一次可以传给多个连接函数.这样通过相应的分区策略可以用一个MapReduce作业完成多表连接，从而减少多个作业处理过程带来的大量中间结果存储和传输问题.

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。