分布式数据库查询优化方法

分布式数据库查询优化方法【摘要】本文介绍分布式数据库系统查询优化的目标、策略，着重讨论了一种分布式数据库系统查询优化策略是如何影响查询的，并对分布式数据库系统的查询优化的典型方法进行了分析、总结。分布式数据库系统由于数据的分布和冗余使得分布式查询处理增加了许多新的内容和复杂性，对于一个给定的查询，通常会有多种可能的策略，查询优化就是从这许多策略中找出最有效查询计划的一种处理过程。并针对分布式数据库系统的查询优化，讨论了三个典型的算法：INGRES算法、SystemR*算法、SDD-1算法。【关键词】分布式数据库；分布式查询；查询优化；查询处理策略；算法0引言近年来，随着计算机网络和数据库技术的发展，对分布式数据库的应用越来越广泛；随着应用不断扩大，数据的查询也越来越复杂，对查询的效率要求也越来越高，因此查询处理成为分布式数据库系统中的一个关键性的问题［1］。在分布式数据库中，由于数据的分布与冗余，使得查询处理中一般需要站点间的数据传递及通信费用，成为查询优化的主要矛盾；另一方面，数据的分布与冗余也增加了查询的并发处理的可能性，从而可以缩短查询处理的响应时间，提高处理速度。总之，分布式查询的规模与优化的因素，都与集中式查询优化不同，因此许多数据库专家学者致力于研究分布式数据库查询优化技术这一重要课题，并且己经在这一领域作了大量的工作，也找到了规律，包括一些大家公认的经典算法；然而由于分布式数据库本身的灵活性，要想设计一个算法对于各种情况都是最优的几乎不太现实，只能说设计一个较优的优化算法，它可以解决某一类型的问题⑵。分布式数据库中查询优化是一项复杂问题，已经被证明属于NP完全问题，至今都没有得到彻底地解决，里面尚有许多问题值得研究和探讨。1分布式查询优化的目标分布式数据库系统的查询优化有两种不同的目标：一种目标，是以总代价最小为标准；另一种目标，是以查询响应时间最短为标准，这一点在分布式数据库系统中具有重要的意义。因为分布式数据库系统是由多台计算机组成的系统，数据的分布和冗余也增加了查询的并行处理的可能性，从而可以缩减查询处理的响应时间，加快查询处理速度。在分布式查询优化中也常同时使用这两种标准，根据系统应用的不同，一种作为主要标准，另一种作为辅助标准［3］。在分布式数据库系统中，查询优化包括两个内容：查询策略优化和局部处理优化，而查询策略优化尤为重要。分布式查询策略的优劣将直接影响计算机网络资源耗费的多少。在集中式数据库系统中，查询优化的目的可以总结为以下三个方面：1）为每个用户查询寻求总代价最小的执行策略；2） 总代价是以查询处理期间的CPU代价和I/O代价来衡量的；3） 总代价最小就意味着查询的响应时间最短。从上可看出，在集中式数据库系统中，一个查询策略的选择是以执行查询的预期代价为依据的。由于系统大都运行在单个处理器的计算机上，所以查询执行总代价为CPU代价加I/O代价［4］。而在分布式数据库系统中，由于数据的分布在多个不同的站点上，使得查询处理中需要考虑站点间传输数据的通信费用，所以除了考虑CPU代价和I/O代价之外，还应该包括数据在网络上的传输代价。所以在分布式数据库系统中，常以两种不同的目标来考虑查询优化：以总代价最小为标准和以每个查询的响应时间最短为标准。2分布式查询优化的基本方法在分布式查询处理技术中，查询优化有两种基本方法：第一，是查询转化，即以不同的顺序执行关系操作，如连接和投影操作：第二，是查询映射，即使用一系列高效的算法来存取各种设备和实现关系操作。查询转化是指关系运算集合运算顺序的改变，对查询的性能有重要影响［5］。在多站点下，查询转化可以减少通信量，从而达到减少查询代价的目的［6］。查询映射则是针对关系的存取方法和操作的执行算法进行决策。2.1查询转化的处理过程查询转化处理一般经历三个阶段：1） 建立关系代数表达式。根据查询问题，编写关系代数表达式。2） 建立查询语法树。根据关系代数表达式，生成查询语法树。3） 全局优化。按照优化策略，对查询语法树进行全局优化。优化策略：查询优化策略按以下步骤进行：1） 将关系代数表达式转换成选择串接形式。2） 尽可能把选择和投影操作移近树的叶端，即尽可能早地执行选择和投影策略，以得到较小的中间关系，减少运算量。3） 把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择和投影能同时执行或在一次扫描中同时完成。4）将上述步骤得到的查询语法树的内结点分组。每个二元运算结点与其直接祖先的一元结点分为一组。如果它的子孙结点一直到叶结点都是一元运算符，则并入该组。5）生成一个程序，每一组结点的计算是程序中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组之前计算。2.2查询优化的三种典型算法INGRES算法INGRES算法是动态的优化算法。这个算法主要分为两个步骤：（1） 将含有多个变量的查询分解为一系列的只含有一个变量的单关系查询。（2） 通过执行其每一个单关系查询：用启发式的方法选择一个初始化的执行计划，通过中间关系的大小来确定查询执