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

论文题目： 专业： 硕士生： 指导教师： 分布式数据库查询优化的研究 计算机应用技术 早空 大7 c 龙熙华 摘要 ( 签名) ( 签名) 随着科学技术的发展以及计算机网络技术的普及，分布式数据库系统逐渐取代了集 中式数据库系统，走进我们的生活中。然而伴随着分布式数据库系统的广泛应用，其所 涉及的查询效率以及性能问题也就随之而来，因此分布式数据库的查询优化成为分布式 数据库领域的研究热点之一。 本文首先介绍了一些分布式数据库的相关知识，如数据分布、数据分片、连接相关 操作以及分布式数据库的查询过程。其次简要讲述了几种常规的优化算法：基于关系代 数等价变换的优化算法，基于连接的优化算法以及基于半连接的优化算法。然后详尽的 分析了两类应用广泛的优化算法及其改进算法：s d d1 及其改进算法和哈希划分等值连 接算法及其改进算法。最后在对上述这些算法进行研究的基础上，对以上算法很少涉及 的i o 代价和c p u 代价，从重复查询的角度，通过两种主要的数据结构结合l i 算法 以及一致性哈希算法，设计了一种基于分布式查询缓存的优化方案，本文称之为 d c o ( d i s t r i b u t e dc a c h eo p t i m i z a t i o n 分布式缓存优化) ，用来提高整个分布式数据库系统 的查询吞吐量以及响应时间。这种方案主要适用于以分布式数据库的主站点作为分布式 查询结果的装配站点这种情况。在缓存实验中设计了三组测试用例，实验结果表明了本 方案的有效性。 关键字：分布式数据库；查询优化；性能优化；分布式查询缓存 研究类型：应用研究 s u b j e c t s p e c i a l 锣 ：r e s e a r c ho nq u e r yo p t i m i z a t i o no fd i s t r i b u t e dd a t a b a s e ： c o m p u t e ra p p l i c a t i o n r e c h n o i o g y n a m e：w ux i a n i n s t r u c t o r： l o n gx i h u a a b s t r a c t ( s i g n a t ur e ) ( s i g n a t ur e ) w i t ht h ed e v e l o p m e n to fs c i e n c ea i l dt e c l l l l o l o g y ，a sw e u 嬲t h ep o p u l 撕够o fc o m p u t e r n e m o r kt e c | l i l o l o g y ，d i s t r i b u t e dc i a 协b a s e 黟a d 吼l l yr e p l a c e dt h ec e n t r a l i z e d 姚b a s e ，a n d e m e r e do u rl i f e h o w e v e r ，a l o n gw i t haw i d er 肌g eo fd i s t r i b u t e dd a t a b a s ea p p l i c a t i o n s ；t h e i s s u eo fe 伍c i e n c ya n dp e 墒r m a n c ei ti n v o l v e dh 嬲c o m et ou s d i s t r i b u t e dq u e 巧 o p t i m i z a t i o nh a sb e c o m eo n eo f t h eh o ta r e a so fr e s e a r c ho nd i s t r i b u t e dd a t a b a s e t h i sp a p e rf i r s ti n t r o d u c e san u m b e ro fd i s t r i b u t e dd a t a b a s er e l e v a i l tk n o w l e d g e ，s u c ha s d a t ad i s t r i b u t i o l l ，i a t am l g m e n t a t i o n ，jo i nr e l a t e do p e r a t i o n ，d i s t r i b u t e dd 撕b a s eq u e 巧 p r o c e s s i n g n e x tt a l b n ga _ b o u ts e v e r a lc o n v e n t i o n a lo p t i m i z a t i o na l g o r i t l u n s ：o p t i m i z a t i o n a l g o r i t l u i l b a s e do nt h er e g u l a t i o no fr e l a t i o n a l a l g e b r ae q u i v a l e n c et r a n s f o r m a t i o n ， o p t i m i z a t i o na l g o r i t l u l lb a s e do nj o i na n ds e m i _ j o i n a n dt l l e nad e t a i l e da i l a l y s i so ft 、o w i d e l yu s e do p t i m i z a t i o na l g o r i t h m ：s d d l la 1 1 d i t sd e r i v a t i v e sa sw e l la si t si m p r 0 v i n g a l g o r i t l u i l ；a r l dh a s hd i v i s i o no p t i m i z a t i o na i l di t si m p r o v i n ga l g o r i t f i n a l l y ，o nt h eb a s i s o fr e s e a u r c ho nt h e s ea l g o r i t h m s ，t h i sp a p e rp r e s e n t san e ws o l u t i o nf r o mt h ev i e wo fr e p e a t e d q u e r i e s ，a i m i n ga tt h ei o a n dc p u c o s t ，w h i c hi sl i n l ei n v o l v e db yt h ea b o v e - m e n t i o n e d a l g o r i t h m t h i ss o l u t i o n ，w m c ha d o p t e d “0m a i nd a t as t m c t u r e s ，c o m b i n e dw i ml r u a l g o r i t h ma 1 1 dc o n s i s t e n th a s ha l l g o r i t h ma n db a s e do nd i s t 曲u t e dc a c h e ，c a l lb ec a l l e dt h e d c o ( d i s t r i b u t e dc a c h eo p t i m i z a t i o n ) ，a n du s e dt oe r l l l a n c et h ed i s t r i b u t e dd a t a b a s es y s t e m t l l r o u 曲p u ta sw e l la st h eq u e 巧r e s p o n s e t i m e t h es o l u t i o nm a i n l ya p p l i e st 0t h ec a s et h a tt h e m a i ns i t eo fd i s t r i b u t e dd a t a b a s ei s t l l ed i s t r i b u t eq u e 巧r e s u l t sa s s e m b l ys i t e i nc a c h e e x p e r i m e n t ，t h r e e s e t so ft e s tc a s e sa r ed e s i g n e d ；t h ee x p e r i m e n t a lr e s u l t ss h o wt h e e 任e c t i v e n e s so ft h es o l u t i o n k e y w o r d s ：d i s 劬u t e 拙a b a s e q u e r yo p t i m i z a t i o np e 偷衄a n c eo p t i m i z a t i o n d i s t r i b u t eq u e r yc a c h e t h e s i s ：a p p l i c a t i o ni 沁s e a r c h 西姿料技大学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究，t 作及 其取得研究成果。尽我所知，除了文巾加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者舭蒙彩吼川j6 、 f 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题冉撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名： 指导教师签名：彳包 坪 日 1 绪论 1 1 选题背景和研究意义 1 绪论 分布式数据库是计算机网络技术与数据库技术互相渗透和有机结合的产物，具有数 据独立性、集中与自制相结合的控制机制、适当增加数据冗余、事务管理的分布性等特 点【l 】。分布式数据库是分散存放在许多台计算机上的数据的集合，它在逻辑上是一个单 一的、集中管理的数据库，但在物理上却存放在多个场地上，既允许局部的数据访问， 同时又实行全局管理。一个完整可靠的分布式数据库系统能够随时随地提供可靠的信 息，用户可以随时灵活地访问信息而不必关心数据存放的地点和方法【2 j 。在分布式数据 库系统中，数据不是集中存放的，而是分开存放在网络的各个节点上，这是和集中式数 据库最大的差异。分布式数据库系统在多年的发展历史中，取得了很多研究成果，许多 问题被提出并得以解决。与此同时，在数据库技术和网络技术相互渗透和有机融合的过 程中也产生很多新的、由分布式环境造成的固有技术难题。但是鉴于分布式数据库系统 在社会生产、生活的多方面，如交通【3 1 、多媒体应用【4 j 、无线通信【5 】等都有深刻的应用 背景，各国还是在分布式数据库系统的研制方面投入了大量的人力、物力、财力，如德 国斯图加特大学的p o i 也l 1 6 j ，美国i b m 公司研制的s y s t e mr i7 】和美国加州大学伯克利 分校研制的d i n g i 辽s 1 8 j 等。在我国，虽然分布式数据库系统的研究和应用落后于发达 国家，但是随着人民生活水平的提高，社会生产生活中基于分布式数据库系统的应用的 增加，国内对于分布式数据库的研究和应用也正在飞速发展。 随着分布式数据库技术在各行各业的应用的深入，人们也逐渐发现分布式数据库系 统的一些难以解决的问题。首先，在存取数据的时候，因为数据位于不同的站点上，所 以在数据传输的时候不可避免的带来大量的通信代价。其次，在存取数据的时候产生的 c p u 代价，i o 代价，造成数据库后台负担进一步加重，使整个系统的性能降低。这两 个原因很大程度上制约了分布式数据库的查询效率，从而影响了分布式数据库的普及。 分布式数据库查询处理和优化不仅是影响分布式数据库管理系统性能的关键因素， 而且还对整个应用系统数据的可用性、可扩展性、提高分布式数据库的使用效率和可靠 性起着不可估量的作用。国内外学者已经在这一领域提出了一些经典理论，但是由于分 布式数据库系统本身的复杂性，分布式查询优化技术还不很成熟，经典的理论大多局限 于某个方面，或者过于复杂而缺乏实际意义。分布式数据库查询优化是一个复杂问题， 还有很多值得探讨与完善的地方，因此该课题具有很具实用价值。 西安科技大学硕士学位论文 1 2 国内外研究现状 传统集中式数据库的查询代价主要有两个方面： ( 1 ) c p u 代价：是查询时占用的c p u 指令周期。 ( 2 ) i o 代价：从磁盘上读取数据所花费的代价。 而在分布式数据库中，查询代价则可以分为以下三个方面： ( 1 ) c p u 代价：在各个站点上执行局部查询占用的c p u 指令周期，以及分解查询， 组装局部查询结果占用的指令周期。 ( 2 ) i o 代价：在各站点上读取数据所花费的代价。 ( 3 ) 通信代价：数据在网络上传输所花费的时问。 就代价而言，分布式数据库中，由于数据的分布性，因而在查询时要涉及多个站点 上的数据，所以产生的c p u 代价和i o 代价远大于集中式数据库，而通信代价则是分布 式数据库的特有产物：数据在网络中来回传输所花费的代价。 在分布式数据库系统中，常以两种不同的目标来考虑查询优化【9 l ： ( 1 ) 代价优化：以总代价最小为标准，除了像集中式数据库系统一样考虑c p u 代价 和i o 代价之外，总代价还包括通信代价。 ( 2 ) 性能优化：使数据库达到其最佳性能，一般用响应时间和吞吐量来衡量。 在代价优化方面，国外学者已经给出了许多优化算法，例如s d dl 算法、基于查 询图的贪婪算法、基于人工智能理论的a 和a 算法、i p s j 和n p s j 算法以及t w o s t 印 p n m i n g 算法等等【1 0 。13 1 。而国内学者的研究成果也很多，尤其是近十年以来，各种优化 算法大量涌现，例如聚簇索引的多连接查询优化方法、遗传最优连接算法、虚连接和虚 半连算法、粒子群多连接优化等等【1 4 d 。 代价优化的策略大多是基于连接和半连接操作，因为数据的分布性，所以连接运算， 特别是多连接操作产生的通信代价往往大于集中式数据库中i o 代价和c p u 代价的总 合。少部分学者从数据i o 方面着手，比如杨艺，杨洲纠硌，1 9 】，他们通过对数据存储做 出调整，使查询操作( 即读取操作) 从存储过程中受益。 当然也有一些学者致力于性能优化，如：w 撕g e ny e e ，s h a m k a mb n a v a t h e 等 1 7 】 给出的数据分配方法对于避免由于系统i o 瓶颈造成的效率下降提供了帮助，从而使整 个数据库系统的吞吐量大幅提高。 从上述文献以及其他一些文献来看，对于分布式数据库的查询优化主要有两种思 路： ( 1 ) 从数据分配，存储着手，优化查询。 ( 2 ) 对查询时连接或者半连接操作的执行方式进行一定的调整，优化查询。 2 1 绪论 1 3 本文研究内容及结构 对大量的文献的仔细研究，发现大多数学者对分布式查询时产生的c p u 代价和i o 代价研究较少，对查询时的通信代价研究较多，比如s d d1 算法，哈希划分算法都是 针对分布式查询的通信代价做优化。基于此原因，本文决定针对分布式数据库的性能， 尤其是吞吐量方面，对分布式数据库查询时的i o 和c p u 代价进行优化，开展研究工作。 本文组织结构如下： 第1 章：绪论部分，简要说明研究背景，国内外研究现状，以及本文的研究内容。 第2 章：分布式数据库系统概述，介绍一些分布式查询的相关知识。 第3 章：典型分布式数据库查询优化算法，对一些常规的分布式数据库优化算法进 行了细致的介绍，同时分析了基于半连接优化的s d dl 算法和基于直接连接的哈希划 分等值连接优化算法，以及一些学者对这两种算法中存在的不足给出的改进方案。 第4 章：基于分布式缓存的分布式数据库查询优化，针对上述学者研究不多的i o 和c p u 代价，本文给出了一种优化方案，提高分布式数据库的吞吐量和缩短分布式查 询的响应时间。 第5 章：缓存验证实验，对第4 章中设计的分布式优化方案进行有效性验证。 3 西安科技大学硕士学位论文 2 分布式数据库系统概述 2 1 分布式数据库系统的特点以及分类 对于分布式数据库系统其一般定义是：分布式数据库由一组数据组成，这些数据物 理上分布在网络上不同的节点( 也叫做场地或者站点) 上，逻辑上属于同一个系统【2 l 。 简单逻辑结构如图2 1 所示。 图2 1 分布式数据库逻辑结构图 上面这个定义强调了两点： ( 1 ) 和集中式数据库不同，分布式数据库中的数据不是存储在同一个场地，确切地 讲，不是存储在同一台计算机的存储设备上，这一点也是和集中式数据库最根本的区别。 ( 2 ) 逻辑整体性。这些数据逻辑上是互相联系的，属于同一个数据库，逻辑上如同 集中式数据库。由于分布式数据库存在着逻辑上的整体性和物理上的分布性，在讨论分 布式数据库的时候就有了全局数据库( 逻辑上) 和局部数据库( 物理上) 的概念。 分布式数据库系统有两个重要的组成部分：分布式数据库( d i s t r i b u t e dd a t a b a s e s y s t e m ，d d b s ) 和分布式数据库管理系统( d i s t 曲u t e dd a t a b a s em a n a g e m e n ts y s t e m ， d d b m s ) 。 分布式数据库管理系统是分布式数据库系统的一组软件，负责管理分布环境中数据 的存取、一致性和完备性。同时，由于数据的分布性，在管理机制上还必须具有计算机 网络通信协议的分布管理特性。 4 2 分布式数据库系统概述 2 1 1 分布式数据库系统的特点 根据上述分布式数据库系统的定义，可知分布式数据库系统具有四个基本特点： ( 1 ) 物理分布性：数据不是存在一个站点上，而是存储在计算机网络的多个站点上。 ( 2 ) 逻辑整体性：数据物理分布在各个场地，但逻辑上是一个整体，它们被分布式 数据库系统的所有全局用户共享，并由一个分布式数据库管理系统统一管理。 ( 3 ) 站点自治性：各站点上的数据由本地的局部数据库管理系统管理，具有自治处 理能力，完成各自站点的应用。 ( 4 ) 站点间协作性：各站点虽然具有高度的自治性，但是又相互合作构成一个整体。 由上述四个基本特点，可以得出分布式数据库系统的其他特点，包括： ( 1 ) 数据独立性：数据独立性是数据库方法追求的主要目标之一。分布式数据库系 统的数据独立性除了数据的逻辑独立性与数据的物理独立性之外，还包括数据分布透明 性。 ( 2 ) 集中与自治相结合的控制机制：在分布式数据库系统中，同一站点上的局部用 户共享本站点上的数据，并由本地数据库管理系统进行管理；而在全局范围内，全局用 户共享系统中各个站点上的数据，这种数据共享由集中的控制机制统一管理。 ( 3 ) 适当增加数据冗余度：在分布式数据库系统中，希望通过冗余数据来提高系统 的可靠性、可用性和改善系统性能。通过在多个站点上存储数据的副本，使得当某一站 点上的数据破坏时，系统仍可以正常运行；另外，系统可以选择用户最近的数据副本进 行操作，来减少通信代价，改善整个系统的性能。 ( 4 ) 事务管理的分布性：数据的分布必然造成事务执行和管理的分布性。简单的说 也就是一个全局事务的执行可分解为在若干站点上子事务( 局部事务) 的执行。事务的原 子性、一致性、隔离性、持久性以及事务的恢复也都应该具有分布性特点。 2 1 2 分布式数据库系统的分类 ( 1 ) 按局部数据库管理系统的模型的差异，可以将分布式数据库系统分为以下三类： 同构同质型d d b s ：各个站点都采用同一类型的数据模型，例如，都是关系型， 并且是同种类的d b m s ，如都是o r a c l e 类型。 同构异质型d d b s ：各个站点采用同一类型的数据模型，例如，都是关系型， 但是d b m s 的种类不同，如d b 2 、o r a c l e 、s y b a s e 、s q ls e e r 等。 异构型d d b s ：各个站点的数据模型不同，甚至d b m s 类型也不同。例如，有 关系型数据库、有面向对象型的数据库【2 i 2 2 j 。比如同一个分布式数据库系统中既存在关 系型的o r a c l e ，m y s q l 结点，也存在面向对象型的d b 4 0 【2 3 】的节点等。 ( 2 ) 按分布式数据库系统的全局控制系统的类型可以将分布式数据库系统分为以下 5 西安科技大学硕士学位论文 三类： 集中型d d b s ：d d b s 中的全局信息位于一个中心站点上。 分散型d d b s ：每一个站点上包含全局控制信息的部分内容。 可变型d d b s ：所有站点分为两组，一组站点包含全局控制信息副本，称为主 站点；另一组站点不包含全局控制信息的副本，称为副站点。 2 2 数据分片和数据分布 数据分片与数据分布是分布式数据库中的两个重要概念。事实上，分布式数据库大 部分问题都与数据分片及数据分布有关。它对整个系统的可用性、可靠性、安全性及效 率都有极大的影响，同时也与分布式数据库系统的其他方面密切相关，尤其是分布式查 询处理问题，往往和数据的分片和分布问题相互交织在一起。 2 2 1 数据分片 数据分片( d a t af r a g m e n t a t i o n ) 也称作数据分割，是分布式数据库的特征之一，在一 个分布式数据库中，全局数据库是由各个局部数据库逻辑组合而成，各个局部数据库是 由全局数据库的某种逻辑分割而获得。在分布式数据库中数据存放的单位是数据的逻辑 片段。对关系型数据库来说一个数据库的逻辑片断是关系的一部分。数据分片有三种基 本方法如下： ( 1 ) 水平划分：水平分片的并集和原始关系相等。分片之间通常没有交集。每个分 片是原始关系所有数据行的子集合。图2 2 就是一个水平划分的例子。 t i de i dn 锄e c i t y t 15 3 l lj o n e sn e wy - o r k t 25 31 2s m i t h c h i c a g o l t 35 3 1 3 m a r yc h i c a g o t 45 3 1 4k 吣 b o m b a y t 55 3 1 5k a t e l a 图2 2 水平划分示意图 ( 2 ) 垂直划分：垂直分片必须是一个无损连接的分解。垂直划分时，每个分片是原 始关系所有数据列的子集合。图2 3 给出一个垂直划分的例子。 6 2 分布式数据库系统概述 t l de i dn 锄e c i t y t l5 3 l lj o n e sn e w 、r o r k t 25 3 1 2s m i t h c h i c a g o t 3 5 3 1 3 m a r yc h i c a g o t 45 3 1 4 k 咐b o m b a y t 55 3 1 5k a t el a 十 人；古。 图2 3 垂直划分示意图 ( 3 ) 混合划分：水平分片和垂直分片混合使用。 在对数据进行片段划分的时候要遵循以下原则： ( 1 ) 完备性条件：必须把全局关系的所有数据映射到各个片断中，不允许有属于全 局关系的数据却不属于它的任何一个片断。 ( 2 ) 可重构条件：必须保证能够由同一个全局关系的各个片断来重建该全局关系。 对水平分片可用并操作重构全局关系，对垂直分片可用连接操作来重构全局关系。 ( 3 ) 不相交原则：要求一个全局关系被分割之后所得到的各数据片段互相补重叠( 对 水平分片) 或者只包含主键重叠( 对于垂直分片) 。 2 2 2 数据分布 数据分布( d a t ad i s t 曲u t i o n ) 是指在计算机网络各站点上的分布策略。分布式数据库 系统中的数据不是存储在一个站点上，而是根据需要将数据划分成逻辑片段，按某种策 略将这些片段分散地存储在各个站点上。常用的数据分布策略有如下几种： ( 1 ) 集中式：所有数据片段都安排在同一个站点上。这种分布策略使系统中所有活 动都集中在单个站点上，比较容易控制。但所有检索和更新必须通过该站点，使这个站 点负担过重，容易形成瓶颈。一旦这个站点出现故障，将会使整个系统崩溃，因而系统 的可靠性较差。 ( 2 ) 分隔式：所有数据只有一份，被分隔成若干逻辑片段，每个逻辑片段被指派在 一个特定的站点上。这种分布策略可以充分利用各站点上的存储设备，数据的存储量大。 检索和更新本地数据有局部自治性，系统有可能发挥并发操作的潜力，系统的可靠性有 所提高，当部分站点出现故障后，系统仍可能继续运行。因为数据在不同站点需要进行 通信，以及分别在各个站点上读取数据，所以对于全局性的查询操作，所需要的存取时 间超过集中式分布方式。 ( 3 ) 复制式：数据在每个站点上重复存储，也就是每个站点上都有整个数据库的一 7 西安科技大学硕士学位论文 个完整的副本。这种分布策略的可靠性最高，响应速度快，数据库的恢复也容易实现， 可以从任何一个站点得到数据副本。但是要保持各站点上数据的一致性则比较复杂且代 价高。另外，整个系统的数据冗余很大，系统的数据容量只是一个站点的数据容量。 ( 4 ) 混合式：这是一种介于分隔式和复制式之间的分布方式。数据库分成若干可相 交的子集，每个子集安置在一个或多个站点上，但是每一站点未必保存全部数据。混合 式兼顾了分隔式和全复制式两个方式，获得了两者的优点，但是也带来了两者各自的复 杂性。这种分布策略的灵活性大，对各种情况可分别对待，以提高整个系统的效率。 2 3 连接相关运算 连接也称作0 连接。它是从两个关系的笛卡尔积中选取属性之问满足一定条件的元 组。记作： r o 。s a o b = t 凡i t r r 人t s s 八t r 【a 。t s 【b 】) ( 2 1 ) 其中a 和b 分别为r 和s 上度数相等，且可比的属性组，0 是比较运算符。连接运算 从r 和s 的广义笛卡尔积r s 中选择( r 关系) 在a 属性组上的值和( s 关系) 在b 属性组 上值满足比较关系0 的元组。 连接运算中有两种最为重要也是最为常见的连接：等值连接和自然连接。 当0 为“= ”的连接运算称作等值连接。等值连接从关系r 和s 的广义笛卡尔积中选 取a 和b 属性相等的那些元组。记作： r s a = b 2 饥i t r ra t s sa “a 】= t s b 】) ( 2 2 ) 自然连接是一种特殊的等值连接，要求两个关系中进行比较的分量必须是相同属 性，并在结果中把重复的属性去掉。即如r 和s 有相同的属性b ，则自然连接可记作： r s = t 凡i t r r 人t s s 人t r b 】= t s 【b ( 2 3 ) 半连接操作是由投影和连接操作导出的一种关系代数操作。 假定有两个关系r 和s ，设r 中属性a 和s 中属性b 为两个关系的公共属性，则 半连接操作有两种可能，可以分别记作： r o c a ：b s2 冗r ( r a ：b s ) = r a ：b ( 兀b ( s ) ) ( 2 4 ) s o c a - b r = 7 【s ( s a ：b r ) = s a ：b ( 兀a ( a ) )( 2 5 ) 则r 和s 连接操作可以分解为： r o 。s = ( s o c r ) 0 0 r = ( r o c s ) s( 2 6 ) 这旱要注意的是，连接操作、等值连接、自然连接操作都符合交换率和结合率，而 半连接操作只符合结合率，不符合交换率。下面给出一个例子用来对比等值连接、自然 连接、半连接。首先给定两个关系r 和s ，如表2 1 ( a ) 和2 1 ( b ) 所示。 8 2 分布式数据库系统概述 表2 1 ( a ) 关系r ： b b l b 2 b 3 b 3 b 5 e - _ 3 7 l o 2 2 表2 1 ( b ) 关系s ： 属性b 为两个关系的公共属性，在这个属性上分别作等值连接、自然连接、r 半连 接s 、s 半连接r ，表2 2 、2 3 、2 4 、2 5 为对应运算的结果。 表2 2 关系r 和s 等值连接的结果 表2 4 关系r 和s 半连接的结果表2 5 关系s 和r 半连接结果 be b 2 b 3 b 3 3 7 1 0 2 9 西安科技大学硕士学位论文 从表2 4 和表2 5 中可以清楚的看到半连接运算不具有交换率，这个性质是大多数 半连接查询优化算法的基础。 2 4 分布式数据库的查询步骤 在分布式数据库中，用户可以根据全局数据模式用全局查询语言对多个局部数据库 同时进行查询。一个全局查询一般要经过三步处理【2 4 】： ( 1 ) 把全局查询分解成多个逻辑子查询，每一个子查询对应一个局部数据库中的数 据，分解后的子查询仍是用全局查询语言表示的。 ( 2 ) 如果全局查询语言与局部数据库的查询语言不同，还要将每一个逻辑子查询都 转换成相应的局部数据库的本地语言，并传到相应的局部数据库中执行。 ( 3 ) 子查询的结果返回并组合成最终的查询结果。 不同的查询分解对应不同的系统性能，因此为达到优化系统性能的目的，还需要相 应的查询优化器。查询分解程序确定出一个执行计划，说明需要访问哪些局部数据库， 如何拼装中间结果，在哪个站点执行全局处理等，最后启动执行查询计划等，简单的查 询过程如图2 4 所示。 图2 4 分布式数据厍甭询流程图 这里也简单举一例说明分布式数据库查询流程。 假设对关系模式s ( 钆b ，c ，d ) 进行水平分片，得到两个子模式s - l ( a ，b ，c ，d ) 和 s _ 2 ( a ，b ，c ，d ) ，其中s _ 1 对应的数据是属性c 的值大于等于0 的记录，而s _ 2 对应的数据 是属性c 的值小于o 的记录，显然 s - 1 ，s - 2 ) 是s 的一个划分，两者不可能存在相交。 对s 做以下查询： s e l e c t 木舶ms w h e r eal i k e 0 2 0 a n dc 3 0 1 0 2 分布式数据库系统概述 显然该查询的目标数据只在分片s1 中，则可直接用局部表名s1 代替全局表名s ， 将上述查询转换为： s e l e c t 矗ms - 1 、v h e r eal i k e 0 2 0 a i l dc 3 0 此时，分布式查询就相当于对一个本地或远程局部数据库进行本地或远程查询，而 无需进行复杂的查询分解。 如果在不同的局部数据库中存在数据相交时，查询分解则相对比较复杂。以全局数 据模式中的学生s t l l d e n “n o ，n a n l e ，a g e ，s e x ，c l a s s ，g r a d e ) 为例，对其进行垂直分片，使其分为 咖d e i l t - l ( n o ，n a m e ，a g e ，s e x ) 和s t u d e n l 2 ( n o ，n 锄e ，c l a s s ，g r a d e ) 两个局部数据模式，显然这两 个局部模式是存在相交的。例如下面的查询语句要查询s t u d e n t 表的所有信息： s e l e c t 木丘o ms t u d e n t 、h e r ea g e 2 5 该查询的目标数据存放于分片s t u d e n t1 和咖d e n t2 中，则必须将该全局查询语句 分解为对两个局部数据库进行访问的子查询语句。通过查找全局数据模式与局部数据模 式之问的映象信息，将查询语句转换为： s e l e c tr l o ，彻m e ，s t u d e i l t _ 1 a g e ，s t u d e i i l l s e x ，s t u d e n t _ 2 c l a s s ，s t u d e n t - 2 g r a l d e f r o ms t u d e n l l ，s t u d e n t 一2 w h e r e 咖d e n l l l a g e 2 5a n ds t u d e n l l n o = s t u d e i l t - _ 2 n 0 进一步分解为对s t u d e n tl 表进行子查询的语句q 1 为： s e l e c tn o ，n a m e ，a g e ，s e x f r o ms t u d e n l l w h e r ea g e 2 5 分解为对s t u d e m2 表进行子查询的语句q 2 为： s e l e c tn o ，n a m e ，c l a s s ，掣a d e f 而ms t u d e n t _ 2 若无查询优化处理，则将分别执行局部数据库的查询语句q l 和q 2 ，并且分别返回 局部查询结果q 1 和q 2 ，再对局部查询结果q 1 和q 2 根据公共连接属性n 0 进行自然连 接操作，连接结果就是最终的全局查询结果。 2 5 小结 本章主要介绍了分布式数据库的一些基本概念：数据分片，数据分布，连接运算， 以及分布式数据库的查询步骤，为下一章具体的分布式查询优化算法作一些铺垫。 西安科技大学硕士学位论文 3 典型分布式数据库查询优化算法 这一章将对现有应用比较广泛的一些分布式数据库查询优化算法进行分析，主要包 括如下内容： 在第一、二、四小节中介绍了三种较为常规的优化策略：关系代数等价变换、半连 接以及连接。 在第三小节中将详细阐述基于半连接优化的s d d1 及其改进、衍生算法。 在第五小节分析了基于连接的哈希划分等值连接查询优化算法。 3 1 基于关系代数等价变换的优化方法 基于关系代数等价变换的优化算法使用启发式优化方法对关系代数表达式进行优 化。在关系代数运算中，对效率影响最大的运算是笛卡儿积和连接操作，为此，学者们 引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小f 2 5 】。 ( 1 ) 尽可能早地执行选择操作； ( 2 ) 尽可能早地执行投影操作； ( 3 ) 避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起 来一起做。 基于关系代数等价变换规则的优化的基本思想在于把查询问题转变为关系代数表 达式，分析得到的查询语法树，按等价变换规则优化。算法首先利用关系代数等价变换 规则，把查询树中的连接和合并操作尽可能上提，选择和投影操作尽可能下移到片段的 定义处。然后判断是水平分片还是垂直分片，若为水平分片，则把分片条件与选择条件 进行比较，去掉存在矛盾的片段，如果只剩下一个片段，就可以去掉一个并操作。若为 垂直分片，则把片段的属性集与投影操作所涉及的属性集进行比较，去掉无关的所有片 段。如果只剩下一个垂直片段，就可以去掉一个连接操作，从而达到优化查询的目的。 以全局数据模式中的学生表s t i l d e n t ( n o ，n 锄e ，a g e ，s e x ，c l 船s ，伊a d e ) 为例，先对学生表 s t l l d e n t 垂直分片，使其分为咖d e n l l ( n o ，n 锄e ，a g e ，s e x ) 和s t u d e n l 2 ( n o ，n 踟e ，c l a s s ，g r a d e ) 两个数据模式，再对咖d e n l l ( n o ，n a m e ，a g e ，s e x ) 水平分片，使其分为s t u d e n l l l ( s e x = m ) 和s t u d e n t1 2 ( s e x = f ) 两个数据模式，最终形成s t u d e n t1 l ( s e x = m ) 、咖d e n t1 2 、s t u d e n t2 三个局部数据模式。现在要查询性别为男性并且成绩在9 0 分以上的所有学生的姓名， 查询的s q l 语句为： s e l e c tn a m e f r o ms t u d e n t w h e r es e x = m a n dg r 乏l d e = 9 0 1 2 3 典型分布式数据库优化算法 其关系代数表达式为： 踟e ( o 辩x = m n g r a d e = 9 0 ( s t u d e n t ) ) 关系代数表达式的查询树如图3 1 所示。 o 辩x m 。n g 隋d e 芒9 0 s t u d e n t 图3 1 关系代数表达式的查询树 对应片段上的查询树如图3 2 所示。 7 k 锄e s t u d e n l l n o t u d e n t - 2 7 【n o n 锄e o s e x d m u s t i l d e n t - ls t u d e i i t 一2 7 c g g m d 2 9 0 图3 2 对应的片段上的查询树 由图3 2 可以看出s t u d e n t _ 1 2 的分片条件与查询选择条件矛盾，故去掉s t u d e l l t - 1 2 片段，也就去掉了一个合并操作，同时还去掉了一个对s t u d e n t _ 1 1 片段的一个选择操作， 从而达到了优化的目的。 优化后的查询树如图3 3 所示。 1 3 eia 厮j l 西安科技大学硕士学位论文 o 。s t u d e n t _ 1 n o = s t u d e n t _ 2 7cnomme兀 i s t u d e n l l l o g r a d 2 9 0 i s t u d e n t _ 1 2 图3 3 优化后的查询树 3 2 基于半连接操作的优化算法 数据在网络中传输时，以整个关系( 也可以是片段) 传输是一种冗余的方法。在一个 关系传输到另一场地后，并非每个数据都参与连接操作或都有用，因此，不参与连接的 数据或无用的数据不必在网络中来回传输。基于半连接的优化策略的基本原理就是采用 半连接操作，尽量在网络中只传输参与连接的数据，放弃不参与连接的数据。 可以采用半连接方法计算连接操作的值。设关系r 和s 的公共属性为a ，其具体运 算流程如图3 4 所示。 站点l ( 关系r )站点2 ( 关系s ) 盆堡箍 锄a ( s ) r 兀“s ) 堡捡， ( i t 0 0 7 c 。( s ) ) s 图3 4 基于半连接的查询优化算法执行示例 由2 3 节式( 2 6 ) r s = ( s o c r ) r2 ( r o c s ) 0 0 s 等式右边的式子称为半连接程序。下面讨论这个半连接程序的操作过程和传输代 价。其传输代价用t = c o + c l x 估算【l l 。 1 4 eman 兀 3 典型分布式数据库优化算法 ( 1 ) 在站点2 计算关系s 在属性a 上的投影7 “s ) 。 ( 2 ) 把锄( s ) 的结果从站点2 传到站点1 ，其传输代价为： t 2 l = c o + c l s i z e ( a ) v a l ( a s 】)( 3 1 ) 其中s i z e ( a ) 表示属性a 的长度，v a l ( a 【s 】) 表示关系s 中属性a 的不同值个数。 ( 3 ) 在站点l 计算半连接，设其结果为r t ，则r t = r o c s 。实际上，这个操作是执行 r 0 0 兀“s ) 。 ( 4 ) 把r 从站点1 传到站点2 ，其传输代价为： t 1 2 = c o + c l s i z e ( r ) c a r d ( r )( 3 2 ) 其中s i z e ( r ) 是r 中元组的数目，c a r d ( r ) 是r f 的元组数。 ( 5 ) 在站点2 执行连接操作r s 。 显然，步骤( 1 ) 、( 3 ) 、( 5 ) 无需传输费用，所以执行这样一个半连接程序，总的传输 代价为： t 半= c o + c l s i z e ( a ) v a j ( a s 】) + c o + c 1 s i z e ( r ) c 刮r d ( r ) = 2 c o + c l ( s i z e ( a ) v a l ( a s 】) + s i z e ( r ) c a r d ( r ) ) ( 3 3 ) 上文说过半连接运算没有交换率，因此另一等价半连接程序( s o c r ) r 可能具有不 同的传输代价，通过对它们的代价进行比较，就可以确定r 和s 的最优半连接程序。下 面举例说明。 假设站点1 有一职工关系：e m p ( e n o ，e n 锄e ，) ，其属性为职工编号( 6 字节) 、姓名( 1 0 字节) 、。假设每个记录是1 0 0 字节，关系中有1 0 0 0 0 条记录，那么关系的大小为 1 0 0 1 0 0 0 0 = 1 0 0 0 0 0 0 字节。 在站点2 有一部门关系：d e p t ( d n o ，d n 锄e ，e n o ) ，其属性为部门编号( 4 字节) 、名称 ( 1 0 字节) 、和部门经理的职工编号( 6 字节) 。假设每个记录是3 5 字节，关系中有1 0 0 个记录，那么关系的大小为3 5 1 0 0 = 3 5 0 0 字节。 现在假设用户在站点2 上有一个查询：检索每一部门的名称和部门经理的姓名