分布式查询优化策略浅析.doc

分布式查询优化策略浅析摘要：为了缓解分布式数据库分片和冗余带来的响应时间和处理速度问题，同时考虑效率、代价是查询过程中的重要问题，分布式查询优化成为分布式数据库研究领域的热点。本文从分布式查询的概念和类型出发，简要的介绍了现今比较成熟的几类分布式查询优化策略，并重点介绍了基于半连接的SDD-1算法。关键字：分布式数据库；查询优化；SDD-1算法引言分布式数据库系统具有数据分布存储及节点高度自治等特征。考虑到系统的安全性、可靠性等要求，而不得不使许多数据以副本的形式存储在多个站点。由于查询过程中的通信代价以及查询效率等一系列需求，查询优化就成了分布式数据库数据管理的一个重要问题。长期以来许多研究者为此做出了不懈的努力，提出了多种优化算法，取得了较大的成功，为提高整个系统的效率奠定了良好的基础1。1 查询优化考虑的问题分布式数据库存在于网络环境中，由于数据的分布性，一次查询所操纵的对象可能分布于不同的网路节点中，由此带来的开销和执行速度就会不一样，优化所要考虑的因素就更为复杂。分布式数据库环境中的查询优化所要考虑的两个关键问题：1. 数据和信息均要通过通信线路进行传输，存在延迟的问题将减慢整个查询执行过程。2. 网络中多处理器的存在提供了并行处理和传输的机会，应充分利用可以加快查询响应的速度。一般分布式查询处理有两个优化准则2：使通讯费用最小；使响应时间最短。分布特性的存在除带来通信开销外还影响到物理查询计划的复杂性和可选方案。选择副本获得数据，选择站点进行连接，是查询算法首先应该考虑的问题。2 分布式查询策略一个好的查询策略应该使数据的传输量和通信次数量少，以减少数据传输和通信的时间, 从而减少查询的总代价4。文献4将查询优化策略分为：简单的连接处理；半连接策略；利用并行性的连接策略。文献2中将优化技术分为：基于关系代数操作的优化；基于请求分解定位的优化；基于存取路径的优化。其中基于请求分解定位的优化方法又可以分为：静态方法、动态方法和混合方法。国内外许多学者针对分布式查询优化提出了许多具体、有效的算法：(1) AHY优化算法AHY算法5指的是由Apers，Hevner和Yao所发表的论文所提出的算法。该算法适用于追求最小系统开销或最小通讯延迟的场合。AHY算法把查询所涉及的关系先进行本地处理，然后利用半连接操作来约简这些关系。最终选择一个查询执行站点，将约简后的关系都传送到这个结点，实施这个查询。(2) SDD-1算法SDD-1中首先提出了用半连接操作来代替连接操作的思想6，并且采取全局优化方法处理查询。其主要思路是，首先用半连接来减少关系的元组数，在半连接施加到最大限度时，取一个站点收集查询所涉及到的所有关系，在这个站点上执行这个查询。(3) R*算法R*的分布式查询算法是对系统R中优化器技术的扩充7，采取编译的方法：在编译时列举所有的查询方案，从中选择一种代价最小的查询策略。R*中查询的编译是分布式执行的，执行的过程由查询的提交站点，即主站点负责协调。主站点负责决定全局的查询策略，从站点负责确定各局部站上的具体查询策略。3 SDD-1算法SDD-1算法采用了半连接程序处理连接操作8。它的查询优化就是对逻辑关系使用基本的运算(如选择，投影，半连接)操作来缩减。SDD-1算法是基于爬山（Hill Climbing）算法而形成的。它有五个主要特征，首先，采用半连接是最主要的，其次，各个局部站点没有重复，也不进行分片。此外，在它的代价计算中，不考虑最后一个站点传送代价。这是由于在它的查询策略中，当使用半连接来缩减操作数关系的基数，当最大限度的缩减以后，把所有关系送到可执行查询的站点上，这个站点不一定是查询所要求的结果站点。譬如说，若S是结果站点（经半连接缩减后建立的），R是查询要求的站点，S、R可能相同，可能不同，若不相同，则还有一次传送代价将S送到R。最后它还能同时减少最小总时间和响应时间。SDD-1算法9有两部分组成：基本算法和后优化。基本算法基于爬山算法，是爬山算法的迭代。根据评估缩减程序的费用、效率、收益估算几个因素，给出全部的半连接缩减程序集，决定一个最有益的（收益大的）执行策略ES，但效率不一定高，然后选择一个装配站点Sa，将已缩减完的关系传送到装配站点Sa上进行连接；后优化，将基本算法得到的解进行修正，以得到更合理的执行策略。基本算法：1. 基础：已有了从查询树转换的优化模型，且所有关系己完成局部缩减。2. 方法：根据已得到的缩减关系的静态特性表，构造可能的半连接缩减程序；按半连接缩减程序的静态特性表分别计算其费用和收益，从一组的静态特性表中选取一个半连接程序，设为M；以M完成缩减后，又将产生一组新的静态特性表再进行计算，再从一组可取的静态特性表中选一个半连接程序，但是每个半连接程序只做一次（避免导致缩减程序太长、效率不高）；反复直到无半连接缩减程序为止。3. 结束：以若干次迭代以后的最后缩减关系的静态特性表为基础，进行站点选择（费用计算），决定执行查询的站点。后优化：在基本算法中，每次迭代时只考虑本次迭代时的“改善”，这种“改善”不一定最好。后优化有两种修正：1. 若最后一次半连接程序缩减关系的所在站点恰好是被选中的查询执行站点，则最后一次半连接可以取消；2. 对基本算法的主迭代所构成的半连接程序的流程图进行修正。4 总结分布式数据库系统的查询处理是用户与分布式数据库系统的接口，查询处理策略的好坏直接影响到系统地执行速度。分布式查询策略的选择对分布式数据库的开发、运行及维护起着至关重要的作用。随着不同的应用领域的出现，所选择的策略也应该不同。尽管许多学者提出了很多优秀的算法，但是还不能完全适应实际应用的需要，分布式查询优化还是一个新的、充满挑战性的课题。 参考文献：1 汤庸, 叶小平, 汤娜. 数据库理论及应用基础M. 北京: 清华大学出版社, 2004.2 卢秉亮. 分布式查询分解及优化J. 辽宁税务高等专科学校学报, 2000(1): 47-493 谢力. 分布式数据处理M, 北京: 国防工业出版社, 2001.4 刘焕亭, 张凌燕. 分布式数据库系统的查询策略研究J. 科学技术与工程, 2005, 5(10): 1533-15355 王以和等, 分布式数据库系统M, 北京: 电子工业出版社, 1988.6 P.A Bernstein, N Goodman E Wong, C J Reeve et al. Query Processing in a System for Distributed Databases (SDD-1) J. ACM Trans Database Syst, 1981, 6(4): 602-6257 郑振相, 于戈. 分布式数据库M, 北京: 科学出版社, 1999.8 Bernstein P