`
Mysun
  • 浏览: 273168 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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

 
阅读更多
本系列的开篇在提到使用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:
AB
ABC 1
ABC 2
ABC 9
ABC 8
ABC 0
ABC 3
ABC 5
ABC 7
ABC 4
ABC 6

集合Q:
CB
DEF 5
DEF 6
DEF 9
DEF 4
DEF 6
DEF 3
DEF 8
DEF 8
DEF 4
DEF 5

我们通过B列对两个数据集合进行Join,首先需要对两个集合在B列上进行排序,得到的接结果如下:
集合P:
AB
ABC 0
ABC 1
ABC 2
ABC 3
ABC 4
ABC 5
ABC 6
ABC 7
ABC 8
ABC 9

集合Q:
CB
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
分享到:
评论

相关推荐

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

    我们将讨论在Map和Reduce阶段执行Join的基本原理、策略以及优化技巧。 首先,理解MapReduce的基本工作流程是必要的。MapReduce包含两个主要阶段:Map阶段和Reduce阶段。在Map阶段,输入数据被分割成多个块,并在...

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

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

    Hive-Summit-2011-join.zip_hive

    8. **Hive的Join挑战**:尽管有各种优化策略,但处理大规模数据集的Join仍然是Hive面临的主要挑战之一,特别是涉及多个大表的复杂Join操作。 9. **Best Practices**:在实际应用中,应考虑数据分布、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程序来执行等值连接

    等值连接(Equi-Join)是指基于两个或更多表中的一个或多个公共列的相等条件进行连接。在Hadoop MapReduce中,我们通常需要将数据分片、映射和规约来实现这一过程。以下是一个详细的步骤概述: 1. **数据预处理**:...

    Hive Summit 2011-join

    Hive作为一个数据仓库工具,主要用于处理大规模数据集的分析和查询,而join操作是数据仓库中常见且关键的操作之一。在大数据的背景下,如何高效地执行join操作对于性能优化至关重要。在这一讨论中,将详细介绍Hive中...

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

    本资源"javamap源码-MR-JOIN-JAVACODES"似乎是一个关于Map在MapReduce框架下的Java实现,特别是针对数据连接操作的优化。MapReduce是一种分布式计算模型,由Google提出,常用于大数据处理。 在MapReduce中,Map阶段...

    基于 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操作效率。在传统的数据库系统中,JOIN操作通常在服务器端完成,而在分布式计算环境中,由于数据量庞大,...

Global site tag (gtag.js) - Google Analytics