《数据库系统概论》笔记整理（二）

关系数据库的查询处理和查询优化

一）简介

查询处理：关系数据库管理系统执行查询语句的过程

查询优化分为：代数优化（逻辑优化）和物理优化（非代数优化）

二）查询处理

步骤

1. 查询分析
2. 查询检查
3. 查询优化
4. 查询执行

1. 查询分析

首先对查询语句进行扫描、词法分析、语法分析。

即：SQL语法规则

2. 查询检查

对合法的查询语句进行语义检查。

模式定义，检查语句中的数据库对象（关系名，属性名）

若对视图操作，则要用：视图消解方法
把对视图的操作转换成对基本表的操作

用户权限和完整性约束检查

检查通过：将查询语句转换成内部表示，即关系代数表达式（查询数或语法分析树）

3. 查询优化

选择执行策略和操作算法：代数优化，物理优化

代数优化：按照一定规则，对关系代数表达式进行等价转换，改变表达式的次序和组合，使查询更高效
物理优化：选择存储路径和底层操作算法

4. 查询执行（一）

根据优化器得到的执行策略，生成查询执行计划

由代码生成器，生成执行这个查询计划的代码，加以执行

返回查询结果

三）举例

select * from Student where <表达式>

条件表达式：

• 无条件
• Sno=‘20151003963’
• Sage>20
• Sdept=‘CS’ and Sage>20

选择操作只涉及一个关系：全表扫描，或基于索引的算法

全表：取内存块，遍历。重复
索引：B+树索引（定位），B+树顺序集（范围）
	通过元组指针，到Student表中检索（O(1)）

2. B+树索引：获取元素指针，根据元组指针在查询的表上找到元素
3. B+树索引+顺序集：获取'20'索引项，在B+树的顺序集得到Sage>20的所有元组指针，去查询表检索
4. 同3+交集：获取'CS'的元组指针，获取Sage>20的元组指针，取交集，去查询表检索
			获取'CS'的一组元组指针，根据这些元组指针到查询表中检索，对得到的元组进行检查(Sage>20)，满足才返回

2. 连接操作，嵌套循环算法：多表，对外层循环的每一个元组，检测内层循环的每一个元组，满足条件，输出
		   排序——合并连接算法
		   索引连接算法
		   hash join

四）查询优化（二）

总代价=IO代价 + CPU + 内存 + 通信，IO代价为查询处理读写的块数作为衡量单位

举例

select * from A,B where A.x=B.x and A.y='2'

选择：条件筛选
投影：输出

策略一：广义笛卡尔积、选择操作、投影操作

策略二：自然连接、选择操作、投影操作

策略三：由于A.y条件，选择A，选择B，连接，投影输出

代数优化和物理优化

数学功底要求，略

物理优化的启发式规则

存取路径

选择操作

小关系，全表

大关系，启发式规则：

1. 主码=值：主码索引
2. 非主属性=值：查询结果元组数，较小则索引，否则全表
3. 非等值或范围查询：结果元组数，较小则索引，否则全表
4. and连接的合取选择：涉及组合索引，则优先采用组合索引扫描，否则索引扫描，否则全表扫描
5. or连接的析取选择：全表

连接操作

算法决定

代价估算

统计信息

表：元组总数，元组长度，占用块数，占用溢出块数

列：列不同值个数，最大值，最小值，是否有索引

索引：（B+树索引）索引层数，不同索引值的个数，索引的选择基数，叶节点数

…