分布式数据库的查询优化算法

摘　要：近年来，随着计算机网络和数据库技术的发展，对分布式数据库的应用越来越广泛；随着应用不断扩大，数据的查询也越来越复杂，对查询的效率要求也越来越高。本文主要论述分布式数据库查询的概念特点，分布式数据库查询优化技术，并从它的优化技术进行深入探讨，就其改进，系统实现做了一定的论述，并进行了部分的程序实现。

关键词：分布式；数据库；查询；优化

分布式数据库是一个逻辑上完整而在物理上分散在若干台互相连接着的计算机上的数据库系统，各组件分布在网络的各个节点上，依靠特定的更新和检索机制进行数据库分布，数据库的所有性能都会显著增强。分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一个统一的数据库系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。
1.分布式数据库查询的定义
　　分布式数据库系统(Distributed Data Base System，DDBS)是物理上分布而逻辑上集中的数据库系统。物理上分布是指分布式数据库系统中的数据分布在由网络连接起来的、地理位置分散的不同站点上；逻辑上集中是指各数据库站点之间在逻辑上是一个整体，并由统一的数据库管理系统进行管理，同时各站点又具有管理本地数据的能力。分布式数据库系统可看成是计算机网络与数据库系统的有机结合。
　　分布式数据库系统有两个重要的组成部分：分布式数据库(Distributed Data Base， DDB)和分布式数据库管理系统(Distributed Data Base Management System，DDBMS)。 分布式数据库是计算机网络中各站点上数据库的逻辑集合。也就是分布式数据库是一组结构化的数据集合，在逻辑上属于同一个系统，在物理上分布在计算机网络的不同站点上，是集中与分布的统一。
这个定义强调了分布式数据库的两种特性；
　　(1) 数据分布性。即这些数据库是分布在不同站点上的。这把分布式数据库与单一的集中式数据库别开来。
　　(2)逻辑关联性。即这些数据库具有某些把它们联系在一起的性质。这把分布式数据库与驻留在计算机网络不同站点上的一组本地数据库区别开来。
　　分布式数据库管理系统是分布式数据库中的一组软件，负责管理分布环境下逻辑集成数据的存取、一致性和完整性。同时，由于数据的分布性，在管理机制上还必须具有计算机网络通信协议的分布管理特性。
2.分布式数据库查询优化的目标与方案
2.1优化的目标
　　分布式查询系统的优化目标一般有两种：一是使网络数据传输量最小，一是使响应时间最短。与集中式的数据库系统相比，网络的传输速度与计算机内部的数据传输速度一般相差几个数量级，因此查询的局部处理时间与节点之间数据传输的时间相比，几乎可以忽略不计。而过多的网络传输可能会给网络造成比较大的负担。因此，减少网络数据传输量成为分布式查询处理的主要问题。因此，分布式查询处理常常以减少网络间传递的数据量作为优化目标。另一方面，不同节点之间的网络传输速率可能是不同的，相同节点之间的传输速率在不同的时间可能也有所不同。同时，局部查询的处理时间有时也会影响整个查询的响应速度。在上述情况下，网络数据传输量已经不能完全代表查询的质量，而要更多地去注意查询的响应时间。在有些情况下，查询处理需要同时考虑网络数据传输量和响应时间。这时，算法需要在这两者之间做出权衡。需要指出的是，设计查询优化算法并不一定要寻求“最优算法”，而是要寻找到“满意算法”就可以了。这首先是因为所谓“最优”的概念本身就是十分模糊的。“最优”的模糊不清首先是由目标的不清引起的，因为分布式查询的优化目标往往是多种因素权衡的结果，是一个半结构化问题。其次是因为寻找“最优”往往要付出比所得到的更多的代价，是不划算的。我们应该全面衡量网络流量、响应时间、服务器负载、算法复杂性等等因素，设计出“满意算法”。
2.2优化方案的内容
　　我们这里提出查询优化方案的概念，而不仅仅是查询优化算法。优化方案包含优化算法，同时还包括其它的和优化相关的系统设计方案。我们认为一个完整的查询优化方案应该包括：分布式查询系统的体系结构：我们在前面曾经提出三种分布式查询系统的体系结构，在我们设计的松散藕合的分布式信息系统中，主要采用的是第一种体系结构，我们将体系结构默认为当前讨论的分布式查询系统的体系结构。优化的位置：分布式查询系统可以在各种位置进行优化。分布式查询算法优化是指GQP的优化。LQP也应该进行优化以提高局部查询的速度，只是因为LQP现在一般都应用比较成熟的商业数据库软件系统，其本身己经优化得非常好了，因此在实际应用中一般不再考虑LQP的优化问题。此外，可以在许多位置增加缓存以提高频繁查询的速度。可以增加缓存的位置有：用户客户端、GQP， LQP等等。软、硬件组成及其结构：用什么样的方式组成一个分布式的信息系统对分布式的查询效果的影响是非常大的。传统的服务器/客户两层结构模式，在局域网中可以比较好地访问数据库中的数据，但是在基于广域网的分布式系统中，服务器/客户两层结构由于在服务器和客户端之间必须要建立一个会话，因此数据访问的效率大大降低了。现在流行多层体系结构就很好地解决了这个问题。
2.3查询优化技术方案
　　数据库系统研究的主要目标是尽可能的对用户隐藏数据结构的细节，使数据库系统的应用更能面向各个领域。同样，分布式数据库研究的主要目标之一是隐藏分布式环境的细节，使系统用起来更加简单、有效。关系数据模型可以为集中式数据库提供一个数据无关的接口。关系数据库语言是关系演算，使用该语言进行数据查询时，只需对要查询的数据进行简单的描述，而无须说明如何获取这些数据，SQL语言就是其中之一。但是，使用这种语言，也要对搜索、存取操作以及数据传输过程进行说明，因此，相应的查询优化技术的研究和发展也在不断进行。所谓查询优化，就是要保证查询总开销和总时间为最小。查询优化器的主要任务是控制和加快查询的执行和数据的传输过程。
　　查询优化器(如图3.1)首先以查询的某种表示作为输入，这种表示是查询处理器的语法分析子模块的输出，查询优化器为查询选择一种适当的数据存取策略。

