分布式查询优化策略浅析

《分布式查询优化策略浅析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分布式查询优化策略浅析摘要：为了缓解分布式数据库分片和冗余带来的响应时间和处理速度问题，同时考虑效率、代价是查询过程中的重要问题，分布式查询优化成为分布式数据库研究领域的热点。本文从分布式查询的概念和类型出发，简要的介绍了现今比较成熟的几类分布式查询优化策略，并重点介绍了基于半连接的SDD-1算法。关键字：分布式数据库；查询优化；SDD-1算法引言分布式数据库系统具有数据分布存储及节点高度自治等特征。考虑到系统的安全性、可靠性等要求，而不得不使许多数据以副本的形式存储在多个站点。由于查询过程中的通信代价以及查询效率等一系列需求，查询优化就成了分布式数据库数据管理的一个重要问题。长期

2、以来许多研究者为此做出了不懈的努力，提出了多种优化算法，取得了较大的成功，为提高整个系统的效率奠定了良好的基础[1]。1查询优化考虑的问题分布式数据库存在于网络环境中，由于数据的分布性，一次查询所操纵的对象可能分布于不同的网路节点中，由此带来的开销和执行速度就会不一样，优化所要考虑的因素就更为复杂。分布式数据库环境中的查询优化所要考虑的两个关键问题：1.数据和信息均要通过通信线路进行传输，存在延迟的问题将减慢整个查询执行过程。2.网络中多处理器的存在提供了并行处理和传输的机会，应充分利用可以加快查询响应的速度。一般分布式查询处理有两个优化准则[2]：使通讯费用最小；使响应时间最短。

3、分布特性的存在除带来通信开销外还影响到物理查询计划的复杂性和可选方案。选择副本获得数据，选择站点进行连接，是查询算法首先应该考虑的问题。2分布式查询策略一个好的查询策略应该使数据的传输量和通信次数量少，以减少数据传输和通信的时间,从而减少查询的总代价[4]。文献[4]将查询优化策略分为：简单的连接处理；半连接策略；利用并行性的连接策略。文献[2]中将优化技术分为：基于关系代数操作的优化；基于请求分解定位的优化；基于存取路径的优化。其中基于请求分解定位的优化方法又可以分为：静态方法、动态方法和混合方法。国内外许多学者针对分布式查询优化提出了许多具体、有效的算法：(1)AHY优化算法A

4、HY算法[5]指的是由Apers，Hevner和Yao所发表的论文所提出的算法。该算法适用于追求最小系统开销或最小通讯延迟的场合。AHY算法把查询所涉及的关系先进行本地处理，然后利用半连接操作来约简这些关系。最终选择一个查询执行站点，将约简后的关系都传送到这个结点，实施这个查询。(2)SDD-1算法SDD-1中首先提出了用半连接操作来代替连接操作的思想[6]，并且采取全局优化方法处理查询。其主要思路是，首先用半连接来减少关系的元组数，在半连接施加到最大限度时，取一个站点收集查询所涉及到的所有关系，在这个站点上执行这个查询。(3)R*算法R*的分布式查询算法是对系统R中优化器技术的扩

5、充[7]，采取编译的方法：在编译时列举所有的查询方案，从中选择一种代价最小的查询策略。R*中查询的编译是分布式执行的，执行的过程由查询的提交站点，即主站点负责协调。主站点负责决定全局的查询策略，从站点负责确定各局部站上的具体查询策略。3SDD-1算法SDD-1算法采用了半连接程序处理连接操作[8]。它的查询优化就是对逻辑关系使用基本的运算(如选择，投影，半连接)操作来缩减。SDD-1算法是基于爬山（HillClimbing）算法而形成的。它有五个主要特征，首先，采用半连接是最主要的，其次，各个局部站点没有重复，也不进行分片。此外，在它的代价计算中，不考虑最后一个站点传送代价。这是由

6、于在它的查询策略中，当使用半连接来缩减操作数关系的基数，当最大限度的缩减以后，把所有关系送到可执行查询的站点上，这个站点不一定是查询所要求的结果站点。譬如说，若S是结果站点（经半连接缩减后建立的），R是查询要求的站点，S、R可能相同，可能不同，若不相同，则还有一次传送代价将S送到R。最后它还能同时减少最小总时间和响应时间。SDD-1算法[9]有两部分组成：基本算法和后优化。基本算法基于爬山算法，是爬山算法的迭代。根据评估缩减程序的费用、效率、收益估算几个因素，给出全部的半连接缩减程序集，决定一个最有益的（收益大的）执行策略ES，但效率不一定高，然后选择一个装配站点Sa，将已缩减完的

7、关系传送到装配站点Sa上进行连接；后优化，将基本算法得到的解进行修正，以得到更合理的执行策略。基本算法：1.基础：已有了从查询树转换的优化模型，且所有关系己完成局部缩减。2.方法：①根据已得到的缩减关系的静态特性表，构造可能的半连接缩减程序；②按半连接缩减程序的静态特性表分别计算其费用和收益，从一组的静态特性表中选取一个半连接程序，设为M；③以M完成缩减后，又将产生一组新的静态特性表再进行计算，再从一组可取的静态特性表中选一个半连接程序，但是每个半连接程序只做一次（避