数据库应用精品教学（华南理工大学）chp9.ppt

An Introduction to Database System 第九章 关系系统及其查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.5 小 结 关系系统及其查询优化（续） 本章目的： RDBMS的查询处理步骤 查询优化的概念 基本方法和技术 查询优化分类 ： 代数优化 物理优化 9.1 关系数据库系统的查询处理 9.1.1 查询处理步骤 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行 9.1.2 实现查询操作的算法示例 9.1 关系数据库系统的查询处理 9.1.1 查询处理步骤 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行 9.1.2 实现查询操作的算法示例 一、 选择操作的实现 二、 连接操作的实现 一、 选择操作的实现 ［例1］ Select * from student where 条件表达式 ； 考虑条件表达式的几种情况： C1：无条件； C2：Sno＝200215121； C3：Sage20； C4：Sdept＝CS AND Sage20； 选择操作的实现（续） 1. 简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表 2. 索引(或散列)扫描方法 适合选择条件中的属性上有索引(例如B+树索引或Hash索引) 通过索引，先找到满足条件的元组主码或元组指针，再通过元组指针，直接在查询的基本表中找到元组 选择操作的实现（续） ［例1-C2］ Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码) 使用索引(或散列)得到Sno为‘200215121’ 元组的指针 通过元组指针在student表中检索到该学生 ［例1-C3］ Sage20，并且Sage 上有B+树索引 使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage20的所有元组指针 通过这些元组指针到student表中检索到所有年龄大于20的学生。 选择操作的实现（续） ［例1-C4］ Sdept＝‘CS’ AND Sage20，如果Sdept和Sage上都有索引： 算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage20的另一组元组指针 求这2组指针的交集 到student表中检索 得到计算机系年龄大于20的学生 算法二：找到Sdept＝‘CS’的一组元组指针， 通过这些元组指针到student表中检索 对得到的元组检查另一些选择条件(如Sage20)是否满足 把满足条件的元组作为结果输出。 二、 连接操作的实现 连接操作是查询处理中最耗时的操作之一 本节只讨论等值连接(或自然连接)最常用的实现算法 ［例2］ SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno； 连接操作的实现 1. 嵌套循环方法(nested loop) 对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc),在连接属性(sno)上是否相等 2. 排序-合并方法(sort-merge join 或merge join) 取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组 连接操作的实现 3. 索引连接(index join)方法 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组 把这些SC元组和Student元组连接起来 连接操作的实现 4. Hash Join方法 把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中 步骤： 划分阶段(partitioning phase)： 对包含较少元组的表(比如R)进行一遍处理 把它的元组按hash函数分散到hash表的桶中 试探阶段(probing phase)：也称为连接阶段(join phase) 对另一个表(S)进行一遍处理 把S的元组散列到适当的hash桶中 把元组与桶中所有来自R并与之相匹配的元组连接起来 第九章 关系系统及其查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 关系系统的查询优化 非关系系统 9.3 代 数 优 化 9.4 物 理 优 化 9.5 小 结 9.2 关系数据库系统的查询优化 影响RDBMS性能的关键因素 由于关系表达式的语义级别很高，