MapReduce-连接优化-厦门大学数据库室

厦门大学数据库实验室MapReduce连接优化报告人：李雨倩导师：林子雨2014.07.26连接技术简介基于传统MapReduce的连接基于数据索引的连接基于改进MapReduce的连接连接技术比较连接操作广泛应用于日志分析、联机分析处理及数据分析处理等方面。如果提高大数据连接计算速度，则可提高数据分析效率和用户体验度。下表对现有的MapReduce连接技术进行了分类与对比。连接技术简介基于传统MapReduce的连接基于数据索引的连接基于改进MapReduce的连接基于传统MapReduce的连接这类算法主要通过实现map函数、reduce函数及之间的数据流传递，来完成数据连接运算。对于这方面的研究主要集中于两表等值连接、两表非等值连接（又称θ连接）、两表相似度连接、多表等值连接（星型连接、链式连接）、多表非等值连接等问题。标准重分区算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法回顾标准重分区算法由一个MapReduce作业来完成连接运算。两个表的数据都由Mapper读入，根据查询条件进行过滤intermediate，生成keyintermediate/valueintermediate对，其中key是待连接列的数值，valueintermediate则由用于标记数据来自哪个表的标签和记录值组成。在混洗过程中，具有相同连接值的数据会被分到同一个Reducer上。Reducer根据标签将数据分为两个集合，再完成连接运算。标准重分区算法在Reducer上需要将数据全部装载到内存中，可能会造成内存溢出。另外，当存在数据倾斜时，标准重分区算法容易造成数据分布不均，以及连接速度缓慢和计算资源分布不均等问题。改进的标准重分区算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法回顾为了解决标准重分区算法需要占用较大内存的问题，改进的标准重分区算法进行了以下优化：生成keyintermediate/valueintermediate对时，keyintermediate值由待连接列的数值与表的标签共同构成，这样可以使一个表的数据都排在另一个表的前面。在混洗阶段，通过自定义的partition函数来使含有同一连接值的数据仍然分到同一个Reducer上。在Reduce阶段，在内存中缓存较小的表，另一表以流式方式读入并进行连接操作。广播算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法回顾广播算法将待连接的两个表中较小的表以广播的方式传输到另一个表所在节点上，然后在该节点上进行连接操作。广播算法只需要一个无Reduce的MapReduce作业就可以完成，省去了数据混洗与排序的过程。当两表数据量相差很大时，广播算法具有很高的效率。然而当待连接的两个表都很大时，广播算法效率很低。半连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法回顾半连接算法使用三个MapReduce作业来完成运算，第一个MapReduce作业生成第一个表S的连接值文件。第二个MapReduce作业利用前一步生成的连接值文件，采用类似广播算法的方法对第二个表R的数据进行过滤。第三个MapReduce作业利用过滤后的R表数据，采用广播算法进行连接。分片半连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法简介分片半连接算法需要三个MapReduce作业来完成连接运算。第一个MapReduce作业对于表S的每一分片生成该分片的连接值文件。第二个MapReduce作业根据表S的每一分片的连接值与表R进行半连接，生成每一分片的连接文件。第三个MapReduce作业读入前一步生成的每一分片的连接文件，进行连接运算，生成最终结果。分片半连接算法半连接存在的一个问题是:并不是过滤后的R中的每条记录都要和L（S）中的某分区做连接。分片半连接解决了这个问题。等值连接前面所介绍的标准重分区算法、改进标准重分区算法、广播算法、半连接算法、分片半连接算法均属于等值连接的算法，相对简单一些。非等值连接处理非等值连接时，由于不能预先知道两表值的分布情况，需要处理比等值连接更加复杂的问题。下面介绍一个利用一个MapReduce作业处理非等值连接操作的算法。非等值连接举例ConsiderajoinbetweendatasetsSandTwithaninequalityconditionlikeS.A=T.A.SuchjoinsseeminherentlydifficultforMapReduce,becauseeachT-tuplehastobejoinednotonlywithS-tuplesthathavethesameAvalue,butalsothosewithdifferent(smaller)Avalues.Itisnotobvioushowtomaptheinequalityjoinconditiontoakey-equalitybasedcomputingparadigm.两个待连接数据集：S、T连接条件：S.A=T.AMapReduce连接遇到的问题：一个T元组可能和一个或多个S元组做连接。非等值连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法简介该算法利用一个二维矩阵来表示两表的笛卡儿积，通过对矩阵中满足运算结果的范围进行标记的方法表示各运算所需要的数据。为了减少任务执行时间，并减小数据倾斜带来的影响，该算法对Reducer的输入量及输出量进行了均衡，将矩阵分成面积相等的R个区域（region），每个区域都有一个RegionID。在map函数中，对每一个记录可能参与运算的区域都生成一个RegionID，Record，Tablename的键值对，在Reduce阶段，每一个Reducer处理该区域内的非等值连接，并生成最终结果。该算法很好地解决了MapReduce在处理非等值连接中的数据倾斜与计算平衡问题，但在数据混洗过程中需要很大的数据传输量。非等值连接算法S={5,7,7,8,9,9}T={5,7,7,7,8,9}①标记的二维矩阵②均衡Reducer的输入量及输出量相似度连接举例Forexample,inmaster-data-managementapplications,asystemhastoidentifythatnames“JohnW.Smith”,“Smith,John”,and“JohnWilliamSmith”arepotentiallyreferringtothesameperson.Asanotherexample,whenminingsocialnetworkingsiteswhereusers’preferencesarestoredasbitvectors(wherea“1”bitmeansinterestinacertaindomain),applicationswanttousethefactthatauserwithpreferencebitvector“[1,0,0,1,1,0,1,0,0,1]”possiblyhassimilarintereststoauserwithpreferences“[1,0,0,0,1,0,1,0,1,1]”.相似度连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法简介该算法首先利用两个MapReduce作业进行数据统计与全局词项排序。接着利用一个MapReduce作业，通过前缀过滤的方法减少需要参加相似连接运算的数据，并生成连接结果的键值对。最后通过一个MapReduce作业，根据前一步生成的键值对生成最后的相似性连接结果。该算法充分利用了相似性连接的特点，过滤掉不可能成为最终结果的数据，提高了查询效率，但应用范围只限于文本字符串的相似性连接。相似度连接算法①数据统计与全局词项排序②b第二阶段用tear-downfunction在内存中排序相似度连接算法①前缀过滤②A属于X组，B、G属于Y组，C、D属于Z组相似度连接算法①前缀过滤②A属于X组，B、G属于Y组，C、D属于Z组③根据前一步生成的键值对生成最后的相似性连接结果把第一阶段产生的结果广播给每个map多表连接在数据库应用领域中，经常需要对多个表进行连接操作，比较有代表性的是星型连接与链式连接。星型连接：在数据仓库应用中,星型模式是最常用的数据表示模型,包括一个事实表和多个维表.链式连接：星型连接事实表LINEORDER和4个维表CUSTOMER、SUPPLIER、PART和DATE.在基于星型模式的OLAP查询中,涉及最多的操作就是维表和事实表的连接,又被称为星型连接.星型连接返回连接的全部结果,是OLAP查询中代价最高的操作之一.例1.SELECT*FROMLineorderF,CustomerC,SupplierS,PartP,DateDWHEREF.custkey=C.custkeyandF.suppkey=S.suppkeyandF.partkey=P.partkeyandF.orderdate=D.datekeyORDERBYF.squantity+C.scredit+S.saddress+P.sbrand1+D.stimeSTOPAFTERk;多表等值连接算法welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience算法简介该算法的基本思想是，对于每一个连接属性，都有一个对应的共享值表示这个属性进行Hash后的桶数，Map输出的keyintermediate/valueintermediate对需要传到该表没有包含的属性对应的每个Hash值中，因此复制的数量由该表没有包含的连接属性所对应的共享值之积所决定。在Reduce阶段，每个Reducer将传到该节点的各表的数据进行连接，形成最终结果。随着表数的增加，应用这种算法产生的中间传输数据量将急剧增加，因此比较适合用于星型连接与表数不太多的链式连接。多表等值连接算法•Supposethatthetargetnumberofmap-keysisk.Thatis,weshallusekReduceprocessestojointuplesfromthethreerelations.EachofthethreeattributesA,B,andCwillhaveashareofthekey,whichwedenotea,b,andc,respectively.WeassumetherearehashfunctionsthatmapvaluesofattributeAtoadifferentbuckets,valuesofBtobbuckets,andvaluesofCtocbuckets.•Considertuples(x,y)inrelationR.WhichReduceprocessesneedtoknowaboutthistuple?RecallthateachReduceprocessisassociatedwithamap-key(u,v,w),whereuisahashvalueintherange1toa,representingabucketintowhichA-valuesarehash