【数据库系统概论】第九章关系查询处理何查询优化

9.1查询处理

一：查询处理步骤

关系数据库管理系统查询处理可以分为4个阶段：

• 查询分析
• 查询检查
• 查询优化
• 查询执行

（1）查询分析

任务：对查询语句进行扫描，分析词法、语法是否符合SQL语法规则

如果没有语法错误转入下一步

如果有语法错误则在报告中显示错误

（2）查询检查

任务：

• 对合法的查询语句进行语义检查，即根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效
• 如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作
• 还要对权限、完整性约束进行检查，如果违反则拒绝查询
• 检查通过后，把SQL查询语句转化为内部表示，也即等价的关系代数表达式
• 在此过程中，要把数据库对象的外部名称换为内部表示
• RDBMS一般用查询树（又称为语法分析树）来表示扩展的关系代数表达式

（3）查询优化

任务：每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询处理策略。按照优化的层次一般可以将查询优化分为

• 代数优化：是指关系代数表达式的优化，也即按照一定规则，通过对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询更高效
• 物理优化：是指存取路径和底层操作算法的选择。选择依据可以是基于规则的(rule based)、基于代价的(cost based)、基于语义的(semantic based)

（4）查询执行

依据优化器得到的执行策略生成查询执行计划，由 代码生成器(code generator) 生成执行这个查询计划的代码，然后加以执行，回送查询结果。

二：实现查询操作的算法示例

（1）选择操作的实现

①：全表扫描

优点：只需要用很少的内存（最少为1块）就可以运行，且控制简单。适用于规模较小的表

缺点：对于规模大的表进行顺序扫描，当选择率低时会使效率很低

②：索引（或散列）扫描

思想：如果选择条件中的属性上有索引（例如B BB+树索引或h a s h hashhash索引），可以用索引扫描。通过索引先找到满足条件的元组指针，再通过元组指针在查询的基本表中找到元组。 一般来说，当选择率低于10%时建立索引才有意义

（2）连接操作的实现

①：嵌套循环方法（nested loop）

思想：对外层循环(Student表)的每一个元组，检索内层循环(SC表)中的每一个元组，并检查这两个元组在连接属性(Sno) 上是否相等。如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止

②：排序-合并方法（sort-merge join）

如果参与连接的表没有排好序，首先对Student表和SC表按连接属性Sno排序

取Student表中第一个 Sno,依次扫描SC表中具有相同Sno的元组，把它们连接起来

当扫描到Sno不相同的第 一个SC元组时，返回Student 表扫描它的下一 个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来

重复上述步骤直至Student扫描完毕

③：索引连接（index join）

在SC表上已经建立了属性Sno的索引

对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组

把这些SC元组和Student元组连接起来

循环执行第二步和第三步，直至Student中的元组处理完毕

④：哈希连接（hash join）

思想：它把连接属性作为hash码，用同一个hash函数把Student表和SC表中的元组散列到hash表中

• 划分阶段（创建阶段）：即创建hash表。对包含较少元组的表( 如Student表)进行一遍处理，把它的元组按hash函数(hash码是连接属性)分散到hash表的桶中
• 试探阶段（连接阶段）：对另一个表(SC表)进行一遍处理，把SC表的元组也按同一个hash函数(hash 码是连接属性)进行散列，找到适当的hash桶，并把SC元组与桶中来自Student 表并与之相匹配的元组连接起来。

9.2查询优化

一：查询优化概述

（1）查询优化的地位和重要性

关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点所在。用户只要提出“干什么”，而不必指出“怎么干”。

查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较高的效率，而且在于系统可以比用户程序的“优化”做得更好。

（2）执行代价

总代价=I/O代价+CPU代价+内存代价+通信代价

• 计算查询代价时一般用查询处理读写的块数作为衡量单位

问问老师这个例子需要理解吗？真的好繁琐！

9.3代数优化与查询树

（1）启发式规则

• 【规则1】选择运算应尽可能先做：这是为了减少中间结果的规模
• 【规则2】投影和选择运算同时进行：这是为了避免重复扫描
• 【规则3】将投影运算与其前后的双目运算结合起来：这是为了避免重复扫描
• 【规则4】把某些选择运算和其前面的笛卡尔积结合起来成为一个连接运算：这是为了减少中间结果的规模
• 【规则5】提取公共子表达式（公因子）：这是为了保存计算结果，避免重复计算

（2）实现算法：输出优化查询树

【步骤1】分解选择运算：这是为了便于不同的选择运算沿树的不同分枝向树叶移动，一直移动到与这个选择条件相关的关系处，使选择尽可能先做。

【步骤2】通过交换选择运算，将每个选择运算尽可能移动到叶端：利用规则4~9尽可能把选择移动到树的叶端

【步骤3】通过交换投影运算，将每个投影运算尽可能移动到叶端：利用规则3、11、10、5尽可能把投影移动到树的叶端

【步骤4】合并选择和投影的串接：利用规则3~5把选择和投影的串接合并成单个选择、单个投影或一个选择后面跟一个投影。这是为了使多个选择或投影能同时进行，或在一次扫描中全部完成

【步骤5】对内结点分组：每一双目运算

和它所有的直接祖先的一元运算结点（σ 或Π）分为一组（如果其后代直到叶子全是单目运算，则也将他们并入该组）；注意当双目运算是笛卡尔积（×），而且其后的选择不能与它结合为等值连接时，则不能将选择与这个× ××并为一组

（3）很重要的例子

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

• 先对Student和SC做笛卡尔积
• 再对中间结果做选择（条件为 Student.Sno=SC.Sno）
• 再对中间结果做选择（条件为SC.Sno='2'）
• 最后投影

查询树：

优化1：首先选择条件尽可能下移

• SC.Sno='2'只和SC有关，所以它会沿着分支恰当的分支下移到SC的上方
• Student.Sno=SC.Sno同时涉及Student和SC，所以只能待在那里

优化2：把选择和其之前的笛卡尔积合并为等值连接，或者干脆变为自然连接

问？为什么倒数第二行上面没有投影？ 应该有的吧

另一个例子：

SELECT Student.Sno,Sname FROM Student,SC,Course
WHERE Cname='datebase' AND Ssex='女';

将SQL语句转为关系代数表达式

查询树：

优化1：选择条件复杂，先分解选择条件

优化2：运算结果去树叶子

优化3：涉及投影，保留连接属性

优化4：一些没必要的投影给他删除