（计算机软件与理论专业论文）基于散列的查询优化技术的研究与应用.pdf

兰塑妻兰! 塾型堕窒塑垡堡垫兰箜堕窒皇些里! 坐奎兰堡主兰垒垦堕 基于散列的查询优化技术的研究与应用 计算机软件与理论 硕士生：邓韶勇 指导教师：李磊教授 摘要 实际应用中的大型数据库系统常常同时要求更新实时、查淘快。传统的查 询优化技术只关注奁询效率的提高，在提高查询速度的同时却造成了更新速度 的下降。索引、散列簇和扫描等技术都不能很好的解决更新实时、查询快的问 题。索引的更新维护代价大，敫列簇限制条件太多，全表扫描查询速度慢。在 综合考虑索引、散列簇和全表扫描的优缺点的基础上，本文提出一种基于散列 的查询优化算法。该算法将敌歹i j 和扫描结合在一起，实现简单，兼顾查询和更 新效率。为了迸一步提高查询优化的效果，本文又提出了一种高效的散列捧序 算法和两种改进增强的查询优化算法双层的查询优化算法和双项的查询优 化算法。最后本文在个自主研发的数据库管理系统内实现了本文算法，并 结台实际应用的数据进行了实验，给出了实验结果。实验结果表明本丈提出 的基于散列的查询优化算法维护代价小，查询效率高，特别适用于更新和查询 频繁、实时性要求高的大型数据库系统。 关键词： 玫列，查询优化，扫描 里塑苎 墨! 墼型竺奎塑垡垡壁苎垫里塞皇查墨 ! 坐查主堡主兰些茎 a 7 i e 圮h n o l o g yo fq u e r yo p t i m i z a t i o nb a s e d o nh a s h c o i t l p u t e rs o 脚盯ea i i dn 圮o r y n a n 砖：d c n gs h a o y o n g s u p c r v s o r ：p m 把s s 0 rl ik i a l b s t i c t i k a i t i l i l e u p d a t ca n d 自s tq u c r y 缸eb 【，t hr e q u h di l l 眦n yl a r g cd a t a b a s e a p p l i c a t i o 璐t r a d i t b 髓iq u 钉yo p t i n i i z i i i gt c c h l o g i e si n c r c 砒ct l i cq r ys p c c db i l t d c c 咒a s et h e u p d l t cs p c e d a tt h cs 锄e t i i i 砖i 璀王c x l l a s hc k s t c ra n ds c a n t e c 蛔m i o g i c s n i 帕t l v ct h cp f o b i c mo f 代a “i l n cu p d a t ca n dh 甜q u c r y i n d c xi i a s l a r g cu p 血t c0 0 甜s h 私hc l l l s t 盯h st m n yr e s t r i c t sa i l df i i ut a b i cs c 疆nbt o os 1 0 w a na l g o r i 【h i no fq u c f yo p t i h i 妇i o nb a do nh 勰hi sp 黜mb y0 0 憾i d c r i i i gt l 他 a d v a b t 啦sa n dd i s 甜v a n t 2 9 髓o fi n d c x ，h a s hc h l s t e ra n d 缸珏t a b ks c 柚t h i s a i 矿r i t l i m t h a t 。o m b i n c sh l s h w i n is c 蛐a n d 璐“c 娼b o t hq 眦r ya n du p d a t c p c o 唧锄c ci se 稿yt o 巾l c 蹴i - t i no f d c ft o 缸r t h c fh p v et h cq u c f yc 饪熏c i e 舵y a nc 圩函i v ch 蹈h - r ta i g o f 袖ma n d 咐oi n l p v e dq u e r y o p t i l n 谊i n ga l g o r 诬l l l l 峪， w h 蚰a f cc a u c dd o u b k l a y e ra i l dd o u b k i t c ma l g o r i t l i i no fq r yo p t i - i z a t i o l i 盯e p r c s c n t t h ea i g o r i t l 娜o fq u c f yo p t i m i 规t i o na 陀i m p l c m e m c di l i ad a t a b a s e m a n a g c m e ms y s t e i nt b cc 冲e r i l l 他n t sa r cd o f 峙u s i n g a lp m j e c td a t aa n dt h c r e s u l t sa p r e m t l l cr e 弧n ss h o wt h a tt h ca l g o r i t i l mh 嬲l i i t ku p d a t oc o s ta r i dh i g h q u e r yc 任；c i c 眦y i tj sa p p l i c a b l ct ob eu di nl a f g ed a t a b a a p p i i c a l i o 鸺i i a v i n g 丘c q u e mu p d a t c sa i l dq u e r i c sr e q u 哥i i l gf “i i l l cr c s p o n k e yw o i d 戬h a s h i l i g q u e r y ，o p t i m j z a t i 0 t i s c a n ! 塑里 墨三墼型堕查塑垡些塾查塑里塞复查旦! 些苎兰垡生兰兰堕! ! 兰 ll 研究背景 第1 章引言 随着企业对智能化通信的要求越来越高，p c p b x ( p e r s 0 舱lc o m p u t e r p r i v a t eb r a n c he x c 忸n 鼯，计算机专用分组交换机) 的应用也越来越广泛。据美 国i t 调查公司c a l l n e r si 1 1 s t a tg r o u p 调查预测，到2 0 0 4 年，p c p b x 产业将会 从2 0 0 0 年的1 2 2 亿美元上升到4 0 亿美元的销售收入。 p c p b x 应用中的数据库系统常常具有以下的特点： ( 1 1 每天有大量新数据插入，数据库规模不断增大。 ( 查询频繁，要求查询速度快。 f 3 1 更新频繁，要求更新实时响应。 ( 4 1 数据摹本上是按照时间先后顺序存储。 ( 5 ) 查询模式比较固定，对近期数据查询较多。 实际应用中的大型数据库系统也常常像p c p b x 应用系统一样，要求更新 实时、查询快。按照一股的处理方法，在数据库应用中遇到表数据量大、壹询 频繁的情况时，应该建立索引来加快查询速度。但是索引会引入额外的负担， 索引的更新可能引起页合并和页分裂，在提高查询速度的同时也降低了更新速 度，不适用于实时性要求高的场合。 传统的查询优化技术只关注查询效率的提高，而不太重视额外引入的更新 维护代价，造成实际应用中虽然一方面提高了查询效率，但是另一方面却降低 了更新效率。有的查询优化技术注重于理论研究实现过于复杂，执行开销太 大，因此在实际中很少应用。除索引外，分区、簇聚、散列簇和扫描也是常用 的查询优化技术但都不能很好的解决更新实时、查询快的问题。 在综合考虑索引、散列簇和全表扫描的优缺点的基础上，本文提出一种基 于敞列的查询优化算法，兼顾更新和查询速度，并应用于c r m ( c o m d u c c r t e l c p h o n ym a n a g e m e n t ，计算机电话管理系统) 中，取得了良好的效果。本文 提出的查询优化算法简单商效在满足更新实时性要求的同时，也提高了蕾询 的速度。 1 2 研究现状 苣询优化问题一直是数据库领域的一个研究热点。对于同一个查询，由f 翠韶勇巷于散列的查询优化技术的研究与应蹦 中山大学硕士学位沦文 眚询处理策略的不同，查询的处理时间可能相差很大，甚至相差几个数量级n 所以，给定一个查询，需要选择优化的查询处理策略，以减少查询处理时间， 提高系统的处理能力。 传统的查询优化技术主要包括启发式关系代数优化方法、启发式关系演算 优化方法、基于复杂性估计的查询优化方法和语义优化方法等四种。下面简单 介绍一下传统查询优化技术的研究历史和现状。 在关系代数优化方面，文献【l 】是有关查询优化的最早文献，描述了双变量 查询的优化方法。文献【2 1 描述了把关系演算表达式转换为关系代数进行优化。 文献【3 1 给出了关系代数优化的详细算法。文献1 4 1 介绍了关系代数变换方法。文 献【5 】讨论了查询树和关系代数优化方法。 在关系演算优化方面，文献【6 】介绍了查询分解优化方法并讨论了连接超图 消解算法。文献【7 】讨论了查询分解优化算法的性能。文献 8 】讨论了q b e 语言 的查询优化问题文献【1 9 】讨论了基于关系演算的查询优化技术。文献【2 0 l 扩展 了基于关系演算的查询优化技术。 在复杂性估计优化方面，文献 9 l 介绍了基于复杂性估计的查询优化算法。 文献【l o 讨论了具有多连接操作的查询的优化阏惠。文献1 1 1 j 提出了嵌套s q l 查询的优化方法文献【1 2 耐论具有聚集函数的查询优化问题。文献【1 3 】研究了 主存数据库止的查询优化问题。 在语义优化方面，文献f 1 7 】和f 1 8 l 讨论了语义查询优化的问题。文献f 2 l l 讨 论了一种实现基于语义数据模型的数据库系统的查询优化的分类技术。 此外文献【1 4 】对很多查询优化算法进行了比较分析。文献【1 5 1 系统的综述 了奁询优化的主要研究成果。文献1 1 6 l 讨论了查询优化研究领域中的新问题。 文献【2 4 l f 2 5 】【2 6 l 和f 2 7 】介绍了o f k 数据库系统中的查询优化技术。文献【2 8 j 介绍了s q ls c r v e r 数据库系统中的查询优化技术。文献【2 9 】分析了索引对查询 开销的影响。文献f 3 0 l 【3 l 】和f 3 2 l 介绍了用散列恩怨进行捧序的算法。文献f 3 3 1 和f 3 4 j 讨论了散列技术在视图连接查询优化中的作用。 查询优化在关系数据库中有着非常重要的地位。关系数据库系统和非过程 化的s 0 l 语言能够取得巨大的成功，关键是得益于查询优化技术的发展。关系 查询优化是影响关系数据库管理系统性能的关键。近年来，不断有新的查询优 化技术提出来。例如参数化的查询优化技术，针对的是关系大小频繁变化的查 询处理问题。其思想是在编译时先计算出一系列的计划，每个计划针对不同大 ，j 、关系中的一种，然后将这些计划保存下来。执行时根据关系的实际大小选出 其中的一个，避免运行时傲完整优化导致的开销。又例如多查询的优化技术 研究将几个查询视为一组来执行时如何优化的问题。 现有的查询优化技术大多只关注如何提高查询效率，而忽视了由此带来的 2 邛韶勇 鐾于敞列的查询优化技术的研究与应用 中山大学碰七学位论文 对更新效率的负面影响。绝大多数查询优化技术在提高查询速度的同时不可 避免的要增加额外的开销，造成更新速度的f 降。同时考患查询效率和更新效 率的奁询优化技术，特别是同时兼顾高查询性能和低维护代价的查询优化技术 的研究，目前还很少见。 1 3 本文贡献 针对实际应用中的大型数据库系统同时要求更新实时、查询快的问题，庄 综合考虑索引、敝列簇和全表扫描的优缺点的基础上，本文提出一种基于散列 的查询优化算法。该算法将散列和扫描结合在一起，实现简单，兼顾查询和更 新效率。实验表明，本文提出的查询优化算法维护代价小，查询效率高，特别 适用于更新和查询频繁、实时性要求高的大型数据库系统。 本文的主要贡献如下： ( 1 ) 提出了一种基于散列的查询优化算法，证明了算法的正确性并分析了算 法的性能和空闻占用。该算法维护代价小查询效率高。 ( 2 ) 提出了一种高效的散列捧序算法。该算法可以有效的提高查询优化算法 的效率，并且可以控制排序结果的有序度。 ( 3 ) 提出了两种改进增强的查询优化算法双层的查询优化算法和双项 的查询优化算法，并证明了算法的正确性和有效性。 ( 4 ) 在一个数据库管理系统内实现了本文的算法，并结合实际应用的数据进 行了实验，给出了实验结果。 1 4 本文结构 本文共分为六个章节。 第一章简单介绍了查询优化技术的研究背景、相关的研究现状以及作者的 研究工作。 第二章介绍了查询优化问题的理论基础，包括查询处理过程、传统的直询 优化技术、索引技术、扫描技术以及散列技术，并分析了索引、敞列簇和扫描 技术的优缺点。 第三章详细阐述了基于敞列的查询优化技术，给出了查询优化算法和更新 维护算法，对算法进行了正确性证明和性能分析，井给出了构造敝列函数的具 体方法。 弗韶勇蜂于敝列的查询优化技术的研究与应用 中山大学硕七学使论文 第四章在第三章的基础上阐述了增强的查询优化技术，给出了一种高效的 散列捧序算法，提出了两种改进增强的查淘优化算法双层的查询优化算法 和双项的查询优化算法并证明了算法的征确性和有效性。 第五章介绍了实验系统给出了实验环境和实验结果。并对实验结果进行 了分析。 第六章是对本人研究工作的一个总结回顾了本文的创新点，同时指出了 不足之处以及未来的工作，对将来的研究方向作出了一个展望。 邛韶勇簋于教列的查询优化技术的研究与应用 p 山大学硕士学位论文 2 1 查询处理 第2 章传统的查询优化技术 数据库管理系统的主要任务是有效的处理用高级查询语言编写的用户查 询。查询的处理是数据库管理系统的核心。 查询是由高级查询语言表示的对数据库的一个或一组操作。查询处理需要 经过语法分析、查询优化、代码生成和查询执行四个步骤才能完成。 查询处理过程如图2 1 所示： 查询优化 图2 一l 语法分析模块具有四个功能。第一个功能是对给定的查询进行语法检查。 第二个功能是执行语义有效性检查，即检查给定查询是否i f 确的引用了数据库 ! 塑苎墨王墼型堕童塑垡垡垫查盟曼塞皇查旦 坐查兰堡主兰! ! 羔! 羔 模式、属性等。第三个功能是对给定的查询进行完整性和安全性检查。第四个 功能是产生查询的内部表示，如查询树或查询图。 查询优化模块的功能是优化处理给定的查询，确定执行该查询的优化执行 策略，产生优化的查询执行计划。 代码生成模块的功能是组合数据库管理系统提供的实现各种数据操作的算 法，形成查询优化执行计划的可执行代码。 查询执行模块的功能是控制执行查询计划，产生查询结果。 其中。查询优化是查询处理的核心。由于产生优化的查询执行计划要求大 量的信息并且相当耗时，数据库管理系统的查询优化程序通常并不产生优化的 查询执行计划，仅产生具有较高效率的查询执行计划。 2 2 查询优化技术 传统的查询优化技术主要有四种：启发式关系代数优化方法、启发式关系 演算优化方法、基于复杂性估计的查询优化方法和语义优化方法。 2 2 。l 启发式关系代数优化方法 启发式关系代数优化算法的主要思想：一个查询可以变换为一个等价的关 系代数表达式。通过运用等价规则和优化规则对该表达式进行等价变换，可 以得到一个具有较高效率的等价表达式。 常用的关系代数等价规则主要有： ( 1 ) 选择串接律 ( 2 ) 选择交换律 ( 3 ) 投影串接律 ( 4 ) 选择投影交换律 ( 5 ) 连接和笛卡尔乘积的交换律 ( 6 ) 集合操作的交换律 ( 7 ) 连接、笛卡尔乘积和集合操作的结合律 ( 8 ) 选择、连接和笛卡尔乘积的分配律 ( 9 ) 投影、连接和笛卡尔乘积的分配律 ( 1 0 ) 选择与集合操作的分配律 ( 11 ) 投影和集会操作的分配律 ( 1 2 ) 德摩根等其他等价交换律 邛韶勇 基于敞列的青询优化技术的研究与应用 巾山大学硕士学位论文 启发式关系代数优化规则主要有： ( 1 ) 规则l ：选择和投影操作尽早执行。 ( 2 ) 规则2 ：把某些选择操作与邻接笛卡尔乘积相结合形成一个连接操作。 ( 3 ) 规则3 ：同时执行相同关系上的多个选择和投影操作。 ( 4 ) 规则4 ：把投影操作与邻接操作结合起来执行。 ( 5 ) 规则5 ：提取公共表达式。 2 2 2 启发式关系演算优化方法 启发式关系演算优化算法的主要思想：使用超图来表示一个查询，然后用 超图消解算法实现奄询的分解，从而确定高效率的查询执行策略。 选择消解超边的启发式规则主要有： ( 1 ) 小关系规则：在超图消解过程中，优先选择两种超边进行消解处理。一 种是表示小关系的超边。另一种超边是从超图中将其消除以后能得到包 含表示小关系的超边的超图。 ( 2 ) 投影规则：在进行超图消解过程中，尽早消除查诲结果中不需要的属性。 超图消解算法比较复杂其关键是超边消解的顺序。 2 2 3 基于复杂性估计的查询优化方法 基于复杂性估计的查询优化算法分为两个阶段。第一个阶段利用启发式关 系代数优化方法或者启发式关系演算优化方法产生逻辑上优化的关系代数表达 式或查询计划。第二个阶段为查询计划中的每个关系代数操作选择具有最小复 杂性的实现算法，确定优化执行策略。 影响查询执行效率的因素主要有： ( i ) 查询执行期间存取的磁盘存储器上的数据量。用存取的磁盘块数表示。 ( 2 ) 奁询执行期间产生的中间结果占用的磁盘存储器空间量。 ( 3 ) 查询执行期间使用的处理机时间。 这三个因素的度量称为查询执行策略的复杂性。对于大规模数据库来说， 影响查询执行效率的主要因素是磁盘存取块数，因此很多查询优化方法都把磁 盘存取块数定义为查询策略的复杂性。一个查询的执行策略的复杂性是所调用 的各关系代数操作算法需要的磁盘存取块数的总和。 2 2 4 语义优化方法 语义查询优化利用关系上定义的各种完整性约柬条件，通过修改查晦条件 椰韶勇 基于敲列的查诲优化技术的研究与应用中山大学硕士学位论文 把给定的查询变换为更有效的等价杳询。 语义查询优化的关键是寻找与给定查询有关的完整性约束条件，可以使用 人工智能领域的定理证明技术来实现约束条件的查找。但是，如果约束条件查 找过程需要很多时间，则语义查询优化的效率可能比较低。在这种情况下，语 义查询优化方法可能不适合于实时查询处理。 语义查询优化方法和启发式关系代数优化方法、启发式关系演算优化方法 以及基于复杂性估计的查询优化方法结合起来，可以得到更好的优化效果，获 得更有效的查询执行策略。 2 3 索引技术 索引是数据库系统中使用最多的查询优化技术之一。查询优化器中一般都 会利用索引技术。 按照索引文件的结构，索引可以分为下面两类： ( 1 ) 耩琉索引；稀酸索引把所有的数据记录按关键字的值分成很多组，每组 设立一个索引项。这种索引的索引项很少，管理方便，但插入和删除的 代价较高 ( 2 ) 稠密索引：稠密索引为每个记录设立一个索引项，记录存放是任意的， 但索引是有序的。这种索引的查找和更新都比较方便，但索引项多，空 间复杂性大。 按照索引域的特点，索引可以分为下面三类： ( 1 1 主索引：主索引的索引域是数据文件的键即可用来区分文件记录的域， 而且数据文件已经按照链值大小拌序。由于索引域是键，每个索引域值 对应一个记录，索引记录的第二个域只存储一个指针。主索引在处理数 据插入、删除和修改操作时，需要维护数据文件和索引文件记录之间的 序关系。 ( 2 ) 聚集索引：聚集索引的索引域不是键，一个索引域值可能对应于多个记 录，索引记录的第二个域可能存储多个指针。聚集索引是稀疏索引，数 据维护操作的处理比较复杂。 ( 3 ) 辅助索引：辅助索引的索引域是数据文件的任何非键域。一个文件只能 具有一个主索引，但是可以具有多个辅助索引。辅助索引也需要维护数 据文件和索引文件记录之间的序关系。 椰韶勇甚f 敞列的查询优化技术的研究与应用中山大学硕士学位论文 在多数情况下，使用索引能够减少磁盘i o 次数，提高查询速度。但是， 索引也具有以下的缺点【2 3 l ： ( 1 ) 数据插入、删除或者修改时。部必须对相关索引进行处理，需要多次磁 盘i o 操作，如果有多个索引则维护代价更大。这样会造成更新的速度 下降不适用于实时性要求高的场合。 ( 2 ) 随着查询所检索的数据量的增大，索引的性能下降，甚至会比全表扫描 还要慢。 ( 3 ) 索引要另外占用大量数据库空间。 b 一树是最重要的动态文件索引结构，但是插入和删除操作十分复杂。b + 讨是b 一树的改进，但在插入和删除时仍具有分裂、合并的问题。 总的来说，索引不适用于更新频繁、实时性要求高的应用场合。 位图索引也是一种常用的索引技术。位图索引存储位图，每个位图是一系 列的1 和0 的字位。位图索引包含索引中的一列或一组列中每一个不同值的位 图。当相关的链值存在时，位图中的该位为l ，否则为0 。位图索引比传统的索 引节约时间和空间。但是，位图索引也不适用于有频繁插入、删除和修改的应 用场合1 2 射。 2 4 散列簇和扫描技术 大型数据库通常包含许多大型的表，在用户执行查询操作时往往需要浏览 大量数据，查询效率较低。为了便于大型数据库的管理，改善应用程序的性能， 有的数据库系统为用户提供了分区的功能。分区就是动态地将表中记录分割成 多个易于管理的块，并创建在若干个表空间上。分区虽然将表中的数据在物理 e 分割开来，但是通过建立连接所有分区的视图，这些数据仍将在逻辑上体现 为一个有机的整体，同时在对表的某一分区进行管理和维护时不会影响到其它 分区，这就使数据的整个管理和维护工作更加灵活。在查询优化过程中，优化 程序可以知道分区的范围值。当访问表时，优化程序将直接访问指定的分区， 这样在访问中只浏览了少量数据，提高了查询效率。同时分区在表和行之间增 加了一个数据级别，为数据的并行操作提供了便利条件。但是分区的更新维护 代价是比较大的。 数据查询时，为了充分发挥索引和连接操作的优势，提高查询效率，可将 参与连接的具有相同列的若干表聚集起来存储在一起，这种数据存储方式称为 9 邙韶勇基于散列的查询优化技术的研究与应用 中山大学硕七学位论文 聚簇。使用聚簇可以节省存储空间，减少索引的存储空间和维护开销，同时还 能减少数据检索期间的磁盘“o 操作。和索引的使用一样，并不是所有情况下 使用聚簇都能改善查询性能。对于那些关系并不密切，极少有连接操作，或是 碜改、插入和删除操作频繁的表，如果使用聚簇存储方式，反而会降低查询性 能。 数列簇瞄l 是簇聚的一种特殊形式。这种技术通过散列函数计算得出元组的 物理位置，可以极大程度地提高等值查询的效率【2 2 l 。采用散列簇作为查询操作 的访问路径，通过散列函数就能直接计算出相应行的存储位置，而采用索引则 需要多次磁盘i ，o 操作。数列簇技术在大型数据库的查询中具有较强的优势。 但是，散列簇也具有以下的缺点： ( 1 ) 对插入、删除和修改操作频繁的表，采用散列簇反而会降低查询性能 ( 2 ) 如果查询条件与数列关键字无关，或者为非等于操作，或者表长难以预 计，或者全表扫描操作比较多时，采用散列簇将不利于提高查询效率。 ( 3 ) 表的大小只能有很小的增长。 ( 4 ) 对范围查询效力很弱。 全表扫描1 2 6 l 指的是在访问表时，从磁盘上存储该表的起始位置开始，逐条 记录读取数据，直到该表的结束位置如果所处理的关系表比较小，则应该采 用全表扫描，因为索引会加重系统负担。一般的查询优化器在制定查询计划时， 如果命令所检索的数据超过表中数据的2 0 ，系统会选择全表扫描，而不是使 用索引【矧。 扫描的优点是避免了非顺序读页。顺序读文件可以使磁盘的预读效率得到 提高。磁盘读写数据的时间由寻道时间、等待时间和传输时间决定。其中，寻 道时间是最主要的。随机读写文件会造成磁头的频繁摆动，使寻道时间增加。 著名测试软件w 甜i 、l 的测试结果表明，顺序读数据的速度比随机读快大约2 5 倍，顺序写数据的速度比随机写快大约5 倍。 但是，全表扫描需要读取表中的所有记录，因此速度较慢，不适用于大型 表的查询。 2 5 散列技术 散列函数又称为哈希( h 舔h ) 函数，是在记录的存储位置和关键字之问建立的 一个确定的对应关系f 使每个关键字和唯一的存储位置相对应。只要根据这 个对应关系f 找到给定值k 的像耳k ) ，若存在关键字和k 相等的记录，贝l j 必定 1 0 率韶勇量于教列的直询优化技术的研究与应用 中山大学硕士学位论文 庄f r k l 的存储位置上。因此，不需要进行比较就能够直接找到所需的记录。按 照这个思想建立的表称为散列表。 教列函数是一个映像，因此其设定很灵活，只要使得任何关键字由此所得 的散列函数值都落在表长允许范围之内即可。对不同的关键字可能得到同一个 散列地址，即k 1 k 2 ，而f ( k 1 ) = 珂i 【2 ) 。这种情况称为冲突。选择一个恰当的散 列函数可以避免冲突的发生。但是一般情况f ，冲突只能尽可能的少，而不能 完全避免。因为散列函数是从关键字集合到地址集合的映像，通常关键字集合 比较大，其元素包括所有可能的关键字，丽地址集合的元素仅为散列表中的地 址值。 若对于关键字集合中的任意一个关键字，经散列函数映像到地址集合中任 何一个地址的概率是相等的，则称此类散列函数为均匀的散列函数。换句话说， 就是使关键字经过敏列函数得到一个随机的地址，以便使一组关键字的散列地 址均匀分布在整个地址区间中从而减少冲突。 常用的构造数列函数的方法有： ( i ) 直接定址法：取关键字或者关键字的某个线性函数值为敞列地址。 ( 2 ) 数字分析法：取关键字的若干数位组成数列地址。 ( 3 ) 平方取中法：取关键字平方后的中间几位为散列地址。 ( 4 ) 折叠法：将关键字分割成位数相同的几部分( 最后部分的位数可以不 同) ，然后取这几部分的叠加和( 舍去进位) 作为散列地址。 ( 5 ) 除留余数法：取关键字被某个不大于敬列表表长的数除后所得余数为散 列地址。 ( 6 ) 随机数法：选择一个随机函数，取关键字的随机函数值为散列地址。 实际选择散列函数要视具体的情况，通常考虑的因素有 ( 1 ) 汁算散列函数所需时间( 包括硬件指令的因素) 。 ( 2 ) 关键字的长度。 f 3 ) 散列表的大小。 ( 4 ) 关键字的分布情况。 ( 5 ) 记录的查找频率。 通常的处理冲突的方法主要有： ( t ) 开放地址法：将冲突的地址加上一个增量后再取模。根据增量序列的不 同主要有线性探测再散列、_ 二次探测再散列和随机探测再数列等几种。 ( 2 ) 再教列法：在产生地址冲突时，计算另一个散列函数地址，直到冲突不 再发生。 邛韶勇鹭干教列的查诲优化技术的研究与应用 中山大学顾七学位论文 ( 3 ) 链缝址法：将所有映射到同一地址的关键字的记录存储在同一线性表 中。 ( 4 ) 公共溢出区法：建立一个公共溢出区，将发生冲突的全部记录都放入溢 出表中。 敞列函数选择是否恰当影响出现冲突的频繁程度。不同的冲突处理方法影 响记录查询的效率。一般来说，散列表的装填因子( 定义为散列表中填入的记 录数除以数列表的长度) 标志数列表的装满程度。装填因子越小，发生冲突的 可能性越小。装填因子越大，发生冲突的可能性也越大。 率韶勇 基于教列的查诲优化技术的研究与应用中山大学硕士学位沧丈 第3 章基于散列的查询优化技术 3 1 算法描述 3 1 1 符号和定义 襄3 1 给出了下面用到的一些符号及其含义。 表3 1 t 数据库中的一个单表关系 r 1 1 表t 的记录数 f 表t 的一个字段属性 r - f ) 属性f 的值域 u 表t 中的一条元组记录 u f 元组u 的属性f 的值 l t n o ( u ) 元组u 的记录号 o 用户查询 q 替代查询 h 散列表 s 散列表h 的大小 h i i 】1 n i n f 表h 下标i 对应的记录号下限 h 【i 】m 盯n o 表h 下标i 对应的记录号上限 p ( x ) 散列函数 m l n r n 0 记录号下限的变量 m a x r n o 记录号上限的变量 g m 叫a b ) 表h 下标( a ，b ) 范围对应的记录号下限 g r m x r b ) 表h 下标( a ，b ) 范围对应的记录号上限 这里解释一下散列表h 中m i n r 肿和 p ( x ) = y ，叉h 【y 1 m i 盯= a ，h 【y 1 n a n o = b ， 记录和第b 条记录之间。 m a 】【r f l 0 的含义。假设散列函数是 表示值为x 的记录只出现在第a 条 毋韶勇垦于敞劓的查询优化技术的研究与应用卜山大学硕士学位论文 下面的讨论仅限于数据库中的一个单表t 。假定一个单表中的记录是按照 插入的先后顺序连续存放的。对每一条记录u ，部有一个唯一的记录号r n 0 ( u ) 来标识其存储位置。第l 条记录的记录号为l ，第2 条记录的记录号为2 ，以此 类推。 类似于索引，对于要查询的一个关键字段f ，建立一个散列表h 。散列表h 实际上可以用数组来表示，通过选择一个合适大小的s 值( 例如1 0 0 0 0 0 0 ) ，可 以将数列表h 全部放在内存中，这样访问h 表就不需要磁盘i o 操作。 散列函数p ( x ) ：r a 峨争， o 1 一，s - l 是一个非负单调增函数。该函数的构造 方法将在后面详细介绍，这里为简单起见， 仅以 p ( x ) = ( x m i n r a i l ( 9 ) + ( s - l m r a n ( d i 作为例子来说明。 查询优化算法的散列表示意图如图3 1 所示： 数据库表h 数列表 图3 1 在上面的示意图中，敫列函数为p ( x ) = x 。h 【1 1 m i n r = l ，h ( t 】- m a 】【r n 0 = 3 ， 表示值为1 的记录只出现在第1 条记录和第3 条记录之间。h 【2 l 。m 妇= 2 ， h 【l 】脚x f = 6 ，表示值为2 的记录只出现在第2 条记录和第6 条记录之间。 h 3 1 m i n r = 5 ，h 【3 】m x r = 8 ，表示值为3 的记录只出现在第5 条i 己录和第8 条记录之间。 1 4 堪骝勇善f 敞列的查询优化技术的研究与应用 中山大学碛七学位论文 定义辅助函数g m i i l 亿b ) ，g m a a ，b ) 如下： g l m n ( a ，a ) = h 【a 1 m i n m o g r i l i n ( a b ) = m i n h 【a 】m i n r n o ，h 【a + l1 m i n m o ，h f b 】m i n m o a b g m 砜a ，a ) = h 【a 】m a x m o g m a x ( a ，b ) = m a x ( h 【a 1 m a x m o ，h f a + l j m a x m o ，h p j 啪x m o a 八 ) ：= v ：= 【 i l 庄此规定，关系运算的优先级最高，析取v 次之，合取八最低。 f 面给出一些查询优化算法中使用到的概念： 定义3 1 ：敞列字段。 建立了敞列表的关键字段，称为散列字段。 定义3 2 ：可优化的关系运算符。 如果关系运算符是= 、 = m 函佃o r n 0 = m a x r 八o 。 情况2 ：如果原子公式是k a 或者f = a 的形式。 则令 m i i l f n o = g m i n ( o ，p ( a ) ) m a = g 啷l x ( o p ( a ) ) 并令q 等于r n o = m 岫八r n o c = m a x r 0 。 情况3 ：如果原子公式是b a 或者b = a 的形式， 则令 m 妇n 0 = g m i n ( p ( a ) ，s 1 ) m 煳= g 雌p ( a ) s - 1 ) 并令q 等于i 蝌o = m i n f n o r n o c = 嫩x r n o 八q 。 ( 2 ) 如果q 是可优化的表达式，且q 有两个或以上可优化的子公式。 情况4 ：选择其中两个可优化的原予公式。 如果其中一个是b a 或者b = a 的形式，另一个是f 专 ，个是f ( b 或f = 2 0 0 3 1 2 0 1 八p r i o r n y = h i g h v p a s s = 、r c s 瞢代查询q 为r n o = 8 0 0 0 0 0 八r n 0 = 2 0 0 3 1 2 0 i 八 p r i o r 诬y = h i g l l v p a s s = 1 盹s 。 3 1 3 更新维护算法 数据库启动时，要构造敝列表并对散列表h 进行初始化。 仞始化算法如下： 向r ( i = o ；i ( s ；i + + ) h 【i l l i m = 一 h 【i 1 嘲盯= o f b f 表t 的每一个元组ud o ( x = u f y = p ( x ) h 【y 1 1 i l i 眦= l i l i h 【y j ，m i n r 0 ，r n o ( u ) h i y l 眦】= 腑x h 【y 】m a x r n 0 ，r n o ( u ) ) 初始化算法的时间复杂度为o ( n ) 。 数据库进行更新操作( 插入、蹦除和修改1 时，教列表h 的维护算法如下 ( 1 ) 插入操作：假设插入一个新元组u ，令x = u f ly = p ( x ) ，则 h 【y j m i i i r = m i l l h 【y 1 m j i i r n 0 ，r n o ( u ) ， h ( y 1 n n 】【r n o = r n o ( u ) ( 2 ) 删除操作：假设删除表中一个元组u ，令x = u f y = p ( x ) ，则 h y 1 m i 盯n 0 保持不变 h 【y i 啊皿】【r 保持不变 ( 3 ) 修改操作：假设将表中一个元组u 改为u ，令x = u f y = p ( x ) ，则 h 【y 】m 泌= m i n h 【y 】m i n h m ，r n o ( u ) h 【y 1 m 叠肺如= m 童x h 【y j m a 】哪m ，r n o ( u ) 更新维护算法的时间复杂度是o ( 1 ) 。 可以看出，本文算法所需要的维护代价是非常小的。 1 9 哪姐勇羲千敞列的彘询优化技术的研究与应_ 【 j 中山大学硕士学位论文 3 2 算法分析 3 2 1 算法的正确性 引理3 1 ：v u q ，有h 【p ( u 1 ) 1 m i i i f n o = m i i l f 八 r n 0 = m m r n o 八r n 0 = m a 材 q ，则q = q ， 证明： 由引理3 1 知 h 【p ( u f ) 】m i n f = r n 0 ( u ) = h ( p ( u oj m 盯n o 又m i i l f = h 【p ( u f ) 】n 协】【r 所以 m i 啪o = r n o ( u ) = 毗x r a 由引理3 2 知u q ，因此眶q 。 又由引理3 3 知q o ，所以q = 0 。 定理3 1 ：q = q ，即替代查询q 和用户查询q 是等价的。 证明： 蕾询重写规则一共有6 种情况，下面逐一讨论。 ( 1 ) 对于情况l 。v u q ，有u b a 。 又m i 加的= g m 抽( p ( a ) ，p ( i ) ) = h 【p ( a ) j m i i l r m a x r n 0 = g 腿x ( p ( a ) ，p ( a ) ) = h 【p ( a ) 】m a x r 所以 m i i l f = h 【p ( u f ) 1 n i i l i “帕 m a x m o = h 【p ( u f ) 1 嘴】【r 由引理3 4 得q = q 。 ( 2 ) 对于情况2 。v u 0 ，有u f a 或者u f ( = a 。 又m i i l r n 0 = g m i n ( 0 ，p ( a ) ) = m i i l h f 0 1 m i i i r ，h 【l 】m i i l r 衄，h 【p ( a ) j i l l i 盯n o m a x r = g m x ( o ，p ( a ) ) = 脚x h 【o 】船舶帕，h 【1 】m x m o ，h 【p ( a ) 】- m a x n o 因为u f ( a 或者u k = a ，p ( x ) 是非负单调增函数，所以o = p ( u f ) = a 。 又m i i l r = g l l l i f p ( i ) ，s - 1 ) = m h h 【p ( 童) 1 m i n r f 的，h ( p ( a ，+ 1 1 m i n n 的，h s - l 】m i i l r n o 2 l 平韶勇羹f 数列的查询优化技术的研究与成用 中山大学硕十学位论文 m 五r = g n 瑚p ( a ) s - 1 ) = m x h 【p ( a ) 】嘲加，h 【p ( a ) + l 】m a ，h f s _ i 】m a x r n o 因为u 6 a 或者u 6 = a ，p ( x ) 是非负单调增函数，所以p ( a ) = p ( u f