一、概述

1.1 代价估算

在传统的集中型数据库中：
查询总代价=CPU代价+I/O代价。
分布式数据库中：
查询总代价=本地代价(CPU代价+I/O代价)+通信代价
响应时间=局部处理时间+通信时间(和并行处理程度有关)
其中上述通信代价可用如下公式衡量：

TC(X)=C0 + C1 * X`
C0: 通信初始化时间
C1:数据传输率(单位:秒 / bit)
X:传输的数据量(单位:bit)

远程通信网通常是以减小通信代价为主 ；而高速局域网通常以减小局部处理时间为主。

1.2 优化的必要性

通过一个例子来看看数据库优化的必要性。存在这样一个分布式教学数据库:

S(Sno, Sn, Age, Sex)10000个元组，存放在A站点;
SC(Sno, Cno, Grade)1000000个元组，存放A站点;
C(Cno, Cn, Teacher) 100000个元组，存放在B站点;

其中S表示学生信息，C表示课程信息，SC表示学生选课信息。假设每个元组的长度为100 bit，通信系统传 输速率为10000bit / 秒，通信延迟时间为1秒。根据上述条件查询选修‘Maths’课的男生的学号和姓名。查询语句一般会这样写:

SELECT Sno, Sn FROM S, SC, C 
WHERE S.Sno = SC.Sno 
AND SC.Cno = C.Cno 
AND Sex = ‘M’
AND Cn = ‘Maths’

再次之前我们还应该知道代价估算的计算公式：

T = 传输延迟时间 + 传输数据量 / 数据传输速率
= 传输次数 * 1 + 传输的bit数 / 10000

可以有如下六种不同的方案查询,选择不同的方法查询时间上会相差很大，由此可见做查询优化是很有必要的。

二、查询优化基础

关系代数表达式可以表示出各操作的执行顺序， 可以利用等价变换，实现查询优化。关系代数所有操作数都是关系，计算结果也是关系。关系代数有九种常见操作符：其中2个(选择和投影)一元操作符，7个二元操作符。

一元运算:选择(σ)，投影(π)
二元运算:并(∪)，交(∩)，差(-)，除 (÷)，笛卡儿积(x )，连接(∞)，半连接 (∝)

关系代数中的运算符也可以分为集合运算符和专门的关系运算符，如下图:

按照1.2中的例子，执行如下查询语句查询选择 c1 课程的学生:

Select Sn
from s,sc
Where s.Sno=sc.Sno and Cno=‘c1’

对于上述查询语句，在关系代数中可以有如下三种表达形式:

对一个关系代数表达式表示的查询进行语法分析，可以得到一棵操作树。树的叶子是已知的关系，树的各个节点是关系代数操作符，树的根是查询结果。

三、查询的分类和查询处理步骤

3.1 查询的分类

分布式数据库中的查询分为三类:局部查询、远程查询、全局查询。

• 局部查询:只涉及本地站点的数据
  局部查询中的优化策略和集中式数据库类似。主要从下面四个方面做起：
  1、先做选择和投影。 先操作使数据量变小的操作，后期的遍历效率也会高。
  2、在执行连接前对数据库数据进行适当的预处理，入队数据按连接属性排序和在连接属性上简历索引，以减少扫描。
  3、将一些操作组合起来，减少扫描次数。如从左边往右边连接，扫描次数可能是n+m * n；从右边往左边连接扫面次数可能是m * n+m，此时比较两者的大小，找出最佳组合方式。
  4、找出公共表达式。可按照 2 x 3 + 2 x 4 = 2 x (3 + 4) 这个做类比，明显后者运算步骤少。
• 远程查询:只涉及远程站点的数据
  优化策略与局部查询基本类似。但是在多副本的情况下，需要注意如果有多个远程站点的数据都满足查询数据，需要选择通信代价比较低的站点。
• 全局查询:查询涉及多个站点的数据
  全局查询中主要需要做好以下四种操作。
  1、具体化，即为全局查询选定片段的副本。
  2、确定操作次序，主要是确定连接和并运算的次序。
  3、确定操作的执行方法，将操作组合，选定访问路径、处理方法，其中重点是连接的处理。
  4、确定执行站点。

3.2 查询处理步骤

1. 查询分解:把查询问题转换成定义在全局关系上的关系代数表达式或SQL语句。
2. 数据本地化:把一个全局关系上的查询，转化为对片段的查询。涉及分片模式、分配模式。
3. 全局优化:找出各个分段查询之间的最佳操 作次序，使得代价最小。其重点在连接运算的 优化。
4. 局部优化:对各站点的局部查询做优化，类似于集中数据库。

四、基于关系代数等价变化优化

• 将连接、并运算向根部移动，选择、投影移动到叶子(即先做选择和投影操作，连接和并运算放到最后)。
• 将选择条件与水平分片条件结合，去掉矛盾的分支(假如筛选条件中为男，则首先把女给排除)。
• 将投影属性与垂直分片属性比较，去掉无关的分支。

五、基于半连接运算优化

办理按揭可以缩减关系的大小，以减少数据传输量。适用于通信费用矛盾的场合。具体优化请看下面的例子。

假设有两个站点Site1和Site2，Site1上存放R关系，R关系中有属性A，Site2上存放S关系，S关系中有属性B。
如果想让R和S关系执行连接操作，可以按照下面公式做转化计算。

代价估算的流程如下:

计算过程如下：

计算结果如下:

对于上述流程也可以反过来执行，即站点Site1和Site2分别反过来计算，则计算结果如下：

显然针对上述计算，共有两种方式，至于究竟该采用那一种方式，可以根据二者计算出来的大小做比较，进而做出合适的选择方案。

六、基于直接连接查询优化

从上面直接连接转换为半连接的方案中可以看出，直接连接方案金座一次数据传输即可，但是直接连接转换为半连接计算会增加通信数量(两次)和本地处理时间。转换半连接的最大好处在于减少了网络数据传输量。 一般而言对于高速局域网络环境，可以忽略数据传输量因素，本地处理费用才是最应该考虑的因素。接下来简单讨论下高速局域网中直接连接的优化。

6.1 利用站点依赖信息

所谓的站点依赖信息可以理解成诱导分片的条件。利用站点依赖特性可以使一些数据无需传输。

无数据传输连接的判定算法。

6.2 分片和复制算法

假设有两个站点S1和S2以及两个关系R1和R2(均包含A属性)。其中R1被分成两部分分别存放在S1和S2上，R2也被分为两部分分别存放在S1和S2上。即下图:

如对果两个关系R1和R2在属性A上进行连接操作。第一种方案可以让R1保持分片状态，R2保持完整状态，则处理方式为:将片段F21复制到站点S2 ，与F22合并得到R2 ;将片段F22复制到站点S1 ，与F21合并得到R2，然后分别在站点S1和S2做连接运算。反过来第二种处理方式可以让R2保持分片状态，R1保持完整状态，计算方式同第一种方案类似。

设各个片段的大小为:| F11 |=50 | F12 |=50 | F21 |=100 | F22 |=200
设数据通信代价为:C(x)=x
本地并运算代价为:U(x1,x2)=2(x1+x2)
本地连接代价为:J(x1,x2)=5(x1+x2)

令R1保持分片状态:
站点S1上的代价FT(Q, S1, R1)=2550 :
200 --传输F22
2(100+200) --F21UF22
5(50+300) --F11 ∞ ( F21UF22 )
站点S2上的代价FT(Q, S2, R1)=2450 :
100 --传输F21
2(100+200) --F21UF22
5(50+300) --F12 ∞ ( F21UF22 )
取2450和2550中的最大值，所以总代价为2550。

令R2保持分片状态
站点S1上的代价FT(Q, S1, R2)=1250
50 --传输F12
2(50+50) --F11UF12
5(100+100) --F21 ∞ ( F11UF12 )
站点S2上的代价FT(Q, S2, R2)=1750 :
50 --传输F11
2(50+50) --F11UF12
5(200+100) --F22∞ ( F11UF12 )
总代价为:1750

综上，选择令R2保持分片状态。

补充(笛卡尔积、自然连接(直接连接)以及半连接的区别)

笛卡尔积

笛卡尔积

自然连接是一种特殊的等值连接。注意两点，1、两个关系中比较分量必须是相同的属性值。2、在结果中吧重复的属性所在列去掉。

半连接：