（计算机应用技术专业论文）基于聚合函数的物化视图关键技术的研究.pdf

硕上论文基于聚合函数的物化丰见图关键技术的研究 摘要 在数据库应用系统中，加快数据查询的执行速度非常重要。主要的方法有两 种，一种方法是对s q l 查询语句进行优化，另一种方法则是采用物化视图技术。 物化视图存储了视图的定义和预查询结果，通过将用户针对数据库基本关系表提 出的查询转化为对物化视图的查询，避免了直接访问大量的原始记录以及耗时的 计算，从而大幅减少了查询执行阶段所需的数据量和计算量，节省了查询的响应 时间，最终有效地改善了系统的性能。 本文首先阐述了物化视图在数据库应用中的重要意义，综述了当前国外主流 商业数据库在物化视图研究领域的发展历程及研究现状。随后，本文重点研究了 物化视图的选择和查询重写技术。对于一个给定的s q l 查询语句，数据库系统 首先需要决定的是哪些物化视图可以被该查询所利用，这个问题即为物化视图的 选择问题。物化视图的选择主要分为候选物化视图筛选、物化视图代价估计和最 优物化视图配置搜索三个阶段，本文将基于物化视图选择的总体框架对上述三个 阶段的具体实现及相关算法进行详细的研究和讨论。 在物化视图选择给出了可供系统利用的物化视图集合后，系统还需要决定如 何利用这些物化视图对s q l 查询语句进行重写，并在可能存在有多种查询重写 策略的情况下尽量从中选择出最好的一种方案，以便最大限度地提高查询重写后 的执行性能。为此，本文后半部分着重研究了基于连接物化视图和聚合物化视图 的聚合查询重写算法，并提出了基于搜索二叉树的最优重写选择方法。 在系统的详细设计上，我们对o s c a r 数据库现有的体系框架进行了扩充和 修改，主要添加了物化视图选择模块和查询重写索引管理器，同时对保存了物化 视图元数据的数据字典进行维护。查询重写索引管理器作为一个辅助模块，其作 用在于将系统中的有效物化视图组织起来构造成为一棵多路搜索二叉树，以便于 物化视图查询重写搜索算法的实现。 最后，本文以神舟o s c a r 数据库为平台，给出了上述关键技术的实现，并 进行了性能优化的实验测试。通过实验验证了本文各关键技术实现方法的有效性 和高效性，在减少d b a 工作量的同时自动优化数据库系统的性能。 关键字：物化视图选择，聚合查询重写，o s c a r 数据库，性能优化 a b s t r a c t i ti sv e r yi m p o r t a n tt oq u i c k l ya n s w e rq u e r i e si nd a t a b a s ea p p l i c a t i o ns y s t e m b e s i d e ss q lq u e r yo p t i m i z a t i o n ，a n o t h e re f f i c i e n tw a y i st ou s em a t e r i a l i z e d e w 8 t h ed e f l n i t i o n sa n dp r e q u e r yr e s u l t so fm a t e r i a l i z e dv i e w s a r eb o t hs t o r e dm d a t a b a s e w h e nu s e r sg i v et h e i rq u e r i e sa g a i n s tb a s e t a b l e s ，t h ed a t a b a s ew i l l t r a n s p a r e n t l yr e w r i t et h e s eq u e r i e sb yu s i n gm a t e r i a l i z e dv i e w s ，w h i c hc a n n o to n l y a v o i da c c e s s i n gt h eh u g er a wr e c o r d sd i r e c t l ya n dp e r f o r m i n gt i m e c o n s u m i n g c o m p u t i n g b u ta l s oc a ns a v et h er e s p o n s et i m ea n di m p r o v eq u e r yp e r f o r m a n c e f i n a l l y i nt h i sp a p e r , t h es i g n i f i c a n c eo fm a t e r i a l i z e dv i e w st e c h n o l o g yf o rt h ed a t a b a s e a p p l i c a t i o n ，w i t ht h ed e v e l o p m e n th i s t o r ya n d t h ep r e s e n ts i t u a t i o no fm a t e r i a l i z e d v i e w sf o rt h ef - 锄o u sc o m m e r c i a ld a t a b a s e sa b r o a d ，i sd e s c r i b e df i r s t t h e n ，w e m a i n l yd i s c u s st h es e l e c t i o na n dq u e r yr e w r i t i n gt e c h n o l o g y o fm a t e r i a l i z e dv i e w s f o rag i v e ns q lq u e r ys t a t e m e n t ，t h ef i r s tt h i n gd a t a b a s es y s t e mn e e d st od oi s t o d e c i d et h em a t e r i a l i z e dv i e w st h a tc o u l db eu s e d g e n e r a l l y , m a t e r i a l i z e dv i e w s s e l e c t i o ni sc o n s t i t u t e db yc a n d i d a t ev i e w sf i l t e r , c o s te s t i m a t i o n a n do p t i m a l c o n f i g u r es e a r c h s ow ew i l lp a r t i c u l a r l yf o c u s o nt h ei m p l e m e n to ft h e s et h r e es t e p s ， i n c l u d i n gt h ed e t a i l e dr u l e sd e s c r i p t i o na n da l g o r i t h m s ，w h i c hi sb a s e do n t h ee n t i r e f r 舭l eo fm a t e r i a l i z e dv i e w ss e l e c t i o nw ed e s i g nf i r s t a f t e rt h em a t e r i a l i z e dv i e w ss e l e c t i o n ，t h ep r o b l e m st h a th o w t h es y s t e mu s e s t h es e l e c t e dm a t e r i a l i z e dv i e w st or e w r i t et 1 1 et h es q lq u e r y a n ds e l e c t st h eo p t i m a l o n ef 两mn 啪e r o u sr e w r i t i n gs t r a t e g i e sf o r t h ef i n a lp e r f o r m a n c eo p t i m i z a t i o nh a v e b e e ni n v e s t i g a t e d s oi nt h ef o l l o w i n gp a r to f t h i sp a p e r , t h er e w r i t i n ga l g o r i t h m sf o r a g g r e g a t i o nq u e r i e sb a s e do nc o n j u n c t i v ev i e w sa n da g g r e g a t i o nv 1 e w s h a v eb e e n d i s c u s s e d ，a n dt h e nt h eo p t i m a lr e w r i t i n gp l a ns e l e c t i o nm e t h o db a s e d o nt h eb i n a r y s e a r c ht r e ei sp r o p o s e d w i t hr e g a r dt ot h ed e t a i l e dd e s i g n , t h ee x i s t i n gf r a m e w o r ko fo s c a r d a t a b a s e i se x t e n d e db ya d d i n gt h em a t e r i a l i z e dv i e w ss e l e c t i o nm o d u l ea n dq u e r yr e w r i t i n g i n d e xm a i l a g e r ，a n di sm o d i f i e db ym a i n t a i n i n gt h em e t a d a t ao fm a t e r i a l i z e dv i e w s i i ld a ：t ad i c t i o n a r y a sa na s s i s t a n tm o d u l e ，t h eq u e r yr e w r i t i n gi n d e xm a n a g e r l sm c h a r g eo fc o n s t r u c t i n ga n dm a i n t a i n i n gam u l t i p a s st r e ew h i c hc a ni n d e xa l l t h e a 、，a i l a b l em a t e r i a l i z e dv i e w sf o rt h e c o n v e n i e n c eo ft h er e a l i z a t i o no fq u e r y r e w r i t i n gs e l e c t i o nm e t h o d i i 硕二i 二论文基于聚合函数的物化视图关键技术的研究 f i n a l l y , w i t hs h e n z h o uo s c a r d a t a b a s ea st h ep l a t f o r m ，w ei m p l e m e n tt h ea b o v e k e yt e c h n o l o g i e sa n dp r o v i d ee x p e r i m e n t sf o rp e r f o r m a n c eo p t i m i z a t i o nt e s t t h e r e l e v a n tr e s u l t sd e m o n s t r a t et h ev a l i d i t y t e c h n i q u e s ，w h i c hc a i l r e d u c et h ew o r k p e r f o r m a n c ea u t o m a t i c a l l y a n dh i g he f f e c t i v e n e s so ft h ep r o p o s e d l o a do fd b aa n do p t i m i z et h es y s t e m k e yw o r d s ：m m e r i a l i z e dv i e w ss e l e c t i o n ；a g g r e g a t i o nq u e r yr e w r i t i n g ；o s c a r d a t a b a s e ；p e r f o r m a n c eo p t i m i z a t i o n i i i 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他入已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：c 沏汐年乡月以日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文 按保密的有关规定和程序处理。 研究生签名：幽0 年6 月淑日 硕士论文 基于聚合函数的物化视图关键技术的研究 1 绪论 1 1 引言 经过近半个世纪的发展，数据库技术已经成为现代信息科学与技术的重要 组成部分，数据库管理系统( d a t a b a s em a n a g e m e n ts y s t e m ，d b m s ) 也已经成为 计算机信息系统和应用系统的基础和核心。 目前，人们对数据库的要求，已不仅仅局限于简单的数据查询、数据统计， 而是需要对原始数据进行深层次的加工、分析和挖掘，从而进一步支持决策分 析。在数据仓库和联机分析处理等决策支持系统中，则需要在数据库之上进行 海量数据的多表连接和分组聚合等的复杂查询。因此，如何有效地降低复杂查 询的执行代价，减少用户查询的响应时间，成为了目前面临的重要问题之一。 物化视图技术【l 】是解决该问题的关键技术之一，物化视图通过预先计算，大大 减少计算量和数据量，从而快速地响应复杂查询。 物化视图是对某些包含连接、聚合等复杂查询结果的实体化，预先计算并 保存比较耗时操作的结剁2 1 。当复杂查询可以从物化视图中得到全部或者部分 数据时，从物化视图中直接获得计算结果或者通过进一步计算而得到相应的结 果，同时不需要去访问大量的基表数据【3 】；在减小查询执行计算量的同时可能 减少访问的数据量，从而节省查询的响应时间。使用物化视图的目的是提高数 据库的查询性能，增加或者删除物化视图并不会影响查询结果的正确性和有效 性 4 1 。 神舟o s c a r 数据库【5 】是拥有完全自主知识产权的企业级大型、通用对象 关系型数据库管理系统；是北京神舟航天软件技术有限公司集多年的数据库研 发经验，在国家8 6 3 数据库重大专项、发改委安全数据库专项、国家“核高基 数据库专项等项目的支持下研发的。神舟o s c a r 数据库系统已广泛应用于各 类企事业单位、政府机关，尤其是国防、航天、航空等涉及国家安全的领域。 神舟o s c a r 数据库系统的成功研制和应用，一方面将彻底解决由于广泛应用 国外数据库产品可能带来的信息安全问题，另一方面也将在基础软件领域极大 地推动我国民族软件产业的发展。 1 绪论硕士论文 1 2 本文研究内容 在数据库中，传统意义上的视图只保存了视图定义，而没有保存视图的查 询结果，仅仅只是在需要时才通过视图定义计算出真实结果。对于复杂视图， 实时进行视图计算需要耗费很大的时间代价。物化视图则是在物理上保存了真 实数据，当用户查询时，可从物化视图中或者仅需要经过简单的计算得到查询 结果，从而大大提升复杂查询的执行效率。其中主要涉及以下三个问题【6 l ： 物化视图选择：根据数据库系统的限制要求，选择出最能提升数据库性 能的一个有效物化视图集合。 物化视图查询重写：基于物化视图选择阶段得到的有效物化视图集合， 透明地将用户查询重写为等价但效率更高的查询，从而自动提升查询 执行的效率。 物化视图维护：基表数据发生变化时，利用维护策略保持物化视图数据 与基表数据的一致性。 本课题着重围绕查询优化器研究物化视图的选择和查询重写。查询优化器 【7 1 是数据库管理系统中查询处理的重要部分，主要是对查询语句进行优化，选 择效率最高的执行计划。查询优化主要分为规则优化和代价优化【8 】。规则优化 主要是利用预先定义的规则集作为主要决策依据。代价优化则产生可供选择的 执行计划，通过估计各个计划的运行代价，进而选择代价可能最低的执行计划。 查询优化器对于数据库系统的性能，特别是对于复杂查询的执行性能至关重要。 本课题主要是利用查询优化器的某些特性提出解决方案，并对查询优化器进行 改进。 因为物化视图本身的物理存储需要占用一定的空间代价，并且物化视图的 致性维护也需要耗费相应的c p u 代价，所以在系统空间代价和维护代价等系 统资源的限制下，如何根据已知负载( 即查询语句集合) 选择一组合适的视图 进行物化操作，以求最大限度提高数据库系统对负载的响应速度，成为了物化 视图选择需要解决的主要问题 9 1 。而物化视图的查询重写则主要是解决物化视 图如何利用的问题，通过对物化视图能否用于重写用户查询进行判断，符合重 写要求的查询将被查询优化器改写为与原查询结果相同但执行效率更优的等价 2 硕十论文基于聚合函数的物化视图关键技术的研究 查询【1 0 1 。 本文后续章节主要对物化视图选择和物化视图查询重写这两个问题进行了 研究，首先通过查阅国内外相关科技文献，综合比较文献中对上述两个问题的 研究思路和解决方案；然后分析现有方法的优势和不足；最后结合o s c a r 数 据库的特点提出相应的解决方法，并在o s c a r 数据库系统上实现和验证。 1 3 国内外研究现状 目前，各大商业数据库均已经支持物化视图功能，o r a c l e 是最早提供物化 视图功能的商业数据库1 0 】，s q ls e r v e r 的索引视 ( i n d e x e d v i e w s ) s 1d b 2 的物 化查询表( m a t e r i a l i z e dq u e r yt a b l e s ) 也都采用了物化视图的思想。目前，物化视 图技术的应用非常广泛，o r a c l e 中的高级复制同样用到了物化视图技术。物化 视图同样也是数据仓库、数据集成的主要技术之一。在学术界，物化视图仍 然是数据库研究的热点问题之一。本文着重研究了物化视图选择和查询重写， 以下分别介绍了物化视图选择和查询重写的研究现状。 1 3 1 物化视图选择 物化视图选择是物理数据库设计的子问题之一，物化视图选择的研究基本 上是在索引选择的基础之上完成的，在s q ls e r v e r 和d b 2 中，物化视图选择 功能均是在其早期的索引推荐工具中加入了物化视图的选择功能。 s q ls e r v e r 中早期的索引选择工具【1 2 1 的整体架构由候选配置选择、配置枚 举、配置代价估计和配置选择四个模块组成；之后又提出了利用“w h a t i f ”思 想【1 3 】来精确评估一个给定索引配置的代价，并描述了虚拟配置分析引擎及相应 接口的实现。后来，a g r a w a l 等人【1 4 】贝0 在已有成果的基础上，继续研究了如何 在不改动总体架构的前提下将物化视图选择功能融入索引选择工具中，从而最 终实现了s q ls e r v e r2 0 0 0 中能够同时进行索引和物化视图选择的工具t u n i n g w i z a r d 。 d b 2 中早期的索引推荐工具d b 2a d v i s o r t l 5 】贝0 是通过改进查询优化器，由 优化器选择候选索引并计算每个索引的代价和增益，并利用贪心算法得到近似 最优的索引集合。z i l i o 等人在此基础上研究了同时进行索引和物化视图选择 3 i 绪论硕士论文 的算法，其中采用了多查询优化技术来实现候选物化视图集合的选择，从而减 小了对查询优化器的频繁调用。 在上述基础之上，b r u n o 等人【1 刀提出了基于松弛方法的自动物理设计调优， 其中，对候选配置选择算法和配置搜索算法进行了修改，使其更具有客观性。 b r u n o 等人研究了一种物理配置改进的算法，不需要重新进行物理数据库设计， 而是仅对当前配置进行“分裂和“合并”等转换操作就能得到满足新的限制 条件的配置。 近年来，使用进化算法进行最优物化视图配置搜索也受到了大量关注。 z h a n g 等人提出了在数据仓库系统中利用进化计算技术自动选择物化视图； 在此基础上y u 等人例研究了基于限制的进化计算算法来解决o l a p 中的物化视 图自动选择问题。 1 3 2 物化视图查询重写 物化视图技术的主要目的是利用物化视图对查询进行重写，避免直接访问 大量的基表数据，从而提高查询的执行效率。查询重写主要涉及的问题是判断 物化视图是否能够重写查询，即物化视图匹配；其次是利用物化视图构造替换 查询，即查询替换。 l a r s o n 等人【1 9 】、c h a u d h u r 等人【2 0 】早期就开始研究连接物化视图和查询的匹 配算法，但其是基于集合语义的，显然已经不适宜于s q l 查询语言和关系代数， 并且没有考虑连接谓词的包含从而重写效率都比较低。 s r i v a s t a v a 等人【2 1 1 研究了包语义下聚合物化视图和查询匹配和重写算法， 其中涉及了查询谓词的相互包含，但没有具体的谓词包含判断的算法，也没有 考虑多个物化视图对于查询的重写和多种物化视图重写的选择。 z a h a r i o u d a k i s 等人【2 2 】描述了i b md b 2u d b 中物化视图和查询的匹配算 法，一种至底向上对查询图形( q u e r yg r a p hm o d e l ) 进行匹配的算法，但并不要 求严格匹配，考虑了谓词包含判断( 也没有具体算法) ，但并没有重写查询的具 体算法，也没有考虑多个物化视图对于查询的重写和多种候选重写的选择问题。 g o l d s t e i n 等人【6 1 描述了s q ls e r v e r2 0 0 0 中的查询重写的解决方法，其中考 虑了物化视图和查询谓词的派生关系，并将谓词进行了分类，提出了等价类( 相 4 硕士论文基于聚合函数的物化视图关键技术的研究 等列的集合) 的概念，给出了查询重写应该满足的一些条件和方法。在该文献基 础之上，l a r s o n 等【2 3 】针对外连接的特征提出了将外连接转化为连接析取范式后 再进行匹配的算法，该算法能够实现外连接物化视图和查询的完全语义匹配。 数据集成环境下的物化视图查询重写研究也比较广泛【2 4 】，但因为其是对查 询的最大包含重写，所以在数据库系统中并不是完全可行。 1 4 论文组织 物化视图功能设计 l 第四章o s c a r 物化视图功能实现 弋夕 第五章实验验证 弋夕 i第六章总结与展望 图1 4 1 论文组织结构 本文共分六章，如图1 4 1 所示。论文内容如下： 第一章是绪论，简单描述了课题的研究背景和意义；介绍了本文研究的主 要内容；其次对相关研究进行综述，并着重介绍了本文所研究技术的研究现状。 第二章主要研究了物化视图的有效选择技术。其中首先提出了物化视图选 择的总体框架，并分析了框架中各模块的主要功能和关键点；然后详细介绍了 各模块的设计框架和具体实现。 第三章主要研究如何基于选择出的有效物化视图实现对聚合查询的重写。 首先对物化视图进行了分类；其次针对不同类型物化视图的聚合查询重写问题 5 1 绪论硕士论文 进行了研究，给出了相关的匹配条件和实现算法；最后，通过采用近似最优的 重写搜索算法，来最终实现了有效重写方案的选择。 第四章是对o s c a r 物化视图功能实现的总体设计。首先介绍了自管理环 境下o s c a r 数据库的查询处理整体流程，然后通过扩展查询处理引擎把本文 第二章和第三章所述的物化视图功能融入了当前的查询处理流程中，并在最后 的系统实现部分给出了基于o s c a r 数据库平台的物化视图详细设计方案。 第五章主要是本文所研究技术的具体实验验证。首先描述了物化视图功能 的具体实现；其次通过实验验证了物化视图选择和重写功能，进而证明了本文 研究内容的有效性。 第六章对全文进行了总结和展望。 6 硕士论文基于聚合函数的物化视图关键技术的研究 2 物化视图的有效选择 物化视图技术是数据库系统中的一个关键性技术，它是一种将视图所对应 的数据进行实际物理存储的技术，其目的是通过预计算来加快数据库系统对用 户查询的响应速度。然而，视图的物化不仅需要占用可观的磁盘空间，还需要 耗费大量的系统资源来对其进行维护【2 5 1 。此外，不同的物化视图对数据库查询 性能的影响也是截然不同的f 2 6 1 ，有效的物化视图可用于重写负载中的大多数查 询，快速提高数据库系统的查询性能；而无效的物化视图不仅对大多数乃至于 所有的查询而言都是不可利用的，甚至还会成为系统查询性能提升的阻碍【2 7 1 。 因此，任何数据库系统都不可能对系统中的所有视图进行物化【2 引，而仅仅只能 从数据库系统的庞大视图集合中选择出一个合适的视图子集来加以物化，以求 使系统能够充分利用有限的资源、最大限度的提高数据库系统对用户查询的响 应速度。综上所述，本章着重研究了有效物化视图的自动选择，首先给出了物 化视图有效选择的总体架构；然后分别研究了其中的三个关键问题，并针对不 同问题给出了对应的解决方案。 2 1 物化视图选择总体框架 本文所提出的物化视图自动选择总体框架如图2 1 1 所示，主要由候选物化 视图选择、最优配置搜索和代价估计三部分组成。其中，候选物化视图选择具 体分为了有效表集筛选、物化视图裁减和物化视图合并三个阶段。 负载计划收集模块收集数据库系统的工作负载，并同时收集其他模块可能 用到的环境信息；语义结构选择模块则根据收集到的环境信息为负载选择合适 的语义结构，该语义结构将成为分析和建立整个候选物化视图集合的基础。作 为优化器实现必需的基础模块，负载计划收集模块和语义结构选择模块两者的 设计与实现在各种数据库优化器中都已非常成熟，所以本文将不再对它们进行 详细描述。 候选物化视图选择主要对工作负载的语义结构进行分析，利用各种规则和 算法生成那些提高查询性能的各种物化视图集合，进而生成用于搜索最优物化 7 2 物化视图的有效选择 硕j 二论文 视图的候选配置空间。最优配置搜索主要从候选配置空间中根据一定的算法搜 索物化视图配置，最终得到最优的物化视图配置结果并交付给查询重写模块进 行后续处理。此外，代价估计作为一个独立的公共支持模块，通过调用系统统 计信息评估各种物化视图的代价，向上为候选物化视图选择和最优配置搜索提 供支持。 候选物化视图选择和最优配置搜索是上述框架的核心模块，它们直接影响 着物化视图选择的最终效果。候选物化视图选择的任务是生成那些能够降低负 载代价的物化视图( 包括基本物化视图和合并视图) ，并通过物化视图合并尽可 能避免各种语法相关且作用相近的冗余物化视图存在，其中的关键在于对各种 物化视图选择算法和合并算法的设计，算法的合理性将是影响最终系统生成的 物化视图效率的主要因素。而最优配置搜索中对候选配置空间搜索算法的设计， 则是影响系统所选物化视图效率的另一个主要因素。 图2 1 1 物化视图选择总体框架图 综上所述，本文所研究的物化视图有效选择主要涉及以下关键问题： 1 ) 候选物化视图选择：候选物化视图选择是整个物化视图选择的核心任务 之一。在本文解决方法中，将具体分为三个阶段详细实现：在有效表集筛选阶 8 硕士论文基于聚合函数的物化视图关键技术的研究 段，我们将给出两个评估公式来对一个表集合的物化视图在系统负载性能中影 响的重要性进行评估，这两个公式的同时应用确保了最终筛选得到的表集的有 效性；在物化视图裁减阶段，基于有效表集的视图裁减确定出了有效表集上那 些真正能够降低系统负载执行代价的物化视图；最后，在物化视图合并阶段， 通过循环迭代双视图合并的方法，最终进一步生成得到了那些能够同时作为多 个查询解决方案的合并视图。 2 ) 物化视图配置代价估计：对配置代价进行估计将采用虚拟配置分析引擎 来实现。因为实际应用中的很多查询语句都是非常复杂并且运行耗时很长的， 所以如果是对物化视图的真实配置进行分析很可能会导致物化视图的自动生成 过程过于迟缓，最终影响查询的整体性能，也使得物化视图丧失了查询优化的 意义。虚拟配置分析引擎仅仅只是利用查询的物理特征信息来模拟相应物化视 图的真实执行环境，从而能够实现对物化视图的快速生成和选择。 3 ) 最优配置搜索：在候选物化视图空间中枚举所有可能的物化视图配置是 不符合现实情况的，其实现代价也是任何系统都无法承受的。为此，我们将采 用遗传算法来避免枚举情况的出现，从而最终有效解决最优配置的生成问题。 2 2 候选物化视图选择 理论上，物化视图能够建立在查询语句所涉及的所有查询表的任意一个表 子集上。对于某个表子集，如果查询语句包含了大量涉及该子集的选择条件和 分组条件，则会导致该子集上语法相关的物化视图数量剧增。比如，假设查询 语句中涉及表子集t 的选择条件有m 个，那么建立在表子集t 上且包含了任意 k ( 1 k m ) 个选择条件的物化视图都是语法相关的。综上可知，在系统实际 运行中，绝大多数s q l 查询语句所对应的语法相关的物化视图空间往往都非常 庞大，而由大量查询语句所构成的系统负载的情况则更是如此。因此，对于一 个系统已经给定的负载，如果在配置枚举阶段才列举和判断该负载所有语法相 关的物化视图显然是不可行的，因为庞大的物化视图空间对应着庞大的配置枚 举搜索空间，从而将导致系统根本无法在特定时间内搜索出合适的物化视图。 如图2 2 1 所示，候选物化视图选择的目的，就是在最优配置搜索之前清除那些 9 2 物化视图的有效选择 硕上论文 虽然语法相关但是却不可能被系统在后期选中的物化视图，从而在尽可能多的 包含有效物化视图的同时，缩小配置枚举搜索空间，为最终有效物化视图的最 优配置搜索奠定基础。 图2 2 1 候选物化视图选择阶段的作用 不难发现，为系统负载中的每一条s q l 查询语句都选择一个与之精确匹配 的物化视图是不可行的。因为在很多数据库系统中，物化视图语法本身就不是 和s q l 查询语句的语法一一对应的。比如，s q l 查询语句中经常出现的嵌套 子查询就无法在物化视图定义的语法中找到与之对应的部分。此外，在存储空 间受到约束条件限制的情况下，忽略负载中各种s q l 查询语句的共性将导致系 统丧失大幅提升性能的优势，并且这种情况在系统负载量很大时尤为突出，举 例如下： 例2 2 1 ：给定t p c h 基准测试中一个由1 0 0 0 条s q l 查询语句组成的系 统负载，每条s q l 查询语句的具体格式为： s e l e c t l r e t u r n f l a g ，l _ l i n e s t a t u s ，s u m ( 1 _ q u a n t i t y ) l n 硕十论文 基于聚合函数的物化视图关键技术的研究 f r o ml i n e i t e m w h e r e l _ s h i p d a t e b e t w e e n a n d g r o u p b y l _ r e t u m f l a g ，l _ _ l i n e s t a t u s ； 上述1 0 0 0 条查询语句中，每条语句的参数 和 的取值均为 不同的常量。在这种情况下，如果为这1 0 0 0 条查询语句均分别生成与之匹配的 物化视图，那系统负载的整体性能必然大打折扣。因为根据这1 0 0 0 条语句的共 性，系统只需要生成如下所示的一个物化视图就可以同时为这1 0 0 0 条查询语句 提供服务了。 s e l e c t l _ s h i p d a t e ，l r e t t t m f l a g ，l _ l i n e s t a t u s ，s u m ( 1 _ q u a n t i t y ) f r o ml i n e i t e m g r o u pb y l _ s h i p d a t e ，l r e t u m f l a g ，l _ l i n e s t a t u s ； 除了确定那些包含了各种查询语句共性的物化视图之外，候选物化视图选 择阶段还需要考虑去除大量在系统负载性能优化方面影响不大的物化视图。因 为对于那些在负载中很少涉及的表集、以及那些在执行代价很小的查询语句中 出现的表集而言，建立在这些表集上的所有物化视图均不会对系统负载的性能 产生明显的影响，所以这些物化视图的存在是完全没有必要的。比如，给定一 个包含了1 0 0 条查询语句的负载，假设系统运行该负载的总代价为1 0 0 0 0 ，同 时假设涉及表集t 的查询语句为2 5 条，而这2 5 条语句的执行总代价为5 0 。在 这种情况下，哪怕系统提供了表集t 上所有可能的物化视图，整个负载性能的 最大收益也不过是节省了系统原有负载总代价的0 5 而已。 值得注意的是，有时还会存在一些表子集，这些表子集在负载中出现的频 率很高，或者总是出现在一些执行代价昂贵的查询语句中，但是建立在这些表 子集上的物化视图却仍然对系统负载的性能不会产生太大影响，举例如下： 例2 2 2 ：给定t p c h 基准测试中一个1 g 的数据库以及相应的系统负载， 在负载中关系表l i n e i t e m 、o r d e r s 、n a t i o n 、r e g i o n 总是同时出现。然而在该负载 上，建立在表子集 l i n e i t e m ，o r d e r s a 2 的物化视图明显要比表子集 n a t i o n ，r e g i o n ) 上的物化视图有效。这是因为关系表l i n e i t e m 和o r d e r s 分别含有6 0 0 万行和1 5 0 万行数据，而关系表n a t i o n 和r e g i o n 却非常小，仅仅只包含了2 5 行和5 行的 2 物化视图的有效选择硕士论文 数据纪录。因此，和表子集 l i n e i t e m ，o r d e r s 相比，对负载中的查询语句预先 建立 n a t i o n ，r e g i o n ) 上的物化视图显然是无关紧要的。 综上所述，下面我们将分三个阶段来实现候选物化视图的选择： 1 ) 对系统负载中出现的所有表集进行筛选，从中得到一个有效表集的集 合。 2 ) 在有效表集上为负载中的每个查询建立相应的物化视图集合，并采用 基于代价的方法对当前查询对应的物化视图集合进行分析，选择出一个对当前 查询来说最优的配置。 3 ) 对负载中每个查询的最优配置物化视图进行合并，使合并后的物化视 图能够同时为负载中的多个查询服务，而所有合并结果的集合就是我们最终得 到的候选物化视图集合。 2 2 1 有效表集筛选 有效表集筛选的目的是从负载查询中所有可能的表集合里筛选出那些在应 用物化视图后能够使系统获得最大性能收益的表集合。直观上来看，如果一个 表集合上建立的物化视图对负载执行代价的减幅越大，那么这个表集合也就越 有效。因此，首先我们需要给出一个公式来评估一个表集合上的物化视图对系 统负载性能影响的重要性。 考虑一个给定的表集合t ，假设负载中与表集合t 相关的所有查询q i ( i = l ， 2 ，n ) 的执行代价为c o s t ( q i ) ，则根据概率统计的方差思想，最直观的公 式应该是： t s _ c o s t ( t ) = 砉c o s t ( q , ) 】2 亿2 ， 但是，公式( 2 2 1 1 ) 虽然简单，却不是一个好的评估标准。如例2 2 2 所示， 如果负载中的所有查询都涉及了四个表l i n e i t e m 、o r d e r s 、n a t i o n 和r e g i o n ，那 么尽管建立在表子集t l = l i n e i t e m ，o r d e r s 上的物化视图明显要比建立在表子集 t 2 = n a t i o n ，r e g i o n 上的物化视图有用，但是按照公式( 2 2 1 1 ) ，t 1 和t 2 的重要 性却是相同的。 基于上述理由，假设s u m ( t ) 为表集合t 中所有关系表的数据规模大小之 1 2 硕士论文基于聚合函数的物化丰见图关键技术的研究 和，s u m ( q i ) 为查询q i 所涉及的所有关系表的数据规模大小之和，我们给出了 如下公式来更好地评估一个表集合上的物化视图对系统负载性能影响的重要 性： t sw e i g h t ( t ) = 萋c o s 媳) 丽s u m ( t ) ( 2 2 1 2 ) t 2 1 当所有表集合都同时在相同查询中出现的情况下，公式( 2 2 1 2 ) 能够很好地 判断出各种表集合的相对重要性。但是尽管如此，对于任何一个给定的参数值 c ，我们也很难设计出一个有效算法来查找出所有t s _ w e i g h t 值大于c 的表集 合。需要注意的是，对于公式( 2 2 1 1 ) 而言，t s c o s t 的取值是单调性的，也就 是说，给定表集t l 和t 2 ，如果t 12 t 2 ，则t s _ c o s t ( t l 砭t s _ c o s t ( t 2 ) 。这是因 为所有涉及了t 2 的查询，必然都涉及t l ，反之却不一定成立。此外，对于任 何一个给定的参数值c ，只要t s w e i g h t ( t ) _ c ，则必有t s _ c o s t ( t ) _ c 。结合 上述性质，下面我们给出了算法2 2 1 1 来对负载中的各种表集进行有效筛选。 算法2 2 1 1 ：对负载中出现的各种表集进行有效筛选。 输入：系统参数c ，当前负载中的所有表集t 。 输出：筛选得到的有效表集的集合r 。 t a b l e f i l t e r ( t ，c ) s l = tt s _ c o s t ( t ) _ c & & s i z e ( t ) = = 1 ) ； i = l ； w h i l e ( i o ) i + + ；s i = ； g = tls i z e ( t ) = = i & & 3 s s i 一1 爿s c t ) ； f o re a c ht g i f ( t s _ c o s t ( t ) c ) s i = s iu ( t ； 1 3 2 物化视图的有效选择硕上论文 s2s 1us zu us m a x 3 m , e ； 1 1 = ( tlt s & t s l $ r e i f l h t ( t ) 2q ； r e t u r nr ： ) 在算法2 2 1 1 中，函数s i z e ( t ) 表示获取表集合t 所包含的关系表的个数； m a xt a b l e 表示构成负载的所有查询中涉及到的关系表数目的最大值：参数 c 为系统预先设定的参数，c 的取值越小，则最终获取的集合r 中表集的数目 越多，一般情况下，c 的取值设置为系统负载的1 0 可以达到较好的效果。 2 2 2 物化视图裁减 2 2 1 节的有效表集筛选大幅减少了整个负载需要考虑的语法相关的物化 视图数量。但是尽管如此，对于所有筛选得到的有效表集而言，也并不是建立 在其上的所有语法相关的物化视图都是有用的，因为判断一个物化视图是否有 效只有通过优化器进行代价估计才能最终确定。因此，物化视图裁减的目的是 将那些语法相关但是却不能降低系统负载执行代价的物化视图清除，避免它们 在配置枚举阶段的出现导致配置枚举搜索空间过于庞大。通过分析参考文献【2 9 】 中搜索候选索引的算法，我们总结出一个事实，即：“如果一个物化视图无法成 为负载中某一条查询最佳解决方案的一部分，那么这个物化视图必然也不可能 成为整个负载最佳解决方案的一部分。 基于上述事实，我们采用基于代价估计 的模型，根据以下步骤来对有效表集上的整个语法相关的物化视图空间进行裁 减。 步骤1 ：设置存储物化视图的变量m ，m 中保存的每一个物化视图至少都 是负载w 中某一个查询最佳解决方案的一部分； 步骤2 ：设置变量i ，i 依次取值从1 到n ，1 3 为负载w 中所包含的查询数 目； 步骤3 ：设置变量s i ，s i 对应保存建立在负载w 中查询q i 上的合适的物化 视图； 步骤4 ：调用函数f i n d _ b e s t _ c o n f i g u r a t i o n ( q i ，s i ) ，函数返回结果保存在 m 中； 1 4 硕- ：论文基于聚合函数的物化视图关键技术的研究 步骤5 ：如果变量i 小于n ，返回步骤2 ；如果i 等于n ，返回m 中的所有 物化视图，裁减过程结束。 在上述裁减步骤中，对于一个给定的查询q ，以及在q 上建立的物化视图 集合s ，步骤4 通过调用函数f i n d _ _ b e s t c o n f i g u r a t i o n ( q ，s ) 来返回s 中最优 的物化视图配置。因此，函数f i n db e s t c o n f i g u r a t i o n ( o ，s ) 必须采用代价估 计的方法才能获取到s 中被优化器估价最低的配置。在函数 f i n d _ b e s tc o n f i g u r a t i o n ( q ，s ) 的具体实现上，我们可以采用各种经典的搜索算 法，比如贪心算法或者