一、执行代价估算

 
 
即查询操作的不同执行策略的代价估算

目前关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。
 
 
 

执行开销

 
查询操作的执行开销主要包括：（以集中式数据库为例）

1. 磁盘存取块数（I/O代价） 因为磁盘I/O操作涉及机械动作，所以需要的时间和内存操作相比要高几个数量级，所以我们计算查询代价时一般以查询处理读写的块数作为衡量单位。
2. 处理机时间（CPU代价）
3. 查询的内存开销
   （如果是分布式数据库，还要考虑 4. 通信代价）

执行开销计算实例

eg：求选修了2号课程的学生姓名。
 
1）用SQL语句来表达这个查询：

SELECT Student.Sname FROM Student,SELECT WHERE Student.Sno=SC.Sno AND SC.Cno='2'; 

 
 
2）系统可以使用多种等价的关系代数表达式完成上面的查询操作，但是查询执行的策略不同，查询效率相差非常大。
我们下面分析三种非常有代表性的关系代数表达式，研究这3个表达式/执行策略需要耗费的I/O（处理读写的块数）代价。
 

为了方便计算我们先做一些假定：
a. 学生-课程数据库中有1000个学生记录，10 000个选课记录，其中选修2号课程的选课记录为50个。

b. 计算笛卡儿积时，以Student和SC的元组连接为例，一般采用的做法是：

在内存中尽可能多地装入某个表（如Student表）的若干块，留出一块存放另一个表（如SC表）的元组：然后把SC中的每个元组和Student中每个元组进行连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的Student元组连接，直到SC表处理完；
之后再读入若干块Student元组，读入一块SC元组，重复上述处理过程，直到把Student表处理完。

其实就是类似于嵌套循环算法的处理方式，但是这里由于内存的限制，只能每次取出一部分Student中的元组来和SC中的全部元组进行 连接 ，即每次读进一部分Student中的元组，都要遍历一遍SC表。

整个过程可以这样描述（上述Student对应下面的R表 SC对应S表）：

设连接表R和S分别占用的块数是Br和Bs，连接操作使用的内存缓冲区块数是为K，分配K-1块给外表。如果R为外表，则嵌套循环法存取的块数是Br+BrBs/（K-1），显然我们选择外表时应该选择块数较小的表。

c. 一个（内存缓冲区中的）块能装10个Student元组或100个SC元组。

d. 内存缓冲区中总共使用6个块，其中5块用来存放Student元组，1块用来存放SC元组

 
 

下面是对这三种执行策略的代价估算：

上面的例子不仅说明了查询优化的重要性，也给了我们十分宝贵的优化经验和优化“直觉”，之后的启发式规则就是基于类似这样的经验得出的。

二、等价变换公式

关系代数表达式的等价变换规则
我们可以通过下面这些等价关系，对关系代数表达式进行等价变换以达到提高查询效率的目的

详细描述以及证明可见王珊老师的《数据库系统概论》的代数优化章节。

1.连接、笛卡儿积的交换律

2.连接、笛卡儿积的结合律

3.投影的串接定律

4.选择的串接定律

5.选择与投影的交换律

6.选择与笛卡儿积的交换律

7.选择与并的分配律

8.选择与差运算的分配律

9.选择对自然连接的分配律

10.投影与笛卡儿积的分配律

11.投影与并的分配律

这些等价变换规则是接下来查询树优化的依据
 

三、启发式规则与查询树优化

遵循启发式规则，使用关系代数表达式的等价变换公式优化关系表达式的算法（为了形象的理解，引入查询树来表示具体的查询策略）。

（一）启发式规则

启发式规则是基于经验的规则，可以结合维基百科对 启发法 的定义来理解这个词

启发法（heuristics，源自古希腊语的εὑρίσκω，又译作：策略法、助发现法、启发力、捷思法、拍脑袋）是指依据有限的知识（或“不完整的信息”）在短时间内找到问题解决方案的一种技术。
它是一种依据关于系统的有限认知和假说从而得到关于此系统的结论的分析行为。由此得到的解决方案有可能会偏离最佳方案。通过与最佳方案的对比，可以确保启发法的质量。
典型的启发法有试错法和排除法。
鉴于启发法基于经验，有时它也可能是基于错误的经验（如感知偏离和伪关系）。

1.选择运算尽可能先做。

它往往可以使执行代价节约几个数量级。

2.把投影运算和选择运算同时进行。

如果有若干投影和选择运算，并且他们都对同一个关系操作，则可以在扫描此关系的同时完成所有这些运算以避免重复扫描关系。

3.把投影同其前或后的双目运算结合起来

没有必要为了去掉某些字段而扫描一遍关系。

4.把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算

连接运算要比同样关系上的笛卡儿积省很多时间。

（这里可以参考笔者在上面写的执行开销计算实例，执行策略2和执行策略1的第一步骤的比较。 这里省下来的I/O代价，在于写出数据块时，连接运算的结果比笛卡儿积的结果少很多，很可能是差很多数量级）总之这个第四点可以概括成一句话，连接运算比笛卡儿积少花费很多I/O代价，能不笛卡儿积就不笛卡儿积

5.找出公共子表达式

对于重复出现的子表达式，如果它的结果不是很大的关系，并且从外存读入这个关系比计算该子表达式的时间少得多，则可以考虑 先计算一次该公共子表达式，并把得到的结果写入中间文件。

（二）查询树

关系数据库管理系统一般都用**查询树（query tree），也称为语法分析树（syntax tree）**来表示扩展的关系代数表达式。

DBMS对合法的查询语句进行语义检查、安全性和完整性的检查后，将SQL查询语句转换为内部表示，即等价的关系代数表达式，查询树此时就是用来表示扩展的关系代数表达式。

根据上面的那些启发式规则，我们可以使用前面写的那些等价变换公式来优化关系表达式（即优化查询树）

查询树优化方法：（主要为了缩减I/O代价）

1.利用等价变换规则4，进行如下变换

（笔者是这样理解的，对一个关系进行一次选择之后，得到的结果就会少一些，这样可以减少下一次选择涉及到的I/O代价。而如果采用左边的式子，则需要对同样的关系进行多次选择再对结果集取交集，I/O代价过大。
而且以下的几个规则，也是基于类似的对减少I/O代价的考虑。）

2.利用规则4-9，将选择移到查询树的叶端。

3.利用规则3,5,10,11中的一般形式尽可能把 投影移到树的叶端

规则3可以使一些投影消失，而规则5可以把投影分裂成两个，其中一个有可能被移向树的叶端。

4.利用规则3-5，进行选择或投影的串接合并

把选择和投影的串接合并成 单个选择、单个投影或一个选择后跟一个投影，使多个选择和投影能够同时进行，或在一个选择后跟一个投影，使多个选择和投影能够同时进行，或在一次扫描中全部完成。
尽管这样子似乎违背了“投影尽可能早做”的原则，但是这样做效率更高。

5.进行内结点分组

每一个双目运算和它所有的直接祖先为一组。如果其后代直到叶子全是单目运算，也将它们并入该组，但当双目运算是笛卡儿积，而且后面不是与它组成等值连接的选择时，则不能把这个选择与这个双目运算组成一组。把这些单目运算单独分为一组。

（三）查询树优化实例分析

NICE~~