数据库原理及应用-第9章关系查询处理和查询优化.pdf

《数据库原理及应用-第9章关系查询处理和查询优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库原理及应用DatabasePrincipleandApplication第九章关系查询处理和查询优化第九章关系查询处理和查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结关系查询处理和查询优化（续）本章目的：了解RDBMS的查询处理步骤掌握查询优化的概念掌握基本方法和技术查询优化分类：代数优化物理优化9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1.1查询处理步骤RDBMS查询处理阶段：1.查询分

2、析2.查询检查3.查询优化4.查询执行查询处理步骤（续）查询语句词法分析语法分析查询分析查询处理步骤语义分析符号名转换安全性检查数据库查询检查完整性检查执行策略描述数据字典查询树代码生成查询执行代数优化查询优化查询计划的执物理优化行代码1.查询分析对查询语句进行扫描、词法分析和语法分析判断是否符合SQL语法规则从查询语句中识别出语言符号如SQL关键字、属性名和关系名2.查询检查根据数据字典对合法的查询语句进行语义检查根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句

3、转换成等价的关系代数表达式RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式把数据库对象的外部名称转换为内部表示3.查询优化查询优化：选择一个高效执行的查询处理策略查询优化分类：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择查询优化方法选择的依据：基于规则(rulebased)基于代价(costbased)基于语义(semanticbased)4.查询执行依据优化器得到的执行策略生成查询计划代码生成器(codegenerator)生成执行查询计划的代码

4、9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1.2实现查询操作的算法示例一、选择操作的实现二、连接操作的实现一、选择操作的实现例1：Select*fromstudentwhere<条件表达式>；考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝'200215121'；C3：Sage>20；C4：Sdept＝'CS'ANDSage>20；选择操作的实现（续）选择操作典型实现方法：1.简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件

5、，把满足条件的元组作为结果输出适合小表，不适合大表2.索引(或散列)扫描方法适合选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组选择操作的实现（续）例1-C2:以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)使用索引(或散列)得到Sno为‘200215121’元组的指针通过元组指针在student表中检索到该学生例1-C3:以C3为例，Sage>20，并且Sage上有B+树

6、索引使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。B-树从根结点开始查找：若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。B＋树从根结点开始查找：在B＋树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。选择操作的实现（续）例1-C4:以C4为例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引

7、：算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage>20的另一组元组指针求这2组指针的交集到student表中检索得到计算机系年龄大于20的学生算法二：找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索对得到的元组检查另一些选择条件(如Sage>20)是否满足把满足条件的元组作为结果输出。二、连接操作的实现连接操作是查询处理中最耗时的操作之一本节只讨论等值连接(或自然连接)最常用的实现算法例2:SELECT*FROMStudent，S

8、CWHEREStudent.Sno=SC.Sno；连接操作的实现（续）1.嵌套循环方法(nestedloop)2.排序-合并方法(sort-mergejoin或mergejoin)3.索引连接(indexjoin)方法4.HashJoin方法连接操作的实现（续）1.嵌套循环方法(nestedloop)对外层循环(Student)的每一个元组(s)，