哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　数据库哈希连接算法研究 目录 目 录 目蜀乏……………………………………………………………………………………………………．I 摘要…………………………………………………。……………………………………………．．Ⅲ ABSTRACT………………………………………………………………………………………………IV 第一章绪论………………………………………………………………………．1 1．1课题背景………………………………………………………………………………1 1．2国内外概况…………………………………………………………………………。1 1．2．1连接算法的研究概况………………………………………………………………～2 1．2．2几个商用数据库的哈希连接算法…………………………………………………．．4 1．3课题主要研究工作……………………………………………………………………6 第二章哈希连接算法的设计……………………………………………………7 2．1数据库哈希连接分析…………………………………………………………………7 2．1．1哈希连接功能需求……………………………………………………………………7 2．1．2数据库哈希连接算法分析……………………………………………………………8 2．2哈希归并连接算法…………………………………………………………………。9 ．2．2．1哈希归并连接算法基本思想………………………………………………………一10 2．2．2哈希阶段……………………………………………………………………………．．10 2．2．3归并阶段……………………………………………………………………………．．13 2．2．4算法正确性证明……………………………………………………………………．．15 2．2．5算法优缺点以及性能分析…………………………………………………………一16 2．3哈希连接算法的设计………………………………………………………………．19 2．3．1数据库操作符设计…………………………………………………………………．．20 2．3．2数据库的哈希连接操作符设计……………………………………………………．．21 2．4本章小结……………………………………………………………………………24 第三章数据库哈希连接算法实现…………………………………………．…．25 3．1哈希连接实现方法分析……………………………………………………………．2s 3．2哈希归并连接算法哈希阶段的实现…………………………………………………z8 l 万方数据 数据库哈希连接算法研究 目录 3·3哈希归并连接算法归并阶段的实现………………·㈣删ⅢⅢ㈣舢删删删删………3。 3．4本章小结…………………………………………．Y2704396……．．．33 第四章实验及结果分析………………………………………………………34 4．1实验环境与设计……………………………………………………………………．．34 4．1．1实验环境……………………………………………………………………………．．34 4．1．2实验数据……………………………………………………………………………一34 4．2哈希连接测试………………………………………………………………………35 4．3本章小结……………………………………………………………………………39 第五章总结与展望……………………………………………………………．40 5．1总结…………………………………………………………………………………………………………………40 5．2展望………………………………………………………………………………………40 参考文献…………………………………………………………………………42 致 谢………………………………………………………………………………………………。47 万方数据 数据库哈希连接算法研究 摘要 摘 要 连接操作是基本的关系数据库查询操作之一，是从两个不同的关系中检索 满足条件的信息。实现连接的方法较多，其中哈希连接在所有的连接算法中被 证实是性能最好的，但现有的哈希连接都存在分区溢出问题。如果连接过程中 发生分区溢出现象，会严重降低算法效率。研究并改进现有的哈希连接算法对 于提高哈希连接效率具有重要意义。 为了解决现有哈希算法分区溢出的缺点，设计一种哈希归并连接(Hash Join，HMJ)算法，是一种使用归并连接思想实现哈希连接的方法，对现 Merge 有的哈希连接算法进行改进。算法分成两个阶段：哈希阶段和归并阶段。哈希 阶段利用哈希表的哈希值作为数据对比键值，对哈希表中所有数据进行排序， 把整个哈希表中的数据当作～个分区，然后依次对所有数据进行类似处理，使 得数据基于哈希值和原始键值有序；归并阶段则对排好序的数据进行归并连接， 完成整个连接操作。该算法具有不会产生分区溢出现象的特点。根据关系数据 库中的操作符特点，设计并实现哈希内连接、外连接和半连接操作符，实现过 程中临时数据的存储采用列存储技术，归并操作采用败者树算法对数据进行排 序。 通过对使用新算法实现的哈希连接进行实验，结果证实不论是内连接、外 连接还是半连接，新提出的算法较以前算法在性能上有较大提高。 关键词： 连接，哈希连接，归并，分区溢出 万方数据 数据库哈希连接算法研究 Abstract Abstract The isoneofthefundamentalrelationaldatabase joinoperation query facilitatestheretrievalofinformationfromtwodifferentrelations． operations．It andmethodareusedto oinisfoundto oins，Hash Manytechniques implementj j betterthanother overflowissaidtooccur perform algorithms，butpartition when traditionalhashoin overflowoccur using algorithm．If j partition during j would reducethe is to and oining，it seriously efficiency．Itimportantstudy thehashoin to improve j algorithmimprovequeryefficiency． ToSolvethe of will anew shortcomingpartitionoverflow,itpropose isthe of hash algorithm——hash—mergejoin(HMJ，forshort)，itwayimplement ideas，and thetraditionalhash joinbyusingmerging improve joinalgorithms． Thenew hastwo andthe algorithmphases：thehashingphase mergingphase． The considersthehashvalueofhashtableas the value，and hashingphase key datainthehashtablearesortedontheoinattributewithhashvalueandasa j similar ofother relationisorder partition．Followedby processingdata，the basedonthehashvalueandthe value．The is originalkey mergingphase bothrelationsfor theoinsresult．The doesnot merging producingj algorithm overflow．The hashinner producepartition operatorsincluding join，outerjoin and oinare and withthenew ofhash semi-j designedimplemented algorithm oinbasedonrelationdatabase tothecharacteristicsof j according operator． the ofthe modelis Duringimplementationalgorithm，decompositionstorage usedtostorethe loseris to dataand treeused temp merge． The resultsconfirmthatwhetheritistheinner outer experimental join，the orthe new morethanthe join semi-join，thealgorithmproposedperforms ones． original words：Join，Hash Overflow Key Join，Merging，Partition IV 万方数据 数据库哈希连接算法研究 第一章绪论 第一章 绪论 1．1课题背景 Data 自从Codd在1970年提出关系数据模型(RelationalModel)之后， 该模型就较多地使用在数据库产品中，这类产品也被称为关系数据库。目前 关系数据库被广泛应用在国防军事、国民经济的各个领域。使用关系数据库 的用户都关心数据的查询效率，如果一个数据库产品的查询效率满足不了用 户需求，必将会失去大量的用户。 关系数据库中定义了许多关系代数操作，如选择(SELECT)、投影 连接操作是从两个关系的笛卡尔积中选取属性之间满足一定条件的元组，且 是处理两个关系之间联系的唯一操作。连接是数据库的基本操作，且是开销 最大的关系运算操作之一【31。 实现连接的技术与方法有很多，如嵌套循环连接、基于归并排序的连接 算法、基于哈希的连接算法、基于索引的连接算法等，这些算法在不同的应 用场合表现出不同的性能。对于连接属性上不存在索引且条件表达式中存在 等值连接的情况，虽然嵌套循环连接、基于归并排序和基于哈希的算法都可 以处理，但由于算法各自的优缺点，性能都受到一定影响。针对这些不足， 本文提出一种使用归并连接实现哈希连接的方法，该方法充分利用了哈希与 排序两者的思想，利用哈希思想来进行排序，然后利用归并排序思想对有序 数据进行归并连接。既利用了哈希分隔数据的优点，又利用了归并排序减少 数据对比次数的优点，使得算法在连接处理上的性能有较大的提升。 本文基于通用关系数据库，在对数据库中连接算法进行仔细分析的基础 上，提出了一种改良的哈希连接算法，以加快查询速度，更快地响应用户的 查询请求，改善用户体验。 1．2国内外概况 在关系查询处理中，连接是最耗时且为数据密集型操作之一，国内外许 多学者对连接操作进行了大量的研究与讨论【31。根据Priti Mishra和Margaret H．Eich在文献[31中总结的连接算法的分类，连接算法可以按照数据分区性质 进行分类。图1．1展现了基于分区描述的连接算法分类。 万方数据 数据库哈希连接算法研究 第一章绪论 D 蛳 把 ～ Grace 一 删娜 下一LL N 一 Hybrid 一 m娜 Simple 一 Hash Partition Index 图1．1基于数据分区的连接算法分类 在图1．1中，None(无分区)表示算法中没有进行分区；Pre(已经分区) 表示算法中没有进行分区的步骤，但算法已经假设分区存在，如基于索引的 连接；Implicit(隐式分区)表示算法中没有分区步骤，但通过对数据进行 一定处理(如排序、划分)，隐式地进行了分区，使得在匹配步骤中更少的 元组需要进行对比；Explicit(显式分区)表示算法中执行了显式的分区步 骤。 接下来主要讨论隐式、显式以及无分区的连接算法，对于Pre情况的连 接，大多是以连接的关系上已经创建索引为前提，本论文不讨论此类情况， 也即讨论无索引情况。 1．2．1连接算法的研究概况 到目前为止，国内外学者提出了许多实现连接的算法，并提出了许多改 进方法。1977年，Blasgen在文献14】中提出了许多经典的连接算法。基于元 组的嵌套循环连接(Nested Join，NLJ)是最容易想到的一种算法，也 Loops 是最简单的一种算法，在具体实现嵌套循环连接过程中，都是使用基于块的 嵌套循环连接算法【5】思想。该方法适合于数据量较小且内存可以存放下情况 使用，但如果数据量超过内存大小，则内关系需要多次扫描，扫描的次数为 万方数据 数据库哈希连接算法研究 第一章绪论 的思想，把每次循环中读取内关系的最后一块当作下次循环的第一块，这样 就节省了一块内存大小数据的I／0操作。Hagmman在文献[7】指出，使用 “rocking”思想的嵌套循环方法在缓存区的大小等于两个关系的大小时， 该方法是最佳策略。但数据量较大情况下，嵌套循环连接算法的效率都较差。 针对嵌套循环连接方法的在大数据量下性能较差的缺点，Blagen在文献 Join，SMJ)。该算法适 【4J中还提出了基于归并排序的连接算法(Sort．Merge 合于大数据量情况，在某段时间内，还被认定为是最好的连接算法【81。该算 法主要的缺点在于需要对连接的两个关系进行排序，排序过程中数据对比时 间较长。虽然该算法在一段时间内被认为是最好的连接算法，但是随着哈希 连接算法的提出，证明这种观点不一定成立。 Join相比，基于哈希的连接算法【9J使用了另一种方法达 与Sorted．Merge 到了同样的效率【l…。基于哈希的连接算法有多种，最简单的哈希连接算法 Hash Join，SHJ)，该算法首先在一个关系上建 是简单哈希连接算法(Simple 立哈希表，然后另一个关系中的数据到哈希表中进行探测。该方法相当于把 数据进行了分片，对相同哈希值的数据进行对比，减少了大量的数据对比次 o】中指出，在数据量较小的关系上建立哈希表可 数。Bratbergsengen在文献【l 以提高该算法的效率。但是算法在数据量较大、可用内存存放不下情况下， 需要多次对较大关系进行读取，性能较差。针对这一缺点，Kitsuregawa提 Hash 出了优美哈希连接算法(GraceJoin，GHJ)【l¨，该方法把需要连接的 两个关系分别划分成等大小的子分区，然后对下标相同的子分区进行连接， 2j中指 问题就简化成了对应的n个不同的子分区进行连接。Gerber在文献【1 出相比于SHJ，GHJ不太受限于可用内存大小。因避免了反复多次地扫描， GHJ性能一般对优于SHJ，但当可用内存可以存放下大部分数据时，GHJ 3J中提出了一种新的哈 算法的性能不及SHJ。针对该缺点，Shapiro在文献【l Hash Join，HHJ)。该算法结合了 希连接算法一一混合哈希连接算法(Hybrid SHJ和GHJ算法两者的优缺点，与GHJ算法不同的是，它把第一个分区保 存在内存中，并未进行刷盘，所以当内存能存放大部分数据时，HHJ可以 4‘16j。 表现更好的效率11 为了论证上述算法的性能优劣，大量的文献对这些算法进行了研究与讨 论。文献[17-191通过对比归并排序连接算法、简单哈希连接算法、Grace哈希 连接算法和混合哈希连接算法，总结出混合哈希连接算法是其中代价最低的 算法，性能表现最佳。而归并排序连接算法与混合哈希连接具有类似的I／O 性能，GHJ与HHJ算法在性能上较接近。 虽然大量研究证明哈希连接算法在大多数情况下表现出较优越的性能， 万方数据 数据库哈希连接算法研究 第一章绪论 但是哈希连接算法也存在着缺点。文献【3】中指出了哈希连接算法存在分区溢 出现象、哈希冲突以及非等值连接难以处理问题等缺点。分区溢出是指哈希 分区之后的子分区数据大小仍然大于可用内存大小，产生主要原因是由于数 据倾斜[20,21J，如果分区溢出发生会严重降低连接的效率。针对这些缺点，国 出了动态降级策略(DynamicDestagingStrategy)来进行处理，处理的方法 是根据分区的数据量大小来动态调整连接的策略。如果分区数据量小于给定 内存大小，则可以使用简单哈希连接算法进行；当数据量超过给定内存大小， 则可以先改变哈希函数，对分区中的数据继续进行分区，递归地处理数据分 区，直到分区大小小于可用内用大小。如果递归的次数超过给定值，分区之 后溢出还存在，则改变分区终止，使用哈希循环连接(Hash Join)等 Loops 其他算法来进行处理。 1997年，Hsiao H．．I．和Chen M．．S．在文献[241中首次把Bloom过滤器 (Bloomfilter，又名位向量过滤器)[251思想应用到连接算法中，虽然他们 仅仅是把Bloom ioin算法中，但之后Bloomfilter被广 filter应用Sort．Merge 泛应用到哈希连接等其他算法中，与以前算法相比增加了Bloomfilter的连 接算法表现出更高的效率126J。 上述连接算法都是假设数据是事先提供的，不存在阻塞现象，也被国内 Join 外学者称为阻塞式连接算法(Blocking 络不稳定、延迟等引起算法效率较差问题，大量的非阻塞式连接算法 Join Join[30,31】、XJoin[32,331、 (Non．blockingAlgorithms)【29】被提出，如Ripple Join[341、PR．Join[”】，但是这些算法较以前传统连接算法相 ProgressiveMerge 比，都没有在算法性能本身上提出更好的思想，所以这些算法在商用数据库 中也很少被使用，因哈希连接算法在所有的连接算法中具有最好的性能表现， 被大量地使用在主流数据库产品中。在1．2．2中将介绍几个典型商用数据库 的哈希连接算法。 1．2．2几个商用数据库的哈希连接算法 目前，许多商用数据库中，都支持使用哈希连接算法来实现连接，下面 具体介绍几种常见商用数据库的哈希连接算法。 Microsoft Server中的哈希连接算法主要是通过结合简单哈希连接、 SQL Grace哈希连接和混合哈希连接三种算法思想进行实现[36,371，即采用了动态 降级(DynamicDestaging)思想。哈希连接实现中，一般都选择在小关系上 建立哈希，MSSQL根据建立哈希的关系的大小来进行动态调整，并划分为 三种情况。第一种情况为可用内存能够容纳下所有数据，则使用简单哈希连 万方数据 数据库哈希连接算法研究 第一章绪论 接算法；第二种情况为数据量不能全部存放在可用内存中，且分区之后的大 小都小于可用内存大小，此时选择Grace哈希连接算法；第三种情况为分区 之后，分区大小仍然超过可用内存大小，即分区溢出发生，此时采用递归思 想处理分区，即继续进行分区，直到分区大小小于可用内存大小。MS SQL 在具体实现中，也采取了其他优化策略来提高性能。当分区大小比可用内存 大小不是大很多时，使用的是混合哈希连接算法，避免了再次分区。且在每 vectorfilter)，主 一个建立与探测哈希过程中，都使用了位向量过滤器(bit 要是用来减少不可能产生连接结果的数据之间的对比。可以看出MSSQL 的哈希连接实现主要是采用了经典的哈希连接算法思想，针对分区溢出现象 采用了DynamicDestaging思想进行解决，且增加了位向量过滤器。 PostgreSQL中哈希连接的实现采用了混合哈希连接算法思想，实现方式 与文献【14】中描述的混合哈希连接算法基本一致【2引。由于在实现过程中， PostgreSQL不支持连接基数(JoinCardinality)，使得在哈希连接处理过程 Partition) 中，容易出现分区溢出现象，PostgreSQL采用了动态分区(Dynamic 进行处理。从PostgreSQL哈希连接实现可以看出，它依然存在着分区溢出 现象带来的性能降低的缺点，且没有把Bloomfilter应用到连接算法，由于 Bloom过滤器。 在Oracle中，确定连接操作类型是执行计划生成的重要方面。各种连接 操作类型代表着不同的连接操作算法，不同的连接操作类型也适应于不同的 数据量和数据分布情况。从Oracle7．3开始，哈希连接正式进入优化器执行 计划生成。本质上说，哈希连接是借助哈希算法，连带小规模的嵌套循环， 同时利用内存空间进行高速数据缓存检索的一种算法。Oracle实现哈希连接 大致流程如下：首先选出2个表中的小表，然后将经过哈希处理过的小表连 接列，连同数据一起存放到OraclePGA空间中，之后对进行哈希连接大表 数据连接列依次读取，并且将每个哈希值进行桶匹配，定位到适当的桶上， 最后在定位到的桶中，进行小规模的精确匹配。 上述几种商用数据库产品中，采用的都是传统哈希连接算法，使用动态 调整分区策略来处理分区溢出现象，虽然MSSQL增加了Bloom过滤器， 但这些方法都存在着分区溢出现象带来的额外开销问题。动态调整过程中需 要再次分区所花费的时间，且对应分区进行连接的对比次数是两者分区元组 个数的平方。这些缺点降低了算法效率，性能较低。 万方数据 数据库哈希连接算法研究 第一章绪论 1．3课题主要研究工作 本文主要的研究工作是结合现有关系数据库的特点，设计出一套哈希连 接的方法，对现有的哈希连接算法进行改进。需要完成的工作有以下： 1．基于数据库管理系统的特点，对哈希连接算法进行设计 首先分析哈希连接适用的场合，并简单分析数据库原有的哈希连接算法 的实现。根据之前哈希连接算法的缺点，提出一种新的哈希连接算法，对该 算法的两个重要部分进行了详细说明，并从算法的完备性方面给出该证明， 分析算法的优缺点及性能。然后对数据库的操作符设计进行简单介绍，给出 使用新算法的哈希连接操作符的设计。 2．根据提出的新哈希连接算法，在数据库中对该算法进行实现 首先分析哈希连接的实现，说明各种连接类型的实现特点，详细给出哈 希内连接的实现过程。然后对新提出的哈希连接算法的实现给出详细步骤， 提出实现过程中的优化策略。 3．算法性能方面进行测试 测试主要是针对哈希连接算法的效率，测试的数据是基于TPC．H标准生 成的，总共的数据量大小为SF=I，约为1G。测试点分为了8个，数据量依 次增多。通过对比新提出的算法与原有哈希连接算法两者之间在8个不同数 据量上的执行时间，分析出两者算法的优劣。 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 第二章哈希连接算法的设计 本章给出一套适合于数据库的哈希连接的设计方案。首先提出所有哈希 连接算法的要求，给出每一种哈希连接操作的设计要求；其次分析数据库已 有哈希连接算法，提出其中存在的问题，然后给出一种新的哈希连接算法， 并给出该算法的正确性证明、性能分析等；根据数据库在执行SQL语句时， 真正的物理执行计划都是通过操作符的实现来完成，先简单介绍关系数据库 中操作符的设计，然后给出哈希连接操作符的设计。 2．1数据库哈希连接分析 本节首先给出数据库中哈希连接功能需求，给出支持的哈希连接种类以 及哪些查询会使用到哈希连接，然后分析数据库已有的哈希连接的设计，指 出其中存在的不足，提出本课题需要达到的目标。 2．1．1哈希连接功能需求 关系型数据库支持许多种类的连接操作，有的数据库产品不支持哈希连 接(如MySQL)，但提供了哈希连接的实现。 数据库中表的连接是指在一个SQL语句中通过表与表之间的关联，从 一个或多个表检索出相关的数据。连接是通过SQL语句中FROM从句的多 个表名，以及WHERE从旬里定义的表之间的连接条件来实现的。 2、≠、、、≥一。哈希连接仅当连接谓词中至少存在一个等值条件语句时 才使用，以下讨论中如果使用了哈希连接，则表示连接连接中至少存在等值 条件，不再明确说明。 Join)、 连接除了臼．连接外，还有等值连接(Equijoin)、自然连接(Natural 半连接(Semijoin)、外连接(Outer 数据库中在对SQL语句进行查询处理时，对一些没有显式要求连接的语句 进行查询转换后，执行计划中会存在着连接，如嵌套查询。下面给出数据库 中连接存在的场合。 数据库执行哈希连接大致可分为两种情况，分别是显式指定和隐式产生。 1．显式指定是指查询SQL语句中存在着指定需要进行连接的关键字。 包括以下几种情况： (1)CROSS JOIN。返回被连接的两个表所有数据的笛卡尔积。 7 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 (2)NATURAL JOIN。返回被连接的两个表符合等值条件，但去 掉重复的属性列的结果。 (3)INNER JOIN。返回符合等值连接条件的结果。这三种情况都 会执行内连接。 (4)LEFT／RIGHT／FULLOUTER JOIN。分别是左／右／全外连接， 返回到查询结果集合中的不仅包含符合连接条件的行，而且 还包括左表(左外连接时)、右表(右外连接时)或两个边接表 (全外连接)中的所有数据行。此情况会执行外连接。 2． 隐式产生是指SQL语句在经过查询处理之后会产生各种连接。包括 以下情况： (1)连接查询。是指一个查询同时涉及两个以上的表。对于这种 情况，如果连接谓词中存在等值条件就会执行内连接。 (2)嵌套查询。是指将一个查询块嵌套在另一个查询块的 WHERE子旬或HAVING短语的条件中的查询。这类情况的 查询有带有IN谓词的子查询、带有比较运算符的子查询、带 的子查询。对于带有IN、ANY、ALL、EXISTS的子查询， 如果生成哈希连接，一般都是半连接，对于比较运算符的子 查询，则会根据比较运算符的类别以及连接内外子查询的连 接条件决定，生成的连接一般都是内连接。 2．1．2数据库哈希连接算法分析 关系数据库中，使用的较多的哈希连接算法是GRACE哈希连接算法。 以下介绍GRACE哈希连接算法的基本思想。 假设关系R为建立哈希输入(Built Input)，关系s为探测哈希输入(Probe Input)。 算法步骤如下： 1．计算分区数(fanout)； fun fun2 2．读取关系R的每条记录，分别利用哈希函数hash1和hash 计算该记录的哈希值，记为v1，v2。根据v1将数据插入到相应的哈希分区中， v2存放在记录中； 3．创建hash位图。根据v1，v2的值创建hash位图(即BloomFilter)， 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 用于过滤； 4．如果hash区域(哈希可用内存)被填满，则选择最大的一个分区刷 入磁盘； 5．对分区排序，按照各个分区的大小重新排序； fun 6．读S表的每条数据，通过hash1计算hash值，记为x1，检查 内存中的分区x1是否一直在内存，如果是，则进行Join操作，否则，写到 相应的分区中； 7．读完S表后，在关系R和s的磁盘分区中选择最小的一个写入内存， fun 根据hash 2哈希函数计算的hash值创建hash表(用于动态角色分配)； 8．读取磁盘中对应的分区，进行连接操作； 9．重复步骤7，8； 10．如果步骤7读取的分区太大无法放入内存，则进行普通嵌套循环连 Nested HashJoin) 接(NormalLoops)或者嵌套循环哈希连接(NestLoop 或者采用递归分区解决方法。 数据库的哈希连接算法若增加了BloomFilter过滤器，与普通GRACE 哈希连接算法相比，其主要的作用是过滤一部分根本不需要连接的数据，从 而节省了数据对比开销。但与GRACE哈希连接算法相比，分区溢出 (Partition Overflow)现象依然存在，并且分区溢出产生的概率并没有减少， 因为没有对该部分做过任何优化操作。而使用BloomFilter过滤器之后，只 有对多个等值条件的情况才有可能起到一部分作用，如果连接条件只有一个， 则BloomFilter反而增加这部分的开销，影响了效率。总体来讲，这种思路 的哈希连接算法并没有解决GRACE哈希连接算法存在分区溢出问题，增加 的Bloom Filter过滤器在一定程度上还有可能影响查询效率。 下面将提出一种新的哈希连接算法，采用归并连接来实现哈希连接的一 种方法，利用哈希表槽号对数据进行排序，然后对有序数据进行归并连接。 该方法将有效地解决了GRACE哈希连接算法分区溢出问题，在性能上比 GRACE哈希也有较多的提升。 2．2哈希归并连接算法 本节提出一种新的哈希连接算法，然后给出算法的主要设计思想、分析 算法的正确性、以及算法的效率问题进行分析。本文命名该方法为哈希归并 连接算法(Hash Join，HMJ)，以下都使用该名字简称该算法。 Merge 9 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 2．2．1哈希归并连接算法基本思想 哈希归并连接算法在任何数据量大小的情况下都适应，也即数据在内存 中完全容纳下，以及数据量过大不能全部存放在内存的情况。 在介绍该算法之前，提出了以下假设： (1)存在两个数据关系R和S； (2)关系R作为算法处理中建立哈希表的那个关系，即Built Input，关 系S作为算法处理的探测关系(Probe Input)，其中R的数据量总是小于等 于S的数据量，这是为了满足需要建立哈希的关系为小表的条件。记R的 R R s s 总共页数为I I，元组个数为IffI，S的总共页数为Il，元组个数为Jllf所 R S 以I ffI； (3)如果R的大小大于S的大小，则可以对R和S进行左右互换，使 得R作为右表，S作为左边，这样也符合了条件(2)。 普通哈希连接算法是分为两个阶段，分别是哈希阶段和探测阶段，其中 小关系用于建立哈希，大关系用于探测。而该算法中，也同样分为两个阶段， Phase)。 分别是哈希阶段(HashingPhase)与归并阶段(Merging 在哈希阶段中，如果关系R较小，即可用内存可以存放得下，则大关系 S不需要建立哈希，直接在关系R的哈希表中进行探测返回结果。在这种小 数据量的哈希连接情况下，与简单哈希连接算法基本一致。如果关系R较 大，数据不能全部存放在内存中，则需要对关系R与s都进行哈希，然后 刷入磁盘，做为临时处理数据，并经过该阶段之后的关系R(或者S)被分成 了n和m个有序的子分区。 在归并阶段中，由于关系R和S的数据部分已经有序，则只需要对关系 R和S的临时分区有序数据进行一次或者多次归并排序，得到整个有序的关 系R和S，然后对两者有序的数据再进行归并连接，返回哈希连接结果。 以下详细介绍建立哈希阶段与归并阶段中所需要的处理工作。 2．2．2哈希阶段 建立哈希阶段，是对稍后的归并阶段做好充分的准备工作，主要目的是 与普通归并排序相比，减少读取数据的I／O次数和对比次数来对所有数据进 行排序，为归并阶段的归并操作做好工作。图2．1显示了哈希阶段的描述。 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 {(olR01)} O 叫o H…I f‘(㈤猁 1 叫鬻FH潺I I鬻鬻猢 2 组成 一鬻H攀尊 章C．；L隧羹滔鬻i{ 组 ●●● 卜i蠹惹矗l 卜 1；1 { N．1 隧。鳓1 N 叫jRjjNH：．， Io菱鋈圆．。涮 ” 分区Pj 图2．1HMJ的哈希阶段 假设关系R(a·，口z，…，％)与s(岛，如，…，am)的连接属性为(q，…，q)与 (bj，…，bk)，即存在的等值查询条件为㈣26，，…，at2‰)。记两个关系的等值 一条元组的连接属性的键值为(key·，…，慨)，其中2力keys。 建立哈希阶段算法如算法2．1。 算法2．1哈希阶段算法 输入：关系R(或者s) 输出：无 BEGIN 1： 建立哈希表，即关系R(或者s)所需要的哈希表，哈希表的大小为N，即槽号个 数有N个； 2： k=1／}入磁盘的分区ID；4／ 3： while(从关系R(或者s)O取出一条元组tuple(t)) 4： If(有足够内存存放元组t)then 5： 计算哈希值H(t)； 6： 按照哈希键值的顺序(升序)插入到哈希表中相应位置，即插入后保证该 桶中所有数据有序； 7： Else 8： 置刷盘标记RFLUSHFLAG=TRUE(只有关系R才会置，s置该标 记没有用)： 9： 按照哈希表的槽号顺序(升序)，把哈希表中所有数据刷入到磁盘，同时 把哈希表的槽号也一并刷入了磁盘，每次刷完之后，记该数据分区为Rk(S々)； 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 10： k++： 11： 清空哈希表，即删除哈希表中所有数据； 1 2： 计算哈希值H(t)； 1 3： 按照哈希键值的顺序(升序)插入到哈希表中相应位置； 14： endif 15：endwhile 16：把最后一次哈希表中所有数据，也按照上述同样规则刷入磁盘； END 算法2．1主要是对关系的所有元组进行哈希处理，仅需要对所有元组遍 历一次。假设关系元组个数为n，则时间和空间复杂度为uL川。 在关系R所有数据可以存放在内存情况下，与简单哈希连接算法一致， 只需对R建立哈希表，然后使用关系S在R关系的哈希表中进行探测就得 到连接结果。如果是这种情况，由于与简单哈希连接算法并无差别，如果无 特别说明，以下讨论都是基于大数据量的情况下。 如果关系R的数据不能全部存放在内存，则在哈希阶段过程中，需要对 关系R与s进行算法2．1处理，即需要对关系R和S建立哈希表，并把数 据刷入到磁盘，进行了分区。在对关系R和s进行处理中，建立的哈希表 的大小需一致，并且对元组进行处理的哈希函数也是同一个，这样可以保证 哈希键值相同的元组被哈希到同一个槽号，插入到同一个哈希桶中，即哈希 值相等的元组在哈希表中相同的槽中。 算法说明：在算法2．1中，本课题处理时，元组插入哈希表是根据每个 元组的哈希键值升序插入。行9中显示当可用哈希内存满之后，需要对数据 刷入磁盘，把哈希表的槽号也一并刷入，即如果原始键值的个数为胛keys， 元组的键值为(keYl，…，key．)，则新刷入磁盘的元组的键值个数为(胛缈s+1)， 整个哈希表中存放的数据刷入磁盘后，当作一个有序分区。 经过哈希阶段的处理之后，关系R和S分别被临时存储在磁盘，并进行 了分区，关系R的数据为瓜·，…“一，关系s的数据为‘)-，…一m，其中刀，m可 能相等，也可能不相等，需根据关系R和关系S的大小而定。其中经过哈 希阶段处理之后的数据具有以下特点： (1)每个子分区的数据有序，即R，(或者s，)子分区有序。从哈希阶段处 理过程可以看出，把每个元组插入到哈希表的过程中，因插入时是按照哈希 键值的升序插入，这样哈希表中每个槽号对应的数据都是有序；当哈希表中 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 的数据满之后，也即内存存放不下时，需要把哈希表中所有的元组(数据)， 作为临时数据存入磁盘。在数据刷入磁盘时，对元组进行了改造，增加了一 列组成新元组。新元组的特点是，键值比原来的增加了-N。如0槽号的数 据进行刷盘时，假设此槽号中的元组为t(keyl，．一，key。，U)，其中U为非键值 组后按照哈希表的槽号顺序把桶中的所有元组进行刷盘，则算法中根据以下 几点确定每个分区是有序的。 (a)不同槽号中元组由slotno槽号确定了新数据的大小，槽号大的元 组比槽号小的元组大。 (b)slotno相同的元组，则根据它们本身的键值key而确定了大小。 (c)元组刷入的顺序。算法中是按照哈希表的槽号从小到大的顺序刷 入，这样保证了先刷入的元组的slotno较小，根据(a)、(b)的规则 保证了刷盘所有元组是有序的。 (2)每个子分区中元组个数一样，除了最后一个分区外。哈希归并 连接算法中，判断内存中是否可以存放下所有数据是根据内存的大小和 元组属性计算出可以存放多少条元组，记为阙值。这样，当元组个数到 达该阙值时，就需要把哈希表中所有数据刷入磁盘，而每次刷入过程中， 只有最后一次刷入的时机不是通过判断是否内存容纳得下，所以最后一 个子分区存放的元组个数小于该阙值。 2．2．3归并阶段 哈希归并连接算法的归并阶段只需对哈希阶段处理之后的数据进行归 并连接，就得到最终结果。图2．2给出了归并阶段的描述。 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 图2．2HMJ的归并阶段 当进行到归并阶段时，哈希归并连接算法所需要做的工作主要是分别对 两个关系中每个已经排好序的分区再进行一次归并排序。如果分区数过多， 则还需要进行再次归并排序，直到归并排序的结果是只有一个分区为止，然 后按照传统排序归并连接算法对关系R和s的数据进行连接从而得到最终 结果。 归并阶段算法如算法2．2。 算法2．2归并阶段算法 输入：关系R和S的子分区：Rl，．一，吃和S，…，瓯， 输出：连接的结果集 BEGIN 1． ／+循环从R和s的子分区中得到各自的分组，如果存在一个分组为空，则循环 结束+／ 2． 对RI，…，R进行归并排序，并获得一个分组咚，；对S，…，最进行归并排序， 并获得一个分组Sg，； 3． While(R酽不为空并且％不为空) 4． If(Rgf与％的键值相等)then 5． 对R∥与Sea进行归并连接； 6． 取关系R中的下一个分组RgI； 7． 取关系S中的下一个分组Sea； 8． Else if(分组％的slotno小于分组％的slotno) 9． 取关系R中的下一个分组R口； 10． Else 1 1． 取关系S中的下一个分组Sea； 12． endIf IV,ND 算法2．2中有个重要的操作，一个是对已经排好序的分区进行归并排序 操作，另一个是对最终排好序的所有数据进行连接操作。假设关系R和S 的分区个数为别为n和m，则在归并排序过程中，采用多路归并算法，一次 R 数据对比次数为log；和l097，元组个数为ll II和IISII，则时f7复杂度为 o(RII Sl log：+11 l092)；在归并连接过程中，只需要分别对关系R和S读取 14 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 M II+《S 一次， 时间复杂度为D(II II)， 则总体时间复杂度为 0((11 s R+1)logT+(1l II+II l})。 S+1)l092)，空间复杂度为D(M 假设由子分区墨，…，R和S，…，Sm组成新的关系为R’和S。。算法2．2中， 首先需要对关系R和S进行归并，使得两者都基于键值有序。然后从关系R 和s中分别得到一个分组，对比两者分组的键值是否相等，由于增加了一个 可能相等，则可以取分组ngi和o∥中，slotno较小的关系的下一个分组；如 果两个分组的slotno相等，则继续对比其他键值，如果也相等，则返回儿gi和 。剁分组的笛卡尔积。然后依次取每个关系的下一个分组，直到存在一个关 系中没有了分组，则归并阶段结束。返回的结果即为最终哈希归并连接算法 的结果。 2．2．4算法正确性证明 哈希归并连接算法符合以下两个定理，满足算法的正确性。一个是完备 性，即可以计算出所有的哈希结果值，一个是无重复值。 定理2．1给定两个关系R和s，哈希归并连接算法产生所有的满足连接 条件的输出结果集。 证明：假设j(，．，引，其中，∈R，s∈s，并且(r，s)满足连接条件。 我们假设Lr，JJ不能由该算法产生，使用反证法证明这种情况不可能存在。 假设r∈Rgi,s∈Sg／，R鲫与S副分别为关系R和S的一个分组。根据归并 阶段中的算法2．2中可以得出，儿gi与og，中的元组只存在以下三种关系： (1)R。，中元组的键值小于s。，中元组的键值，也即，．S，而由(r，S)满 足连接条件得知，r，S的键值必然相等。所以R，，中元组的键值不可能小于S。， 中元组的键值。 (2)R。中元组的键值大于s。中元组的键值，也即厂的键值大于S的键 值，而同样由(r，S)满足连接条件得知，r，S的键值必然相等。所以R。，中元组 的键值不可能大于。彤中元组的键值。 (3)R。，中元组的键值等于J5，。，中元组的键值，也即，．的键值等于S的键 值。而此种情况正是由归并阶段的算法2．2中的满足该键值相等的条件中得 出的结果，与假设(r，s)不能有该算法产生矛盾。 所以假设不成立，即不存在Lr，川，不能有该算法产生。 定理2．2给定关系R和s，哈希归并连接算法产生所有符合连接条件的 结果集，且仅产生一次。 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 证明：有定理1得知，哈希归并连接算法可以产生符合所有连接条件的 结果集。 假设存在(，，引，其中r∈R，s∈s，并且(r，s)满足连接条件。假设(r，s)在 算法中被产生了两次，我们记为妒，s九利妒，s凡。由于在哈希阶段不可能会产 生(y，s)，所以∽，s)t利婶，s)z只有可能在归并阶段产生。而由算法2．2中，可 以得出产生得出满足结果集的条件只有在，，s两者的键值相等情况下才可以 产生，而满足条件中计算结果的算法是通过归并连接算法得到，由归并连接 算法的正确性可以得出，(，，s)必然只产生一次，(r，sJ·不u∽，s)z不可能会产生 两次。 由上述两个定理得知哈希归并连接算法，可以得出正确的连接结果。 2．2．5算法优缺点以及性能分析 哈希归并连接算法主要的特点就是在进行哈希阶段过程中，保证了数据 Join相比，节省了 的每个分片有序，然后进行排序归并连接，与Sort．Merge 算法单独排序所需要的大量时间，包括数据对比与读取110，与哈希连接算 法相比，节省了哈希探测过程中需要对哈希桶中所有数据进行比较的时间。 HMJ算法在关系R(小关系)数据量较小、可用内存能容纳的情况下， Hash 结合了SimpleJoin算法思想。HMJ此时使用SHJ算法，充分利用了 SMJ算法在数据可全部存放内存情况时有着高效率的优点。当关系R数据 量较大时，由上面的假设可知此时s关系更大，这种情况结合了Sort．Merge Join算法思想，充分利用了该算法的节省数据对比次数的优点。 在关系R数据量较大情况下，哈希连接的主要时间都花费在数据的读写 I／0与数据之间的对比次数。由于不能把所有数据都存放在内存情况下，这 样对一些中间结果集都需要刷入磁盘，而哈希连接算法中为了得到最终的结 果集，需要对原始数据读取多次，这些都是给算法的效率带来严重影响因素。 如简单哈希算法中，由于不能够确保所有数据都保存在内存中，所以如果关 系R数据量较大，则每次读取部分数据时，都需要把关系S数据．列取一次， I朋lI。这种情 这样关系R数据的I／0次数为1次，右表数据的I／0数则为I 况下I／0次数明显过多，效率较差。 哈希归并连接算法的提出主要是为了处理在大数据量情况下，尽量减少 原始数据的读写I／0以及大数据量的对比次数。下面分析在最好情况下、最 差情况下以及一般情况下，读写磁盘的I／0数以及数据对比次数。 在分析之前，先给出对关系R和s进行归并时，可以进行的优化操作， 这样可以节省一次I／0的读写。假如关系R进行分区之后，根据排序区域的 内存大小，只需要一次归并操作就可以完成，则可以采用空间换取时间的策 16 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 略来节省I／O操作，即可以把归并排序操作得到的结果，当作归并连接的输 入，每次得到两个关系的分组之后，进行一次归并连接操作，这样关系R 就不需要全部归并排序之后，先临时保存在磁盘，再重新读取一次。如果一 个分组过大，则也需要临时保存在磁盘，这个时候，该分组就需要多两次的 I／O操作，读写各一次。同样关系S也是如此。 1．I／O次数分析 f1)最好情况，即关系R和s只需要一次归并排序就可以得到最终的 排序结果，且每组相同键值的元组不会超过给定内存大小。 由哈希归并算法中的哈希阶段可以推知，在此阶段，只需要对关系R和 s的数据分别读写一次I／O。读取数据主要是对所有元组进行哈希函数求值， 找到其在哈希表中对应的槽号。写数据主要是需要把哈希表中所有数据全部 刷入磁盘，由于每条元组只会在关系R(或s)ee读取一次，所以也只会写入 一次。这样在哈希阶段，总共的I／O次数是2次。在归并阶段，需要把数据 全部读取到内存中，根据假设，关系R和S中的每个分组都可以存放在内 g， 存中，即ngi和。甜可以同时存放在内存中，然后对R和S的小分组Ag。和o 进行归并连接，得到了两个关系的分组的连接结果集。根据归并阶段算法， 依次取下一个分组，且分组都可以存放在内存中，则关系R和S在进行归 并连接时，只需在内存中进行计算，得到连接的结果集。由于归并阶段中， 每次都可以处理完内存中所有的分组，而不需要把数据J临时存入磁盘，这样 磁盘的I／O数只有1次。这种最好情况下，关系R和s的磁盘I／O数都只需 要3次即可。 (2)最坏情况，即关系R和S只一个分组，所有数据的键值都相同。 与最好情况下类似，哈希归并连接算法的哈希阶段需要2次I／O操作。 而在归并阶段，由于内存不能存放整组数据，只能够把关系R的部分数 据存放在内存中，然后取出关系s的数据进行归并，由于R和s需要把 所有数据进行笛卡尔积操作，这样内存中的部分数据就需要和S中的数 据全部进行连接，然后输出结果集。显然，关系R只需要读取1次，而 关系S需要读取}等次，其中fIRII为关系R的元组数，fIMII为给定可用 内存能容纳的元组数℃由于在获取分组过程中，分组过大，需要临时保 存在磁盘，所以归并阶段关系R的I／O次数为2+1=3，关系s的I／O次 数为—峰兴+2，两者的2次表示分组过程需要的I／O次数。此时还需要考 虑，蜥栗对关系R或s分区之后，分区数过大，超过了给定的排序内存 大小，则需要进行多次归并排序操作。假设给定的排序内存为10M，每 次归并操作的个数为500，则一次归并操作可以对5000M数据进行归并， 万方数据 数据库哈希连接算法研究 第二章哈希连接算法的设计 也即当数据量大于5G时，才需要多次归并操作；如果继续归并，二次 归并操作的数据量可以达到5500=2500G，所以如果数据量小于2．5T时， 都可以在二次归并操作中完成，一次归并操作需要增加2次I／0操作， 即读写各一次。如果稍微增加排序区域的内存大小，则一次归并的数据 量也可以增加。 由此看出，在最坏情况下，如果是蛀次归并操作，则整个算法过程关系 MJ R需要5次I／O操作，关系S需要II次I／O操作；如果需要；次归并 M 11 次I／O 操作，则整个算法过程关系R需要7次I／0操作，关系S需要II 操作。 (3)一般情况。如果关系R和S的每组数量都较小，连接结果较少， 则I／O次数与最好情况差不多；如果关系R和S的每组数量过大，给定 内存大小不能存放下，则这部分数据需要多读取2次。则对上述两种情 况进行折中，关系R的I／O次数为6次，关系S的I／0次数为爿蠡翔+5。 2．对比次数分析 对比操作发生在哈希阶段的插入元组到哈希表中、关系R和s进行归并 排序，以及关系R和s进行归并连接，数据插入哈希表中的对比次数与元 组数有关，而归并排序的对比次数则与归并次数和元组数有关，最好与最坏 情况下，这些都是定值，所以不予考虑。 在哈希阶段，在插入元组过程i监嗵堕型壁蛤煎!擅鲎的麴援趟星刈魁封