9.1 关系数据库系统的查询处理
9.1.1 查询处理步骤
关系数据库系统查询处理分为4个步骤：查询分析、查询检查、查询优化、查询执行
- 查询分析
对查询语句进行扫描、词法分析和语法分析。 - 查询检查
对合法的查询语句进行语义检查，还要根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。
这是的完整性检查是初步的、静态的检查。
检查通过后便把SQL查询语句转换成内部表示，即等价的关系代数表达式。这个过程中要把数据库对象的外部名称转换为内部表示，即等价的关系代数表达式。这个过程要把数据库对象的外部名称转换为内部表示。关系数据库管理系一般都用查询数，也称为语法分析树来表示扩展的关系代数表达式。 - 查询优化
查询优化分为代数优化和物理优化 - 查询执行
依据优化器得到的执行策略生成执行计划，由代码生成器声称执行这个查询计划的代码
9.1.2 实现查询操作的实现
9.1.2.1 选择操作的实现
9.1.2.2 连接操作的实现
连接操作是查询处理中最常用也是最耗时的操作之一
循环嵌套算法
最简单可行的算法，对外层循环的每一个远足，检索内层循环中的每一个元组，并检查这两个元组在连接属性上是否相等。
嵌套循环算法是最简单通用的连接算法，可以处理包括非等值连接在哪的各种连接操作
排序-合并算法
等值连接常用的算法，尤其适合参与连接的表已经排序的情况
算法步骤：
1. 如果参与链接的表没有排序，首先按照链接属性排序
2. 取外循环中的第一个元组，扫描内循环中同属性下的同值的元组，把它们连接起来
3. 当扫描到不同值的元组时，返回外循环表，使用下一个元组直到外循环表扫描完毕
这样内外表都仅需扫描一遍即可，但是注意考虑时间时还需要加上排序的时间，不过对于大表扫描，该算法时间还是会比循环嵌套算法短
索引连接算法
步骤：
- 在内表上已经建立了属性的索引
- 对外表中每一个远足，由需要连接的属性的值通过内标的索引查找对应的元组
- 把内外表查询到的元组连接起来
- 执行2、3直到外表处理完
hash-join算法
把连接属性作为hash编码，用同一个hash函数把内外表中要连接的元组散列到hash表中，
第一步，划分阶段，也称为创建阶段：
创建哈希表，对包含较少元组的表进行处理，将其元组按哈希函数分散到哈希表的桶中
第二步，试探阶段，也称为连接阶段：
对另一个表进行处理，把表的远足按同一个哈希函数进行散列，找到适当的哈希桶，并把元组中来自外表并与之匹配的元组连接起来。
9.2.1 查询优化概述
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得最高的效率，而且在于系统可以比用户程序的优化做得更好
在集中式数据库中，查询执行开销主要包括从盘存取块数（I/O代价）、处理机时间（CPU代价）以及查询的内存开销，在分布式数据库中还要加上通信代价
计算查询代价时一般用查询处理读写的块数作为衡量单位