浅析分布式数据库查询优化

1、分布式数据库查询优化【摘要】本文针对分布式数据库查询优化进行了分析与探讨，讲述了其特点，与原理供相关计算机方面人员参考。【关键字】分布式、数据、查询、优化一、 分布式数据库及其特点：分布式数据库系统是物理学上分散而逻辑上集中的数据库系统。分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一个统一大业的数据库系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。一个分布式数据库系统应该具有如下特点：数据的物理分布性、数据的逻辑整体性、站点自治性二、 分布式数据库查询基本概念1. 分布式数据库查询优化的研究意义：分布式查询技

2、术主要把用户提交的全局查询请求翻译为几个相关节点都可以识别的本地查询请求，以及把各个节点的查询结果汇总返回的问题，它包括分布式查询处理和分布式查询优化。分布式查询处理研究整个分布式查询处理的过程和策略；分布式查询优化研究查询策略的优化问题，即如何从多种方案中选择查询代价最少方案。分布式查询处理作为分布式数据库研究主要问题之一，它是用户与分布式数据库之间的接口，在分布式数据库中由于数据的分布与冗余，使得数据在各站点间的传输代价成为查询处理的主要矛盾；另一方面，数据的分布与冗余也增加了查询的并发处理的可能性，从而可以缩短查询处理的响应时间，提高处理速度。因此，与集中式数据库相比，分布式查询处理增加

3、了不少新内容与复杂性。2. 分布式查询处理的层次结构：分布式查询处理按不同的层次执行，符合分布式数据库系统的层次结构。分布式查询处理可分为如下所示四个层次结构。(1)查询分解查询分解是将查询问题(如SQL语句)转换成一个定义在全局关系上的关系代数表达式。这一层的做法与集中式DBMS相同，因为并未涉及分布问题。本层转换所需要信息在全局概念模式中得到。(2)数据本地化数据本地化是把一个在全局关系上的查询进行具体化到合适片段上的查询。这一变换所需要信息在分片模式和片段的分配模式中获得。(3)全局优化全局优化输入是分片查询，全局优化是找出分片查询的最佳操作次序，包括使得代价函数最小。全局优化一个重要方

4、面是关于连接操作的优化，全局优化处理层输出是一个优化的、片段上的关系代数查询。这层转换所需要信息来自数据库的统计信息，包括各站点片段统计信息、资源信息和通信信息等。(4)局部优化局部优化由与查询有关片段的各个站点执行。它由该站点上的DBMS进行优化，采用集中式数据库系统中查询优化的算法，所需要信息来自于局部模式。分布式查询优化通常在分布式查询层次结构中的数据本地化层和全局优化层。数据本地化阶段一般采用的是基于关系代数等价变换的优化算法。而全局优化阶段采用的算法，可具体分为基于半连接算法的查询优化和基于直接连接算法的查询优化两大类。3. 分布式数据库数据库查询优化的一般过程：分布式查询处理问题是

5、由E-Wong首先提出的，分布式查询处理的基本思想认为分布式查询处理是数据传递和局部处理相交织的过程，分布式查询处理策略由数据传递策略与局部处理策略组成;分布式查询处理的过程实质是利用数据传递策略和局部数据处理策略，把分布查询转化为局部查询的过程。分布式数据库中的查询过程可分为逻辑分解、评议转换和优化组合几分。分布式数据库系统中，用户可以用全局查询评议对多个数据库同时进行查询，即为全局查询。全局查询一般经过以下几个过程：首先，对全局查询进行逻辑分解成几个子查询，每个子查询对应一个局部数据；其次，若全局查询评议与局部查询评议不同，则进行语言的等价转换；最后，各个子查询的结果优化组合后返回。不同的

6、查询分解对应不同的系统性能，因此为了达到优化系统性能，需要相应查询优化器来确定一个相对较好的执行计划，最后启动查询计划。4. 分布式数据库查询优化的衡量标准：一个查询策略的选择是以执行查询的预期代价为依据的，由集中式系统大都运行在单个处理器的计算机上，所以查询执行总代价为CPU代价加I/O代价之外。分布式查询优化可用CPU代价、I/O代价、通信代价3个参数来徇，总代价为三者之和。在分布式数据库系统中，常以两种不同的目标来考虑查询优化：1. 以总代价最小为标准，除了CPU代价和I/O代价之外，还包括数据通过网络传输的代价。2. 以每个查询的响应时间最短为标准。响应时间就是从接收 查询到完成查询所

7、需要的时间。它既与通信时间有关，又与局部处理时间有关，而通信费用与所传输的数据量和通信次数成正比。5. 分布式数据的查询优化策略：一般来说，在分布式数据库中的查询优化主要考虑以下几种：1. 操作执行的顺序：操作执行顺序的改变主要指关系运算及集合运算的改变，它们常常对铁性能产生重要的影响。2. 关系的存取方法：在关系数据库系统中，关系或使用索引，如果关系中90%的要被访问，则扫描整个关系是较好的；如果只有30%的被访问，则使用索引是更为有效的方法。3. 操作的执行算法（尤其是连接操作）：连接操作是将两个关系在指定的公共属性上以相同值为依据进行合并，连接操作通常有多种：自然连接、造价连接、外连接和

