（计算机应用技术专业论文）分布式数据库查询优化机制研究.pdf

分布式数据库查询优化机制研究 石小艳( 计算机应用技术) 指导教师：张丈东( 高级工程师) 摘要 在分稚式数据库系统中，由于数据的分御和冗余，增加了分布式查 询处理的难度和复杂度，因此如何进行查询优化是分布式数据库系统的 一个重要问题。 通过分析现有分布式数据库查询处理技术，提出一种新的分匆式数 掘库查询处理方案，并对查询处理模型、数据字典进行设计，对查询流 程进行了改进。该方案通过将常用查询结果存储在本地，从而减少查询 时的数据传输量，缩短响应时白j ；该方案在查询处理模型中添加用户模 块，使用户可以根据需求选择不同的查询优化标准。 针对用户的不同查询优化标准，采用不同的查询优化算法，对其中 的s d d 1 算法迸行改迸，在优化过程中添加并行参数，提高了s d d - 1 算法的并行执行能力。以传输费用最小为目的，提出一种新的查询优化 算法，该算法以连接属性为关键字， 连接关系问相互传送b l o o mf i l t e r s ， 对连接关系建立b l o o mf i l t e r s ，在 缩减掉大部分不参与连接的元组， 形成计算结果表，通过在站点i 日j 传送计算结果表使连接关系得到更大的 缩减，从而减少了传输费用，并通过实验验证了该算法的有效性。 关键词：分布式数掘库，查询处理，数据字典查询优化 s t u d yo fq u e r yo p t i m i z a t i o ni nd i s t r i b u t e dd a t a b a s e s h ix i a o y a n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y ：s e n i o re n g i n e e rz h a n g w e n - d o n g a b s t r a e t i nd i s t r i b u t e dd a t a b a s es y s t e m , i tb e c o m e sm o r ed i f f i c u l ta n dc o m p l e xt o d i s t r i b u t e dq u e r yp r o c e s s i n gb e c a u s eo fd i s t r i b u t i o na n dr e d u n d a n c yo fd a t a d i s t r i b u t e d t h e r e f o r e ，q u e r yo p t i m i z a t i o ni si m p o r t a n ti nd i s t r i b u t e dd a t a b a s e s y s t e m b a s e do nt h ea n a l y s i so fp i o n e e rt e c h n o l o g yo fd i s t r i b u t e d q u e r y p r o c e s s i n g ，an e wm e t h o df o rd i s t r i b u t e dq u e r yp r o c e s s i n gi sp r o p o s e di nt h i s p a p e r t h em o d e lo fq u e r yp r o c e s s i n ga n dd a t ad i c t i o n a r ya l ed e s i g n e d ，a n d t h ep r o c e s so fq u e r yi si m p r o v e di nt h en e ws c h e m e t h em e t h o dc a l lb eu s e d t or e d u c et h eq u a n t i t yo fd a t at r a n s f e rt h r o u g hk e e p i n gp a r t so fq u e r yr e s u l t s a tl o c a l u s e rm o d u l ei sa d d e di n t ot h em o d e lo fq u e r y p r o c e s s i n g ，s ot h eu s e r s c a nc h o o s ed i f f e r e n tc r i t e r i o no fq u e r y o p t i m i z a t i o na c c o r d i n gt ot h e i r d e m a n d b a s e do nd i f f e r e n tc r i t e r i o no fq u e r yo p t i m i z a t i o no fu s e r s ，d i f f e r e n t a l g o r i t h m so fq u e r yo p t i m i z a t i o na r ea d o p t e d ap a r a m e t e ri sa d d e di n t ot h e o p t i m i z a t i o np r o c e s so fs d d - 1a l g o r i t h mi no r d e rt oi m p r o v et h ea b i l i t yo f p a r a l l e li m p l e m e n t a t i o n an e wa l g o r i t h mo fq u e r yo p t i m i z a t i o ni sp r o p o s e d a i ma tm a k i n gl e a s tt r a n s f e rc h a r g e t h i sa l g o r i t h mb u i l tb l o o mf i l t e r su s i n g j o i n ta t t r i b u t ea sk e yw o r d s c u to f fam a j o n t yo ft u p l e st h a ta l eu s e l e s sf o r j o i n tr e s u l tt h r o u g ht r a n s f e r r i n gb l o o mf i l t e r s t h e nf o r mc a l c u l a t i o n a lr e s u l t s i nt a b l e s t h i s a l g o r i t h m c a nm a k em o r er e d u c t i o nb y t r a n s m i t t i n g c a l c u l a t i o n a lr e s u kt a b l e sb e t w e e nd i f f e r e n tn o d e s i t sv a l i d i t yi sv e r i f i e db ya e x p e r i m e n t k e yw o r d s ：d i s t r i b u t e dd a t a b a s e ，q u e r yp r o c e s s i n g ，d a t ad i c t i o n a r y ，q u e r y o p t i m i z a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得石 油大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 签名：丕出拦工- 。7 年中月 j 1 ：1 关于论文使用授权的说明 本人完全了解石油大学有关保留、使用学位论文的规定即：学校 有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： ，丕d ! 袒 纭重煎： 工口口7 年眵月日 以7 年妒月f 同 中国t i 油人学( 华东) 硕十论文第1 章前言 1 1 研究背景及意义 第1 章前言 近年来，随着计算机网络和数据库技术的发展，对分布式数据库的 应用越来越广泛；随着应用不断扩大，数据的查询也越来越复杂，对查 询的效率要求也越来越高，因此查询处理成为分布式数据库系统中的一 个关键性的问题【1 4 】。 在分布式数据库中，由于数据的分布与冗余，使得查询处理中一般 需要站点间的数据传递及通信费用，成为查询优化的主要矛盾：另一方 面，数据的分布与冗余也增加了查询的并发处理的可能性，从而可以缩 短查询处理的响应时日j ，提高处理速度。总之，分布式查询的规模与优 化的因素，都与集中式查询优化不同，因此许多数据库专家学者致力于 研究分布式数据库查询优化技术这一重要课题，并且己经在这一领域作 了大量的工作，也找到了规律，包括一些大家公认的经典算法f 纠l 】；然 而由于分布式数据库本身的灵活性，要想设计一个算法对于各种情况都 是最优的几乎不太现实，我们只能说设计一个较优的优化算法，它可以 解决某一类型的问题。分柿式数据库中查询优化是一项复杂问题，已经 被证明属于n p 完全问题，至今都没有得到彻底地解决，里面尚有许多 问题值得研究和探讨旧13 1 。 通过研究现有分布式数据库查询处理技术，提出一种新的分布式数 据库查询处理方案，该方案能够提高常用查询语句的查询效率，并能满 足用户的不同查询优化标准。针对不同用户的不同查询优化标准，本文 对其中的s d d 1 优化算法进行了改进，引入并行参数p ，提高s d d 1 中国i i 油人学( 华尔) 硕十论文第1 章前言 优化算法并行执行能力，从而缩短了查询响应时间，适合应用于用户的 查询优化标准是响应时间短的情况；提出一种以传输费用最小为目的的 优化算法，该算法不依赖于任何参数的估计，所以它的可靠性更强，适 合应用于用户的查询优化标准是传输费用小的情况。由于查询语句重复 出现是不可避免的，而且随着应用范围的扩大，人们查询时所关心的优 化标准也越来越不同，所以该方案具有一定的实用性，对其他的查询处 理方案也有一定的借鉴作用。 1 2 国内外研究现状 查询是数据库中最常用、最基本的操作，同时也是用户操纵、维护 数据库中的数据的唯一途径。用户对数据库性能的直接感觉就是数据库 管理系统对查询的处理是否高效、快速。查询处理的效率在很大程度上 决定了数据库管理系统的性能，因此，自从分稚式数据库问世以来，分 布式查询优化问题一直倍受关注。 1 2 1 国外研究现状 美国计算机公司( c c a ) 研制了第一个分布式数据库系统的原型系 统s d d 1 ( s y s t e mo f d i s t r i b u t e dd a t a b a s e ) ”“。它概括了分布式数据库的 几乎全部理论和实现技术，支持水平和垂直分片，是分布式数据库发展 中的一个典范。e w o n g 针对s d d 1 系统的情况提出了减少通信开销 的一种方法，设计了一个启发式算法；而后p a b e r n s t e i n 等对w o n g 的算法作了进一步优化，提出了半连接和缩减器的概念。s d d 一1 算法采 用了半连接程序处理连接操作。它的查询优化就是对逻辑关系用基本的 运算( 如选择，投影，半连接) 操作束缩减。它的主要特征，首先，采 中国t 舳人学( 华东) 硕十论文第1 章前言 用半连接是最主要的，其次，各个局部站点没有重复，也不进行分片。 此外，在它的代价计算中，不考虑最后一个场地传送代价。这是由于在 它的查询策略中，当最大限度地缩减以后，把所有关系送到可执行查询 的场地上，这个场地不一定是查询所要求的结果场地。最后它还能同时 最小化总时间和响应时间。 r 是i b m 圣约瑟研究实验室研制的s y s t e mr 的分靠式后继，它的 目的是建立由协同操作，但却是独立的地点构成的分御式数据库系统 【l5 1 。每个地点支持一个关系数据库系统。r 是r 系统向分布式环境的 自然扩展。它是采用直接连接作为查询处理策略的分布式数据库系统。 r 采用枚举算法寻找最优策略。酣系统直接处理连接操作1 1 6 1 ，通过穷 举所有可能的连接方法，并把连接分配在每个可能的场地，最后选择一 个最优的连接操作的执行计划。为了快速计算还采用了动态规划的方 法。在r t 系统中，s q l 查询既可以静态地进行编译，也可以动态地进 行编译。l j 一种情况用于重复查询；后一种情况用于预先不知道的查询。 分布的i n g r e s ，是美国加州大学伯克利分校研制的1 n g r e s 的分布 式后继。e p s t e i n 在分布式i n g r e s 上实现了基于分解的优化算法。 i n g r e s 算法是动态的，解释性的算法。这个算法主要分为两个步骤：( 1 ) 将含有多个变量的查询分解成为一系列的只含有一个变量的单关系查 询。( 2 ) 执行每一个单关系查询，用启发式的方法选择一个初始化的执行 计划，通过中间关系的大小来确定查询执行的顺序。 o r a c l e 是世界上第一个商品化的分布式数据库管理系统，它采用 完全丌放策略，能在所有主流平台上运行，完全支持所有的工业标准。 o r a c l e 的查询处理模块由三个部分组成：p a r s e r ，o p t i m i z e r ，e x e c u t o r 。 p a r s e r 对输入的查询进行语法分析，并检查用户涉及到的数据库对象是否 存在及用户是否具有操作权限。o p t i m i z e r 利用基于代价的优化或基于规 3 中国t i 油人学( 华东) 硕十论文第1 章前言 则的优化找出一个执行代价较低的执行计划，由于在确定数掘的分布时， 引入了直方图来描述数据值的分布而不是假设数据值是均匀分布的，从 而大大提高了代价估计的精确度。如果执行计划可能并行，对某些可能 节点，e x e c u t o r 会启动多个进程来并行执行该节点。在e x e c u t o r 中， o r a c l e 还增加了很多的存取路径，如位图索引等来增加对数据库中数 据存取的速度，为了能充分发挥并行处理的优势，o r a c l e 的存储结构 提供了数据的分区存储和数据的分段扫描来支持并行i o 操作。 1 2 2 国内研究现状 c p o r e l 是由中国科学院数学所设计并由该所和上海科技大学及 华东师范大学合作实现的。主要目标是实用性、先进性和有限的可移植 性。c p o r e l 是关系系统，支持关系的水平分片，在代数优化、非代 数优化及分布式查询优化方面实现了精致的算法1 9 1 。 l s z 异构分布式数据库系统是南京大学在开发了d d b a s e i i 和 d d b a s e i l l 之后设计实现的异构型分布式数据库管理系统。l s z 的全 局数据库语言为g r d l ，它以s q l 为基础扩充分布式数据库的数据定 义部分。它支持关系的水平分片。l s z 建立了从g r d l 到u n i f y 和 d d b a s e 的翻译程序，并进行了局部查询优化。l s z 采用a i 技术实现 了基于启发式规则的语义优化策略，并进行了多重连接优化。 s u n d d b 是东南大学设计和实现的分布式数据库管理系统1 2 。 s u n d d b 采用关系模型，支持多复本、关系水平分片并提供快照功能。 其全局数据库语言为d s q l ，在s q l 语吉的基础上增加了一些全局处 理功能。s u n d d b k 由两部分组成，事务管理模块s u n d d b k i 负责语 法分析，查询优化，并发控制，目录管理等。s u n d d b k 2 负责子事务 4 中国_ i 油人学( 华东) 硕+ 论文第1 章前言 执行管理及恢复等。 东南大学研制的g a l a x y 是一个基于c o r b a 的分布式异构数据源 集成系统，可以查询数据库、w w w 数据库等信息源，但对查询优化考 虑得并不多【2 1 1 。东北大学在基于c o r b a 的多数据库系统s c o p e c i m s 中，使用对象查询语言作为全局查询语言，并提出了基于模式集成语义 的查询处理规则和路径表达式的查询处理方法【2 2 】。 1 3 本文的组织结构 全文根据内容共分五章。 第1 章介绍了本课题的研究背景和意义，详细介绍了分布式数据库 查询处理技术的国内外研究现状。 第2 章介绍了分布式数据库查询处理的相关知识，详细介绍了分布 式数据库系统中的查询处理技术和查询优化技术，重点介绍了分布式查 询优化算法。 第3 章分析了现有分布式查询处理技术，提出一种新的查询处理方 案，并对该方案进行了设计，包括构建总体模型，重新设计数据字典， 并对其中的操作及各模块进行了设计，对查询流程进行了改进。 第4 章研究了s d d 1 算法，并对其进行了改进；研究了连接操作 优化算法，提出一种新的查询优化算法，通过实验验证了该算法的有效 性。 第5 章介绍了论文的主要工作和创新，并对下一步工作进行了展 望。 中国i i 油人学( 华东) 硕十论文第2 章论文研究相戈技术 第2 章论文研究相关技术 2 1 分布式数据库系统定义及模式结构 2 ，1 1 分布式数据库系统 分布式数据库系统是物理上分散而逻辑上集中的数据库系统”2 1 。 分御式数据库系统使用计算机网络将地理位置分散而管理和控制又需 要不同程度集中的多个逻辑单位连接起来，共同组成一个统一的数据库 系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的 有机结合。 一个分布式数据库系统应该具有如下特点j ： ( 1 ) 数据的物理分布性：分御式数据库系统中的数据不是集中存储 在一个站点上，而是分散存储在由计算机网络连接起来的多个站点上， 而且这种分散对用户来说是感觉不到的，所以，分布式数据库系统的数 据具有物理分布性，这是与集中式数据库系统的最大差别之一。 ( 2 ) 数据的逻辑整体性：分布式数据库系统中的数据物理上是分散 在各个站点中，但这些分散的数据逻辑上却构成一个整体，它们被分布 式数据库系统的所有用户共享，并由一个分布式数据库管理系统统一管 理，它使得“分御”对用户来说是透明的。这是分布式数据库的“逻辑 整体性”特点，也是与分散式数据库的最大区别。 ( 3 ) 站点自治性：系统中的每个站点都具有独立性，能执行局部的 应用请求，每个站点又是整个系统的一部分，可通过网络处理全局的应 用请求。 中国i i 油人学( 华东) 硕十论文 第2 章论文研究相关技术 2 1 2 分布式数据库系统的模式结构 在分布式数据库中，一般可以将模式结构分为四层【2 】： ( 1 ) 全局 外层：全局外模式。( 2 ) 全局概念层：全局概念模式、分片模式、分 配模式。( 3 ) 局部概念层：局部概念模式。( 4 ) 局部内层：局部内模 式。各个模式之间由数据库管理系统提供的多次映像来实现转换，如图 2 1 所示。 图2 1 分布式数据厍的模式结构 ( 1 ) 全局外模式 全局外模式是全局应用的用户视图。分布式数据库与集中式数据库 的视图有同样的概念，不同的是它不是从某一个具体站点中的局部数据 库中抽取，而是从一个由各个局部数据库组成的逻辑集合中抽取。然而 对全局用户而占，都可以认为在整个分布式数据库系统的各个站点上的 所有数据库都如同在本站点一样，只关心他们自己所使用的那部分数 ， 中国- i 油人学( 华尔) 硕十论文第2 章论文研究相关技术 据。 ( 2 ) 全局概念模式 全局概念模式描述了分布式数据库中全局数据的逻辑结构和数据 特性，与集中式数掘库中的概念模式是集中式数据库的概念视图一样， 全局概念模式是分布式数据库的全局概念视图。 ( 3 ) 分片模式 分片模式是描述全局数据的逻辑划分。它是全局数据逻辑结构根据 某种条件的划分，即成为局部的逻辑结构，每一个逻辑划分是一个片段， 或称为分片。 ( 4 ) 分配模式 片段是全局关系的逻辑部分，一个片段在物理上可以分配到网络的 不同结点上，分配模式描述局部逻辑的局部物理结构，是划分后的片段 的物理分配视图。 ( 5 ) 局部概念模式 局部概念模式是全局概念模式的子集，全局概念模式经逻辑划分成 一个或多个逻辑片断，每个逻辑片段被分配在各局部场地上。在分布式 数据库局部场地上，对每个全局关系有该全局关系的若干个逻辑片段的 物理片段集合，该集合是一个全局关系在某个局部场地上的物理映像， 其全部则组成局部概念模式。 ( 6 ) 局部内模式 局部内层是分布式数据库中关于物理数据库的描述，类同集中式数 掘库中的内模式，但其描述的内容不仅包含只局部于本站点的数据的存 储描述，还包含全局数据在本站点的存储描述。 中国i i 油人学( 华东) 硕十论文第2 章论文研究相关技术 2 2 分布式查询处理及优化 分布式查询技术主要把用户提交的全局查询请求翻译为几个相关 节点都可以识别的本地查询请求，以及把各个节点的查询结果汇总返回 的问题，它包括分布式查询处理和分布式查询优化。分御式查询处理研 究整个分布式查询处理的过程和策略；分稚式查询优化研究查询策略的 优化问题，即如何从多种方案中选择查询代价最少的方案。 2 2 1 分布式查询的层次结构 在分布式数据库中，数据分布对用户一般是透明的，用户向系统提 出查询请求时，不必关心所涉及的关系是否分割、有无复本、存于何处 等问题，可以像集中式数据库一样，用关系而不是片段表达查询。分布 式查询从结构上可分为四个层次，包括查询分解、数据本地化、全局优 化、局部优化【2 - 2 3 1 。 布式杳询问题卜到查询分解卜+ 弋全局模式 局磷数7 医亟圈_ 匝亟 j i 段查询 括通信操作 化 段上查 全局优化 局部优化 优化的局部奁 j i 段统计 局部模式 图2 - 2 分布式布询处理的层次结构 ( 1 ) 查询分解：对全局查询语句进行词法分析、语法分析并转化为一 9 中国t 啪人学( 华东) 硕十论文第2 章论文研究相关技术 棵全局查询树，再将全局查询树转化为段查询树。 ( 2 ) 数据本地化：对查询所要访问的每一个关系进行具体化，落实到 合适( 使尽可能做到本地化或近地化) 片段上的查询。如果查询所访问的 关系只有一个副本，则称为非冗余具体化，否则称为冗余具体化。 ( 3 ) 全局优化：全局优化是指找到分片查询的最佳操作次序，使得代 价最小。代价一般是指i 0 ，c p u 和通信代价之和。全局优化输出的是一 个优化的关系代数查询，所需要的信息来自数据库的统计信息，包括各 站点片段统计信息、资源信息和通信信息等。 ( 4 ) 局部优化：局部优化在各个本地站点执行，由各个站点上的 d b m s 进行优化，采用集中式数据库的优化算法。 2 2 2 全局查询处理策略 为了执行全局查询和确定一个好的查询策略，一般应该从以下三方 面来考虑： ( 1 ) 确定具体副本：在分布式数据库中一个关系可分为若干逻辑 片段，这些片段又可以在系统的多个节点上存放，所以，对于一个查询 所涉及的关系需要确定一个物理片段，选择不同的物理片段执行查询操 作会直接影响查询执行的效率，因此必须选择查询开销最省的那些物理 片段。 ( 2 ) 选择操作执行的顺序：主要是确定连接和并操作的顺序，其 他操作的顺序是不难确定的，例如选择和投影操作总是应尽可能地提前 执行，这个原则与集中式数据库所考虑的策略相同，但在分向式数据库 系统中涉及到的是在不同站点上关系的连接和并操作的顺序，更需认真 考虑。 0 中国l 袖人学( 华尔) 硕十论文第2 章论文研究相关技术 ( 3 ) 确定操作执行的方法：这包括把若干个操作连接起来在一次 数据库访问中执行，确定可用的访问路径，以及确定某种计算方法等。 连接是查询中最费时的操作，因此连接操作的执行方法是分布式查询研 究的重点。 上述三个问题不是孤立的，为了找到个查询的最优策略，就要确 定执行查询的物理片段，还必须了解查询中各操作执行的顺序，而这又 依赖于每个操作的执行方法【2 1 。 2 2 3 全局查询处理步骤 在分布式数据库中，全局查询的处理步骤分两步，即全局查询到逻 辑查询的转换以及逻辑查询到物理查询的转换。一个全局查询任务只有 经过这两步转换后才能交付给各个局部数据库管理系统执行。 ( 1 ) 全局查询到逻辑查询的转换 包括两个方面的内容： 在转换过程中利用等价变换规则，将全局查询表达式转换成查询 内部结构全局查询树。对这一查询树的逻辑优化技术可以概括出三 点：查询树中的一元操作尽量下移到叶节点；查询树中的二元操作的操 作数尽量归约；提取公共因子，消去无用子表达式。 将全局查询树转换成部分优化的逻辑关系查询树。其中包括将全 局查询树叶节点按分片模式定义的逻辑关系名取代全局关系名，同时运 用变换规则化简成部分优化的逻辑查询树。 ( 2 ) 逻辑查询到物理查询的转换 所谓物理查询转换，是指将逻辑查询得到的简化了的查询树转换成 具体的每个场地上的局部操作命令和数据传输命令序的过程。在逻辑查 中国f i 油人学( 华东) 硕十论文第2 章论文研究相关技术 询到物理查询转换过程中将涉及物理副本及查询的处理场地，有很多具 体的策略。这些策略都是对处理环境有假定条件的，也就是说在物理转 换时更多地涉及到场地因素即执行环境，特别是对于多个副本或多个场 地进行二元操作，注意力集中在副本选择，操作执行顺序的选择，操作 方法的选择这些因素。 2 2 4 分布式查询优化的目标和代价估算 在分布式数据库系统中，常以两种不同的目标来考虑查询优化。一 种目标是以总代价最小为标准，除了像集中式数据库系统一样考虑c p u 代价和i ，o 代价之外，总代价还包括数据通过网络传输的代价。这是由 于数掘的分布和冗余，使得查询处理中，一般需要考虑站点间传递数据 所需要的通信费用，引起查询总代价的增加。另一种目标是以每个查询 的响应时自j 最短为标准，这一点在分布式数据库系统中具有重要的意义 2 1j 。因为，分布式数据库系统是由多台计算机组成的系统，数据的分布 和冗余也增加了查询的并行处理的可能性，从而可以缩减查询处理的响 应时问，加快查询处理速度。 在分稚式查询优化中也常常同时使用这两种标准，根据系统应用的 不同，一种作为主要标准，另一种作为辅助标准。例如，可能先找到一 个总代价最小的执行方案，然后使总代价不增加的条件下修正方案，以 使响应时间最短。在某些情况下，查询处理同时以减少通信费用与响应 时问作为优化目标，这时，算法往往需要在这两者之间作出权衡。 查询代价的估算方法【2 】： 设一个查询执行的预期代价为q c ，则： 在集中式数据库中：q c = i o 代价+ c p u 代价 中国t i 油人学( 华尔) 硕十论文第2 章论文研究相关技术 在分布式数据库中：q c = i o 代价+ c p u 代价+ 通信代价 通信代价可用如下公式作粗略估算： t c ( x ) c o + c i x ( 2 1 ) 其中：x 为数据的传输量，通常以b i t 为单位计算；c o 为两站点间 通信初始化一次所花费的时间，它由通信系统确定，近似一个常数，以 秒为单位；c ，为传输率( 传输速度的倒数) ，即单位数据传输的时问， 单位是秒b i t 。 2 3 分布式查询优化算法 在对分伟式查询优化算法进行研究时，需着重考虑以下几个问题： ( 1 ) 对于算法的研究是采用动态优化算法还是静态优化算法。 ( 2 ) 如何寻求最佳的优化方案。 ( 3 ) 在分布式数据库中查询还要考虑异构的影响，分布在几个站点 上的数据存在重叠的可能性，局部查询丌销因各个站点而不同等因素是 在分布数据库查询优化时不可忽略的。 2 3 1 基于关系代数等价变换的查询优化算法 基于关系代数等价变换的优化算法是一种既能减少操作量又能减 少操作次数的算法，该算法的基本思想是：利用关系代数等价变换规则， 对表达式进行转换，尽可能早地执行选择操作，尽可能早地执行投影操 作，避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和 投影合并起来一起做，以减少中间关系的大小。 基于关系代数等价变换规则的优化算法使用启发式优化方法对关 系代数表达式进行优化，算法的步骤如下：把查询问题转变为关系代数 中国_ i 油人学( 华东) 硕十论文第2 章论文研究相关技术 表达式，对关系代数表达式进行语法分析，得到查询语法树；算法利用 关系代数等价变换规则，把查询树中的连接和合并操作尽可能上提，选 择和投影操作尽可能下移到片段的定义处；然后判断是水平分片还是垂 直分片，若为水平分片，则把分片条件与选择条件进行比较，去掉存在 矛盾的片段，如果只剩下一个片段，就可以去掉一个并操作。若为垂直 分片，则把片段的属性集与投影操作所涉及的属性集进行比较，去掉无 关的所有片段，如果只剩下一个垂直片段，就可以去掉一个连接操作， 从而达到优化查询的目的，通过以上的变换，减少了数据在站点问的流 量，达到了查询优化的目的。 2 3 2 基于半连接操作的查询优化算法 基于半连接操作的查询优化的思想是经过半连接操作，可减少操作 关系的数据量，从而减少站点白j 数据的传输量【3 1 。基本思想是：数据以 整个关系在网络中传输，这显然是一种冗余的方法，在一个关系传输到 另一场地后，并非每个数据都参与连接操作或都有用，因此，不参与连 接的数据或无用的数据不必在网络中来回传输。基于半连接的优化策略 的基本原理就是采用半连接操作，在网络中尽量只传输参与连接的数 据。连接查询的优化问题几乎是分御式数据库的分布式查询优化算法的 全部，在分布式数据库中连接查询的主要手段是半连接技术，各种不同 算法的差异主要是在连接顺序上，即在保证结果一致的情况下，以什么 样的顺序将这些表连接起来最优。优化的对象一般是数据传输量的总和 【2 4 l 。 半连接方法的描述如下：假设站点l 和站点2 的两个关系r 和s ， 在属性r a = s b 上作连接操作，则有1 4 中国_ i 油火学( 华东) 硕+ 论文第2 章论文研究相关技术 r o o m s = ( ro c 。口s p m s 或r o o 月，口s = ( s j ：口r ) o o j 。月r 其中so c 。r 和ro c 。s 称为“半连接”。 ( 2 2 ) r o o 。；。s = ( 眉o c 。；。s ) o o 。s 这个半连接程序的操作过程和传输费用 如下( 其中传输费用用公式：t = c o + c j x 估算) ： 第一步：在站点2 计算关系s 在属性b 上的投影岱) 。 第二步：把万。( s ) 的结果从站点2 传输到站点1 ，其传输费用是： c o + c 1 s i z e ( b ) + v a l ( b s ) 。( 其中s i z e ( b ) 表示属性b 的长度，v a l ( b 【s 】) 表示关系s 中属性b 的个数) 第三步：在站点l 计算半连接，设其结果为r ，则r 。= ro c s 。实 际上，这个操作是执行ro o j 。l 。( s ) 。 第四步：把r 从站点l 传到站点2 ，其传输费用为：c o + c i * s i z e ( r ) * c a r d ( r ) 。( 其中s i z e ( r ) 是r 中元组的长度，c a r d ( r ) 是r 。 的元组数) 第五步：在站点2 执行连接操作r m s 。 由上面五步可以计算出总的传输费用为： t = 2 c 0 + c j + ( s i z e ( b ) + v a k b s ) + s i z e ( r ) + c a r d ( r ” ( 2 - 3 ) 同样可以计算出月m 。；。s = o c 。：。r ) o o 。r 这个半连接程序的传输 费用，和r o o 。s = ( r * j 。s 。s 的传输费用相比较，可以确定r 和 s 的最优半连接程序。 在一般情况下，采用半连接方法的传输费用较小，所以在很多情况 下采用半连接方法执行连接操作是合适的【”1 。 中国t i 油人学( 华东) 硕十论文第2 章论文研究相关技术 23 3 基于直接连接操作的查询优化算法 基于直接连接操作的查询优化是一种完全在连接的基础上考虑查 询处理的策略【。6 1 ；有时直接连接也可能会产生好的效果，特别是当有下 述情况时： ( 1 ) 查询目标表中的属性很少，也不是某些连接条件属性。 ( 2 ) 半连接的缩减效果较差时。 例如，对一个涉及到存储在不同场地的三个关系进行连接的查询， 首先把一个关系传送给第二个关系所在地，然后进行连接运算；再把运 算结果传送到第三个关系所在地，计算它们的连接并产生查询结果。 究竟用直接连接还是半连接方案，取决于数据传输和局部处理的相 对费用。一般，如果认为传输费用是主要的，那么采用半连接策略比较 有利；如果认为局部处理费用是主要的，则采用直接连接策略比较有利。 2 ，3 4s d d 1 算法 用半连接查询取代连接查询的方法。可以减少数据在网络中的传输 量，但是事先我们不可能知道哪个关系表的元组被更多的包含在连接结 果中，所以如何确定传输哪一个关系表的属性列是摆在我们面前的问 题，而s d d l 算法很好的解决了这个问题【矧。 在s d d 1 查询策略中，使用半连接柬缩减操作数关系的基数，当 最大限度的缩减以后，把所有关系送到可执行查询的场地，这个场地不 一定是查询所要求的结果场地。s d d 1 算法由两部分组成：基本算法， 根据评估缩减程序的费用、效率、收益估算几个因素，给出全部的半连 接缩减程序集，决定最有益的执行策略；后优化，将基本算法得到的解 进行修正，以得到更合理的执行策略。 1 6 中国i 油大学( 华东) 硕+ 论文第2 章论文研究相关技术 s d d ，1 基本算法： 前提：已经存在一个查询图g ； 第一步：对查询图g 中的所有的半连接程序进行收益评估； 第二步：选取收益最大的那个半连接程序，并修改其他的半连接程 序的静态特性，然后再次对修改后的半连接程序进行收益评估； 第三步：循环第二步，直到所有有收益的半连接程序都被选取了： 第四步：选取通信代价最小的那个站点作为连接操作的执行站点。 后优化： 在基本算法中，每次迭代时只考虑本次迭代时的改善，这种改善不 一定最好。后优化有两种修正： ( 1 ) 若最后一次半连接程序缩减关系的所在场地恰好是被选中的 查询执行场地，则最后一次半连接可以取消； ( 2 ) 对基本算法的主迭代所构成的半连接程序的流程图进行修正。 因为一开始的半连接缩减程序的代价很高，如果有r o o s ，这时把s 进 行缩减后再进行半连接缩减，即可修正半连接的操作序。 2 4b l o o m f i l t e r 方法 b l o o mf i l t e r 方法自从1 9 7 0 年由b u r t o nb l o o m 提出来之后，就广 泛应用于网络、数据库、p 2 p 系统等众多领域。它的优点是可以有效地 节省空日j ，缺点是不能做到精确无误，不过这个缺点可以使用调节参数 的方法来得到有效控制，也可以通过不同的应用手段来避免差错。下面 给出b l o o mf i l t e r 的概念和原理f 加。 b l o o mf i l t e r 是一种空间效率很高的随机数据结构，它利用位数组 很简洁地表示一个集合，并能判断一个元素是否属于这个集合。b l o o m 中国t i 油人学( 华尔) 硕十论文第2 章论文研究相关技术 f i l t e r 的这种高效是有一定代价的：在判断一个元素是否属于某个集合 时，有可能会把不属于这个集合的元素误认为属于这个集合( f a l s e p o s i t i v e ) ，因此，b l o o mf i l t e r 不适合那些“零错误”的应用场合。而在 能容忍低错误率的应用场合下，b l o o mf i l t e r 通过极少的错误换取了存 储空间的极大节省。 假设有一集合s = x l ，x 2 ，x 。 ，b l o o m f i l t e r 初始状态时是一 个包含m 位的位数组，每一位都置为0 ，如下图： 幽2 - 3b l o o mf i l t e r 初始状态幽 下面具体来看b l o o mf i l t e r 是如何用位数组表示集合s 的，使用k 个独立的哈希函数，将s 中的每个元素x 映射到这个m 位数组中的某 一位上， s 中的每个元素要做k 次哈希。对任意一个元素x j ，第j 个 哈希函数映射的位置h j c x ) 就会被置为1 ( 1 _ j s k ) 。如果一个位置多次 被置为1 ，那么只有第一次会起作用，后面几次将没有任何效果。在下 图中，k = 3 ，且有两个哈希函数同时选中第7 位。 i 0 o10l10 0 o1o | 鳘| 2 - 4b l o o mf i l t e r 例i 芏| 在判断元素y 是否属于这个集合时，对y 应用k 次哈希函数，如 果所有h j ( 的位置都是1 ( 1 匀韭) ，那么我们就认为y 是集合中的元 素，否则就认为y 不是集合中的元素。下图中y i 不是集合中的元素。 y 2 可能属于这个集合，也可能刚好是一个f a l s ep o s i t i v e 。 中国t 讨山大学( 华东) 硕十论文第2 章论文研究相关技术 i oo l01lo o o1o 幽2 5 兀累判断例幽 ( 1 ) 错误率估计 b l o o mf i l t e r 在判断一个元素是否属于它表示的集合时会有一定的 错误率，下面我们就来估计错误率的大小。在估计之前为了简化模型， 我们假设k n m 且各个哈希函数是完全随机的，当集合s = ( x l ， x 2 ，x n 的所有元素都被k 个哈希函数映射到m 位的位数组中时， 这个位数组中某一位还是0 的概率是：p = ( 卜土) “* p 一“ ( 2 4 ) j 竹 其中1 m 表示任意一个哈希函数选中这一位的概率( 前提是哈希函 数是完全随机的) ，( 1 1 m ) 表示哈希一次没有选中这一位的概率。要把 s 完全映射到位数组中，需要做l 【1 1 次哈希。某一位还是0 意味着l 【1 1 次 哈希都没有选中它，因此这个概率就是( 1 - l m ) 的l c l l 次方。令p = e - 1 是为了简化运算，这罩用到了计算e 时常用的近似：l i m ( 1 一二) 一= 8 。 x - o 工 令p 为位数组中0 的比例，则p 的数学期望e ( p 产。在p 已知 的情况下，要求的错误率为：( 1 一p ) 。* ( 1 一p ) 。“( 1 - j 口) ( 2 5 ) ( 1 一p ) 为位数组中1 的比例，( 1 - p ) 。就表示k 次哈希都刚好选中1 的区域，即错误率。上式中第二步近似在前面已经提到了，现在来看第 一步近似。只是p 的数学期望，在实际中p 的值有可能偏离它的数 学期望值。m m i t z e n m a c h e r 已经证明，位数组中0 的比例非常集中地 分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将 中国i m 人学( 华尔) 硕十论文第2 章论文研究相关技术 p 和p 代入上式中，得： f = ( 1 一( 1 一上) “) 。= ( 1 一，) 。， m = ( 1 一e - “) 。= ( j _ ，) ，相比p 和，使用p 和f 通常在分析中更为 方便。 ( 2 ) 最优的哈希函数个数 b l o o mf i l t e r 要通过多个哈希函数将集合映射到位数组中，下面讨 论应该选择几个哈希函数爿。能使元素查询时的错误率降到最低。这罩有 两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的 元素进行查询时得到0 的概率就大；但另一方面，如果哈希函数的个数 少，那么位数组中的0 就多。为了得到最优的哈希函数个数，我们需要 根据上- d , 节中的错误率公式进行计算。 先用p 和f 进行计算。注意到厂= e x p ( k i n ( 1 一p 4 “) ) ，令 g = k i n ( 1 一e - k “) ，只要让g 取到最小，f 自然也取到最小。由于 p = e - k n m ，可以将g 写成g = 一r n i n ( p ) l n ( 1 一p ) ，根据对称性法则可以 很容易看出当p = l 2 ，也就是k = i n 2 + ( m n ) 时，g 取得最小值。在这种情 况下，最小错误率f 等于( 1 2 ) 。* ( o 6 1 8 5 ) u 。另外，注意到p 是位数组 中某一位仍是0 的概率，所以p = l 2 对应着位数组中o 和1 各一半。换 句话说，要想保持错误率低，最好让位数组有一半还空着。 需要强调的一点是，p = l 2 时错误率最小这个结果并不依赖于近似 值p 和f o 同样对于，= e x p ( k i n ( 1 一( 1 1 m ) “) ) ，g = k l n ( 1 一( 1 1 i r a ) “) ， = ( 1 - 1 m 户，可以将写成= j 高1 n ，) 1 n ( 1 - - p ) ，同样根 据对称性法则可以得到当p = 1 2 时，取得最小值。 中国t i 油人学( 华尔) 硕十论文第2 章论文研究相关技术 ( 3 ) 位数组的大小 下面讨论在不超过一定错误率的情况下，b l o o mf i l t e r 至少需要多 少位才能表示全集中任意1 1 个元素的集合。假设全集中共有u 个元素， 允许的最大错误率为f ，下面我们来求位数组的位数m 。 假设x 为全集中任