`
lt200819
  • 浏览: 187542 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

通过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

转自:http://mysun.iteye.com/blog/1748484

分享到:
评论

相关推荐

    【MapReduce篇06】MapReduce之MapJoin和ReduceJoin1

    今天,我们将讲解 MapReduce 之 MapJoin 和 ReduceJoin 两种 Join 操作的实现原理和应用场景。 MapJoin 概述 MapJoin 是一种特殊的 Join 操作,通过在 Map 阶段对数据进行 Join 操作,减少了 Reduce 阶段的数据...

    19、Join操作map side join 和 reduce side join

    本文主要探讨了两种 MapReduce 中的 Join 实现:Map Side Join 和 Reduce Side Join。 一、Join 的概念 Join 操作在数据库中是非常常见的,它用于将来自两个或更多表的数据根据某些共享字段(即键)关联起来。在 ...

    Map-Reduce-Join-Locate: a Data Processing Framework for

    Map-Reduce-Join-Locate: a Data Processing Framework for

    hadoop Join代码(map join 和reduce join)

    本文将深入探讨Map JOIN和Reduce JOIN两种在Hadoop中实现JOIN的方法,并通过代码示例来阐述它们的工作原理。 1. Map JOIN: Map JOIN在Hadoop中主要应用于小表与大表的连接。小表的数据可以完全加载到内存中,而大...

    Mongo-Commands:MongoDB命令速查表。 包含map-reduce,aggregate等

    在MongoDB中,map-reduce用于执行复杂的分析任务,通过将数据分发到多个节点并进行并行处理来提升性能。 **Map阶段**: 在这个阶段,开发者定义一个JavaScript函数(map函数),它遍历集合中的每个文档,并为每个...

    在Hadoop Map-Reduce中实施联接

    4. **Bucket Join** 或 **Sort-Merge Join**:如果所有数据集都可以预先排序并按键分桶,Reducer可以通过合并相邻的桶来执行Join。这种方法适用于多个已排序且大小相当的数据集。 5. **Three-way Join 和 Multi-way...

    thetaJoin:使用 Map-Reduce 编程框架实现 theta 连接的算法

    在MapReduce环境中实现Theta连接,通常分为三个主要步骤:Map、Shuffle和Reduce。 1. **Map阶段**:在这个阶段,我们对输入的数据进行预处理。对于每个表,我们分别读取其记录并生成键值对。键通常是连接字段,值则...

    Hive-Summit-2011-join.zip_hive

    3. **Map-side Join**:为了解决大规模数据集的Join问题,Hive引入了Map-side Join。这种方法适用于小表与大表的连接,小表可以被完全加载到内存中,从而避免了在Reduce阶段的昂贵数据交换。 4. **Bucketing与...

    pig-0.9.2.tar.gz下载

    Pig Latin编写的脚本最终会被转化为一系列的Map-Reduce作业,这是通过Pig的编译器实现的。Pig的这种特性使得开发者可以专注于业务逻辑,而不必关心底层的分布式计算细节。在Pig-0.9.2版本中,对Map-Reduce的优化和...

    大数据课程设计-Hadoop-MapReduce实现sql的统计、groupby和join-全部源码

    3) 内连接(Inner Join)和左连接(Left Join)可以通过一次MapReduce作业实现,Map阶段将JOIN键和对应数据发送到同一Reducer,Reduce阶段根据JOIN条件进行匹配。 在提供的"mapreduce-sql"压缩包文件中,很可能包含...

    Map_Reduce_Hadoop:实施map-reduce程序来执行等值连接

    在大数据处理领域,...总之,通过理解Hadoop MapReduce的工作原理和Java编程接口,我们可以有效地实现等值连接操作,处理大规模数据集的联合任务。这不仅有助于提升数据处理效率,还为大数据分析提供了强大的工具。

    javamap源码-MR-JOIN-JAVACODES:地图减少连接的Java源代码

    4. 测试用例和样例数据:用于验证和测试JOIN实现的正确性和性能。 5. 配置文件:可能包含Hadoop相关的配置信息,如输入/输出格式、分片策略等。 通过对这些源代码的深入学习,我们可以理解如何在分布式环境中有效地...

    Hive Summit 2011-join

    4. Bucket Map Join(分桶Map Join) 分桶Map Join用于处理需要join的大表与大表之间的操作。它通过预先定义的分桶列来分割数据,并确保每一张表都基于相同的列进行分桶。在join过程中,只会将相关桶的数据进行操作...

    基于 MapReduce 快速 kNN Join 方法1

    为了解决这个问题,我们引入了 map-reduce 框架来运行 kNN join 并提出了两种新的方法:基于 map-reduce 的分布式网格概略化 kNN join(DSGMP-J)和基于 map-reduce 的 voronoi diagram 下 kNN join(VDMP-J)。...

    hadoop_join.jar.zip_hadoop_hadoop query_reduce

    本文将深入探讨如何使用Hadoop和MapReduce进行高效的Join查询,并解析如何通过`hadoop_join.jar`这个工具来实现这一过程。 Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它的核心组件包括HDFS(Hadoop ...

    hadoop_join_aggregate:在hadoop中加入和聚合mapreduce算法

    Query4.java 使用两个 map-reduce 任务来完成。 此方法适用于减速器侧连接。 它需要一个 map-reduce 任务来加入 2 个数据集,将中间结果写入 HDFS,另一个 map-reduce 任务读回中间结果进行聚合。 Query4_1.java ...

    Mapside-Join

    Mapside Join是大数据处理领域中的一种优化策略,主要用于Hadoop MapReduce框架,旨在提高大规模数据集的JOIN操作效率。...通过Java编程,我们可以实现高效、可靠的Mapside Join,为海量数据处理提供强大的支持。

Global site tag (gtag.js) - Google Analytics