9.1查询处理 一：查询处理步骤

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

（1）查询分析

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

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

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

（2）查询检查

任务：

（3）查询优化

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

（4）查询执行

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

二：实现查询操作的算法示例 （1）选择操作的实现 ①：全表扫描

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

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

②：索引（或散列）扫描

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

（2）连接操作的实现 ①：嵌套循环方法（ loop）

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

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

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

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

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

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

③：索引连接（index join）

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

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

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

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

④：哈希连接（hash join）

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

9.2查询优化 一：查询优化概述 （1）查询优化的地位和重要性

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

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

（2）执行代价

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

问问老师这个例子需要理解吗？真的好繁琐！ 9.3代数优化与查询树 （1）启发式规则 （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';

查询树：

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

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

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

另一个例子：

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

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

查询树：

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

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

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

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