（计算机应用技术专业论文）数据库中间件的查询优化机制研究.pdf

摘要 数据库中间件是连接信息孤岛的“桥梁”，是所有中间件中应用最广泛、技 术最成熟的一种。在集成异构数据库时，数据库中间件内在的优化和转换机制提 高了数据访问的执行效率。然而，随着i n t e r n e t 信息网络的飞速发展及大型分布 式处理的出现，数据库中间件面临诸多问题的挑战：庞大的用户群、并发的查询 请求、众多的数据源站点、海量数据访闯。 为了解决上述问题，本文提出了一种基于带权查询树的数据查询优化机制的 新数据库中间件方案。在数据查询优化方面，降低查询执行代价、减少数据迁移 量和缩小查询响应时间是数据全局查询优化的重要目标。因此根据数据全局查询 优化在分布式条件下的特点，给出了分布式环境下的查询优化算法：基于带权查 询树的优化算法。该算法以优化查询操作的逻辑执行位置来降低的执行代价，优 化查询操作的物理执行位置减少数据迁移量作为数据库中间件系统的查询优化 核心。同时，为了满足该算法的运行要求，本文对现有的数据库牵闯件系统进行 改进，设计了基于带权查询树和代码迁移的数据库中间件的体系结构。 最后，本文通过对一个查询实例的分析和评估来论证这一新方案的可行性。 关键词：数据库中间件、全局查询优化、带权查询优化树、基于带权查询树和代 码迁移的中间件体系结构 a b s t r a c t b r i d g i n ge a c hi n f o r m a t i o ni s o l a t e di s l a n d d a t a b a s em i d d l e w a r ei s o n eo ft h e m o s tw i d e l yu s e da n dm a t u r e s tm i d d l e w a r e w h e ni n t e g r a t i n gt h eh e t e r o g e n e o u sd a t a s o u r c e s ，d a t a b a s em i d d l e w a r ei m p r o v e st h ee f f e c t i v eo fi m p l e m e n to f d a t aq u e r yb y u s i n g i t sb u i l t - i n t oo p t i m i z a t i o na n dt r a n s l a t i o n h o w e v e r , w i t ht h e r a p i dd e v e l o p m e n t o fi n t e r a c te n t e r p r i s er e q u i r e m e n t sf o rd i s t r i b u t e dp r o c e s s i n ga n di n t e m e ti n f o r m a t i o n n e t w o r k , d a t a b a s em i d d l e w a r ei sc h a l l e n g e db ys o m ep r o b l e m s ：l a r g en u m b e r so f u s e r s ，t h ec o n c u r r e n tq u e r yr e q u e s t s ，al o to f d a t as o u r c es i t e sa n dm a s s i v ed a t aa c c e s s t h e s ep r o b l e m sc a l lb er e d u c e dt os u c ht w os u b j e c t s ：t h ea r c h i t e c t u r eo fd a t a b a s e m i d d l e w a r ea n di t sq u e r y o p t i m i z a t i o n m e c h a n i s m t os o l v et h e s ep r o b l e m sd i s c u s s e da b o v e ，t h et h e s i sp r e s e n t san e wd a t a b a s e m i d d l e w a r es o l u t i o nb a s e do nd a t aq u e r yo p t i m i z a t i o nm e c h a n i s mo faw e i g h t e d q u e r yt r e e ( w - t r e e ) i nt h eg l o b a lq u e r yo p t i m i z a t i o n ，d e c r e a s i n gt h ec o s to fq u e r y p e r f o r m a n c e ，r e d u c i n gt h es i z e o fd a t as h i p p i n ga n dl o w e r i n gt h et i m eo fq u e r y r e s p o n s e a r ei m p o r t a n t o b j e c t s t h e r e f o r e ，b a s e d o i lc h a r a c t e r so f d a t a g l o b a lq u e r y o n t h ec o n d i t i o no fd i s t r i b u t e de n v i r o n m e n t ，a l lo p t i m i z a t i o na l g o r i t h mi sp r e s e n t e df o r t h eg l o b a lq u e r y ：a na l g o r i t h mo f o p t i m i z a t i o nb a s e do n aw e i g h e dq u e r yt r e e t h e a l g o r i t h m d n i m i z e st h ec o s to fo p e r a t o r sb yu s i n go p t i m i z a t i o no fl o g i c a lp e r f o r m p l a c e m e n ta n dt h es i z eo fd a t as h i p p i n gb yu s i n go p t i m i z a t i o no f p h y s i c a lp e r f o r m p t a c e m e n t a t1 h e 跚雌缸，t b ep r e s e u t1 ) a t a b a s em i d d l e w 越- es y s t e m si s 讧删e d t o a d a p t t ot h e r e q u i r e m e n t s o fr u n n i n gt h e a l g o r i t h m ，d e s i g n i n g m o w c h a ( m i d d l e w a r eb a s e do naw - t r e ea n dc o d e s h i p p i n ga r c h i t e c t u r e ) a tl a s t , t h i st h e s i s a n a l y z e sa n d e v a l u a t e sa ne x a m p l et od e m o n s t r a t et h e f e a s i b i l i t yo f t h en e ws o l u t i o n k e y w o r d s ：d a t a b a s em i d d l e w a r e ,g l o b a l q u e r y & o p t i m i z a t i o n ，w - t r e e , m o w c h a i i 河海大学硕士学位论文 数据库中间件的查询优化机制研究 第一章绪论 1 1 本文研究背景 数据库中间件【1 1 是连接信息孤岛的“桥梁”，信息孤岛的“终结者”。一般而 言，数据库中间件在现代企业信息环境下提供了通用一致的数据访问技术，包括 应用在关系、层次、面向对象的数据库甚至在文字档案中等数据库系统中。在连 接异构数据库时，数据库中间件内在的优化和转换提高了数据访问的执行效率。 然而，随着大型分布式处理的出现及i n t e r a c t 信息网络的飞速发展，数据库中间 件面临诸多问题的挑战：并发的查询请求、众多的数据源站点、海量数据访问、 庞大的用户群。这就会使大量的数据在网上迁移，导致系统的吞吐量减少和响应 时间减慢，极端时甚至会由于负载过重带来网络瓶颈而造成系统的瘫痪。因此现 在的网络信息系统对数据库中间件的性能提出了更高的要求叫： 1 数据查询的代价最小； 2 数据查询的响应速度最快； 3 数据查询执行的并发控制； 4 系统负载的平衡等： 数据查询的总代价包含三个方面的代价：查询运算代价、v o 代价和网络代 价。查询运算代价是指查询中运算符执行时c p u 所花费的时间代价。i o 代价是 指查询的执行所需要的输入，输出时间代价。网络代价是指数据在网络上的传输 迁移时间代价和建立传输连接的时间代价。数据查询的响应时间是指查询开始提 交直到获得第一个结果之间的时间。网络中多处理器的存在提供了并行数据处理 和传输的机会，应充分利用可以加快查询的响应速度。并发控制是指数据库中间 件系统对多用户并发查询的处理。系统负载的平衡是指庞大的用户群在某时间段 提出查询请求时，数据库中间件系统的某部分的负载过重，导致系统无法响应 用户请求，当数据量超过一定限度时可能导致系统瘫痪。 1 2 数据库中间件的相关研究 1 2 1 数据库中间件系统的栩冶： 数据库中间件是应用广、技术成熟、发展前景好的一种中间件。数据库中间 件对数据库系统集成构成数据库中间件系统。 数据库中间件作为前端客户机和后端数据库之间的一个中间层，所起的作用 塑塑查兰堡主兰堡笙苎 墼塑壁里里堑堕奎塑垡垡璺! ! ! ! 生 自然也是桥梁的作用，它允许应用程序与本地或异地的数据库之间进行通信a 它 提供了一系列应用程序接口a p i ，通过中间层而不考虑操作系统及网络来访问数 据库。 一 一般来说，数据库中间件系统遵循这样的体系结构( 如图l - l 所示) ：以数 据集成服务器为中心，它为客户提供对每个数据源可用数据的统一视图和透明访 问。这样的统一数据视图是通过抽取每个数据源使用的局部数据模型，得到一个 全局数据模型实现的。 图1 1 数据库中间件系统的体系结构 集成服务器的具体部署主要有两种方法嘲：商用数据库服务器( ac o m m e r c i a l d a 舡l b 鼬es e r v 哪或者介体系统( am e d i a t o rs y s t e m ) 。商用数据库服务器方案中，通 过数据库网关来配置一个商用数据库服务器去存取远程数据源，数据库网关提供 了远程数据的透明访问机制。对于远程数据的存取，原本是由数据库服务器直接 访问远程数据源的，但是，这里存在数据源之间的异构问题，需要对异构数据源 提供的数据预先进行集成。现在，数据库网关加在了数据库服务器和数据源的中 间，首先对各数据源的局部模式进行集成，用一个统一的全局模式表示。当系统 程序通过访问数据库以获取数据时，只要遵循全局模式来提出对数据的访问即 可，不用关心要访问的数据库类型和性能，真正做雯l 无关和透明。 在第二个方案中，为分布式查询处理定制的中介体( m e c u a t o r ) 服务器作为 集成服务器。介体( m e d i a t o r ) 服务器利用包裹器( w r a p p e r s ) 的功能将数据源的信 息存取和传输到全局数据模型中。 在这两种中间件解决方案中，全局数据模型下的用户定义的、特定应用的数 据类型和查询运算符号包含在连接到客户、集成服务器、网关或系统部署的 w r a p p e r s 的库中。这样的优点是：从多数据源整合数据：保持“瘦”客户端：复 用现存服务器。 2 1 2 2 数据库中间件系统的现状 当前数据库中闻件应用广泛、产品较多，大多产晶还是建立在一些基本的标 准接口技术5 】基础上的产品，如c g i 、a p i 、o d b c 和j d b c ，特别是j d b c 技术。 1 通用网关接口( c g i ：c o n l r l o ng a t e w a y i n t e r f a c e ) 通用网关接口是一组关于如何在客户端w e b 浏览器、w e b 服务器与c g i 应 用程序之问传递信息的规范，是瓤1 p ( h y p e m x t t r a n s f e rp r o t o c 0 1 ) 服务器与程 序进行“交谈”的一种方式。 c g i 接口为从h t t p 服务器内执行程序提供了一种简单易用的方法，可以 使用这种机制来刨建动态文档以及作为与h t t p 服务器之外的服务程序之间的 接口。c g i 接口有许多好处，包括服务器软件之闻的可移植性，以及大量的公 用领域程序( 免费程序) 和为它设计的开发工具。最大的优势就在于，几乎所有 的w e b 服务器都支持c g i 程序。但是，c g i 接口也存在着一些不足，其中最主 要的就是性能问题，特别是在需要多个数据库连接的多用户应用程序中尤其明 显。c g i 程序不能被多个客户请求共享，当一个新的请求到达时，即使c g i 程 序有一个实例在运行，也必须再启动个新的实例。并发请求越多，服务器上创 建的并发迸程也越多。为每个请求创建一个应用进程会消耗较多时间且需要大量 内存。同时限制了应用程序自身可用的资源。最终导致性能降低，增加等待时间。 2 专用a p i ( a p p l i c a t i o np r o g r a m m i n g i n t e r f a c e ) 针对c g 程序的上述不足之处，为了提高w e b 服务器与数据库服务器之间 的通信效率和性能，各大w e b 服务器厂商和数器库厂商纷纷推出各自的专用 a p i 。 在w e b 服务器与数据库服务器的连接方案中，m i c r o s o f t 和n e t s c a p e 分别推 出了适用于各自w e b 服务器的i s a p i ( i n t e m e ts e r v e ra p p l i c a t i o np r o g r a m m i n g i n t e r f a c e ) 和n s a p i ( n e t s c a p es e r v e r a p p l i c a t i o np r o g r a n a m gi n t e r f a c e ) 。与c g i 程序是作为独立的进程运行不同，i s a p i 和n s a p i 都是以动态链接库的形式存 在的，且一般与w e b 服务器软件处在内存的同一地址空间中，因此每次调用时 是在内存中运行相应的程序段，蔼不是像c g i 那样需要启动新的进程，所以i s a p i 和n s a p i 应用程序的效率和性能较之c g i 程序有大幅度的提高。当然，采用这 种类型的a p i 也存在一些缺陷，例如，缺乏通用性；i s a p i 和n s a p i 相互之间 不兼容，程序可移植性差，开发出的应用程序只能在相应的w - e b 服务器上和操 作系统上运行；由于采用了动态链接库的形式，一旦代码质量较差就比较容易造 成服务器系统的崩溃；并且进行程序设计时会更复杂，开发难度大。丽三大数据 库厂商o m c l e ，s y b a 始和i n f o r m i x 提供的w 曲服务器与数据库服务器的接口方 案都与各自的数据库产晶紧密集成，因而无论是在效率、性能还是安金性方面都 河海大学硕士学位论文 数据犀中同件的查询优化机铺研究 达到了较为理想的水平。但也正是由于这种紧密集成，导致了它们只能局限于各 自豹数据库产品之上，所以兼容性和可移植性差。 3 开放数据库连接( o d b c ：o p e n d a t a b a s ec o n n e e t i v i t y ) 1 9 9 1 年1 1 月，微软宣布了o d b c ，次年推出可用版本。1 9 9 2 年2 月，推出 了o d b cs d k 2 0 版。 o d b c 是用来访问数据库系统的一个统一接口标准。它可以为c s 系统提供 连接客户端应用程序与服务器端各种数据源。o d b c 可以用来访问几乎所有类 型的数据库，包括o r a c l e 、a c c e s s 、s y b a s e 、m y s q l 、文本文件等。o d b c 克服 c g i 程序访问数据库效率低和专用a p i 可移植性差的缺陷，但是当事务的吞吐量 和通信效率很重要时【1 1 ，o d b c 就不能胜任了。 4 j a v a 数据库互连( j d b c ：j a v a , d a t a b a s ec o n n e c t i v i t y ) o d b c 较前述a p i 有较大的改进，但是存在不少缺点，如不容易使用，没 有面向对象的特性等。s u n 公司针对这些不足，而开发的j a v a 语言为接口的数 据库应用程序接口j d b c 。 j d b c 定义了j a v a 与数据库之阔的接口类库( j a v as q l 包) ，它是j a v a 语言 中执行s q l 语句的a p i ，它由一系列类和接口所组成，程序开发者可以通过这 些类和接口在j a v a 语言中建立与数据库的链接，执行s q l 语句和处理s q l 语句 返回的结果。它易于向任何关系数据库发送s q l 语句，支持对多种数据库的访 问。运用j d b ca p i ，只需写出单独一个程序就能够发送j d b ca l l 给相应的数 据库，如s y b a 船，o r a c l e 或i n f o r m i x 等。j a v a 语言的中性结构和j d b c 的开放性 使得程序员只需写一次程序就能让它到处运行。j d b c 是一个低层次的a p i ，它 是更高层次a p i 的基础。开发人员可以在d b c 的基础上，设计出用户更容易理 解、便于使用的更高层次的接口和工具。由于j d b c 技术的可操作性、可维护性 和安全性及事务处理能力、使用效率都比较高，因此具有很大的优势。 现有数据库中间件产品晕j 用上述接口作为底层接口的基础上，还增加了新的 功能，如数据源连接池、异构数据集成、数据查询的全局优化等。 在这些数据库中间件产品中，e j b f 4 】技术中的实体b e a n 是j 2 e e 规范下的数 据访问层a e j b 有两种主要类型b m p ( b e a nm a n a g e dp e r s i s t e n c 嚣) 和c w ( c o n t a i n e r m a n a g e dp e r s i s t e n c e ) 。 b m p 是在b e a n 中完成对数据d b c 的各种调用，即在实体b e a n ( e n t i t yb e a n ) 中，明确写入了具体的s q l 语句，如”h m e r t i 或n s e l e c t i t ，并且使用d a m s o u r c e 获得一个数据库资源以及连接( c o 衄e c 垃o n ) 从丽对数据库直接进行增加删除修改。 灵活但效率低。c m p 是在实体b e a n 中写入s e t x x x 或削d 0 0 ( 方法，并部署， 由e j b 容器自动完成对数据库的操作，效率高但灵活性差。二者均不能动态豁 署，部署后，服务器必须重启，可维护性差。 4 河海大学硕士学位论文 数据库中同件的查询优化机制研究 在数据库系统中，支持用户自定义的数据类型和用户自定义的函数，当前的 数据库中间件中，也需要支持这些数据类型和查询函数。m o c h a 2 , 3 1 ( m i d d l e w a r e b a s e do nac o d es h i p p i n ga r c h i t e c t u r e ) 是由m r o d r 7 l g u e z - m a r t7 m e z 和n r o u s s o p o u l o s 等人为美国n a s a 的e s i p f 0 1 a r t bs c i e n c ei n f o r m a d o np a r t n e r s h i p f e d e r a t i o n ) - 提的自扩展的数据中间件解决方案，用于分布式数据源间的相互连 接。m o w c h a 采用查询代码的自动分发部署技术以及基于数据的膨胀缩减 ( i n f l a t i n g - r e d u c i n g o f d a t a ) 的查询优化枧制，解决了查询将大量的数据在i n t e r a e t 中迁移的严重瓶颈问题。但是m o w c 珏a 的模块之一查询处理协调器参与了对 全局查询优化甚至参与了具体查询运算符的执行，将会导致该模块的负担过重， 在大量的用户访问下可能会出现系统性能下降，甚至瘫痪的可能。 1 3 本文目标及主要工作 如同上文所述，数据查询的代价、响应速度、并发控制、系统负载的平衡性 是数据库中间件系统的重要性能，其主要手段是通过对现有数据库中间件系统的 体系结构和查询优化算法进行分析和改造。因此，体系结构和查询优化算法对企 数据库中间件系统具有至关重要的作用和实际使用的意义。 本文主要工作如下： 1 探讨了当前查询优化规则和查询树的局限性，提出了基于一种带权查询 树的查询优化算法。 2 利用数据库中间件系统的一些研究成果，改进m o c h a 的体系结构，采 用本文提出的优化算法，解决了原有系统负载不平衡的问题。 3 结合实例对改进的体系结构和优化算法的分析与评价。 1 4 本文研究的主要内容 本章是绪论部分，主要介绍数据库中间件系统的一些基本概念、体系结构与 工作原理，并给出了国内外关于数据库中间件系统研究的背景及成果、以及本文 所作的工作简介。 第二章主要介绍数据查询优化机制的基本概念、优化途径、代价模式、全 局查询的层次结构、全局查询查询处理技术及全局查询查询优化技术。 第三章探讨了当前查询优化规则和查询树的局限性，提出了基于w - t r e e 的 查询优化机制。3 2 节提出了带权查询树；3 3 节带权查询树查询优化原理； 3 4 节实现带权查询树查询优化的算法，并分析了算法的复杂度。 第四章利用前一章提出的查询优化算法，介绍m o w c h a 的体系结构和结 构设计 第五章是对本文所介绍方法进行了测试和评估。 河海大学硕士学位论文 数据库中间件的查询优化机制研究 第六章总结全文并提出了进一步工作。 6 河海大学硕士学位论文 数据库中问件的壹询优化机制研究 第二章数据的查询优化机制 数据查询是数据库的最基本、最常用、最复杂的操作。数据库的查询一般都 是以查询语言表示，如用s q l 语言表示，或用关系代数表达式表示。用户提交 的查询请求出发，直到获得查询的结果，需要一个处理过程，该过程被称为查询 处理( q u e r yp r o c e s s i n g ) 。用户提出查询请求，得到查询结果，而不关心查询请求 的具体执行过程，而由d b m s 确定合理的、有效的执行策略。d b m s 确定这一 合理的、有效的执行策略的作用称为查询优化( q u e r yo p t i m i z a t i o n ) 。查询优化是 数据查询处理中重要和必要的一环，对系统的性能影响颇大。查询优化的益处的 最直接的表现是降低数据查询开销。 数据的查询优化机制在数据库中间件系统中同样发挥重要的作用。在分布式 环境下，数据库中间件系统用于集成数量庞大的数据源站点。数据库中间系统的 全局优化策略关系到客户查询请求的执行代价和查询的响应时间。 2 1 数据查询代价的目标函数 2 1 1 数据查询优化的目标 无论是集中式数据库，还是分布式数据库，降低数据查询的优化历来是数 据查询的经典问题。 在集中式环境下，查询优化的目标f 6 l 研在于为每个用户查询寻求总代价最小 的执行策略。通常，总代价是以查询处理期间的c p u 代价和f o 代价衡量的。 由于集中式环境下数据库系统大都运行在单个处理器的计算机上，使总代价最小 就意味着使查询的响应时闻最短。 在分布式环境下，常以两种不同的目标来考虑查询优化。一种目标是以总 代价最小为标准，除了像集中式环境一样考虑c p u 代价和u o 代价之外，总代 价还包括数据在网络迁移的代价。另一种目标是以每个查询的响应时间最短为标 准，因为分布式系统的数据站点，具有数据的分布性和一定的冗余性可以增加查 询的并行处理的可能性，从而可以缩减查询处理的响应时间，加快查询速度。在 分布式查询优化中，分布式查询常常兼顾使用这两种标准，根据应用系统的不同， 一种作为主要标准，一种作为辅助标准。 显而易见，与集中式查询相比，分布式的查询处理增加了新的内容和复杂性。 不同的查询处理方法，其查询的通讯费用和并行处理程度不同。虽然，在分布式 7 查询处理中也使用某些集中式查询处理中的技术和方法，但就其问题的规模和优 化的因素，有与集中式查询处理有本质的区别。 2 1 2 数据查询优化的准则 虽然不同的数据查询处理环境，有不同的查询处理目标，但是查询处理都遵 循一个基本的准则：使通信代价最低和响应时间最短，即以最小的总代价和最短 的响应时闻内获得目标数据。所谓晌应时间，是从接收查询到完成查询所需要的 时间。该参数与通信时间有关，也与局部处理时间有关；通信代价与所迁移的数 据量和通信次数成正比，通信代价还与分布式数据源所基于的网络类型有关，对 不同的通信网络有不同的查询优化处理方法。 2 1 ；3 数据查询的代价函数 根据前述查询优化目标和准则，设一个查询执行的预期开销为q u e r y c o s t ， 则： 在集中式中：q u e r y c o s t = ，钾：价+ c p u 代价 在分布式中：q u e r y c o s t = z o f e 价+ c p u 代价+ 通信代价 通信代价可用如下公式作粗略估算： t a n s f e r c o s t ( x ) = c o + c 1 + z 其中：x 为数据的迁移量，通常以b i t 为单位计算； c o 为通信初始化一次所花费的时间，它由通信系统确定，近似个常数， 以秒为单位； c 1 为传输率( 传输速度的倒数) ，即单位数据传输的时间，单位是秒b i t 。 2 1 4 数据查询策略的重要性 在分布式数据源查询中，查询优化包括两个内容：查询策略优化和局部处理 优化a 查询策略优化尤其重要，因为查询策略的优劣直接关系到查询的效率。 例2 - i 在教学数据库中，有： s ( s 挽s n a m e ，a g e ，s e x ) 有1 铲+ 4 个元组，在数据站点a 存放 c ( c # ，c n a m e ，t e a c 硒 r ) 有1 0 + 5 个元组，在数据站点b 存放 8 河海大学硕士学位论文 数据库中同件的查询优化机制研究 s c ( s # ，c 拌，g r a d e ) 有1 0 + + 6 个元组， 假定：若每个元组的长度均为1 0 0 b i t ； 通信延迟时间为1 秒。 在数据源a 存放 通信系统的传输速度为1 0 + + 4 b i “秒 问题：要求查出所有选修m a t h s 课的男学生的学号和姓名。 解在分布式数据的透明性支持下，s q l 语句是： s e l e c ts # s n a b 幢f r o m s ，s c ，c w h e r es s 撑= s c s 榉a n ds c c 撑= c c 萍( 连接条件) a n ds e x = m a n d 心r a 诬= m 删s ( 选择剁牛) 通信开销的估算公式是： t = 传输延迟时间c o + ( 传输的数据量xx 数据传输率c 1 ) = ( 传输次数x 1 ) + ( 传输的b i t 数l o + + 4 ) 为了实现这一查询，可以有六种可能的查询策略： 策略l ： a传cb o o s , s c 通恤次c 把关系c 传输到a 地，在a 处理查询，t l = l + ( 1 0 s * l o o 1 0 4 ) * 1 0 3 a 1 6 7 j r j q 9 策略2 ： o = o s s c 避信2 次 c 把关系s 和s c 传输到b 地，在b 地处理查询， t 2 = 2 + 0 0 4 + l o b * 1 0 0 1 0 4 * l o l o o 秒2 纠、时 策略3 ： 8 警昌 芯奄祷茗 先在a 地求出男学生的成绩元组有1 0 5 ，再根据c 带的值询问b 地，核实 是否c = m a t h s , 乃一( 2 l o s * 1 ) = 2 q 0 移* 2 3 天 策略4 ； 京2 先在b 地求出m a t h s 的元组，有1 0 个，再根据c 撑的值询问a 地的s ， s c 的连接，核实是否为选修m a t h s 的男生，t 4 2 ( 2 + 2 0 + 1 ) = 2 0 秒 9 河海大学硕士学位论文 数据库中间件的查询优化机制研究 策略5 ： 台竺塑竺：，吕 s , s c 通信1 次c 先在a 地求出男生选课元组，有1 0 5 个，再把结果传输到b 地，在b 地 执行查询，t 5 = 1 + ( 1 0 5 1 0 0 ) q 0 4 2 1 0 0 0 秒* 1 6 7 分钟 策略6 ： 乌_ 堂! 昌 s , s c 通信1 次c 先在b 地求出为m a t h s 的元组，有1 0 个，再把结果传输到a 地，在a 地执行查询，t 6 = 1 + ( 1 0 1 0 0 ) 1 0 4 一1 秒。 由此可见，一个好的查询处理应该使数据的传输量和通信次数最少，这样才 能使查询所花费的数据传输和，或通信时间减少，从而减少查询的总代价。 如果对第6 种方法利用分布式的并行处理，即在a 地选择男生和在b 地选 择m a t h s 课程名同时进行，这样总的处理时间还可以减少。 2 2 查询表示 2 2 1s q l 语言 查询是从数据库中检索数据的过程或命令。s q l 6 ，s a u c t u r e dq u e r y l a n g u a g e ，是关系数据库的标准语言。s q l 语言中的数据查询语言( d a t aq u e r y l a n g u a g e ，d q l ) ，是被大多数数据库系统支持的数据查询语言。 如前例所示，s q l 查询语句可以由为s e l e c t 子句、f r o m 子甸、w h e r e 子旬、g r o u pb y 子句和o r d e r b y 子句组成。s e l e c t 子旬指明需要查询的 项目，一般指列名，也可以是表达式。利用表达式，可以查询表中并未存储但可 导出的结果。f r o m 子句指明被查询的表( t a b l e ) 或视图( v i e w ) 名。w h e r e 子句说明查询条件。s e l e c t 、f r o m 和w h e r e 三个子旬构成最常用的、最基 本的s q l 查询语句。 s q l 语句可能含有w h e r e 子句。w h e r e 子句中包含一个随机的逻辑表达 式，而逻辑表达式中有常量和查询变量的范围。这样的子句可以被分解为“布尔 因子( b o o l e a n f a c t o r s ) ”的集合f 1 3 】，每个布尔因子作为一个不厨的t l 胃词， f e r e d i c m o r ) 来查询每一元组。在以下的讨论中，查询中的w h e r e 子旬中的布尔因子”，都 l o 塑塑查兰堕主兰丝堡茎 塑塑塞! 堕丝塑垡堡垫型蔓旰墨 称为谓词。谓词通常分为连接谓词( j o i np m d i c a t , ) ；选择谓词( s e l e c t i o n p r e d i c a t e ) 。 连接谓词是涉及多表的谓词，而选择谓词只是涉及单表的谓词。 2 2 2 关系代数 关系代数是一种抽象的查询语言，是关系数据操纵语言的一种表达方式，它 是用对关系的运算来表达查询的。关系代数的运算对象是关系，运算结果也是关 系。大多数s q l 查询语言都可转换为等价的关系代数表达式。常见的关系代数 操作有以下几种： ( 1 ) 投影操作( pj _ a ) 万。( 固 ( a 为关系r 中的属性列) ( 2 ) 选择操作( s l y ) o ，职)为逻辑表达式) ( 3 ) 连接操作( j n f ) 只a f s 为逻辑表达式) ( 4 ) 并操作( t 脚r u s ( 5 ) 乘积操作r s ( 6 ) 分组操作( g 鼬 例2 - i 的关系代数表达式是： 厅s # a 矗仃f ( s x s c x c ) ) ， 其中f 主“s j 撑= 5 s 却 ( s c 弹= c c 妁 ( 鼬* ；m ) , , ( c n a m e - - 埘粥譬 2 2 。3 查询树 数据库系统对个关系代数表达式表示的查询进行语法分析，可以得到一 棵语法树，该语法树称查询树【9 】。树中的叶子节点是关系名，树中的内部节点是 一个一元或多元的查询操作符，元组由树叶流商讨根，树的根是查询结果，因此 又称为操作符树( o p e r a t o rt r y ) 。查询树清晰、直观地描述了一个查询请求，而 且易于分析和调整查询问题的具体操作次序。 以s q l 语句表示的查询请求为例：查询树是一个s q l 语句的p q 部表现形 式，组成该语句的每个独立地部分都是分别存储的。该语句被分解后放在查询树 里的成员。查询树的成员有： 命令类型( c o m m a n dt y p e ) 这是一个简单的值，说明哪条命令( s e l e c t ，i n s e r t ，u p d a t e ，d e l e t e ) 生成这个查询树。 范围表( r a n g e t a b l e ) 范围表是一个查询中使用的关系的列表。在s e l e c t 语句里是在f o r m 关 键字后面给出的关系。每个范围表表示一个表或一个视图，表明是查询里哪个成 员调用了它。 结果关系( r e s u l tt e l a t i o n ) 这是一个范围表的索引，用于标识查询结果前往的表。 s e l e c t 查询通常没有结果关系表。特例s e l e c ti n t o 几乎等于一个 c r e a t et a b l e ，i n s e r t s e l e c t 序列， 在i n s e r t ，u p d a t e 和d e l e t e 命令里，结果关系是更改发生影响的表 ( 或视图! ) 。 目标列( t a r g e tl i s t ) 目标列是一列定义查询结果的表达式。目标列里的每个元素都包含着个表 达式，它可以为常量值，可以为一个指向某个范围表里面的关系的一个字段的 变量，可以为一个由函数调用，常量，变量，操作符等构成的表达式树。 条件( q u a l i f i c a t i o n ) 查询条件是一个表达式，它非常类似那些包含在目标列里的条目。这个表 达式的值是一个布尔值，通过此值来判断对最终结果行是否要执操作( i n s e r t ， u p d a t e ，d e l e t e 或s e l e c t ) 。它是一个s q l 语句的w h e r e 子句。 连接树a o 妫 查询的连接树显示了f r o m 子句的结构。对于象s e l e c tf r o ma ，h ，c 这 样的简单查询，连接树只是一个f r o m 项的简单列表，因为我们允许以任意 顺序连接它们。但如果使用了j o i n 表达式一尤其是o u t e r j o i n 的时候，就 必须按照该连接显示的顺序进行连接。连接树显示j o 甜表达式的结构。与 特定的j o i n 子旬( 来自o n 或者u s i n g 表达式) 相关的限制做为附加在那 些连接树节点的条件表达式存储。事实证明把顶层w h e r e 表达式也当做附加 在顶层连接树项的条件来存储是非常方便约。所以实际上连接树代表s e l e c t 语句的h 的m 和w h e r e 予旬。 其他o t h e r s ) 查询树的其他部分，像o r d e rb y 子旬，本文不准备在这里讨论。例2 1 中的关系代数表达式所对应的查询树如图2 i 所示。 1 2 河海大学硕士学位论文 数据库中间件的壹询优化机制研究 ，r s * s t c a m e i o f ! x 。 s s c f = ( ( s s 岸= s c s 册 ( c 撑= c c 抑 ( s e x ；m ) a ( c n a m e = m a r b s g ) 图2 - 1 查询树 2 3 查询分类 在分布式环境下，查询可分为三种类型 7 1 ：局部查询，远程查询和全局查询。 局部查询是指在本站点上执行查询，即查询本站点上存放的数据。远程查询是指 在某个站点上执行查询，即查询在网络上的另一个站点上存放的数据。对于局部 查询，可以使用集中式查询处理的技术。全局查询是涉及多个站点的数据查询， 因此其查询处理和优化技术非常复杂。 2 3 1 局部查询 局部查询只涉及本地、单个站点上的数据，查询优化的技术与集中式数据库 查询所采用的优化技术相同。如关系代数的优化，查询树的优化。局部查询处理 的四阶段：语法分析哪i i l g ) 、优化( 0 p 豳1 曲d o n ) 、代码生成( c o d eg e n 啪舶n ) 和查询执行( e x e c 砸o n ) 。 2 3 2 远程查询 远程查询也只涉及单个站点上的数据，它的局部处理的优化策略与本地查询 所采取的优化策略相同。在有多个副本的情况下，为了减少远程查询的通信代价， 尽可能选择距发出查询应用的站点最近的站点。 2 3 3 全局查询 全局查询涉及多个站点上的数据，因此查询处理和优化技术要复杂的多。所 塑壅墨兰堡主兰垒篓壅 塑塑壁主囹堡鲤壅塑垡些垫型堑翌 以在分布式查询处理中主要研究全局查询处理。下面将详细介绍全局查询处理及 其优化技术。 2 4 全局查询的层次结构 在分布式数据库系统中，要求数据分布对用户一般是透明的，用户向系统提 出查询请求时，不必关心所涉及的关系是否分割、有无复本、存于何处等问题， 可以如同集中式数据库一样，用关系而不是裂片表达查询，这样表达的查询称为 全局查询( g l o b a lq u e r y ) 。分布式查询从结构上可分为四个层次，包括查询分解、 数据本地化、全局优化、局部优化，如图2 - 2 所示p l 。 图2 - 2 分布式查询的层次模式 ( 1 ) 查询分解：将一全局查询语句进行词法分析、语法分析转化为全局 查询树，再将全局查询树转化为段查询树。 ( 2 ) 数据本遗化：对奄询所要访问的每一个关系进行具体化，落实到合适 ( 使尽可能做到本地化或近地化) 片段上的查询。如果对每一个查询所访问的关 系只认定一个副本，则成为非冗余具体化，否贝称为冗余具体化。 ( 3 ) 全局优化；全局优化是指寻找分片查询的最佳操作次序，使得代价函 数最小。代价函数一般是i o 、c p u 和通信代价之和。全局优化输出的是一个优 化的、片段上的关系代数查询。所蔫要的信息来自数据摩的统计信息，包括各站 点片段统计信息、资源信息和通信信息等。 ( 4 ) 局部优化；局部优化在各个本地站点执行，由各个站点上的d b m s 进 行优化，采用集中式数擐库的优化算法。 1 4 河海大学硕士学位论文 数据库中间件的壹询优化机制研究 2 5 全局查询处理 在分布式查询中，局部查询和远程查询都只涉及到单个结点上的数据( 本地 或者远程) ，查询处理采用集中式查询技术，全局查询涉及到多个站点上的数据， 其查询处理要复杂得多，所以在分布式查询处理中主要研究全局查询处理。 2 5 1 全局查询处理策略 为了执行全局查询和确定一个好的查询策赂，一般应该从以下三方面来考 虑： ( 1 ) 确定具体副本( 具体化) ；在分布式数据库中一个关系可分为若于逻辑 片段，这些片段又可以在系统的多个结点上存放。所以，对于一个查询所涉及的 关系需要确定一个物理片段，选择不同的物理片段执行查询操作会直接影响查询 执行的效率。因此必须选择查询开销最省的那些物理片段。 ( 2 ) 选择操作执行的次序：主要是确定连接和并操作的次序，其他操作的 次序是不难确定的。例如选择和投影操作总是尽可能地提前执行。这个原则与集 中式数据库所考虑的策略相同。但在分布式数据库系统中涉及到的是在不同站点 上关系的连接和并操作的次序，更必须认真考虑。 ( 3 ) 确定操作执行的方法：这包括把若干个操作联结起来在一次数据库访 问中执行，确定可用的访问路径，以及确定某种计算方法等。连接是查询中最费 时的操作，因此连接操作的执行方法是分布式查询研究的重点。 ( 4 ) 确定不同站点之间数据迁移的颐序：数据在网络上的大量迁移，必然 要产生迁移开销。 上述三个问题不是孤立的，为了找到一个查询的最优策略，就要确定执行查 询的物理片段，也必须了解查询中各操作执行的次序，而这又依赖于每个操作的 执行方法【7 】。 2 5 2 全局查询的处理步骤 在分布式数据库中，全局查询的处理步骤分两步，邵全局查询到段查询的转 换以及段查