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

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

 
阅读更多
在本系列的第一篇中,介绍了几种在数据库应用中常见的Join算法,本文将会介绍两种使用Map-Reduce实现对两个数据集合进行Join的算法,其中的一种会用到第一篇中提到的哈希Join算法。这里将这两种方法分别命名为Map-Reduce Join和Map-Only Join。 
1. Map-Reduce Join 
这种Join方法,需要在hadoop上执行一个完整的Map-Reduce过程。下面的图说明了这个过程。 
  • Map过程
Map过程从需要进行合并的数据集合中读取数据,以Join条件中被用到的那一列的值为key,以整行数据为Value,将结果写到输出流中。为了标记Map集合中的每一行记录来自于哪个源数据集合,需要位Key添加一个标识。例如,有数据集合P(A,B)和Q(C,B),其中P集合有A、B两列,而Q集合有B、C两列,在根据B列对两个数据集合进行Join的情况下,P集合中的数据经过Map之后将以(B,tag,A+B)的形式输出,其中B列的值与tag的值共同组成Key,而整行记录将作为Value输出。对于Q来说也是如此,Q集合经过Map之后将以(B,tag,B+C)的形式输出。
  • tag的作用
tag的作用是为了区分数据来源,以便在Reduce阶段可以对不同来源的记录进行Join。但是,由于在Key中增加了一个tag,如果使用Hadoop默认的切分方法(Partitioner),会将B列值相同的记录分配给不同的Reducer,因此我们需要提供自定义的Partitioner,在选择Reducer的时候,不去考虑tag。 
在数据丢给Reducer的reduce方法进行处理之前,Hadoop会根据key将数据进行聚合,把具有相同key的数据组合到一起去。由于在Key中增加了tag标识,如果使用Hadoop提供的默认分组方法,来自于不同集合的记录是无法被组合到一起去的,因此,我们同样需要提供自定义的分组排序算法,在分组的时候不去考虑tag标识,同时保证在同一个Key下面,来自于一个集合的所有记录都会排在另外一个集合的所有记录之前。
  • Reduce过程
在Reduce阶段,由于Map-Reduce方法保证具有相同Key的数据会被丢给同一个Reducer进行处理,因此P和Q中,在B列值相同的记录会被同一个Reducer进行处理,这个时候就可以执行Join操作了。所采用的算法如下: 
Java代码  收藏代码
  1. void reduce(TextPair key , Iterator <TextPair> values ,   
  2.         OutputCollector <Text , Text > output , Reporter reporter)  
  3.         throws IOException {  
  4.     ArrayList<Text> T1 = new ArrayList<Text>();   
  5.     Text tag = key.getSecond();  
  6.   
  7.     TextPair value = null;   
  8.     while(values.hasNext()){  
  9.         value = values.next();   
  10.         if(value.getSecond().compareTo(tag)==0) {  
  11.             T1.add(value.getFirst());   
  12.         } else {  
  13.             for(Text val : T1) {  
  14.                 output.collect(key.getFirst(),  
  15.                 new Text(val.toString() + "\t" + value.getFirst().toString()));  
  16.             }   
  17.         }  
  18.     }   
  19. }  

算法中的Key和Value都使用了TextPar类,找个类可以封装两个Text对象,对于Key来说,这个TextPair封装了被Join列的值以及第一个其中一个数据集合的tag,而对于Value来说,TextPair则封装了每个集合中的记录以及这个记录的来源。 
2. Map-Only Join 
这种Join算法类似于本系列第一篇中提到的哈希Join,本质是将哈希Join应用到分布式环境中。这种Join方式,要求被Join的两个数据集合中,至少有一个集合的数据量能够被完全载入内存中。 
这个算法,在每一个Mapper启动之前,将数据量较小的结合中的数据载入内存的哈希表中,而map方法则是读取另外一个集合的数据记录,与预先载入到内存哈希表中的另外一个集合的记录进行Join。 
由于在这种算法中,需要将数据量比较小的那个集合中的记录复制到每一个Mapper的内存中,因此也被叫做广播Join算法(Broadcase Join)。
 转自:http://mysun.iteye.com/blog/1748480
 
3. 半链接等其他
 请参考 

MapReduce中的两表join几种方案简介


   
分享到:
评论

相关推荐

    【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中实施联接

    2. **Map-Side Join**:当数据可以预先排序且可以划分到Map任务的大小时,可以在Map阶段进行部分Join。每个Mapper会加载其负责的部分小表数据,然后与大表数据进行Join。这种方法减少了网络传输,但需要额外的排序和...

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

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

    Hive-Summit-2011-join.zip_hive

    2. **MapReduce与Join**:Hive的Join操作通常通过MapReduce任务执行,这意味着数据被分发到集群的不同节点进行处理。在处理大表连接时,可能会导致大量的数据交换,这被称为“shuffle阶段”,是Join操作的性能瓶颈。...

    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源代码

    2. `Reduce`类:处理Map阶段产生的中间结果,执行实际的JOIN操作。 3. `Driver`类:主程序,负责设置输入、输出路径,启动MapReduce作业。 4. 测试用例和样例数据:用于验证和测试JOIN实现的正确性和性能。 5. 配置...

    Hive Summit 2011-join

    2. Map Join(映射Join) Map Join是针对大数据集join操作的一种优化策略。在Map Join中,小表会被复制到每个Mapper节点的内存中。因此,在Map阶段完成之后,只需要对大表进行处理即可,减少了数据的Shuffle传输,...

    基于 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算法

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

    Mapside-Join

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

Global site tag (gtag.js) - Google Analytics