（计算机应用技术专业论文）基于查询计划的查询优化研究.pdf

摘要a b s t r a c t 摘要 在数据库应用系统中，查询速度的快慢直接影响到应用系统的生命力。数据库用 查询计划表示查询优化器选择的查询优化策略，查询计划的好坏直接影响到查询速度 的快慢。本课题将基于查询计划来优化应用系统的查询。 现实情况表明，编写形式不同而功能相同的查询语句可能有很大的性能差异。这 是由于数据库查询优化器采用动态优化的方法，优化可用的时间和空间有限以及查询 成本估计可能不准确造成的。 本课题设计一个查询优化工具，采用静态优化的方法，克服优化时间有限的缺陷； 对要优化的查询构造尽可能多的等价查询，扩大查询计划的探测空间，克服优化空间 有限的缺陷；按照实际运行的成本选择优化结果，克服成本估计不准确的缺陷，从而 通过帮助数据库查询优化器生成高效的查询计划，达到优化查询的目的。 本课题使用两种方式构造等价查询，扩大查询计划的探测空间：一种是根据关系 代数等价的转换，另一种是根据语义等价的转换。课题实现了关系代数等价转换的算 法，总结了语义等价的情况，并根据回调函数的原理设计了可扩展的语义等价转换系 统。 本文提出的优化查询方式能够帮助应用系统的查询找到高效的等价查询，提高了 应用系统的查询速度。 关键词：查询计划；查询优化；关系代数；语义等价 a b s t r a c t t h ee f f i c i e n c yo fad a t a b a s ea p p l i c a t i o ns y s t e mi sd e t e r m i n e db yt h eq u a l i t yo fq u e r i e s a q u e r yp l a nm e a n st h eq u e r ys t r a t e g ye m p l o y e db yad a t a b a s eq u e r yo p t i m i z e rs ot h i s t h e s i sa i m sa tt h eo p t i m i z a t i o no ft h eq u e r yq u a l i t yi nad a t a b a s ea p p l i c a t i o ns y s t e m t h r o u g haq u e r yp l a n t h er e a l i t ys h o w st h a td i f f e r e n t e x p r e s s i o n s o faq u e r yp r o b a b l yh a v ed i f f e r e n t p e r f o r m a n c es i g n i f i c a n t l yw h i l et l l e yh a v et h es a m ef u n c t i o n s t h ed i f f e r e n c ei sc a u s e db y t h r e ea s p e c t s ：f i r s tt h eq u e r yo p t i m i z e ro ft h ed a t a b a s ei sb a s e do nd y n a m i co p t i m i z a t i o n , s ot h et i m ea n dt h es p a c ef o ro p t i m i z a t i o na l el i m i t e d ，a n dt h ec o s te s t i m a t i o no ft h eq u e r y m a yb ei n a c c u r a t ea l s o t h i st h e s i sd e s i g n e daq u e r yo p t i m i z a t i o nt o o lt oo v e r c o m et h ed e f e c t s f i r s tt h et o o li s b a s e do ns t a t i co p t i m i z a t i o n ；s e c o n d ，t h et o o lg e n e r a t e se q u i v a l e n tq u e r i e sa sm a n y 嬲 p o s s i b l ef o rs u f f i c i e n tc h o i c e s ；f i n a l l y , t h et o o le v a l u a t e st h eo p t i m i z a t i o no na c t u a lc o s t s t h u s ，t h i st h e s i si n t r o d u c e sat o o lt oh e l pt h eq u e r yo p t i m i z e ro ft h ed a t a b a s eg e n e r a t e e f f i c i e n tq u e r yp l a n ，w h i c hi m p r o v e st h ee f f i c i e n c yo ft h ed a t a b a s ea p p l i c a t i o ns y s t e m t h i st h e s i sa p p l i e dt w om e t h o d st og e n e r a t ee q u i v a l e n tq u e r i e s o n em e t h o di sb a s e d o nt h et r a n s f o r m a t i o no fe q u i v a l e n tr e l a t i o n s h i pa l g e b r a ；t h eo t h e rm e t h o di sb a s e do nt h e c o n v e r s i o no fs e m a n t i ce q u i v a l e n c e t h et h e s i si m p l e m e n t st h ea l g o r i t h mo ft h ee q u i v a l e n t t r a n s f o r m a t i o nb a s e do nr e l a t i o n s h i pa l g e b r a , s u m m a r i z e st h ec a s e so fs e m a n t i c e q u i v a l e n c e ， a n dd e s i g n sa ne x t e n s i b l et r a n s f o r m a t i o ns y s t e mb a s e do ns e m a n t i c e q u i v a l e n c ef o l l o w i n gt h ep r i n c i p l eo f c a l l b a c k - f u n c t i o n t h i st h e s i sc o n t r i b u t e st oi m p r o v et h eq u e r ye f f i c i e n c yo ft h ed a t a b a s ea p p l i c a t i o n s y s t e ma n dt h es p e e do fs y s t e m si n q u i r yt h r o u g hf i n d i n gt h ee q u i v a l e n th i g hq u a l i t yq u e r y k e yw o r d s ：q u e r yp l a n ，q u e r yo p t i m i z a t i o n ，t h e r e l a t i o n sa l g e b r a ，s e m a n t i c e q u i v a l e n c e i i 学位论文版权使用授权书 本人完全了解北京信息科技大学关于收集、保存、使用学位论文的 规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子 版本：学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本 学位论文全文或者部分的阅览服务；学校有权按有关规定向中国科学技 术信息研究所等国家有关部门或者机构送交论文的复印件和电子版；在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用 于学术活动。 学位论文作者签名：i 自爿齐 垮 沙7 年d 月t 3 日 经指导教师同意，本学位论文属于保密，在年解密后适用本授 权书。( 注：论文属公开论文的，作者及导师本处不签字) 指导教师签名：学位论文作者签名： 年月日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的论文题目为基于查询计划的查询优化研 究学位论文，是本人在导师指导下，进行研究工作所取得的成果。尽 我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论 文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方 式标明。本学位论文原创性声明的法律责任由本人承担。 作者签字： 向渊埒 2 0 0 8 年1 2 月0 6 日 第一章引言 1 1 选题背景和意义 第一章引言帚一早ji 商 数据库系统是各类管理信息系统的支撑平台，是信息化建设中应用最广泛的基础 性软件。随着应用系统提供的服务功能不断扩大和数据库系统的使用时间的不断增 加，数据库容量迅速增长，应用程序的查询请求复杂度在不断增加。 数据库应用系统不能因为数据库容量的增大而降低服务的质量，相反，在不断增 多的应用和快速增长的数据情况下，企业要求数据库应用系统提供更快的响应速度， 这样才能使企业对瞬息万变的信息资源快速反应，提高服务质量和顾客满意程度。因 此，对数据库应用系统的查询优化的研究不仅具有实用性，而且经济意义巨大。 在数据库系统中，查询优化器的功能是把一个查询语句分析处理后描述成一个可 高效执行的查询计划，一个好的查询计划，能够成指数级别地提高查询性能。但是由 于市场竞争激烈，各数据库厂家对自己的查询优化器原理总是三缄其口。而数据库查 询优化器本身有一定的限制，对于一个应用系统的查询来说，完全依靠数据库内部的 查询优化器不一定能得到一个最优化的查询计划。因此，研究使应用系统的中的查询 总是能够使用数据库最优化的查询计划是查询优化的一个发展方向。 在对具体的应用程序的查询优化中，有经验的开发人员凭着对具体数据库特征的 了解，对查询语句进行语法重新构造，能够帮助数据库查询优化器获得更好的查询计 划( 这个查询计划是无法靠数据库查询优化器自身独立工作产生的) 。因此，应用程 序需要这样的一个工具，它模拟人的行为对应用系统的查询语句进行优化，它使用有 经验的开发人员的查询编写经验对查询语句进行语法重新构造，帮助数据库查询优化 器获得更好的查询计划，从而对应用系统的查询进行优化。 1 2 文献综述 自从1 9 7 7 年c o d d 提出关系数据库理论以来，关系数据库的应用得到了极大的 发展，目前广泛使用的数据库系统主要有o r c a l e ，d b 2 ，s q l s e r v e r ，s y b a s e 。 在众多的商业化数据库产品中，都为标准s q l 2 】语句提供了扩展的实现，如 s q l s e r v e r 的t - s q l t 3 】，o r a c l e 的p _ s q l e 4 , 5 】，应用程序使用这些语法编写程序， 向数据库程序发送查询请求来处理数据。 应用系统的范围在扩大，数据库的数据量在增加，应用系统对查询的效率要求越 来越高。应用系统的要求促使数据库查询优化器对查询请求进行高度优化，因此，数 1 第一章引言 据库查询优化器是数据库系统的核心功能之一，也是各数据库厂商的核心竞争力。但 是为什么在应用程序的实现过程中，程序编写人员还需要不断地总结各种数据库的优 化方法【6 , 7 , 8 , 9 , 1 0 , 1 1 , 1 2 , 1 3 】呢? 实践经验表明，编写形式不同的等价查询语句可能有差别极 大的查询效率，有经验的程序员能把编写形式不好的查询优化上千倍。应用程序为什 么不能完全依靠数据库的查询优化器来获得优化的查询，这要从数据库查询优化器的 实现技术上分析。 从上个世纪7 0 年代以来，数据库系统的查询优化的研究就在持续的开展【1 4 j ，这 可以从g r a e f eg 总结的查询优化中使用的各种技术【l5 】中获知。查询优化是复杂的优 化问题【1 6 】，查询优化涉及的内容众多，查询优化涉及的研究对象在不断扩大：随着 d s s 系统等复杂程序的应用的发展，促使数据仓库【1 7 , 1 8 , 1 9 1 的研究不断深入，查询优化 研究的对象不再仅仅局限于s p j 查询【2 0 1 ，而是含有大量集合运算【2 1 2 2 2 3 】的复杂查询； 查询优化的算法【2 4 】仍是研究的重点；在查询重写机制2 5 2 6 1 加入到查询优化之中，查询 优化研究的方向进一步扩大；最后，查询优化又要充分考虑高速发展的并行技术，早 期的查询优化技术并没有考虑到并行特性【2 7 1 ，从而不能最大限度的发挥并行机或分布 式系统的能力，因此，并行条件下的查询优化技术【2 8 ，2 9 】也成为查询优化研究的重要内 容之一。 多联结查询的查询计划搜索空间很大，使用哪种算法才能有效的搜索到最优的或 者较优的查询计划。目前广泛使用的有如下的四类搜索方法：穷尽搜索算法【3 0 1 ：穷尽 搜索算法穷尽搜索空间，虽然成本很高但是能得到最优的查询计划；启发式方法【3 l 】： 启发式方法采用两段优化原理但是不一定能得到最优的查询计划；随机算法【3 1 3 2 】：随 机算法最大的好处在于其恒定的空间开销对于复杂的、关系数目庞大的查询来说有重 要的地位；全局搜索算法：主要是指重复全局搜索算法如基因算法【3 3 3 钔。 八十年代末，i b ma l m a d e l l 研究中心开发的可扩充数据库系统s t a r b u r s t 中【巧j ， 首次采用了查询重写这一新的技术【2 5 2 6 1 。查询重写是对查询语句的等价重写，一个目 的是重写为效率更高的等价查询，如函数重写【3 6 】。另一个目的是简化查询，例如嵌套 查询和相关子查询【3 7 】转化为联接查询。 基于成本的查询优化器要根据元组数量进行查询成本的估计【3 8 】，因此对关系中的 数据建立统计数据提高预估的准确性，常用的有直方图【3 9 加】，分布函数等。另外索引 作为一项特殊的统计，在查询优化方面有很大的影响，实际使用最多。但是，统计的 数据不准确或者更新不及时，那么查询计划的成本估计就不准确，这是查询优化器的 一个缺陷。 从上面的分析可以看出，数据库查询优化器优化查询所采用的方法和策略众多， 其中的查询重写和查询计划搜索是空间要求和时间要求很高的算法，但是数据库查询 优化器是动态优化的，也就是它会在找到最优计划和找到这个最优计划的时间和空间 2 第一章引言 代价中折中，即从查询计划搜索空间中找到“查询的执行时间+ 找到这个计划的时间 最小的查询计划，这是查询优化器的第二个缺陷。 在实际应用中，应用程序的查询的优化主要是基于经验的改进。但是不同的数据 库有不同的优化方法【9 , 1 1 , 4 4 , 4 5 , 4 6 , 4 7 , 5 2 , 5 3 , 5 4 】，不同的系统【4 , 4 2 , 4 3 优化的方法也各不相同， 没有统一的优化方法，也没有形成统一的优化理论，怎样利用这些优化的经验对应用 系统的查询进行统一的优化的要求迫切郴】。本课题就是要研究数据库查询优化器的优 化过程和优化策略的缺陷，利用这些不断积累和总结的查询优化实际经验，设计统一 的优化过程【4 8 】避免这些缺陷以达到优化应用系统查询的目的。 1 3 课题的主要研究工作 1 3 1 研究思路 利用数据库查询优化器来优化应用程序的查询，第一步要研究数据库查询优化器 的工作原理和它的优化过程，了解数据库查询优化器使用的优化技术，分析应用系统 的查询没有完全优化的原因；第二步根据数据库查询优化器优化查询的技术，研究构 造等价查询语句，扩大查询计划探测空间的方法，并在这些等价查询中选择优化的结 果，反馈给应用程序和数据库：第三步建立优化评估的标准对优化的效果进行评价； 最后，要研究把优化应用到实际的应用程序优化之中。 1 3 2 研究内容和目标 本课题的研究目标是模拟程序员对查询语句的优化过程，通过外挂查询优化器的 使用，克服数据库查询优化器的缺陷，帮助数据库查询优化器找到高效的查询计划， 从而达到优化应用系统的查询的目的。 本课题的研究内容安排如下： 第一，采用文献法研究数据库查询优化器使用的优化和搜索技术，分析数据库查 询优化器的缺陷和这些缺陷的技术原因，研究构造等价查询的原理，为设计外挂的查 询优化器作技术准备。 第二，根据对数据库查询优化器的研究和技术准备，设计外挂查询优化器，模拟 有经验的程序员的优化方法，通过构造尽可能多的等价查询，扩大查询计划探测空间， 帮助数据库查询优化器找到等价查询中的最优查询计划。 第三，在优化器的实现中，要尽可能多地构造等价查询语句；本文把构造等价查 询语句的方法分为两种：关系代数的等价转换和语义等价转换。 3 第一章引言 第四，根据关系代数的等价转换理论，实现关系代数的等价转换算法；根据例证， 对语义等价转换的规则总结并进行分类，设计可扩展的语义等价转换系统。 第五，设计测试过程，用统计的方法评估优化的结果。 最后，针对论文成文过程中的结论和成果以及出现的问题总结。 1 4 课题的技术路线 图1 1 课题的技术路线图 如图1 1 所示，应用系统向数据库发送查询请求时，查询语句的优化由数据库查 询优化器完成：数据库查询优化器对查询语句进行查询重写，然后在等价查询的空间 中搜索最优查询计划。 本课题所用的技术是：对于应用系统的查询语句，进行语法分析，然后根据关系 代数等价转换和语义等价转换的原则，尽可能多地构造等价查询，并测试这些等价语 句的实际执行效率，选择效率最高的等价查询反馈给应用程序和数据库系统来优化查 询。 构造等价查询是技术路线的关键点，等价转换的原则有两个：一是关系代数等价 转换；一是语义等价转换。因此，实现查询语句等价转换第一是实现关系代数等价转 换的算法；第二是总结语义等价转换的情况，对它们分类，按照回调函数的设计思路， 4 第一章引言 设计可扩展的语义等价转换系统，让规则自身描述触发方法和触发后的动作，既实现 规则触发逻辑，又方便新规则的加入。 1 5 论文的组织结构 第一章引言：介绍在应用系统和数据库系统之间使用查询计划优化查询的研 究背景，并根据实际需求给出了课题研究的意义，回顾目前国内外的研究状况以及本 文涉及的主要研究工作，明确本课题的技术路线。 第二章设计查询优化器的技术准备：分析数据库自身的查询优化器存在缺陷 的技术原因，研究数据库查询优化器构造等价查询搜索空间的技术，为设计外挂的查 询优化器作技术准备。 第三章- 夕f 、挂查询优化器的整体设计：根据应用的场景的功能要求，设计外挂 查询优化器，完成原理分析、整体的架构设计、数据结构设计和算法设计以及各个功 能的设计。 第四章一关系代数等价转换的算法实现：根据第三章设计的数据结构，按照关 系代数等价转换的原则，设计构造关系等价的查询语句的算法。 第五章语义等价转换：总结查询语句语义等价的规则并对它们分类，设计可 扩展的语义等价转换系统。 第六章测试过程和优化评估：使用优化器对一实际场景的查询进行优化，设 计测试过程，对优化效果评估。 最后一部分是对论文研究的总结和展望，指出进一步研究的方向。 5 等二章设计查询优化器的技术准备 第二章设计查询优化器的技术准备 本章分析数据库自身的查询优化器存在缺陷的技术原因，描述构造等价查询的实 现方式，为实现外挂查询优化器作技术准备。具体分为三节组成，第一节一数据库 查询优化器的缺陷：分析数据库查询优化器缺陷存在的技术原因；第二节一查询重 写：分类总结数据库查询优化器构造等价查询的查询重写机制；第三节_ 搜索算法： 总结数据库查询优化器在等价查询空间中搜索的优化算法。 2 1 数据库查询优化器的缺陷 应用系统在向数据库服务器发送查询请求的时候，没有也不能处理由于查询语句 不同的书写形式在性能上的差异，但是不同编写形式的查询语句的性能差异在大型或 者复杂的数据库环境中非常突出。应用系统使用初期，由于数据量小，无法对比查询 语句不同写法导致的性能差异，随着系统的持续使用和数据的积累，系统响应速度越 来越慢的状况凸显出来，成为一个不容回避的问题。 应用系统自身可以不断调整来优化查询，如创建索引，编写更高效率的等价查询 语句。但是对于不同的应用系统，表间关系不同，表内数据分布情况也不同，查询的 编写方式更有可能不同，对于这些不同的查询，不同的查询环境，优化查询的策略各 不相同；另外影响数据库性能的因素很多，找出一个通用的方法并不现实。因此在系 统开发和维护的过程中必须针对实际运行的情况，结合经验及对系统的了解，对查询 不断加以调整，必要时进行测试加以修正，才能取得满意的查询优化效果。 在数据库系统中，查询优化器的功能是把一个查询语句分析处理后描述成一个可 高效执行的查询计划，因此查询优化器的输入是查询请求的查询语句，输出正好是给 查询执行器的输入即查询计划。一个好的查询计划，能够成指数级别地提高查询性能。 但是，完全依靠数据库内部的查询优化器又不一定能得到一个最优化的查询计划。 数据库内部的查询优化器为什么不可靠? 上面已提及数据库查询优化器的功能： 当一条查询语句被送入数据库服务器，它将会被解析并提交给数据库查询优化器；查 询优化器将会进行查询重写和表达式评估以产生可供选择的查询计划；产生可供选择 的查询计划的数量取决于在数据库系统的中定义的查询计划搜索空间大小，对于每个 待选的查询计划计算估计成本，有最小成本的查询计划将被选取用来执行查询语句。 这种方法存在着几个无法解决的问题，在2 1 1 ，2 1 2 ，2 1 3 将描述这些问题。 6 等二章设计查询优化器的技术准备 2 1 1 无法产生全部可能的可选查询计划 查询优化器对查询语句进行重写，然后进行优化【3 5 1 。因此查询计划的搜索空间【2 4 】 和两个条件相关，一个是查询语句的语法，另外一个是计划空间的大小。一般来说产 生越多的可供选择的执行计划，获得最高效执行计划的可能性越大，但是查询计划搜 索空间的大小限制了查询优化器能够产生的可供选择的查询计划的数量。例如一条有 1 5 个表联接的查询，它可能的表联接顺序是1 5 的阶乘： 1 5 1 = 1 5 1 4 1 3 x1 = 1 , 3 0 7 ，6 7 4 ，3 6 8 ，0 0 0 个。 2 1 2 要在有限的时间内完成优化 查询优化器优化查询的过程不仅有空间限制，而且有时间限制。查询优化器采用 的是动态优化机制，也就是说，对于发送的查询请求，要在一定的时间之内完成优化。 因此，构造全部可能的可选计划在时间上也不允许。 2 1 3 成本估计不准确 查询优化器一般采用基于成本的优化模式，估计的成本值是查询优化器用来从待 选查询计划列表中选择某条查询计划的标准。 数据库系统在数据字典中维护它所包含的所有数据和结构的信息。查询优化需要 把数据库表的容量的统计信息【3 8 】、索引、基数和数据直方刚3 9 柏1 等存储下来，以使查 询优化器对于待选查询计划进行成本估计时能够更加准确。但是成本估计的计算准确 度依赖于数据库数据字典和统计信息的准确度，因此在没有实际执行之前，并不知道 查询计划的执行效率。 2 2 查询重写 查询重写【2 5 , 2 6 】是得到查询的等价形式转换，扩大查询计划搜索的空间的方式之 一。查询重写一直被数据库查询优化器用来优化查询，但是规则的不断增多使数据库 查询优化器不得不考虑查询重写的成本。 在数据库查询优化器中，查询重写的首要目的是将查询重写为效率更高的形式， 查询重写的另一个目的是尽量将查询重写为比较简单的等价形式，从而为计划优化阶 段提供更多的机会。查询重写包含了语义等价的情况和一部分关系等价转换的情况， 在2 2 1 中总结这些情况，为第四、五章构造等价查询作准备。 7 等二章设计查询优化器的技术准备 2 2 1 查询重写的一些方式 l 谓词重写 虽然数据库执行引擎对各种谓词的处理方法不同，但是不同的谓词描述能够达到 相同的处理结果，这就是谓词等价。例2 1 中的l i k e 关键字支持通配符匹配，技术 上叫正规表达式，但这种匹配特别耗费时间。 例2 1s e l e c ts t u d e n t n a m ef r o ms t u d e n tw h e r ez i p c o d el i k e 9 8 。 把例2 1 按照谓词等价重写的方式转化为例2 2 的形式： 例2 2s e l e c ts t u d e n t n a m ef r o ms t u d e n tw h e r ez i p c o d e _ 9 8 0 0 0 0 。 现在从效率上来考虑，使用查询例2 1 ，即使在z i p c o d e 字段上建立了索引，也 是采用序扫描的方式，使用查询例2 2 在执行查询时就会利用索引来查询。这个例子 也证明查询重写扩大的查询搜索空间可能包含更优的查询。 2 集合重写 数据库查询语言中，集合操作的语法是u n i o n ( 这里先不讨论减法的操作) 。在 一些查询中，单条查询语句包含了集合操作的情况。例2 3 对s t u d e n t 表的查询包含 了集合操作的并和交的情况， 例2 3s e l e c t 枣f r o ms t u d e n tw h e r e ( s t u d e n t l d = 10 4a n ds t u d e n t l d = 10 4a n ds t u d e n t l d 10 0a n dz i p c o d el i k e 1 o r d e rb ys t e d e n t n a m e l 从本章开始所有的查询语句实例按照如下的规则书写：数据库关键词全词大写如s e l e c t ；关系名、属性名和 别名按照匈牙利命名法书写如s t u d e n t n a m e ，e m p l o y e c l d 。 8 等二章设计查询优化器的技术准备 g o 例2 6s e l e c t 辜f r o ms t u d e n tb j ( w h e r ec l a u s e ) 如果把视图的定义放到查询语句之中，这样能得到和查询视图等价的查询语句。 转换后的查询如例2 7 ： 例2 7s e l e c t f r o m ( s e l e c t 拳f r o ms t u d e n tw h e r es t u d e n t l d 10 0a n d z i p c o d el i k e 1 j o r d e rb ys t u d e n t n a m e ) a ss t u d e n t b j ( w h e r ec l a u s e ) 2 3 搜索算法 查询优化器的搜索算法是在等价查询的搜索空间中找最有效的查询计划，和查询 重写一样，也是扩大等价查询的搜索空间。 2 3 1 穷尽搜索算法 这类算法穷尽等价查询搜索空间【3 0 1 ，该类算法适用于任何类型的查询以及不同种 类数据库，而且能够找到最优的查询计划。但是，当关系的数量较多时，查询计划的 空间以n ! 的大小增大，当关系数量较大时，数据库查询优化器是不会迭代所有的等价 情况的。 2 3 2 其他算法 数据库查询优化器还使用了其他的一些查询搜索算法，这些算法不一定能找到全 局的最优的查询计划：如两阶段优化的启发式算法【3 1 】；局部随机搜索算法【3 1 3 2 1 有恒定 的空间开销，常使用在关系数据庞大的查询中；全局随机优化算法【3 3 ，3 4 1 从开始状态重 复执行局部搜索算法，期望从找到的多个局部最优状态中找到全局最优状态。 2 4 本章小结 本章分析数据库查询优化器的缺陷和缺陷存在的技术原因，指出在查询优化器优 化查询的过程中因为以下的两个原因而不一定能找到最优的查询计划： l 查询重写和查询搜索算法需要扩大等价查询的搜索空间，但查询优化器又只有 限的空问和时间； 2 数据库查询优化器是根据成本估计选择查询计划，查询计划的实际运行效率和 统计信息的准确度有关。 本章还总结查询语句等价转换的查询重写的分类，介绍查询计划空间的搜索方 9 等二章设计查询优化器的技术准备 法，为第三章第四节中构造等价查询做技术准备。 l o 第三章外挂查询优化器的整体设计 第三章外挂查询优化器的整体设计 在第二章中对数据库查询优化器的缺陷和缺陷原因进行了分析，本章设计一个外 挂查询优化器克服这些缺陷，模拟有经验的程序员对查询的改进方法，实现对应用系 统的查询优化。 这个外挂查询优化器采用静态优化的方式，克服数据库查询优化器时间限制的缺 陷；通过对应用系统数据库查询的监测，找出要优化的查询语句；对于要优化的查询 语句，根据关系代数的等价变换和语义等价转换的规则，尽可能多的构造它的等价查 询语句来扩大查询计划探测空间，克服数据库查询优化器空间限制的缺陷；对生成的 等价查询语句按照查询计划过滤；把过滤后的等价查询语句发送给服务器测试，按照 实际执行情况统计代价，克服数据库查询优化器成本估计不准确的缺陷，从而找到优 化的等价查询；将这个等价查询反馈给应用程序和数据库系统，达到优化应用系统查 询的目标。 全章具体分为六节，第一节应用场景：从实际的应用要求分析查询优化器的 功能要求；第二节一优化器的架构和实现原理：阐述优化器的实现原理和技术架构； 第三节一查询描述的数据结构：设计查询优化器描述查询的数据结构；第四节 生成等价关系：描述扩大查询计划探测空间的方法；第五节语句过滤：说明过滤 的原因和实现方法；第六节批量测试和选择最优计划执行：比较实际执行的情况， 选择最优的等价查询。 3 1 应用场景 一个有经验的程序员把有问题的查询语句的速度提高数千倍是很常见的。由于对 具体数据库特征的了解和对查询语句进行语法重新构造，开发人员能够帮助查询优化 器获得更好的查询计划，但是这个查询计划是无法靠查询优化器自身独立工作产生 的。 数据库内部的查询优化器并没有对每一个查询生成最优化的查询计划。因为数据 库服务器对查询是动态优化的，也就是说数据库服务器首先是要响应查询，然后马上 对查询进行优化，最后执行并且返回查询结果。这样一来，优化器的时问是有限制的。 任何一个应用程序都不希望他们发送的查询请求在长达几个小时或者几天之后的某 个时候返回来一个优化的查询结果。可以认为，数据库服务器的查询优化器的优化工 作是动态的，立即返回的。 对于一个应用程序来说，对数据库服务器的请求查询的要求是非常巨大的。如果 1 1 第三章外挂查询优化器的整体设计 服务器总是要响应一些低效率的查询请求，即使数据库的优化器尽了最大的可能性去 优化这些查询，但是由于语句本身编写的缺陷，这些查询的效率不可能达到一个理想 的状态，从而不会是一个优化的高效查询。这里给出具体的例3 1 ： 例3 1s e l e c t f r o mt a b l e la saj o i n ( s e l e c t f r o mt a b l e 2w h e r e n o d e t y p e = 1 ) a sbo na m e s s a g e i d = b m e s s a g e i dj o i nt a b l e 3co nb m e s s a g e i d = c m e s s a g e i dj o i nt a b l e tdo na m e s s a g e i d = d m e s s a g e l d 。 在s q l s e r v e r 上执行例3 1 的时候，生成的查询计划是包含了三个n e s t e dl o o p j o i n 的查询计划树。例3 2 是修改这个查询的联接顺序后的查询： 例3 2s e l e c t 宰f r o mt a b l e la saj o i nt a b l e 3co nb m e s s a g e i d = c m e s s a g e i d j o i n ( s e l e c t 事f r o mt a b l e 2w h e r en o d e t y p e = 1 ) a sbo na m e s s a g e i d = b m e s s a g e i dj o i nt a b l etdo i l 巩m e s s a g e i d = d m e s s a g e i d 。 在s q l s e r v e r 上执行例3 2 生成了同样类型的包含四个n e s t e dl o o pj o i n 的查询计划树，但和例3 1 执行的查询计划不一样。在关系数量较大( 实际上在 - - 4 的情况下) ，查询的联接顺序并不都会被s q l s e r v e r 的内部优化器考虑。 从应用程序的角度来看，要求数据库服务器以最高效的方式处理应用程序发出的 查询请求。从服务器的角度来看，要求应用程序发送高效的查询语句以便快速执行返 回，而不是臃肿和低效率的编译和执行。所以，服务器和应用程序来说中间有一个隔 阂，双方的责任不明晰。 图3 1 应用场景图不 图3 1 中除去使用工具优化的步骤( 系统开发人员是依据自己的经验进行优化的) 是系统开发人员和数据库管理人员优化应用系统查询的典型的场景。 如果能模拟这个查询优化的过程，就能明确应用程序和数据库系统的责任，消除 两者之间的这种隔阂，这时应用系统发送给数据库系统的总是高度优化的查询语句： 1 使用优化的工具通过对应用系统数据库查询的监测，找出要优化的查询语句； 查询优化器要接收的原始查询语句可以直接输入或通过检查源代码来捕获，各种 数据库系统都提供了事件监测的工具，因此也可以通过事件监测来发现在服务器上执 1 2 第三章外挂查询优化器的整体设计 行的查询语句，而且更便于发现频繁请求但是响应时间长的查询请求的查询语句。 2 然后处理要优化的查询语句，尽可能多的构造它的等价查询语句来扩大查询计 划探测空间( 在人工优化的过程中，使用的方法有两种，一种是探测，即尝试优化的 行为；而是计算，根据数据分布，统计，索引综合考虑连接顺序，等价重写的情况) ； 3 对生成的等价查询语句按照查询计划过滤； 4 使用这些过滤后的等价查询语句发送到服务器去执行， 5 按照执行情况计算代价，得到所有的等价查询方式中最小代价的查询方式；将 这个等价查询方式反馈给应用程序和数据库系统，达到优化应用系统查询的目标。 本章设计外挂的查询优化器，模拟上述优化的过程，使这个优化器能达到如下的 目标： 1 应用程序无需关心数据库服务器的优化逻辑；数据库服务器优化器完全按照 现有的方式优化接收到的查询； 2 数据库服务器收到的总是可以得到最优化效果的查询请求，应用程序发送的 总是可以得到最优化效果的查询请求； 3 对于这样的一个优化器来说，可以适应多种数据库的结构，优化的场景是统 一的； 4 这个工具为编写查询提供优化的建议。 3 2 优化器的架构和实现原理 输 夕 等价的q 1 p l a n lc o s t l 等价的q 2 10 0 0 0 。 其对应的代数表达：万。呷l 删枷p ，( e m p l o y e e s qs a l l a r y ) ) 。 其中f = c r e a t e d a t e 2 0 0 6 - 0 9 - 0 1 as a l 1 0 0 0 0 。关系代数树图表5 左图。 工如 2 0 0 争- 0 9 - 0 1 a n d s a i l a r y s 3 1 = ：1 0 0 0 0 q e m p l l o y e e s j a s q ) l i d - - s a i l a r y e i _ n p l i d e m p l 0 3 e e ss a l l a r x 兀。广 6 e m p l 0 3 f e e s e m p l i d - s a i l a r y e m p 1 i d l 6 么 二露三f 幽4 1 查询的关系数l查询的关系树2 对该查询表达式进行等价转换，转换后的语句是： 例4 2s e l e c ta e m p l o y e e n a m ef r o m ( s e l e c t 奎f r o me m p l o y e e sw h e r e c r e a t e d a t e 2 0 0 6 0 9 0 1 ) a sa , ( s e l e c t f r o ms a l l a r yw h e r es a l 10 0 0 0 ) a sb 2 0 第四章关系代数等价转换的算法实现 w h e r e a e m p l i d = b e m p l i d 。 对应的关系是：石唧蝴( 仃，l ( e m p l o y e e s p q 盯，2 ( s a l l a r y ) ) 。 其中f i = c r e a t e d a t e = 2 0 0 6 0 9 0 1 f 2 = s a l 1 0 0 0 0 。 查询计划树由一棵扩充的关系代数树构成。查询计划树是在关系代数树上的每个 结点上注明对关系的访问方法或者关系操作的执行方法。因此用关系代数的等价转化 构造的等价查询查询计划的可能不一样，因而成本也不一样。所以本章按照关系代数 等价转换的原则，对原始查询的所有关系代数的等价转换形式一一构造，扩大可能含 有最优等价查询语句的空间。 4 1 1 等价转换的查询计划迁移 表4 1 是只对查询语句进行一次关系等价转换的查询计划迁移的统计表。表的第 一列是查询语句中关系的数量。( 环境s q l s e r v e r2 0 0 0 ) 表4 1 一次关系等价转换的查询计划迁移情况表 选择和并的交换投影和并的交换选择和投影的交换选择的串联 4 是是 否 是 5 是是否是 6 是是是是 表4 1 续 投影的串联联接和笛卡儿积的交换和结合投影和笛卡儿积的交换 4否 是 否