本系列的开篇在提到使用Map-Reduce实现Join之前,先来看看目前在数据库中应用比较广泛和流行的集中Join算法。它们分别是嵌套循环Join(Nested Loops Join)、排序合并Join(Sort-Merge Join)和哈希Join(Hash Join)。
1.嵌套循环Join
for R中的每一条记录r do
for S中的每一条记录s do
if (r和s满足Join条件)
将r和s进行合并,然后输出
end for
end for
这种Join算法实现起来非常简单,而且可以支持任何类型的Join条件。但是在当两个集合包含的记录数变大的情况下,性能下降非常厉害,因为对于一个具有n条记录的集合R和m条记录的集合S来说,时间复杂度是O(m*n)。
2.排序合并Join
合并排序Join,应该使用比较普遍的算法,对于两个需要进行Join的集合P和Q,首先分别对这两个集合进行排序,每个集合在排序时使用的属性就是Join的时候需要用的属性。排序完成之后使用下面的算法对这两个集合进行合并:
p∈P;q∈Q;gq∈Q
while q中还有记录 do
while p.a gq.b do
令gq指向集合Q中的下一条记录
end while
while p.a == gq.b do
q = gq //找到要Join的两条记录了
while p.a == q.b do
将记录p和q Join之后输出
令q指向集合Q中的下一条记录
end while
令p指向集合P中的下一条记录
end while
gq = q //记录查询可以进行Join的记录
end while
假设数据集合P和Q中的记录情况如下:
集合P:
A | B |
ABC | 1 |
ABC | 2 |
ABC | 9 |
ABC | 8 |
ABC | 0 |
ABC | 3 |
ABC | 5 |
ABC | 7 |
ABC | 4 |
ABC | 6 |
集合Q:
C | B |
DEF | 5 |
DEF | 6 |
DEF | 9 |
DEF | 4 |
DEF | 6 |
DEF | 3 |
DEF | 8 |
DEF | 8 |
DEF | 4 |
DEF | 5 |
我们通过B列对两个数据集合进行Join,首先需要对两个集合在B列上进行排序,得到的接结果如下:
集合P:
A | B |
ABC | 0 |
ABC | 1 |
ABC | 2 |
ABC | 3 |
ABC | 4 |
ABC | 5 |
ABC | 6 |
ABC | 7 |
ABC | 8 |
ABC | 9 |
集合Q:
C | B |
DEF | 3 |
DEF | 4 |
DEF | 4 |
DEF | 5 |
DEF | 5 |
DEF | 6 |
DEF | 6 |
DEF | 8 |
DEF | 8 |
DEF | 9 |
根据算法,当第一次发现有可以Join的两个记录时,指向集合P和集合Q的两个记录指针的位置如下图所示:
发现有可以Join的记录之后,根据算法,会将p和q所指向的两条记录进行Join,然后输出,之后q指向下一条记录,这个时候发现p和q的B列值不相等了,根据算法p会指向下一条记录,由于这个时候p和q指向的B列值相等,因此算法中的前两个while循环被跳过,直接进入第三个while循环,找个循环将集合P中B值为4的一条记录与集合Q中B列值为4的两条记录进行Join,循环结束之后,p和q的指向如下图所示:
算法继续执行,知道两个集合中B列值相等的所有记录都被Join之后,算法结束。
3.哈希Join
哈希Join需要将被Join的两个数据集合中的一个全部载入内存的哈希表中。因此,这种Join方式适用于被Join的两个数据集合中,有一个集合数据量比较小,可以全部放入内存的场景。这种Join方式的伪代码如下,其中有两个数据集合,分别是P和Q,而集合P数据量比较小,可以全部载入内存中的哈希表中:
for 集合P中的记录p do
将p载入内存中的哈希表H中
end for
for 集合Q中的记录q do
if H中有记录与q在Join条件匹配
将p和q做Join操作,然后将结果输出
end if
end for
这种Join算法同样只能用于等值Join操作。相比于排序合并Join,这种方式速度要更快,但是对内存的消耗比较大。
- 大小: 25.2 KB
- 大小: 26.6 KB
分享到:
相关推荐
NULL 博文链接:https://mysun.iteye.com/blog/1748484
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之类的高层工具也可以实现,本代码旨在展示手工连接的流程
它需要一个 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...
通过使用 python 执行一些本地 map reduce 任务来模拟算法 data/MapReduce.py -- 执行 mapreduce 的函数。 所有其他脚本都调用此方法来执行 map 和 reduce。 data/inverted_index.py -- 创建倒排索引。 给定一组...
Map/Reduce是海量离线数据分析中广泛应用的并行编程模型.Hive数据仓库基于Map/Reduce实现了查询处理引擎,然而Map/Reduce框架在处理偏斜数据时会出现工作负载分布不均的问题.均衡计算模型(computation balanced model...
The Joins query by using Hadoop and map reduce
数据可以有许多来源,如Kafka, Flume, Twitter,ZeroMQ或传统TCP套接字,可以使用复杂算法对其处理实现高层次的功能,如map,reduce,join和window。最后,经处理的数据可被输出到文件系统,数据库,和实时仪表盘。事实...
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 ...
在这个函数的内部,是通过临时创建一个元素,并将这个元素的 innerHTML 属性设置为给定的标记字符串,来实现标记到 DOM 元素转换的。所以,这个函数既有灵活性,也有局限性。 jQuery 代码: $("<div><p>Hello</p>...
以及 TCP sockets,从数据源获取数据之后,可以使用诸如 map、reduce、join 和 window 等 高级函数进行复杂算法的处理。最后还可以将处理结果存储到文件系统,数据库和现场仪表盘。 在“One Stack rule them all”的...
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 小文件进行合并;...
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.