10.3.4 分布查询处理与查询优化
在分布式数据库系统中有三类查询：局部查询、远程查询和全局查询。局部查询是对本地局部数据库的查询，它与集中数据库上的查询没有什么两样；远程查询和集中数据库的查询基本相同，只是它要通过网络，远程连接其他结点；全局查询涉及多个结点上的数据，查询处理的方法和内容与集中式数据库的查询处理方法和内容大不相同。
在分布式数据库系统中进行全局查询，在执行时需要把全局查询表示成各个结点上的子查询，然后将各个子查询的结果进行汇总得到全局查询的结果。因此，分布式查询处理的实质是利用数据传送策略和局部处理策略，把全局查询转化为局部查询，即DDBMS要把用户发出的全局查询变换为对片段的简单查询。
通常查询语言是描述性语言，仅表达查询的要求，而由DDBMS确定合理的、有效的执行策略，这就是全局查询的优化问题。在分布式查询处理中，有多种可能的执行方案供选择，选择合理的执行策略对分布式查询性能有重要影响。
图10-10给出了分布式查询处理的一般过程，现简要说明如下：
图10-10
（1）词法及语法分析：借助语言语法器(存有查询语言的语法规则)对全局查询的语句进行词法及语法正确性检查。
（2）把查询语句变换成查询树：利用全局数据字典、等价变换规则等，把查询变换成某种内部表示（通常用语法树表示）。为了利用关系代数表达式的优化算法，内部表示可用关系代数语法树。因此，这一步的任务是把用户用高级查询语言表达的查询要求转换为用关系代数表示的查询树。
（3）将全局关系分割成片段，为查询分解提供条件。
（4）全局查询优化：主要包括查询树的变换和简化、副本选择、查询树的分解，以及子查询的执行次序、连接方法的选择等。
（5）子查询的执行和优化属于局部优化问题，优化方法与集中式数据库中讨论的查询优化方法类同。
（6）汇总和处理子查询结果，以获得查询结果。
我们已经知道了分布式数据库系统中查询的步骤，下面重点介绍查询优化。
在分布式数据库中查询的代价，主要由I/O代价、CPU代价和通信代价组成，其实通信代价，在分布式数据查询中是要主要考虑的。因此当处理全局查询的优化时，我们应该主要考虑的是怎么样降低结点之间的通信代价。而对每个结点的局部优化策略可采用集中式数据库中一些有效的优化方法。另一方面，在DDBS中可以利用多结点实现并行处理和均衡负荷。因此，全局查询优化的主要目标是减少通信代价和提高系统的并行性。
一、基于关系代数等价变换查询优化处理
基于关系代数的优化算法的基本原理是：把查询问题转变为关系代数表达式，分析得到查询树（语法树），进行全局到片段的变换得到基于片段上的查询树，然后利用关系代数等价变换规则的优化算法，尽可能先做选择和投影。
实现步骤和方法：
（1）将一个查询问题转换为关系代数表达式。
（2）把关系代数变换到查询树。
（3）从全局查询到片段查询的变换，这个变换的典型方法是把基于全局关系的查询树中的全局关系，用其重构该全局关系的各片段名替换，变换成相应片段上的查询树。
（4）利用关系代数等价变换规则的优化算法，对片段上的查询树进行优化处理，最后达到优化查询的目的。
二、基于半连接方法的查询优化处理
连接操作是常用但代价较高的一种操作。因此，为了使分布式数据库系统能有效地处理连接操作，人们做了大量的研究，形成了各种不同的算法。一般可以分为两类：基于半连接算法的查询优化和基于直接连接算法的查询优化。下面我们介绍一下基于半连接算法的查询优化。
设R、S是两个关系，A、B分别是R、S上的两个属性，我们引入半连接的记号∝，则R、S在A、B上的半连接可以表示为：
当连接操作采用半连接方法表示时，有：
采用半连接方法表示连接操作的操作过程如图10-11所示。
网络
图10-11
传输代价可用下式估算：
T= C 0+ C 1× X
由图10-11可以看出：
（1）在站点2上作关系S在R和S公共属性B上的投影ΠB（ S）。
（2）把ΠB（ S）结果送到站点1，代价为C 0+ C 1× size(B)× val(B[S])，其中size(B)为B的属性长度，val(B[S])为关系S中属性B上不同值的个数。
（3）在站点1上计算半连接，设其结果为R′，则R′=R
（4）把R′从站点1送到站点2的代价是C .0+ C 1×(size(R)×card(R′)，其中card(R′)为R′的元组数。
（5）在站点2上执行连接操作
。
采用半连接方案的总代价为：
T 半R=2 C 0+ C 1(size(B)× val(B[S])+ size(R′)× card(R′))
直观地看，使用半连接可以缩减关系R的大小，使得从结点1传送的关系由R缩减为R′[一般)(card)>>(card RR′]，从而减少了通信代价。
但是，由于执行半连接本身要传送数据[ B SΠ（）]，需要通信代价，因而究竟是否采用半连接还要计算和比较其好处与开销之后再做决定。
不采用半连接，直接把R送到S执行连接的代价为：
T 全=C0C1×size(B)×card(R)
只有当半R <T 全时，采用半连接方案才是合适的。
对于连接的查询优化还有一些别的方法，比如基于直接连接算法的查询优化处理等。在这里我们就不再介绍了，感兴趣的读者可以参考相关的资料进行学习。
分布式查询优化的各种方法均可配合使用，按需要选择。总之对于一个查询，可对不同的查询方法进行代价评估，根据环境条件考虑传输代价与局部处理的相对费用，选出其中代价最小、最有效的方案作为优化的查询方案。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
