处理一个给定的查询，尤其是复杂查询，通常有很多策略。查询优化就是从许多策略中找出最有效的查询执行计划的处理过程。我们期望系统能够构造一个最小化查询执行代价的查询执行计划。

优化一方面在关系代数级别发生，即系统尝试找出一个与给出的表达式等价，但执行更为高效的表达式。另一方面为处理查询选择一个详细的测了。

概述

给定一个关系代数表达式，查询优化器的任务是产生一个查询执行计划，该计划能获得与原关系表达式相同的结果，并且得到结果集的执行代价最小。

为了找到最小代价查询执行计划，该计划能获得与原关系表达式相同的结果，并且得到结果集的执行代价最小。

为了找到最小执行代价查询执行计划，查询优化器需要产生一些能和给定表达式得到相同结果的候选计划，并选择代价最小的一个。查询执行计划的产生：

1. 产生逻辑上与给定表达式等价的表达式。
2. 估计每个执行计划的代价。
3. 对所产生的表达式以不同方式作注释。

要完成第一步，查询优化器需要产生与给定表达式等价的表达式，通过等价规则来进行。等价规则说明了如何将一个表达式转换成逻辑上等价的另一个表达式。通过估计一个查询计划的每个操作的结果集的统计大小来估计出单个操作的代价，把这些单个操作的代价合起来就确定了执行给定关系表达式的代价估计。

选择一个查询执行计划可以是基于执行计划的代价。这种优化称为就代价的优化。

物化视图能够帮助加速某些查询的处理。

关系表达式的转换

如果两个关系代数表达式在所有有效数据库实例中都会产生相同的元组集，则我们称它们是等价的。元组的顺序是无关紧要的。

在SQL语言中，输入和输出都是元组的多重集合，关系代数的一个多重集合版本用于计算SQL表达式。若对于所有有效的数据库，两个表达式产生相同的多重集合，则称多重集合版本的这两个关系代数表达式是等价的。

等价规则

等价规则指出了两种不同形式的表达式是等价的。

关系表达式的一些通用等价规则：

1. 合取选择运算可分解为单个选择运算的序列。该变换成为级联。
2. 选择运算符满足交换律。
3. 一系列投影运算中只有最后一个运算时必须的，其余的可省略。
4. 选择操作可与笛卡儿积以及x连接相结合。
5. x连接运算满足交换律。
6. 自然连接运算满足结合律。
7. x连接具有一定的结合律。
8. 选择运算在选择条件的所有属性只涉及参与连接运算的表达式之一时满足分配律。
9. 选择运算在选择条件1只涉及E1的属性，选择条件2只涉及E2的属性时满足分配律。
10. 投影运算在连接条件只涉及L1UL2属性时具有分配律。

还有很多。

若一组等价规则中任一条规则都不能由其他规则联合起来导出，称这组等价规则集为最小的等价规则集。

连接的次序

一个好的连接运算次序对于减少临时结果的大小是很重要的

等价表达式的枚举

查询优化器使用等价规则系统地产生与给定表达式等价的表达式。

使用等价规则把表达式E2转换成E1，则E1和E2在结构上类似，并且具有一些相同的子表达式。采用一些表达式表示技术，使两个表达式指向共享的子表达式，可以明显减少对空间的需求。此外，不必总是用等价规则产生所有可以产生的表达式。

表达式结果集统计大小的估计

一个操作的代价依赖于它的输入的大小和其他统计信息。首先列出一些有关存储在数据库系统目录中的数据库关系的统计信息，然后使用这些统计信息去估计不同关系操作运算结果的统计信息。具有最小代价估计的计划通常等于或接近于实际最小执行计划。

目录信息

DBMS目录存储了有关数据库关系的下列统计信息：

• Nr，关系r的元组数
• Br，包含关系r中元组的磁盘块数
• Lr，关系r中每个元组的字节数
• Fr，关系r的块因子—即，一个磁盘块能容纳的关系r中元组的个数
• V(A,r)，关系r中属性A中出现的非重复值个数。该值与II（r）的大小相同

关于索引的统计信息，比如B+树索引的高度和索引中叶结点的页数，也保存在目录中。