　　查询优化的基本类型通常包括两类：针对查询执行代价的优化和针对查询响 应时间的优化。针对查询执行代价进行优化的目标是，使查询执行所使用的系统资源(总和)尽量地少，从而降低系统开销，整个系统的开销可以从单个系统资源的开销表达式中推出。针对查询响应时间优化的目标是尽量减少查询的响应时间，而不计较系统资源的耗费。
　　查询处理器中的查询优化子模块将对以下问题进行决策：
　　(1)操作执行的顺序；
　　(2)关系的存取方法；
　　(3)操作的执行算法(特别是联结操作)；
　　(4)不同站点之间数据流动的顺序。
3.基于直接连接的查询优化算法研究
　　采用半连接操作可以对参与查询的关系进行缩减，减少网络上的数据传输量，但同时也会造成通信的次数的增加以及本地处理时间的增加。而在高速局域网中往往将响应时间作为查询优化的目标，由于数据在站点间的传输时间通常要比局部处理时间要短，所以减少局部时间就成为查询优化的关键问题，在这种情况下采用直接连接算法的效果会比较好。
3.1分片复制算法
　　当查询不能在无数据传送情况下进行的时候，站点依赖算法就无法应用了，则需要使用其他算法来实现查询的优化。分片复制算法就是一种解决方案，它的基本思想是：选择分布式数据库系统的一组站点，将某一参加查询的关系进行分片，并将得到的所有片段都放置到这些站点上，而将其他参与查询的关系完整的复制到这些站点上，每个站点都可进行关系的连接操作，而最后查询的结果即是这些站点操作结果的并集。
3.2 Hash 划分算法
　　另一类解决方案是以Hash划分为基础的优化算法，它也是一种基于站点依赖的算法，并且也是一类比较流行的分布式数据库查询优化算法。Hash划分是一种划分方法，它对关系的某一属性或者属性集的元组值应用Hash函数，得到这些元组的Hash值，然后将具有相同Hash值的元组放置到同一个站点。这样经过Hash划分的每一个关系的元组都会根据该元组的Hash值存放到多个不同的站点上而组成相应关系的水平片段，很显然，不同的关系经过同一种Hash划分后是满足站点依赖的。
3.3 Partition 算法及改进
　　在涉及到多个关系的连接操作中，Partition算法通过对两个或多个关系在同一连接属性上进行片段划分，来提高连接操作的并行性，以此来加快整个查询的查询速度。这种方法的目的就是利用分布式数据库的分布性特点，使得查询操作能够在多个站点上并行进行，缩短查询的响应时间。但是对于海量信息以及关系较多连接属性各不相同的查询而言，这种方法的效果仍然不理想，因此下面将查询图划分与Partition算法相结合，对Partition算法进行改进。
　　Partition算法在多种划分方案中只用到了其中的一种，仅对该方案中的关系进行了划分，而其他剩余的参加查询的关系被整个复制到其他站点上。针对此问题，本文引入了一种查询图划分方法，通过查询图的划分可以将整个查询图划分为多个子查询图，这样再对子查询图中的连接应用Partition算法，这样就避免产生大量冗余关系的情况。
　　经过查询图划分后的子查询图，也就是各组中，所有的关系或者大部分的关系都可以在同一连接属性上进行属性划分，这就为Partition算法提供了一个良好的条件。为了简便起见，改进算法做了一个假设，那就是查询图中的所有节点就是该分布式数据库系统的所有站点，那么改进的算法的步骤可以描述为如下几步：
　　（1）查询图划分：按照查询图划分方法进行划分，得到多个组。
　　（2）Partition算法：每一个组中的连接操作都应用Partition算法来处理，每个组内所有节点上的结果取并集就是该组的连接操作的结果，那么经过Partition算法处理过的组可看作是一个节点，但是组内的实际节点数并没有发生变化。
　　（3）迭代：重复执行（1）和（2），直到查询图合并为一个点为止，最后所有站点上的处理结果取并集就是最终的查询结果。

参考文献：
[1]于秀霞，宋雅娟. 分布式数据库半连接查询优化算法的研究[J]. 长春理工大学学报，2006，V29(4)：69-72
[2]王意洁，王勇军，卢锡成．基于半连接的并行查询处理算法的研究[J]．软件学报，2001，V2：53-56
[3]闫丽，华彦涛，王艳辉. 一种基于半连接的分布式数据库多元连接查询优化算法[J]. 通化师范学院学报，2005，V26(6)：22-23