8、半连接等。4. 不同站点间数据流动的顺序：在多站点中，合理地选择数据的流向，可以大大减少通信量，以便达到减少查询代价的目的。三、 常用的分布式数据库的查询优化策略：1. 基于关系代数等价变换的优化算法：基于关系代数等价变换的优化算法是一种既能减少操作量又能减少操作次数的算法。基于关系代数等价变换优化算法的基本原理:把查询问题转变为关系代数表达式，分析得到查询树(语法树)，进行从全局到片段的变换得到基于片段上的查询树，然后利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。这样，一方面可以减少其后操作的操作量，另一方面可以减少操作次数。对该查询树进行优化，从而达到查询优化的目的。关系

9、代数等价变换规则的优化算法:利用关系代数等价变换规则，把查询树中连接和合并操作尽可能上提(向树根方向移)。选择和投影操作尽可能下移(向树叶方向移)到片段的定义处。这就是说，尽可能先执行选择和投影操作，后执行连接和合并操作。经过选择和投影操作不但可以减少其后操作的操作量，而且还可以减少操作次数。2. 基于半连接操作的查询优化算法：基于半连接操作的查询优化的思想是经过半连接操作，可减少操作关系的数据量，从而减少站点间数据的传输量。基于半连接操作的查询优化的基本思想：数据以整个关系在网络中传输，这显然是一种冗余的方法，在一个关系传输到另一场地后， 并非每个数据都参与连接操作或都是有用，因此，不参与连

10、接的数据或无用的数据不必在网络中来回传输。基于半连接的优化策略的基于原理就是采用半连接操作，在网络中只传输参与连接的数据。连接查询的优化问题几乎是分布式数据库的分布式查询优化算法的全部，在分布式数据库中连接查询的主要手段是半连接技术，各种不同算法的差异主要是在连接顺序上，即在保证结果一致的情况下，以什么样的顺序将这些表连接起来最优。优化的对象一般数据传输量的总和。3. 基于直接连接操作的查询优化算法:基于直接连接操作的查询优化是一种完全在连接的基础上考虑查询处理的策略：有时直接连接也可能会产生好的效果，特别是当有以下情况时：a) 查询目标表中的属性很少，也不是某连接条件属性。b) 半连接的缩减

11、效果较差时。究竟用直接连接还是半连接方案，取决于数据传输和局部处理的相对费用。一般，如果认为传输费用是主要的，那么采用半连接策略比较有利，如果认为局部处理费用是主要的，则采用直接连接策略比较有利。四、 SDD_1算法：1. SDD_1概述：SDD-1算法采用了半联接程序处理联接操作zs。它的查询优化就是对逻辑关系使用基本的运算(如选择，投影，半联接)操作来缩减。它有五个主要特征，首先，采用半联接是最主要的，其次，各个局部站点没有重复，也不进行分片。此外，在它的代价计算中，不考虑最后一个站点传送代价。这是由于在它的查询策略中，当使用半联接来缩减操作数关系的基数，当最大限度的缩减以后，把所有关系送

12、到可执行查询的站点上，这个站点不一定是查询所要求的结果站点。譬如说，若S是结果站点(经半联接缩减后建立的)，;是查询要求的站点，S I可能相同，可能不同，若不相同，则还有一次传送代价将S送到I。最后它还能同时减少最小化总时间和响应时间。 SDD-1算法有两部分组成:基本算法和后优化。基本算法基于爬山算法，是爬山算法的迭代。根据评估缩减程序的费用、效率、收益估算几个因素，给出全部的半联接缩减程序集，决定一个最有益的(收益大的)执行策略ES，但效率不一定高，然后选择一个装配站点Sa，将已缩减完的关系传送到装配站点Sa上进行联接;后优化，将基本算法得到的解进行修正，以得到更合理的执行策略。2. 基本

13、算法:(1)基础:已有了从查询树转换的优化模型，且所有关系己完成局部缩减。(2)方法:根据己得到的缩减关系的静态特性表，构造可能的半联接缩减程序;按半联接缩减程序的静态特性表分别计算其费用和收益，从一组的静态特性表中选取一个半联接程序，设为M;以M完成缩减后，又将产生一组新的静态特性表再进行计算，再从一组可取的静态特性表中选一个半联接程序，但是每个半联接程序只做一次(避免导致缩减程序太长、效率不高);反复直到无半联接缩减程序为止。(3)结束:以若干次迭代以后的最后缩减关系的静态特性表为基础，进行站点选择(费用计算)，决定执行查询的站点(可能与查询要求的站点不同)。后优化:在基本算法中，每次迭代

14、时只考虑本次迭代时的“改善”，这种“改善”不一定最好。后优化有两种修正;(1)若最后一次半联接程序缩减关系的所在站点恰好是被选中的查询执行站点，则最后一次半联接可以取消;(2)对基本算法的主迭代所构成的半联接程序的流程图进行修正。因为一开始的(或某一个)半联接缩减程序的代价很高，如有，这时可以把S进行缩减后再进行半联接缩减，即可修正半联接的操作序。3. SDD-1算法总结 本文说明了SDD-1算法在分布式数据库查询中是如何应用的，可以看到使用该算法可以获得很多的收益。 SDD-1算法主要使用了半联接技术，使得数据传输量最小，特别的对于几个关系之间的联接来说，这种半联接策略可以扩展到一系列的半联接步骤。 但是该算法也有一些缺陷，比如半联接程序依赖数据库的静态特性;一个无收益的半联接程序可能到最后会变成