如果希望维护准确的统计信息，则每次关系修改时，必须同时更新这些统计信息。这样更新导致一定量的额外开销。因此，可以当系统处于轻负载时进行更新。

选择运算结果大小的估计

当一个选择运算的结果大小的估计依赖于选择谓词。首先考虑一个单独的等值谓词，其次考虑一个单独的比较谓词，最后考虑谓词联合。

σA=a(r)：如果假设取值是均匀分布的，并假设关系r的某个记录的属性A中的取值为a，则可选择结果有Nr/V(A,r)个元组。

σA<=v(r)：如果进行代价估计时，用于修改比较操作的值(v)已知，可做更精确的估计。属性A的最小值min(A,r)和最大值max(A,r)可存储到目录中。假设值是均匀分布的，我们可以对满足条件A<=v的记录数进行估计:若v<min(A,r)，则为0；若v>=max(A,r)，则为Nr；否则，为Nr*(v-min(A,r)/(max(A,r)-min(A,r))

复杂选择：
合取：选择σi(r)的大小，记为Si。关系中的一个元组满足选择条件n的概率为Si/Nr。上述概率称为选择σi(r)的中选率。满足全部条件的元组数量为Nr(S1S2S3……Sn)/((Nr)^n)
析取：元组满足整个析取式的概率为1减去元组不满足任何一个条件的概率。
取反：选择σ-i(r)的结果集就是不在σi(r)的关系人的元组集。

连接运算结果大小的估计

笛卡尔积r×s包含Nr*Ns个元组。r×s中的每个元组占用Lr+Ls个字节。

• 若R^S=空，则估算笛卡儿积结果集大小的方法估算。
• 若R^S是R的码，则s的一个元组至多与r的一个元组连接。因此r⋈s的元组数不会超过s中的元组数目。R^S是S的码情形一样。
• R^S既不是R的码也不是S的码。这种情况下，估计元组t在r⋈s中产生Ns/V(A,s)个元组。考虑r中的所有元组，估计有Nr*Ns/V(A,r)个元组。

其他运算的结果集大小的估计

• 投影：估计为V(A,r)。
• 聚集：为V(A,r)。
• 集合运算：可以将运算重写成析取、合取或取反。
• 外连接：大小估计为⋈连接的大小加上外连接一侧的关系的大小。

选择执行计划

当我们用等价规则得到较优的关系代数式后，我们需要选择一个较好的算法来执行。

每个关系运算可以用不同的算法，有多个可选的执行计划。另外，还要决定是否采用流水线技术。

查询执行技术的相互作用

最简单是为每个运算选择一个代价最小的算法。只要保证表达式树中层次较低的运算比层次较高的运算先执行，可选择任意的运算执行顺序。

然后总体上最佳的算法可能单个运算不是最优。所以，我们必须为表达式每个运算考虑可选的算法。用类似等价规则的规则来定义每个操作可用的算法，以及决定结果是否流水线化或者是否实体化。

两大类方法：

• 搜索所有的计划，基于代价选择最佳的计划；
• 使用启发式方法选择。

基于代价的优化

基于代价的优化器通过使用等价规则从给定的查询语句产生一系列查询执行计划，并选择代价最小的一个。

我们设计一个动态规划算法来寻找最佳连接算法。动态规划算法能够存储计算结果并将其重用，可大大减少执行时间。

若某个具体的元组排序顺序对后面的元素很有用的话，我们称该特定的顺序是一个感兴趣的排序顺序。还有其他几项技术来减少在大量计划中搜索的代价：

• 如果检查了该表达式的某部分后，发现这一部分最小代价已经比先前已检查过的整个表达式的执行计划的最小代价大，那么，可以终止对这个表达式的检查。
• 发现一个子表达式的最佳计算方法的代价比先前检查过的整个表达式的最小执行计划所需代价还大，则没必要对包含该表达式的任何完整表达式继续检查。
• 通过一开始对好的计划作启发式猜测，可减少全面考虑的执行计划数目。

上述的查询优化方法主要集中在连接操作的顺序优化。

一些数据库系统使用的查询优化器是基于等价规则的，器易于扩展查询优化器以适应新规则。

启发式优化

基于代价的优化的缺点在于优化本身的代价。查询优化器可以使用启发式方法减少优化代价。启发式规则的例子：

• 尽早执行选择运算
• 尽早执行投影运算

多数现实中的查询优化器有更多的启发式规则来减少代价。如，许System R优化器，只对特殊类型的连接次序搜索，仅考虑右操作对象是原始关系的连接顺序，这称为左深连接顺序。

某些版本的Oracle系统最初采用减少连接顺序选择代价的启发式优化方法。有些采用基于SQL嵌套块概念的一个层次化过程。还有基于代价的优化技术独立地应用到每个查询块上。许多应用都会反复执行相同的查询，不过查询中的参数不一样，作为启发式方法，可以只对查询进行一次优化并缓存该查询执行计划。

即使使用启发式方法，基于代价的查询优化仍给查询处理带来不少开销。然而，增加的开销通常小于查询执行时间的节省，查询执行时间主要在慢速的磁盘存取上。

嵌套子程序的优化

SQL概念上讲位于where子句中嵌套子查询处理称传入参数并且返回一个单独值或一个值的集合的函数。参数是嵌套子查询中用到的外层查询的变量。概念上，子查询视为一个函数，它获得一个参数并返回结果集。这种执行称为相关执行，效率不高，因为子查询对外层查询的每一个元组都进行单独运算，导致大量的I/O操作。

SQL优化器尽可能将嵌套子查询转换成连接形式。有效的连接算法避免了昂贵的随机I/O操作。

复杂嵌套子查询的优化是一个困难的工作，许多优化器仅作少量的去除相关工作，最好避免使用复杂嵌套子查询。

物化视图

一个其内容已计算并存储的视图。物化视图引起了冗余数据。在许多情况下，读一个物化视图的内容比通过执行定义该视图的查询得到该视图的内容代价低得多。

视图维护

物化视图的数据必须同原始数据一致，必须进行更新，这样的任务称为视图维护。

视图可以通过人工手写代码维护。也可以对视图定义中每一个关系的插入，删除和更新操作定义触发器。一个更好的方法是对物化视图受影响部分进行修改，称为增量的视图维护。

• 立即视图维护：当更新发生时，增量视图维护作为关系事务的一部分立即执行。
• 延迟视图维护：视图维护延迟到更晚一些，减少了更新事务的负载，但可能导致物化视图与定义它们的关系不一致。

增量的视图维护

导致一个物化视图过时的改变关系的操作包括插入、删除和更新。可以将更新一个元组操作为删除该元组再插入一个更新的元组操作。对一个关系或表达式的改变称作它的一个变化量。

连接操作：考虑物化视图r⋈s。假设对关系r插入一个元组集Ir的改变。可以将插入一个元组集的物化视图的更新表达式重写为V(new)=V(old) U (Ir⋈s)，r的原值记为r(old)，新值记为r(new)。删除一个元组集Dr是：V(new)=V(old)-(Dr⋈s)。

选择和投影操作：记视图为V=σx(r),插入元组集Ir:V(new)=V(old) U σx(Ir)，删除元组集Dr:V(new)=V(old) – σx(Dr).投影是一个更困难的操作，考虑视图V=IIA(r)。对投影的每个元组，将保留一个计数，当关系r中删除一个元组集Dr时，对Dr中对每个元组t:令t.A表示t在属性A的投影。我们在物化视图中找到(t.A)，然后对其中存储的计数减一。如果计数变为0，则删除(t.A)，插入则相应加一，如果没有，则插入。

聚集操作
count：与投影类似，当从关系r中删除一个元组集Dr时，作投影的操作。
sum：大致如上。
avg：大致如上。
min，max：插入处理直截了当，删除时还需查看关系r的其他元组是否有最小值。

表达式的处理

可以从最新的子表达式开始，推导出用于计算每一个子表达式结果的增量变化表达式。

查询优化和物化视图

重写查询以利用物化视图
将使用物化视图的地方替换成它的定义
物化视图的选择必须基于系统的工作负载，类似于索引的选择，在数据库应用系统性能调整中介绍