分布式查询优化.doc

分布式查询优化刘芳（福建信息职业技术学院，福州 350003）摘要：在分布式数据库中，查询优化是一个非常复杂的问题。在分布式数据库中查询优化不同于在集中式数据库中，两者的侧重点不同。集中式数据库侧重于减少IO时间处理，而分布式数据库则侧重于较少通讯代价。半连接算法对于分布式数据库中较少通讯代价有显著的作用，在大多数的分布式数据库中，都不同层次地应用了半连接算法。本文通过对分布式数据库的查询优化原理分析，提出了几种查询优化策略，并且对于半连接算法的实现策略做出了详细讨论。关键词：分布式数据库；查询优化 半连接算法； 分布式查询优化是当今大多数分布式数据库的重要研究方向，查询优化的效能也是衡量数据库性能的一个重要参数。如何设计分布式查询优化策略是关系到数据库优劣的指标。该文以Microsoft SQL Server 2000数据库系统为例，讨论分布式查询优化策略。(一) 基于MSSQL Server 2000的查询优化由于MSSQL Server 2000已经提供了一定的分布式查询处理能力，因此本节主要讨论全局查询优化策略和局部查询优化策略。对于传统的集中式数据库系统，查询优化主要是考虑减少I/O时间和CPU的时间。而在分布式数据库当中，为了更加准确地优化查询，应当有足够的信息，以此来决定哪一种数据访问技术最有效。在目前大多数的分布式系统当中采用了C/S体系结构，在这种结构下，数据存放的位置成为了最主要的因素。分布式查询优化由三个组件构成：访问原理 在大多数的关系数据库管理系统中，主要采用两种方式来访问表：一种方式是对整张表进行扫描，另一种方式是使用索引。使用哪种方式是最好的选择呢？这取决于环境。比如说，如果一张表里90%的内容都要被访问到，使用索引的方式并不是明智的选择。对所有行进行扫描将能够减少I/O和总体代价。然而，当只访问表内容的10%时，使用索引能带来更多的效率提升。当然，在一些关系数据库管理系统中可能提供了其他的数据访问方式，表扫描和索引在几乎所有的系统中都能被找到。连接准则 如果超过一个的表要被访问到，那么这些表连接的方式应当被决定。通常DBMS都提供了几种不同的连接方式，比如，早期的DB2提供了三种不同的连接方式：合并扫描连接，嵌套循环连接和混合连接。优化器(optimizer)应当能决定这些表进行连接的顺序，在分布式的环境当中，连接要从哪个站点开始也是应当慎重考虑的。传输代价 如果在连接过程当中，数据在多个站点之间传送，那么数据传输的代价也应当被慎重考虑。有时简单地将整张表传送到网络的其他节点可能会减低了整体的传输代价。传输代价不仅仅在分布式系统中有效，在集中式系统中也具有一定的意义。查询优化主要通过两种方式来实现：一种是DBMS提供了相关的功能，而另一种是通过程序员的代码来实现。很显然，如果通过编程来实现优化，要求程序员对于数据库的分片和分配方式这些细节很了解，如果一旦数据做了改变相应的程序也要做出修改，但是这种方式在一定的范围内可能查询效率比较高。如果是系统提供了相应的优化，将对每一条查询都进行分析，然后进行优化，但是优化器(optimizer)生成的查询可能不是最好的方案，因为分布式查询优化是一个非常复杂的问题。（二）半连接算法在近几年时间里，为了提高分布式环境的查询效率，一系列新的查询处理技术被提出，其中之一就是半连接约减器(semi-join reducer)，其基本思想是通过计划早期应用连接预言来减少中间查询结果的大小和其他操作的代价，目的是在分布式系统中减少通讯代价。半连接是由投影和连接运算导出的一种关系代数运算。两个关系的半连接表示为：RS=R(B (S)其中，表示半连接，表示完全连接，B (S)表示对S所在的站点对B进行投影。半连接的步骤是：首先在S所在站点对连接属性投影，将投影结果送到R所在站点执行半连接，然后将半连接后的结果送回S所在站点完成连接。一个简单的半连接比较简单，但是在实际应用中，半连接不一定能带来多少效率的提升，因为在一个复杂的查询当中，并不是简单地把完全连接替换成半连接就算是查询优化了，还要考虑连接的顺序，连接的代价，由哪个站点完成连接，甚至于要考虑到服务器负载等各种情况。为了方便讨论，首先对一些基本操作作出定义。设全局关系R的不同片段为Ri，所需Ri的有关信息如下：基数：片段Ri含有的元组数，记为card(Ri)长度：Ri中每个属性A的长度，即属性A的字节数，记作size(A)。元组的长度为Ri的所有属性之和，记作size(Ri)评价一个半连接的代价通常用半连接结果T的基数card(T)来衡量，估算card(T)有一些方式，一个保守的估算公式是：card(AB)min(card(A),card(AB)使用这个公式能够把结果基数的上界估算出来，但是如果使用这种方式来估计代价，使用半连接将毫无意义。作为改进，我们使用了另一种方式来估算。设表示半连接运算的选择率，则可用以下式子估算：=val(AS)/val(dom(A)，其中，val(AS)表示R中每个属性A可能取值的个数，val(dom(A)表示属性A的域中不同值的数目。半连接运算结果T的基数可表示为：card(T)= X card(R)。（三）查询优化策略对于一条查询，首先对其进行分析，然后根据分析的结果选择出最好的查询策略，接着将查询分配到各个站点上去，最后各个站点将查询的结果进行汇总。在分析阶段，分析器将查询代码做出分解，并对该查询进行代价预测，从查询方案中选择出最好的那一条来执行。进行代价预测可以通过为查询建立搜索空间来完成，但是为半连接计划建立搜索空间比较困难，一个典型的方法是利用半连接约简器来优化查询，可以分成几步来完成：（1）为每一张表寻找出优化的半连接约简器（2）为约简表优化连接顺序和连接方法。很显然，这种方式在大多数的场合下都不能生成好的连接计划，它可能会选择错误的半连接约简器，因为最好的选择取决于连接的顺序和使用的连接方法。因而，可以将查询优化器和半连接约简器综合在一起。改进后的算法描述如下：如果将查询认为是树型结构，首先估算出任意两张表的连接代价，由于半连接不具有交换性，即RSSR，因此RS和SR要分别进行计算，计算过程中将代价比较高的连接方式剪除，这个过程称为剪枝(pruning)，这些计算结果位于树的最底层，即叶子节点，接着根据这些结果同样可以估算出任意三张表的连接代价，同样地，在计算过程中一旦发现有更好的连接计划立即进行剪枝(pruning)，如此自底向上，最终建立一个搜索空间。在剪枝(pruning)过程中，如果两种查询方法不可比较，比如说合并连接和哈希连接是两种不同的方法，则将两个节点都进行保留。算法结构如下：for i = 1 to n do optPlan(Ri)=accessPlans(Ri) prunePlans(optPlan(Ri)for i = 2 to n dofor all S R1, R2 Rn such that |S| = i do optPlan(S) = for all O S do optPlan(S) = optPlan(S) semiJoinPlans(optPlan(O), optPlan(S O) prunePlans(optPlan(S) traverseAndMovePlans(optPlan)从算法中可以看出，在每一次生成查询计划(optPlan)之后，马上就进行剪枝(PrunePlans)，这是为了避免产生大量不必要计算。该算法是从经典的动态规划算法改进得到的AccessRoot算法。对于每一个站点都应当建立一个搜索空间，因为即使是相同的查询对于不同的站点的查询代价可能也是不相同的。由于每一个站点都有一个全局字典的副本，从全局字典可以得知每一个表所在的物理位置和相关分布情况，因此能够将任意两个表连接所发生的通信代价估算出来。当一个查询到来的时候，从搜索空间里寻找最优解，然后根据这个最优解将查询分解成几个部分，分配到各个站点上去执行。但是这种方式仍然可能找不到最优解，因为某个查询(optPlan)对于特定的站点(Site A)使用某个计划 (Plan)来执行可能是最好的选择，但在全局的范围之内有可能是最坏的选择，而相同的查询由站点B(Site B)来执行的话可能会提高一半的效率。为了保证查询能在全局范围内找到最优解，可以在站点之间建立某种协议，由该协议来协商(negotiate)执行查询的代价，最终选出最优解，在最优解的站点上执行查询，这个站点就是查询执行的主站点。该协议可以在应用层来实现，也可以在内核级别上实现。在本例中，选择在应用层来解决，由于MSSQL Server 2000不具备跨平台能力，可以通过编写COM+服务组件来完成协商，为了减少通信量，协议应当设计得尽可能简单。下图是一个简单的协议格式。Service typeService codeService resultSql statement其中，Service type表示服务类型，在本例中表示协商请求(negotiate request)或者协商应答(negotiate reply)，一个站点广播请求，其他站点接受到请求后根据连接表达式(Sql statement)在搜索空间中查找完成该连接的代价，然后将结果(Service result)封装成数据返回给发出请求的站点。在一个繁忙的分布式系统当中，一个站点会同时广播大量的请求，为了区分这些不同的请求，必须要给它们编号，Service code就是用来区别不同的请求，对于每一个站点都要负责维护一个缓存，该缓存用来保存已发出的请求编号（Service code），这些编号保证不能重复，一旦决定查询被执行的主站点，就将该请求的相关内容删除。如果服务器拥有足够的内存，可以考虑开辟一块缓存用来保存其它站点的应答（这个应答应当是最优解），这样做的好处是如果该查询被执行的频率很高，下一次就可以直接通过查找缓存就知道该选择哪个站点来执行，但是应答不能无限期被保留，可以使用某种策略，比如最近最少使用策略来淘汰过期的应答。发出请求的站点在发出协商请求(negotiate request)的同时可以设置定时器，如果定时器超时而协商应答(negotiate reply)没有全部到齐，将在已接收到的结果当中选择一个，或是直接在本站点执行。收到协商请求(negotiate request)的站点允许不理会请求，比如在站点非常繁忙的时候(server overload)，但是不允许该站点继续向其它站点转发(forwarding)请求。一旦决定了查询执行的主站点，就将查询以命令(command)的方式发到该站点，并且随后将所需要的表传送到主站点，主站点接收到查询命令(command)必须执行，而且不允许继续向其它站点广播协商请求(negotiate request)，以免形成站点之间的递归查询。主站点从其它站点接收到必需的数据后开始执行，为了提高连接的效率，有时候先在其它站点上得到一个子连接的结果，然后将结果传送到主站点会更加节省时间，而且也能使各个服务器之间负载均衡。例如在下面的例子中有两种方案。对于SQL查询语句SELECT * FROM A, B, CWHERE A.a=B.a AND A.b=C.b其中站点1存放了表A, B，站点2存放了表A, C,一个传统的连接树型结构是 client1 C2 B1 A1连接执行的顺序是，首先将AB表在站点1进行连接，连接的结果1再和站点2的表C连接，在这种结构中，当表C的基数比较大的时候，通信代价较大，可以考虑先将A和C进行半连接，然后将连接的结果送到Client端，这里的Client指的是发出请求的进程，该进程可能属于分布式系统中的某一台数据库服务器。改进后的树型结构如下所示： client 1 2 B1 A1 C2 A2使用这种连接计划的另一个好处是可以充分利用服务器资源，将一个大的连接分解成两个小的任务分配到其他空闲的服务器上去。由于MSSQL Server 2000并不能支持分片透明性，因此必须在查询分析步骤将对逻辑片段的访问映射为物理片段的访问。可以通过查询全局字典来获悉有关片段的物理位置等信息，然后将查询表达式变换为真正的查询指令。我们可以考虑使用一个代理(agent)来完成上述功能，这个agent接收查询请求，通过全局字典和搜索空间将请求转换成最优的查询指令，然后执行该查询。工作流程如下： SQL Query agent Optimized SQL Queryagent可以使用中间件技术来实现，实际上，agent的功能已经包括了语法分析，协商通信和语法转换。 一个完整的查询优化过程应当是：1. 系统初始化，估算连接代价，建立搜索空间。2. 接收到查询请求，对查询进行分析，agent通过协商和查找搜索空间来确定最终的查询站点。如果最终结果不选择在本站点执行，直接将查询发送到目的站点的agent上去（agent之间必须对等通信，不允许其他应用程序同agent通信），目的站点agent接收到查询要求将查询进行优化，生成优化代码，执行该查询。3. 如果最终结果选择在本站点执行，通过查询搜索空间，生成优化代码，选择一个合适的连接顺序，执行该查询。在查询过程中，可以要求其他站点协助，比如某些数据只能由其他站点来提供，或者将某一个子连接分配到站点去，接收到任务的站点应该尽可能地完成任务。如果站点实在过于繁忙，采取措施是简单地丢弃该任务。如果主站点在一定时间内没有接收到应答，将任务重传，重传三次失败选择下一个站点。上述这些过程可以利用事务机制来完成，由于SQL Server2000已经提供了DTC(分布式事务协调器)，我们可以在这个基础上建立过程。4. 如果在实际的连接过程当中，估算值与实际值误差太大，在搜索空间中用实际值来代替估算值，在一个繁忙的系统中，很快就能建立起相对准确的代价树。5. 为了提高查询执行效率，可以考虑开辟一块缓存空间来记录各服务器最近的情况，包括CPU负载，响应时间，以及近期任务的执行记录，作为查询分配的参考。6. 最终的执行结果在主站点上完成连接，然后发送给客户。参考文献：1Konrad Stocker, Donald Kossmann, Reinhard Braumand etc.Integrating Semi-Join-Reducers into State-of-the-Art Query Processors2 Craig S.Mullins.Distributed Query Optimization,19963Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom.Database System Implementation.北京：机械工业出版社，2002 4萨师煊，王珊数据库系统概论第三版北京：高等教育出版社，2000作者介绍：刘芳，女，汉族，福建闽清人，福建信息职业技术学院软件工程系，助教，学士，研究方向为软件编程。Distributed Query OptimizationAbstract: In the distributed database , it is a very complicated problem to optimize query. Inquire about optimizing and is different from in the centralized databa