在本系列的第一篇中,介绍了几种在数据库应用中常见的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操作了。所采用的算法如下:
void reduce(TextPair key , Iterator <TextPair> values ,
OutputCollector <Text , Text > output , Reporter reporter)
throws IOException {
ArrayList<Text> T1 = new ArrayList<Text>();
Text tag = key.getSecond();
TextPair value = null;
while(values.hasNext()){
value = values.next();
if(value.getSecond().compareTo(tag)==0) {
T1.add(value.getFirst());
} else {
for(Text val : T1) {
output.collect(key.getFirst(),
new Text(val.toString() + "\t" + value.getFirst().toString()));
}
}
}
}
算法中的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)。
- 大小: 264.2 KB
分享到:
相关推荐
NULL 博文链接:https://mysun.iteye.com/blog/1748484
Map-Reduce-Join-Locate: a Data Processing Framework for
19、Join操作map side join 和 reduce side join 网址:https://blog.csdn.net/chenwewi520feng/article/details/130455477 本文介绍mapreduce的join操作。 本文前提是hadoop可以正常使用。 本文分为3个部分介绍,即...
thetaJoin 使用 Map-Reduce 编程框架实现 theta 连接的算法
【MapReduce篇06】MapReduce之MapJoin和ReduceJoin1
展示使用MR方式实现表连接的代码示例。利用HIVE PIG之类的高层工具也可以实现,本代码旨在展示手工连接的流程
它需要一个 map-reduce 任务来加入 2 个数据集,将中间结果写入 HDFS,另一个 map-reduce 任务读回中间结果进行聚合。 Query4_1.java 仅使用一个 map-reduce 任务来完成。 此方法适用于映射器侧连接。 它使用...
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。最后,经处理的数据可被输出到文件系统,数据库,和实时仪表盘。事实...
jQuery 的核心功能都是通过这个函数实现的。 jQuery中的一切都构建于这个函数之上,或者说都是在以某种方式使用这个函数。这个函数最基本的用法就是向它传递一个表达式(通常由 CSS 选择器组成),然后根据这个...
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”的...
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.