（计算机软件与理论专业论文）查询执行算法的设计与优化.pdf

华中科技大学硕士学位论文 摘要 查询执行是数据库技术的一个关键组成部分，查询执行的速度直接影响数据库 管理系统的性能和效率。关系数据库系统中执行查询的方法主要有4 种：基于扫描 的方法，基于排序的方法，基于索引的方法，基于散列的方法。 国产数据库系统d m 3 用上述方法执行查询操作。但索引b + 树过低的空间利用率 和过多的散列冲突影响了查询执行的性能。为解决此问题，提出了自底向上构建索 引b + 树的方法和二维定址哈希算法。 自底向上构建索引b + 树的方法提出了一种新的构建索引b + 树的方法，该方法 先生成b + 树的树叶，然后自底向上按层生成内节点，最后生成树根。实现了数据的 批量处理，提高了创建索引b + 树的速度，控制了b + 树的空间利用率，提高了索引 扫描的速度。 二维定址哈希算法提出了一种新的散列算法，通过一个二维地址来确定关键字 在散列表中的位置。二维地址的一维存储在主散列表中，另外一维存储在一个辅助 表中。只要散列函数选择恰当，大部分情况下该方法的散列冲突都不超过1 0 。查 找时关键字平均比较次数不超过1 n 次( n 为辅助表的大小) 。 这些算法在国产数据库系统d m 3 中的应用获得了较好的效果。 关键词：查询执行，扫描，排序，索引，散列，自底向上，二维定址哈希算法 i 华中科技大学硕士学位论文 a b s t r a c t q u e r ye x e c u t i o ni s a ni m p o r t a n tp a r to fd a t a b a s et e c h n o l o g y t h es p e e do fq u e r yc a n d i r e c t l ya f f e c tt h ep e r f o r m a n c ea n de f f i c i e n c yo ft h es y s t e m s t h e r ea r ef o u rp r i n c i p a l m e t h o d sf o re x e c u t i o no ft h eo p e r a t i o n so fr e l a t i o n a la l g e b r a ，w h i c hi n c l u d es c a n n i n g s o r t i n g ，i n d e x i n ga n dh a s h i n g o u rn a t i o n a ld a t a b a s em a n a g e m e n t s y s t e md m 3 u s e st h e s ef o u rm e t h o d st oe x e c u t ei t s q u e r i e s t h e r ea r et w op r o b l e m s t ob es o l v e di nd m 3 o n ei st h a tt h es p a c eu t i l i z a t i o no f b + t r e ei sl o w t h eo t h e ri st h a th a s hf u n c t i o n sh a v em a n yc o l l i s i o n s i no r d e rt os o l v e t h e s e p r o b l e m s ，a n e w b o t t o m u p m e t h o do f c o n s t r u c t i n g b + t r e ea n d an e w t w o - - d i m e n s i o n - a d d r e s sh a s h a l g o r i t h m a r ed e s i g n e dd e t a i l e d l y t h ef i r s tn e wm e t h o du s e sab o t t o m u pm e t h o dt oc o n s t r u c tab + t r e e i tc a ni m p r o v e t h es p a c eu t i l i z a t i o no fb + t r e ea n dt h ee f f i c i e n c yo f c o n s t r u c t i n gb + t r e e i tm a k e ss u r e t h a tt h el e a v e so fb + t r e ea r ei nas e q u e n c eo nt h ed i s k ，s oi ti se f f i c i e n tt or e a dd a t ao fb + t r e e sl e a v e sf r o mt h ed i s k t h es e c o n dn e wm e t h o dd e s c r i b e san e wh a s h a l g o r i t h m ，w h i c h u s e sa t w o - d i m e n s i o n - a d d r e s st od e t e r m i n eak e y sp o s i t i o ni nt h eh a s ht a b l e o n ed i m e n s i o ni s s t o r e di nt h eh a s ht a b l e i no r d e rt os t o r et h eo t h e rd i m e n s i o n ，a l la u x i l i a r yt a b l ei su s e d i th a sf e w e rc o l l i s i o n st h a nc o n v e n t i o n a lh a s ha l g o r i t h m s t h em o s ti m p o r t a n ta n d s u r p r i s i n gp r o p e r t yo f t h en e wh a s ha l g o r i t h mi st h a tt h ea v e r a g ek e y c o m p a r et i m ei sn o m o r et h a n1 nw h e nw eu s et w o - d i m e n s i o n a d d r e s sh a s h a l g o r i t h mt os e a r c hak e yw o r d i nt h eh a s ht a b l e ，w h e r eni st h es i z eo f t h ea u x i l i a r yt a b l e i i 华中科技大学硕士学位论文 i np r a c t i c e ，t h e s ea l g o r i t h m sh a v eg o o dp e r f o r m a n c e k e yw o r d s ：q u e r ye x e c u t i o n ，s c a n n i n g ，s o r t i n g ，i n d e x i n g ，h a s h i n g ，b o t t o m u p t w o - d i m e n s i o n - - a d d r e s sh a s h a l g o r i t h m i i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：旁知函7 日期：p 尹年f 月1 ，曰 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密曰。 ( 请在以上方框内打“4 ”) 学位论文作者签名蕉孥轴 指导教师签名 关谈 日期：沙d 弘年，月f 2 ，日 日期：沙。弘年5 月f i e j j 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 在关系数据库系统( r e l a t i o nd a t a b a s em a n a g e m e n ts y s t e m ，r d b m s ) 中，s q l 语句经过查询编译之后一般用一种类似关系代数运算的方法来表示，然后由查询执 行模块执行。在该表示方法中，查询操作包括：并、差、交、积、连接、选择、投 影、消除重复、分组以及排序。d m 3 中s q l 语句经过编译之后被表示成一种包含 关系代数运算的查询树，查询执行模块使用查询执行算法来实现这棵查询树。 查询执行算法是直接操纵数据库底层数据，其性能的好坏决定了查询效率的高 低。查询执行算法有很多，但最主要的只有4 种：基于扫描的方法，基于排序的方 法，基于索引的方法以及基于散列的方法。在不同情况下，上述的关系代数运算可 以使用这些方法中的一种或者多种实现。但无论具体的实现算法基于哪种方法，决 定算法性能的都是其最基本的算法：扫描、排序、索引或者散列。 d m 3 使用上述方法设计了自己的查询执行算法，但是在实践中发现d m 3 查询的 效率与国外先进数据库系统如o r a c l e 、s q ls e r v e r2 0 0 0 等相比有一定的差距，主 要表现为查询响应的时间太长。深入分析发现其原因正是某些查询执行算法设计不 合理。 本课题来源于国家8 6 3 计划：国产数据库系统d m 3 的开发，是其中的一个子系 统。目标是提高d m 3 查询执行的速度，缩短查询响应时间，提高d m 3 的查询性能。 研究的主要内容有d m 3 中查询执行算法的具体实现以及4 个基本算法的有关内 容。通过研究d m 3 中查询执行算法的具体实现，可以找到影响d m 3 查询性能的具体 算法，通过对具体算法的分析以及对其相关基本算法的研究，找出算法性能不佳的 原因，设计出新算法，从根本上改善算法的性能，从而提高系统查询的效率。 除此之外，对查询执行算法的研究可以深入了解各种算法的优缺点以及性能代 价，为d m 3 查询优化器的设计提供理论基础。新算法的设计与研究可以促进数据库 技术的发展与进步。查询效率的提高可以提高用户的满意度。 华中科技大学硕士学位论文 1 2 国内外研究概况 1 2 1 基于扫描的方法 基于扫描的方法有表扫描和索引扫描。扫描算法的主要工作包括按顺序读入文 件数据，处理数据，输出结果。影响扫描算法性能的主要有文件的组织结构和磁盘 数据读写的速度。 常见的文件组织有3 种：任意顺序的记录文件( 如堆文件) 、排序文件和哈希文 件。现在假设文件有b 个数据页，每页有r 条记录，读或者写一磁盘页的平均时间 是d ，处理一个记录的平均时间是c ，在哈希文件组织中，使用哈希函数把一条记录 映射到数值，对记录使用哈希函数所需要的平均时间是h 。目前典型的取值是：d - 1 5 毫秒，c 和h 都为1 0 0 纳秒。可以看出物理输入输出( i n p u t o u t p u t ，i o ) 是主要 的代价。考察常用的操作：扫描、等值搜索、范围扫描、插入以及删除，对三种文 件组织分析的结果。1 如表1 1 所示。 表1 1i o 代价比较 文件组织扫描等值搜索范围搜索插入删除 堆文件b d0 5 b db d 2 9 搜索代价t d1 排序文件 b d d l 0 9 2 bd l o g2b + 匹配记录数 搜索+ b d搜索代价+ b d 哈希文件 1 2 5 b dd1 2 5 b d2 d 搜索代价+ d 表1 1 表明，没有哪种文件组织能在所有情况下都有优势。其中堆文件适合全 文件扫描；哈希文件实现等值搜索的效率最高；如果是范围搜索，则排序文件是最 优的。 为提高磁盘读写的速度，国外提出了包括基于柱面的组织、多磁盘技术、磁盘 镜像、电梯算法以及预读取等“1 技术。 1 基于柱面的组织：将一起访问的块放置在同一柱面上。这样可以消除寻道 时间，并且可以避免旋转等待。 2 多磁盘技术：在几个较小的磁盘上分派数据，而不是集中在一个大的磁盘 上。同时使用更多的可独立访问块的磁头组合，可以增加单位时间块的访问数量。 3 “镜像”磁盘：制作两份或更多的单个磁盘上的数据的拷贝。除了能够在 部分磁盘出现故障时保护数据外，还可以同时访问多个块。 2 华中科技大学硕士学位论文 4 使用磁盘调度算法如电梯算法来选择读写所请求的块的顺序。 5 预读取：将预期要使用的块预先取到主存储器中。当访问的块已知但是请 求的时序依赖于数据时，可加速访问。不过它需要额外的主存，而且对随机访问没 有任何帮助。 1 22 基于排序的方法 基于排序的方法首先对要操纵的数据排序，然后在有序数据上执行操作。根据 排序是否能一次在内存中完成可以分为内排序和外排序两种o “1 。 内排序算法包括插入排序、选择排序、归并排序、快速排序、堆排序以及基数 排序等。外排序算法包括外归并排序、散列排序以及置换选择排序“3 等，其中最常 用的是外归并排序，其排序过程分为两个阶段。第一阶段为外排序建立所用的内存 缓冲区，根据它们的大小将输入文件划分为若干段，用某种有效的内排序方法，对 各段进行排序，排序完毕就被写到外存中。第二阶段把第一阶段生成的初始归并段 加以归并，一趟趟地扩大归并段和减少归并段个数，直到最后归并成一个有序文件 为止。优化外排序算法主要要减少排序的趟数，减少物理i o 的次数。优化内排序 则需要减少关键字比较移动的次数。 由于数据库系统所处理的数据一般非常大，因此国外的数据库系统包括d b 2 、 i n f o r m i x 、s q ls e r v e r 、o r a c l e 以及s y b a s ea s e 等都采用了外排序算法。s y b a s ea s e 在一个叫做过程缓存的内存分区中运行排序。d b 2 、i n f o r m i x 和o r a c l e 也采用了独 立的主存分区进行排序。s q ls e r v e r 和s y b a s ei q 则在缓冲池中排序。而且上述的 数据库管理系统都采用了外排序优化算法。在所有系统中，物理i o 操作都是异步 的，并且采用了预读取技术。在内存中，s q ls e r v e r 和s y b a s ea s e 采用归并算法 排序，d b 2 和s y b a s ei q 采用基数排序，o r a c l e 则采用插入排序。 另外，国外对算法的应用、分析及优化等各个方面进行了深入研究，譬如：针 对连接运算中的数据倾斜问题，文献 5 中提出了用排序归并来处理倾斜数据的连接 算法。o w e no s t r a c h a n 等o3 则对冒泡排序进行了深入研究和分析。其他的研究成果 还有很多，在此不一一列举。 在排序方面，国内也进行了大量的研究，取得了一些研究成果。针对目前对现 有排序方法处理大规模长记录数据的应用局限性，文献 7 中提出了一种映射链接的 新排序方法。文献 8 中提出了一种利用硬件实现关系排序的模型。根据大多数统计 _ _ _ 一一 华中科技大学硕士学位论文 数据服从正态分布的特性，文献 9 中提出了一种新的散列排序算法。在排序时不需 要用传统的比较排序算法，而是根据分布函数构造出一个序号函数，运用该函数可 以很快计算出每个数据所排的位置。文献 1 0 中提出了一种新的外排序算法，该算 法通过代码转换和分档实现外排序。文献 1 1 对简单排序算法中的冒泡、选择、插 入排序进行了适当的改进。文献 1 2 中提出了一种归并排序算法的阵列映射。文献 1 3 中研究了最优堆排序算法。文献 1 4 中提出了一种新的堆排序算法。文献 1 5 中提出了一种新的多路归并排序网络。 1 2 3 基于索引的方法 如果基表上存在合适的索引，则应该考虑使用基于索引的方法。利用有序的索 引，可以快速找到需要的索引记录。索引算法的设计跟索引结构密切相关，对索引 的研究主要集中于索引的管理，包括索引结构的定义，索引的建立与存储管理等。 索引在各种商业数据库如o r a c l e 、s q ls e r v e r2 0 0 0 、d b 2 、s y s t e mr 、d m 3 等 中得到了充分的利用。在索引研究方面，国外提出了很多索引存储结构，其中包括 线性索引、i s a m 、b + 树、哈希索引等“3 。 线性索引提供了对变长数据库记录的便捷访问，允许对数据库记录进行有效的 检索和随机访问，但是它也不利于更新。 i s a m 是一种静态索引，适合进行扫描操作，有利于并发访问。i s a m 文件一旦被 建立，插入和删除只影响叶子节点内容，当进行大量插入操作时，会产生很长的溢 出链，不利于搜索。如果数据大小相对稳定而且溢出链很少，i s a m 索引的性能相当 好。 b + 树索引是一种动态索引结构。该结构的优点包括叶子节点数据有序，插入删 除操作方便而且不改变树的平衡，利用索引查找数据非常方便等等。适合扫描、查 找、插入、删除等多种操作。不过其空间利用率不高，一般只有6 0 左右。 哈希索引最适合等值查找，利用哈希函数能迅速地找到关键字所在的桶号，通 过该桶号对应的磁盘页面，能很快找到要找的数据。哈希索引有静态哈希索引、可 扩展哈希索引以及线性哈希索引等。静态哈希索引的桶数目b 保持不便，随着文件 的增长，静态哈希的溢出链不断交长，其性能会逐渐恶化。可扩展哈希和线性哈希 都允许b 变化。可扩展哈希索引通过引用间接的目录层扩展了静态哈希，有效地支 持插入和删除而不产生溢出页。线性哈希在创建新桶时利用一个智能策略，不使用 - - _ _ 一 华中科技大学硕士学位论文 目录就能有效地支持插入和删除，尽管也有溢出链，但溢出链长度很少超过2 。与 可扩展哈希相比，线性哈希的缺点是空间利用率低。 随着数据库技术的发展，为解决空间数据库中的多维索引问题，国外又提出了 kd 树1 、四叉树1 、r 树m 1 、r + 一树1 、c o m p a c tr - 树1 、z k d b t r e e 3 以及u b t r e e ” 等，在此不作详细描述。 在实现国产数据库系统d m 的过程中，提出了不少跟索引有关的研究成果。其中 包括：多媒体数据库的时态索引技术。，空间对象数据库的网络索引机制。，用来 处理图像匹配的一种支持快速相似检索的多维索引结构o ”等等。 国内的其他专家和学者也提出了一些跟索引有关的研究成果。文献 2 6 中讨论 了面向对象数据库系统中的索引技术，分析了传统的基于值的索引技术不适合用来 处理有序集合的原因，然后提出了一种新的适合于有序集合的p + 树索引机制。针对 b + 树在并发控制机制中的使用，文献 2 7 中提出了一种新的弹性b + 树，降低了弹性 b + 树上节点合并分裂的次数，减少了弹性b + 树的维护开销，缩短了封锁时间，提 高了操作的并发度和系统的效率。文献 2 8 则对多维向量动态索引的结构进行了深 入研究，提出了e r - t r e e 动态索引结构，提高检索效率；通过引入插入安全点和删 除安全点概念，有效地提高了建树的效率。 1 2 4 基于散列的方法 基于散列“1 的方法通过散列函数来计算关键字在散列表中的位置，非常适合等 值匹配。散列算法的设计必须考虑散列函数的选择以及解决冲突的策略。 散列函数应该尽可能将键散列开，让每个桶分得数量均匀的记录，从而减少访 问一个记录的平均时间。另外，散列函数应该容易计算，因为在应用中它将被多次 使用。 当键为整数时，一种常见选择是计算k 除b 的余数，其中k 是键值，b 是桶的 数目，通常是一个素数。当键为字符串时，把每个字符看作一个整数来处理，把它 们累加起来，求其总和除b 的余数。一个用于数字值的比较好的例子是平方取中方 法。1 。另一个用于有效处理字符串的函数是e l f h a s h 函数”1 。 为了获得效率更高的散列函数，国外很多专家都在致力于获得完美哈希函数 ( p e r f e c th a s h i n gf u n c t i o n ，p h f ) 或极小完美哈希函数( t h em i n i m u m p e r f e c t h a s h i n gf u n c t i o n ，m p h f 1 ) 。理论已经证明：对于确定的集合确实存在相应的p h f 华中科技大学硕士学位论文 或m p h f ，只是找到它们的概率非常的小：只有千万分之一”。国外提出了一些求解 p h f 和m p h f 的算法。文献 2 9 中提到了两种方法：“求商法”和“求余法”，不过该 算法只实用于n 很小的静态集；文献 3 1 中提出了一种求倒数的方法，通过3 个参 数可以确保获得m p h f ，但是该方法只对n 2 0 的集合有用：c h a n g ”提出了一种方 法只需要一个参数，但是他并没有提供具体的算法，因此只能停留在理论阶段；文 献 3 3 中提出了种适用于静态大集合的算法。 解决散列冲突的方法包括：拉链法，桶式散列，线性探查，二次探查以及双散 列”1 等方法。 1 3 主要研究工作 1 3 1 研究思路 本文先研究d m 3 中查询执行的具体实现，找到d m 3 中存在的问题，并分析其原 因。然后设计新算法解决问题。对于新算法，先研究其算法思想并举例说明，接着 论证算法的有关性能特点，最后对算法的主要性能进行实验分析，证明新算法能在 一定程度上解决d m 3 中存在的问题。 1 3 2 主要工作和预期目标 本文的主要工作包括三个方面的内容。 1 分析d m 3 中查询执行算法的不足之处及其原因。 2 研究设计自底向上构建索引b + 树算法。 3 研究设计二维定址哈希算法。 d m 3 中出现的主要问题是b + 树空间利用率过低以及散列冲突太多影响了查询执 行的性能。预期目标是设计新算法解决这些问题。 研究自底向上构建索引b + 树的算法思想及其实现方法，并举例进行说明。分析 自底向上构建索引b + 树的性能，证明白底向上构建索引b + 树的方法可以控制生成 的索引b + 树的空间利用率。 研究二维定址哈希算法的思想，设计散列表的生成算法以及关键字的查找、插 入、删除算法，并举例进行说明，分析二维定址哈希算法的性能，通过实验证明二 维定址哈希算法可以有效减少散列冲突。 华中科技大学硕士学位论文 2 查询执行的策略 本章主要是分析d m 3 查询执行算法的不足之处及其原因。先研究查询执行的一 般过程和主要算法。再研究d m 3 查询执行的具体实现，找出d m 3 中存在的问题，并 分析其原因。通过对问题原因的深入分析，寻找解决问题的思路和方法。 2 1 查询执行的一般过程 在r d b m s 中，一条s q l 查询语句的执行过程如图2 1 所示。 查询在被执行之 前，一般先由查询编译器生成查询计划，然后由查询执行模块按计划执行。查询执 行算法直接操纵着数据库的元数据，对于时间代价主要取决于物理i o 的d b m s 查询 而言，查询执行的性能直接决定查询的性能。 划 图2 1 查询处理器的主要部分 在r d b m s 中，查询经过查询编译器处理之后，一般会表述成一种树形结构，树 中记录了查询操作、查询的对象以及其他辅助信息，根据这些内部信息，r d b m s 服 务器可以完成一个查询。 一棵查询树一般包括一个或者多个查询操作。在提交给查询执行模块之前，这 些查询操作执行的顺序和算法已基本被选定，查询执行模块只需按计划执行，所做 的主要工作是：从磁盘上读入数据，用某种算法操纵数据，在各种操作之间传递数 华中科技大学硕士学位论文 据，输出查询执行的最终结果。在此过程中，涉及到的算法有数据存取的方法、执 行单个查询操作的算法以及多查询操作求解策略。 在r d b m $ 中，数据库元数据一般都存储在外存文件中，查询算法的选取会跟具 体的文件组织结构相关。哈希文件应该适用基于散列的算法，而索引文件则会选择 基于索引的算法。 2 2 查询执行的主要算法 本节从三个方面分析查询执行所涉及的主要算法：数据存取的方法、多查询操 作的求解策略以及执行单个查询操作的方法。 2 2 1 数据存取的方法 根据1 2 1 节的介绍，同磁盘读写的时间相比，数据在内存中的处理时间几乎 是微不足道的，因此在r d b m s 中，数据存取的代价基本决定了查询执行的成本。 数据存取的方法一般有表存取和索引匹配。其速度跟缓冲区大小、硬件速度以 及数据读写的方法有关。更大的缓冲区和更快的硬件速度有利于数据的存取。数据 读写的方法有顺序读写和随机读写。据统计，顺序读取的速度比随机读写的速度快 1 0 倍左右。在软件设计方面，只能通过合理使用内存以及根据操作需要存储和读取 数据文件来提高数据存取的速度，基于柱面的组织、多磁盘技术、磁盘镜像、电梯 算法以及预读取等技术可以有效提高某些操作中磁盘读写的速度。 2 2 2 多查询操作求解的策略 当一个查询包括多个关系运算时，在查询执行过程中会产生临时数据，因此需 要考虑临时数据在操作符之间传递的策略。 多查询求解的策略有流水线求解和实物化求解。流水线求解通过管道将操作的 运算结果直接传递给下一个操作，而不需要将查询执行的中间结果保存在临时的关 系中。一般通过迭代器来实现流水线操作。实物化求解则将临时关系保存在外存 中间结果文件中，当需要处理时再读入内存。很显然，流水线求解比实物化求解方 法的开销小，因此，在允许的情况下，一般选择流水线求解。 具体采用什么策略跟临时结果的大小、后续操作的特点、系统的内存以及d b m s 系统设计有关。如果临时结果集很小，不需要写回外存，则没有考虑求解策略的需 8 华中科技大学硕士学位论文 要。如果后续操作必须处理数据集，而不能处理其中的一部分，则只能使用实物化 求解。如果系统内存容量非常大，能同时处理所有的并发操作而不出现内存太少的 问题，则没有必要考虑使用求解策略的需要。对于内存数据库这种d b m s 而言，所处 理的数据量一般不大，所有操作都可以在内存中完成，因此不需要考虑特别的求解 策略。 2 23 执行单个查询操作的方法 执行单个查询操作的4 种主要方法各有特点，适用于不同的场合。 扫描算法通过扫描数据文件获得查询的结果，但是一趟扫描的代价很高，因此 基于扫描的算法要尽量避免多趟扫描数据，不适合用来实现查询条件中条件值不确 定的查询匹配。如果查询操作不进行条件匹配或者匹配条件确定，则基于扫描的算 法比较合适。 排序之后的数据是有序的，如表1 1 所示，有序文件非常适合进行范围搜索和 等值搜索。因此基于排序的算法非常适合用来实现范围搜索和等值搜索。 基于索引的方法跟索引结构密切相关，商业数据库中较常见的索引有b + 树索引 和哈希索引。如表1 1 所示，哈希索引非常适合等值查询，但是哈希结构并不适合 做范围查询。b + 树结构具有排序文件记录有序的特点，非常有利于范围查询和等值 查找。 数据经过散列算法散列之后，其存储结构为一种哈希结构。哈希文件非常适合 等值搜索，因此散列算法主要用于需要进行等值查找的操作中。 查询执行算法的选择跟算法的特点以及查询操作的特点有关。 1 并。关系r 和s 的并要求将r 的元组和s 的元组合并到一个关系中。并操 作不涉及条件匹配，因此非常适合扫描算法。相比之下，基于排序或者散列的算法 除了扫描数据文件之外，还做了无用的排序或者散列操作，增加了时间代价。同扫 描算法相比，基于索引的算法需要多读入索引数据，增加了操作的代价。 2 差。一个元组在差的结果中出现的次数是其在r 中出现的次数减去在s 中 出现的次数，但是不能比0 小。差操作要求判断元组记录是否相等，涉及到了等值 查找，而且查找条件不确定，因此e e 较适合的方法是散列、排序和索引。因为差比 较的是整条元组，所以只有当索引关键字包含了元组中所有的列时，才使用基于索 引的方法。 9 华中科技大学硕士学位论文 3 交。一个元组在交的结果中出现的次数是其在r 以及s 中出现次数的较小 值。交操作电要求判断元组记录是否相等，涉及到了等值查找，而且查找条件不确 定，因此比较适合的方法是散列、排序和索引。因为差比较的是整条元组，所以只 有当索引关键字包含了元组中所有的列时，才使用基于索引的方法。 4 积。要求r 中的任何一条元组跟s 中的所有元组都进行连接，连接过程中 无需任何比较与匹配，只是简单输出连接的结果。使用简单的嵌套循环扫描算法就 可以很好地实现它，不需要进行额外费时的排序或者散列，也用不上索 1 。 5 选择。要求对选择列进行条件匹配。当选择列上有可利用的索引时，索引 匹配的效率非常高。若没有可利用的索引，则应该利用基于扫描选择算法，在扫描 每一条元组的同时进行条件匹配，一趟就可以找到要找的元组记录。排序和散列除 了扫描一遍关系文件之外，还需要进行排序或者散列，代价比扫描算法高，因此不 考虑。 6 投影。如果投影列上有对应的索引，则使用索引扫描可以快速地获得投影 结果，否则，利用表扫描一趟可以获得投影结果，排序和散列在此都是无用的、浪 费时间的操作，不作考虑。 7 排序。要求输出结果按照排序关键字有序。可用的方法只有排序或索引扫 描。如果排序关键字上有可利用的聚集索引，则使用索引扫描来获取有序数据，否 则都应该采用排序的方法获得数据。 8 消除重复。要求输出结果中没有重复的元组，因此处理过程中必须比较元 组是否相等，相等的元组记录只需要保留一条即可。对于每一条元组而言，比较的 条件基本都不一样。除了扫描，排序、散列以及索引都适合用来进行条件不确定的 查找匹配。当且仅当索引关键字包含了元组所有列时，使用基于索引的方法。 9 分组。要求结果中分组关键字值相等的元组在一起，因此必须比较元组中 分组关键字的值。因为每一组中关键字值都不一样，所以适合的方法只有索引、排 序以及散列。当分组列上有聚集索引时，使用基于索引的算法，否则应使用基于排 序或者散列的方法。 1 0 连接。连接是查询执行中最耗时的操作，需要进行连接条件的匹配，而且 每次匹配时条件列的具体取值基本都不一样。比较适合的方法有排序、散列或者索 引。条件列上有索引时，使用基于索引的方法。否则，若条件为等值条件，则使用 散列连接，其他情况只考虑基于排序的连接算法。 - _ _ - _ - _ _ _ _ _ _ _ _ - - _ _ - _ _ _ - - _ _ _ - _ _ _ _ _ _ _ _ - _ - _ _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ - - _ - _ _ _ _ - _ - h 一一 华中科技大学硕士学位论文 具体采用哪个算法依赖于若干因素，包括关系的大小、现有的索引、元组的存 储方式、相关的统计信息、可用缓冲池大小以及缓冲区的替换策略等。 2 3 达梦3 中查询执行的具体实现 在国产数据库系统d m 3 中，查询经过预编译后生成一棵查询树。查询树中记录 了查询的类型、执行的算法、相关的条件信息、临时表信息以及其他信息。查询执 行模块根据一种特定的顺序执行查询树，并返回执行结果。数据以文件的形式存放 在外存上。文件的存储方式有索引文件和记录文件。d m 3 选择的索引主要是b + 树索 引。 数据通过表扫描和索引扫描获得。当查询存在多个操作时，如果有中间结果产 生，d m 3 的中间结果一般存放在临时表中，如果有足够多的内存，则将临时表保留 在内存中，否则将之写回外存，在需要的时候再读入内存。因此，d m 3 多查询求解 的性能并不好，这也是影响其性能的原因之一。 d m 3 用基于扫描的方法实现了并、积、选择以及投影。其中基于扫描的乘积操 作算法要根据内存的大小及关系的大小决定采用哪一个关系作为循环的内关系。设 内存有b 块内存页面，如果其中至少一个关系可以全部存放在b - 1 个内存块中，则 将该关系作为内循环关系。如果两个关系都太大，没有一个可以完全存入内存的b 一1 块中，为减少物理i o ，将较小的关系作为内关系，较大的作为外关系。下面举例 说明。假设b = i o i ，b ( r ) = 5 0 0 ，b ( s ) = i 0 0 0 ，用r 作为外关系，只有l 块内存供r 读 入，读入s 总共要1 0 0 0 1 0 0 = 1 0 次，读完s 需要1 0 0 0 次i o ，完成乘积操作还需要 i o x 5 0 0 = 5 0 0 0 次t o ，总共需要6 0 0 0 次i o 。如果选择r 作为内关系，则读完r 需 要5 0 0 次i o ，共5 0 0 i 0 0 = 5 次循环就可以将r 全部扫描完，完成乘积操作则还需 要5 x1 0 0 0 = 5 0 0 0 次操作，总共需要5 5 0 0 次操作，比前面的方法少5 0 0 次i o 。 d m 3 的外排序算法和内排序算法都是归并排序算法。考虑到d b m s 元组记录移动 比较耗时，为了减少元组的移动次数，提高内排序的速度，内排序算法使用辅助索 引数组帮助排序，排序时只移动指向记录的索引，排序完毕，根据索引输出排序结 果。d m 3 用排序算法实现了差、交、连接、排序、消除重复以及分组操作，性能表 现比较稳定。 利用索引b + 树，d m 3 实现了基于索引的投影、选择、连接、排序以及分组等操 华中科技大学硕士学位论文 作。在索引b + 树的使用过程中，发现了如下一些问题： 1 当数据量很大时，创建索引b + 树的速度非常慢； 2 空间利用率不高，浪费了大量空间，影响了索引查找和扫描的性能。 d m 3 使用基于散列的方法实现消除重夏以及等值连接操作。基于散列的算法大 部分时候性能很好，但有时候散列冲突很多，最差时冲突甚至高达9 0 以上，严重 的消耗了系统内存，影响了算法性能。 2 4 达梦3 中要解决的问题 正如前面所介绍的，d m 3 中存在3 个方面的问题需要解决。 1 部分多查询求解速度太慢 原因是d m 3 在内存无法容纳时将临时结果保存在外存上，后续操作必须从外存 读入数据才能求解，增加了物理i o 的次数。解决的方法是实现流水线求解，这跟 d m 3 的设计有关，在此不做过多介绍。 2 跟索引有关的问题 同国外同类产品相比，大数据量时创建索引b + 树的速度太慢。传统方法中使用 b + 树的插入算法创建索引b + 树，太多的索引数据使得内存无法容纳索引b + 树所有 的节点，内存的不足降低了系统的性能。同时当数据量大到一定程度时，树节点会 频繁分裂，严重时会导致内存抖动，因此速度非常慢。 空间利用率过低影响了索引查找和索引扫描的性能。索引b + 树生成算法决定其 空间利用率不高，因为插入数据是无序的，在节点分裂时所选取的分界数据是随机 的，只取决于当时节点中数据的分布情况，而不是由所有数据的分布特征决定，因 此各节点数据的分布必定不均匀，不均匀的数据分布必然会产生过多的节点，因此 会有很多的空闲空间。太多的空闲空间降低了索引查找和扫描速度。另外传统方法 生成的索引b + 树，叶子节点是经过多次分裂后生成的，情况好的时候，叶子节点数 据块基本有序，索引扫描的速度会快一些；情况不好的时候，叶子节点数据块杂乱 无章，索引扫描的性能会比较差。 要想提高大数据量情况下创建索引b + 树的速度，新算法必须要确保在内存中的 树节点尽可能少，保证有足够的内存生成后面的节点，而且节点要尽量少分裂。因 此，应该想办法一次性生成节点，而且前后节点的相关性尽量要小。要想提高索引 华中科技大学硕士学位论文 b + 树的空间利用率，应该想办法将索引数据平均分配到各个叶子节点中，让各个分 段点上的数据成为内节点记录所需要的数据，这样节点数就会比较少。要实现这些 目标，需要想办法控制数据在每一个节点中的分布。 3 散列冲突太多 除了散列算法几乎不可避免地会产生冲突之外，d b m s 中数据的不确定性使得散 列冲突更容易产生。不管是消除重复还是基于散列的等值连接算法，处理的数据都 是动态的，不确定的，但散列函数预先设计好了，用确定的散列函数处理不确定的 数据集，某些情况下会出现特别多的冲突。 目前解决问题的方法是寻找高效的散列函数，如p h f ，但是这类算法的代价都 非常高，不适合d b m s ，需要寻找代价较低的方法来获得高效的散列函数。另外的办 法是更改散列表的数据结构，基于新的数据结构设计新算法，通过设计合理的数据 结构以及合适的操纵算法来减少散列冲突。 2 5 小结 查询执行的算法很多，主要的算法只有4 种：扫描，排序，索引阻及散列。d m 3 主要采用了上述方法来实现执行查询操作。在实践中，大部分时候这些算法的性能 都比较好，但是由于索引b + 树和散列算法本身的一些缺陷，d m 3 中出现了一些需要 解决的问题： 1 索引b + 的空间利用率不高； 2 索引扫描的性能不理想； 3 大数据量时创建索引的速度太慢； 4 散列冲突太多，影响了散列算法的性能。 为了解决上述问题，本文提出了自底向上构建b + 树的方法和二维定址哈希算 法，第三章和第四章将对这两种算法进行详细地描述。 华中科技大学硕士学位论文 3自底向上构建索引b + 树 为提高索引b + 树的空间利用率以及大数据量时创建索引b + 树的速度，本章提 出了一种自底向上构建索引b + 树的方法。 首先研究自底向上构建b + 树的算法思想，接着给出其具体实现过程，并举例说 明该过程，然后对算法进行空间利用率分析，论证该算法可以控制生成的b + 树的空 间利用率，最后进行实验论证和分析，证明该算法可以提高大数据量时索引b + 树的 创建速度，同时该算法生成的索引b + 树可以在一定程度上提高索引扫描的速度。 3 1 算法思想 根据b + 树的定义可知，索引b + 树的叶子节点存储实际的索引记录，扫描索引 的叶子节点数据，获得的应该是按照索引关键字有序的记录集合，反过来说，如果 对元组记录求索引关键字及其元组标志符的投影，然后对投影结果排序，所获得的 结果就是b + 树叶子节点中所要存储的记录集。因此，当基表中存在元组数据时，完 全可以先获得有序的索引记录，用该记录集生成b + 树的叶子节点，然后再向上生成 其内节点和根节点。在实际应用中，大部分情况下，创建索引时基表中已经存在元 组记录，根据这一特点，提出了自底向上构建索引b + 树的算法，其算法思想是： 1 通过投影获得所需要的索引记录： 2 对投影的结果按索引关键字排序； 3 对排序后的结果进行必要的处理； 4 自底向上按层构建索引b + 树。先生成叶子节点，接着生成倒数第二层内节 点，最后生成根节点。 第一步是从基表中获得叶子节点所需要的数据，也就是索引记录集。一般情况 下，索引记录的内容包括 ，其中，k e y 是索引关键字，r o w i d 是唯一的 元组标志符，记录元组在关系文件中的位置，因此投影列包括索引关键字列和 r o w i d 。 第二步是对投影结果排序。根据索引关键字排序。若投影结果列很多，建议采 用索引排序算法0 1 进行排序。 华中科技大学硕士学位论文 第三步是消除索引列的重复元组或对索引关键字做唯一性判断。不同的数据库 系统管理索引的方法可能不一样，但是在任何系统中唯一索引必须保证索引关键字 是唯一的，在构建索引b + 树之前必须进行唯一性判断。对于非唯一索引，d m 3 将索 引关键字值相同的记录的r o w i d 写入r o w i d 链，保留其中一个索引记录，并将该记 录的r o w i d 换成r o w i d 链的链头指针，其他记录都删除。经过处理之后，结果集合 中所有的索引关键字都是独一无二的。 第四步是自底向上构建索引b + 树。根据第三步结果集中记录的个数可以计算出 每个叶子节点应该装入的记录个数以及叶子节点的个数；根据叶子节点的装入情况 可以计算倒数第二层内节点的所有记录；根据第二层内节点的情况可以获得 根节点记录。 3 2 具体实现 3 2 1 投影索引记录 投影采用扫描算法实现。扫描操作一般通过迭代器实现。使用迭代器，同一时 刻活跃的操作可以有许多，而且元组可以按照需要在操作符之间传递，这样就减少 了存储要求，同时提高了系统的并发度。迭代器是三个函数的集合，这三个函数允 许物理操作符结果的使用者一次获得一个元组。 1 o p e n 。这个函数启动获得元组的过程，但不获得元组。它初始化执行操作 所需要的任何数据结构，并为操作的任何对象调用o p e n 。 2 g e t n e x t 。这个函数返回结果中的下一个元组，并且对数据结构作必要的调 整。为获得结果的下一个元组，它通常在操作对象上一次或者多次调用g e t n e x t 。 这个函数还设置了一个表明一个元组是否已经产生或者已经没有元组可产生的信 号。定义布尔变量f o u n d ，当且仅当新元组返回时f o u n d 为真。 3 c l o s e 。这个函数在所有的元组或者使用者想得到的所有元组都获得后结束 迭代。 扫描关系r 的迭代器至少应该包含上述的3 个函数，其详细的实现方法如算法 3 1 所示。 基于算法3 1 ，通过对基表的一趟扫描就可以获得索引关键字以及其对应的 r o w i d 的投影，本来投影操作要求消除重复，但是r o w