查询处理是DBMS的核心，而查询优化又是查询处理中的关键技术。

本章介绍关系数据库的查询处理(query processing)和查询优化(query optimization)技术，查询优化技术一般可分为代数优化和物理优化。代数优化指关系代数表达式的优化；物理优化指通过存取路径和底层操作算法的选择进行优化。

关系数据库查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行，如下图所示：

1. 查询分析

对查询语句进行扫描、词法分析和语法分析。判断是否符合SQL语法规则，若没有语法错误就转入下一步处理，否则便报告语句中出现的语法错误。

2. 查询检查

对合法的查询语句进行语义检查。根据数据字典中关系模式的定义检查语句中的数据对象，如关系名、属性名是否存在和有效；还要根据数据字典中用户权限和完整性约束的定义对用户的存取权限进行检查。若通过检查便将SQL语句转换成内部表示，即等价的关系代数表达式。RDBMS一般使用查询树(query tree)或者语法分析树(syntax tree)来表示扩展的关系代数表达式。

3. 查询优化

每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询处理策略。一般将查询优化分为代数优化和物理优化。代数优化指对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效；物理优化则指存取路径和底层操作算法的选择。选择依据可以是基于规则、代价、语义的。

4. 查询执行

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

1. 单表选择操作

例1：SELECT * FROM Student WHERE

考虑的可能情况：

对于单表选择，一般采用全表扫描或基于索引的算法：

(1) 全表扫描

按物理次序读取Student的存储块到内存，检查每个元组\(t\)，如果\(t\)满足选择条件，则输出\(t\)。

(2) 索引扫描算法

对于C2，若Sno上有索引，则可使用索引找到符合条件的元组的指针，再通过指针检索到相应元组。

对于C3，若Sage上有B+树索引，则可使用B+树索引找到Sage=20的索引项，以此为入口点，在B+树的顺序集上得到Sage>20的所有元组指针，再通过指针检索相应的元组。

对于C4，若Sdept和Sage上都有索引，有两种实施方法：①先分别找出符合两条件的元组，然后求交集；②先找出符合其中条件一的元组集，然后再在该集合中找出符合条件二的元组，以此类推。

2. 连接查询操作

(1) 嵌套循环算法

最简单可行。对外层循环的每一个元组，检索内层循环中的每一个元组，并检查这两个元组在连接属性上是否相等。如果满足条件，则串接后作为结果输出。

(2) 排序-合并算法

等值连接最常用的算法，尤其适合参与连接的诸表已经排好序的情况。① 对参与连接的表，首先对这些表按连接属性排序；② 对表一中每个元素，依次扫描表二中具有相同连接属性的元组，将他们连接；③ 当扫描到第一个不相同的元组时，返回并选择表一的下一个元素，继续执行上述操作；

(3) 索引连接(index join)算法

索引连接算法的步骤是：① 在表一上建立连接属性索引；② 对表二中的每个元组，由Sno值通过SC的索引查找相应的SC元组；③ 把这些表一元组和表二元组连接起来；

(4) 哈希连接(hash join)算法

hash join算法也是处理等值连接的算法。它将连接函数作为hash码，用同一个hash函数把表一和表二的元组散列到hash表中。① 划分阶段，也称创建阶段，即创建hash表。对包含较少元组的表进行一遍处理，把它的元组按hash函数分散到hash表的桶中；② 试探阶段，也称连接阶段，对另一个表进行一遍处理，把该表的元组也按同一个哈希函数进行散列，找到合适的hash桶，并把该元组与桶中来自表一的元组连接起来。

关系查询优化是影响关系数据库管理系统性能的关键因素。

优化对关系系统来说既是挑战又是机遇。挑战在于为了达到用户可接受的性能必须进行查询优化；而机遇在于关系数据库可以从关系表达式中分析查询语义，存在着查询优化的可能，这也是关系系统在性能上能够接近甚至超过非关系系统的原因。

在非关系系统中，用户需要使用过程化语言表达查询请求，因此用户必须了解存取路径，系统则需要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。而在关系系统中，用户只需提出"干什么”，而不必指出“怎么干”，查询优化交由系统来做，而系统通常比用户程序的“优化”做得更好，这是因为：

在集中式数据库中，查询执行开销主要包括磁盘存取块数（IO代价）、处理机时间（CPU代价）、查询的内存开销。

代数优化是用过对关系表达式进行等价变换来提高查询效率。

两个关系表达式\(E_1\)和\(E_2\)是等价的，可记为\(E_1\equiv E_2\)。

常见变换规则见《数据库系统概论》王珊第五版 P283。

物理优化即选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。

方法常有：

1. 选择操作的启发式规则

对于小关系，使用全表扫描，即使选择列上有索引。

对于大关系，启发式规则有：