王珊全套配套课件数据库系统概论第5版PPT版本 20150105第5版PPT 第9章 关系查询处理和查询优化.ppt

《王珊全套配套课件数据库系统概论第5版PPT版本 20150105第5版PPT 第9章 关系查询处理和查询优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库系统概论AnIntroductiontoDatabaseSystem中国人民大学信息学院第九章关系查询处理和查询优化第三篇系统篇讨论数据库管理系统中查询处理和事务管理的基本概念和基础知识第9章关系查询处理和查询优化第10章数据库恢复技术第11章并发控制第12章数据库管理系统第九章关系查询处理和查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化*9.5查询计划的执行9.6小结关系查询处理和查询优化（续）本章内容：关系数据库管理系统的查询处理步骤查询优化的概念基本

2、方法和技术查询优化分类：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1.1查询处理步骤关系数据库管理系统查询处理阶段：1.查询分析2.查询检查3.查询优化4.查询执行查询处理步骤（续）查询计划的执行代码代数优化物理优化等查询语句词法分析语法分析语义分析符号名转换安全性检查完整性初步检查代码生成查询执行计划查询树(querytree)查询分析查询检查查询优化查询执行数据库数据字典1.查询分析查询分析

3、的任务：对查询语句进行扫描、词法分析和语法分析词法分析：从查询语句中识别出正确的语言符号语法分析：进行语法检查2.查询检查查询检查的任务合法权检查视图转换安全性检查完整性初步检查根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作2.查询检查根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。关系数据库管理系统一般都用查询树，也称为语

4、法分析树来表示扩展的关系代数表达式。3.查询优化查询优化：选择一个高效执行的查询处理策略查询优化分类代数优化/逻辑优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择查询优化的选择依据基于规则(rulebased)基于代价(costbased)基于语义(semanticbased)4.查询执行依据优化器得到的执行策略生成查询执行计划代码生成器(codegenerator)生成执行查询计划的代码两种执行方法自顶向下自底向上9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的

5、算法示例9.1.2实现查询操作的算法示例选择操作的实现连接操作的实现1.选择操作的实现选择操作典型实现方法：（1）全表扫描方法(TableScan)对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表（2）索引扫描方法(IndexScan)适合于选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组选择操作的实现（续）[例9.1]SELECT*FROMStudentWHE

6、RE<条件表达式>考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝'201215121'；C3：Sage>20；C4：Sdept＝'CS'ANDSage>20；选择操作的实现（续）全表扫描算法假设可以使用的内存为M块，全表扫描算法思想：按照物理次序读Student的M块到内存检查内存的每个元组t，如果满足选择条件，则输出t如果student还有其他块未被处理，重复①和②选择操作的实现（续）索引扫描算法[例9.1-C2]SELECT*FROMStudentWHERESno='201215121'假设Sn

7、o上有索引(或Sno是散列码)算法：使用索引(或散列)得到Sno为‘201215121’元组的指针通过元组指针在Student表中检索到该学生选择操作的实现（续）[例9.1-C3]SELECT*FROMStudentWHERESage>20假设Sage上有B+树索引算法：使用B+树索引找到Sage=20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。选择操作的实现（续）[例9.1-C4]SELECT*FROMStudent

8、WHERESdept='CS'ANDSage>20;假设Sdept和Sage上都有索引算法一：分别用IndexScan找到Sdept＝’CS’的一组元组指针和Sage>20的另一组元组指针求这两组指针的交集到Student表中检索得到计算机系年龄大于20的学生选择操作的实现（续）算法二：找到Sdept=’CS’的一组元组指针，通过这些元组指针到Student表中检索并对得到的元组检查另