在本系列的前面几篇文章中,主要介绍了利用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
- 大小: 15.2 KB
分享到:
相关推荐
Map-Reduce-Join-Locate: a Data Processing Framework for
thetaJoin 使用 Map-Reduce 编程框架实现 theta 连接的算法
19、Join操作map side join 和 reduce side join 网址:https://blog.csdn.net/chenwewi520feng/article/details/130455477 本文介绍mapreduce的join操作。 本文前提是hadoop可以正常使用。 本文分为3个部分介绍,即...
【MapReduce篇06】MapReduce之MapJoin和ReduceJoin1
展示使用MR方式实现表连接的代码示例。利用HIVE PIG之类的高层工具也可以实现,本代码旨在展示手工连接的流程
Query4.java 使用两个 map-reduce 任务来完成。 此方法适用于减速器侧连接。 它需要一个 map-reduce 任务来加入 2 个数据集,将中间结果写入 HDFS,另一个 map-reduce 任务读回中间结果进行聚合。 Query4_1.java ...
Map/Reduce framework seems to be specifically designed for group-by aggregation tasks rather than across-table op- erations; on the other hand, join operation in distributed database systems was never...
Map/Reduce是海量离线数据分析中广泛应用的并行编程模型.Hive数据仓库基于Map/Reduce实现了查询处理引擎,然而Map/Reduce框架在处理偏斜数据时会出现工作负载分布不均的问题.均衡计算模型(computation balanced model...
通过使用 python 执行一些本地 map reduce 任务来模拟算法 data/MapReduce.py -- 执行 mapreduce 的函数。 所有其他脚本都调用此方法来执行 map 和 reduce。 data/inverted_index.py -- 创建倒排索引。 给定一组...
The Joins query by using Hadoop and map reduce
3.5.1 Reduce-Side Join 64 3.5.2 Map-Side Join 66 3.5.3 Memory-Backed Join 67 3.6 Summary 4 Inverted Indexing for Text Retrieval 4.1 Web Crawling 4.2 Inverted Indexes 4.3 Inverted Indexing: Baseline ...
数据可以有许多来源,如Kafka, Flume, Twitter,ZeroMQ或传统TCP套接字,可以使用复杂算法对其处理实现高层次的功能,如map,reduce,join和window。最后,经处理的数据可被输出到文件系统,数据库,和实时仪表盘。事实...
9.3.3 MapJoin;9.3.4 Group By;9.3.5 Count(Distinct) 去重统计;9.3.6 笛卡尔积;9.3.7 行列过滤;9.3.8 动态分区调整;9.3.9 分桶;9.3.10 分区);9.4 数据倾斜(9.4.1 合理设置Map数;9.4.2 小文件进行合并;...
以及 TCP sockets,从数据源获取数据之后,可以使用诸如 map、reduce、join 和 window 等 高级函数进行复杂算法的处理。最后还可以将处理结果存储到文件系统,数据库和现场仪表盘。 在“One Stack rule them all”的...
jQuery 的核心功能都是通过这个函数实现的。 jQuery中的一切都构建于这个函数之上,或者说都是在以某种方式使用这个函数。这个函数最基本的用法就是向它传递一个表达式(通常由 CSS 选择器组成),然后根据这个...
FocusBigData :elephant:Hadoop分布存储框架 Hadoop篇 HDFS篇 HDFS客户端操作 --- 开发环境准备 HDFS客户端操作 --- 文件操作 HDFS客户端操作 --- IO流操作 ...MapReduce之MapJoin和ReduceJoin MapReduce之
这些章节探讨了诸如Task-Parallel库之类的主题,实现了诸如Fork / Join,分而治之和Map-Reduce之类的并行模式。 还讨论了声明式组合,异步操作中的高级抽象,代理程序编程模型以及消息传递语义。 然后,第13章和第...
文件汗有三个java类,两个测试文件txt ReduceClass.java MapClass.java TaggedRecordWritable.java customers.txt orders.txt 经过亲自测试,可以将两个文件中的信息以groupby的key关联起来,查出类似数据库的join.