厦门大学数据库实验室MapReduce连接优化.ppt
《厦门大学数据库实验室MapReduce连接优化.ppt》由会员分享,可在线阅读,更多相关《厦门大学数据库实验室MapReduce连接优化.ppt(39页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、厦门大学数据库实验室MapReduce连接优化 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望连接技术简介连接技术简介基于传统基于传统 MapReduce 的连接的连接基于数据索引的连接基于数据索引的连接基于改进基于改进 MapReduce 的连接的连接连接技术比较连接技术比较 连接操作广泛应用于日志分析、联机分析处理及数据分析处理等方面。如果提高大数据连接计算速度,则可提高数据分析效率和用户体验度。下表对现有的MapReduce连接技术进行了分类与对比。连接技术
2、简介连接技术简介基于传统基于传统 MapReduce 的连接的连接基于数据索引的连接基于数据索引的连接基于改进基于改进 MapReduce 的连接的连接基于传统基于传统 MapReduce 的连接的连接 这类算法主要通过实现map函数、reduce函数及之间的数据流传递,来完成数据连接运算。对于这方面的研究主要集中于两表等值连接、两表非等值连接(又称连接)、两表相似度连接、多表等值连接(星型连接、链式连接)、多表非等值连接等问题。标准重分区算法标准重分区算法welcome to use these PowerPoint templates,New Content design,10 years
3、 experience算法回顾算法回顾 标准重分区算法由一个标准重分区算法由一个MapReduce作业来完成连接运算。两个表的数作业来完成连接运算。两个表的数据都由据都由 Mapper 读入,根据查询条件进行过滤读入,根据查询条件进行过滤intermediate,生成,生成keyintermediate/valueintermediate对,其中对,其中 key是待连接列的数值,是待连接列的数值,valueintermediate则由用于标记数据来自哪个表的标签和记录值组成。在混洗则由用于标记数据来自哪个表的标签和记录值组成。在混洗过程中,具有相同连接值的数据会被分到同一个过程中,具有相同连接
4、值的数据会被分到同一个Reducer上。上。Reducer根据标签将数据分为两个集合,再完成连接运算。标准重分区算法在根据标签将数据分为两个集合,再完成连接运算。标准重分区算法在Reducer上需要将数据全部装载到内存中,可能会造成内存溢出。另外,上需要将数据全部装载到内存中,可能会造成内存溢出。另外,当存在数据倾斜时,标准重分区算法容易造成数据分布不均,以及连接当存在数据倾斜时,标准重分区算法容易造成数据分布不均,以及连接速度缓慢和计算资源分布不均等问题。速度缓慢和计算资源分布不均等问题。改进的标准重分区算法改进的标准重分区算法welcome to use these PowerPoint
5、templates,New Content design,10 years experience算法回顾算法回顾 为了解决标准重分区算法需要占用较大内存的问题,改进的标准为了解决标准重分区算法需要占用较大内存的问题,改进的标准重分区算法进行了以下优化:生成重分区算法进行了以下优化:生成 keyintermediate/valueintermediate对时,对时,keyintermediate值由待连接列的数值与表的标签共同构成,这样可以使值由待连接列的数值与表的标签共同构成,这样可以使一个表的数据都排在另一个表的前面。在混洗阶段,通过自定义的一个表的数据都排在另一个表的前面。在混洗阶段,通过
6、自定义的partition函数来使含有同一连接值的数据仍然分到同一个函数来使含有同一连接值的数据仍然分到同一个Reducer上。在上。在Reduce阶段,在内存中缓存较小的表,另一表以流式方式读阶段,在内存中缓存较小的表,另一表以流式方式读入并进行连接操作。入并进行连接操作。广播算法广播算法welcome to use these PowerPoint templates,New Content design,10 years experience算法回顾算法回顾 广播算法将待连接的两个表中较小的表以广播的方式传输广播算法将待连接的两个表中较小的表以广播的方式传输到另一个表所在节点上,然后在该
7、节点上进行连接操作。广到另一个表所在节点上,然后在该节点上进行连接操作。广播算法只需要一个无播算法只需要一个无Reduce的的MapReduce作业就可以完成,作业就可以完成,省去了数据混洗与排序的过程。当两表数据量相差很大时,省去了数据混洗与排序的过程。当两表数据量相差很大时,广播算法具有很高的效率。然而当待连接的两个表都很大时,广播算法具有很高的效率。然而当待连接的两个表都很大时,广播算法效率很低。广播算法效率很低。半连接算法半连接算法welcome to use these PowerPoint templates,New Content design,10 years experien
8、ce算法回顾算法回顾 半连接算法使用三个半连接算法使用三个 MapReduce作业来完成运算,第一作业来完成运算,第一个个MapReduce 作业生成第一个表作业生成第一个表S的连接值文件。第二个的连接值文件。第二个MapReduce作业利用前一步生成的连接值文件,采用类似作业利用前一步生成的连接值文件,采用类似广播算法的方法对第二个表广播算法的方法对第二个表R的数据进行过滤。第三个的数据进行过滤。第三个MapReduce作业利用过滤后的作业利用过滤后的R表数据,采用广播算法进行表数据,采用广播算法进行连接。连接。分片半连接算法分片半连接算法welcome to use these Power
9、Point templates,New Content design,10 years experience算法简介算法简介 分片半连接算法需要三个分片半连接算法需要三个MapReduce作业来完成连接运作业来完成连接运算。第一个算。第一个MapReduce作业对于表作业对于表S的每一分片生成该分片的每一分片生成该分片的连接值文件。第二个的连接值文件。第二个MapReduce作业根据表作业根据表S的每一分片的每一分片的连接值与表的连接值与表R进行半连接,生成每一分片的连接文件。第进行半连接,生成每一分片的连接文件。第三个三个MapReduce作业读入前一步生成的每一分片的连接文作业读入前一步生
10、成的每一分片的连接文件,进行连接运算,生成最终结果。件,进行连接运算,生成最终结果。分片半连接算法分片半连接算法 半连接存在的一个问题是半连接存在的一个问题是:并不是过滤后的并不是过滤后的R中的每条记录都中的每条记录都要和要和L(S)中的某分区做连接。分片半连接解决了这个问题。)中的某分区做连接。分片半连接解决了这个问题。等值连接等值连接 前面所介绍的标准重分区算法、改进标准重分区算法、前面所介绍的标准重分区算法、改进标准重分区算法、广播算法、半连接算法、分片半连接算法均属于等值连接广播算法、半连接算法、分片半连接算法均属于等值连接的算法,相对简单一些。的算法,相对简单一些。非等值连接非等值连
11、接 处理非等值连接时,由于不能预先知道两表值的分布情处理非等值连接时,由于不能预先知道两表值的分布情况,需要处理比等值连接更加复杂的问题。下面介绍一个况,需要处理比等值连接更加复杂的问题。下面介绍一个利用一个利用一个MapReduce 作业处理非等值连接操作的算法。作业处理非等值连接操作的算法。非等值连接举例非等值连接举例 Consider a join between data sets S and T with an inequality condition like S.A=T.A.Such joins seem inherently difficult for MapReduce,be
12、cause each T-tuple has to be joined not only with S-tuples that have the same A value,but also those with different(smaller)A values.It is not obvious how to map the inequality join condition to a key-equality based computing paradigm.两个待连接数据集:两个待连接数据集:S、T连接条件:连接条件:S.A=T.AMapReduce连接遇到的问题:一个连接遇到的问题:
13、一个T元组可能和一个或多个元组可能和一个或多个S元元组做连接。组做连接。非等值连接算法非等值连接算法welcome to use these PowerPoint templates,New Content design,10 years experience算法简介算法简介 该算法利用一个二维矩阵来表示两表的笛卡儿积,通过对矩阵中满足运算该算法利用一个二维矩阵来表示两表的笛卡儿积,通过对矩阵中满足运算结果的范围进行标记的方法表示各运算所需要的数据。为了减少任务执行时间,结果的范围进行标记的方法表示各运算所需要的数据。为了减少任务执行时间,并减小数据倾斜带来的影响,该算法对并减小数据倾斜带来的
14、影响,该算法对Reducer的输入量及输出量进行了均衡,的输入量及输出量进行了均衡,将矩阵分成面积相等的将矩阵分成面积相等的R个区域(个区域(region),每个区域都有一个),每个区域都有一个RegionID。在在 map 函数中,对每一个记录可能参与运算的区域都生成一个函数中,对每一个记录可能参与运算的区域都生成一个RegionID,的键值对,在的键值对,在Reduce阶段,每一个阶段,每一个Reducer处理该处理该区域内的非等值连接,并生成最终结果。该算法很好地解决了区域内的非等值连接,并生成最终结果。该算法很好地解决了MapReduce在在处理非等值连接中的数据倾斜与计算平衡问题,但
15、在数据混洗过程中需要很大处理非等值连接中的数据倾斜与计算平衡问题,但在数据混洗过程中需要很大的数据传输量。的数据传输量。非等值连接算法非等值连接算法S=5,7,7,8,9,9T=5,7,7,7,8,9标记的二维矩阵标记的二维矩阵均衡均衡Reducer的输入量及输出的输入量及输出量量相似度连接举例相似度连接举例 For example,in master-data-management applications,a system has to identify that names“John W.Smith”,“Smith,John”,and“John William Smith”are pot
16、entially referring to the same person.As another example,when mining social networking sites where users preferences are stored as bit vectors(where a“1”bit means interest in a certain domain),applications want to use the fact that a user with preference bit vector“1,0,0,1,1,0,1,0,0,1”possibly has s
17、imilar interests to a user with preferences“1,0,0,0,1,0,1,0,1,1”.相似度连接算法相似度连接算法welcome to use these PowerPoint templates,New Content design,10 years experience算法简介算法简介 该算法首先利用两个该算法首先利用两个MapReduce作业进行数据统计与全局词项作业进行数据统计与全局词项排序。接着利用一个排序。接着利用一个MapReduce 作业,通过前缀过滤的方法减少作业,通过前缀过滤的方法减少需要参加相似连接运算的数据,并生成连接结果的键
18、值对。最后通需要参加相似连接运算的数据,并生成连接结果的键值对。最后通过一个过一个MapReduce作业,根据前一步生成的键值对生成最后的相似作业,根据前一步生成的键值对生成最后的相似性连接结果。该算法充分利用了相似性连接的特点,过滤掉不可能性连接结果。该算法充分利用了相似性连接的特点,过滤掉不可能成为最终结果的数据,提高了查询效率,但应用范围只限于文本字成为最终结果的数据,提高了查询效率,但应用范围只限于文本字符串的相似性连接。符串的相似性连接。相似度连接算法相似度连接算法数据统计与全局数据统计与全局词项排序词项排序b第二阶段用第二阶段用tear-down function在内存中排序在内存
19、中排序相似度连接算法相似度连接算法前缀过滤前缀过滤A属于属于X组,组,B、G属于属于Y组,组,C、D属于属于Z组组相似度连接算法相似度连接算法前缀过滤前缀过滤A属于属于X组,组,B、G属于属于Y组,组,C、D属于属于Z组组根据前一步根据前一步生成的键值生成的键值对生成最后对生成最后的相似性连的相似性连接结果接结果把第一阶把第一阶段产生的段产生的结果广播结果广播给每个给每个map多表连接多表连接 在数据库应用领域中,经常需要对多个表进行连接操作,比较有代表性的是星型连接与链式连接。星型连接:在数据仓库应用中,星型模式是最常用的数据表示模型,包括一个事实表和多个维表.链式连接:星型连接星型连接事实
20、表LINEORDER和4个维表CUSTOMER、SUPPLIER、PART和DATE.在基于星型模式的OLAP查询中,涉及最多的操作就是维表和事实表的连接,又被称为星型连接.星型连接返回连接的全部结果,是OLAP查询中代价最高的操作之一.例1.SELECT*FROM LineorderF,CustomerC,SupplierS,PartP,DateDWHERE F.custkey=C.custkey and F.suppkey=S.suppkey and F.partkey=P.partkey and F.orderdate=D.datekeyORDER BY F.squantity+C.sc
21、redit+S.saddress+P.sbrand1+D.stimeSTOP AFTER k;多表等值连接算法多表等值连接算法welcome to use these PowerPoint templates,New Content design,10 years experience算法简介算法简介 该算法的基本思想是,对于每一个连接属性,都有一个对应的共该算法的基本思想是,对于每一个连接属性,都有一个对应的共享值表示这个属性进行享值表示这个属性进行 Hash 后的桶数,后的桶数,Map 输出的输出的 keyintermediate/valueintermediate对需要传到该表没有包含的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 厦门大学 数据库 实验室 MapReduce 连接 优化
限制150内