0009 关系查询处理和查询优化.ppt

第九章 关系查询处理和查询优化 授课内容 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.1 关系数据库系统的查询处理 查询处理步骤 RDBMS查询处理阶段 ： 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行 查询处理步骤 1. 查询分析 对查询语句进行扫描，从查询语句中识别出语言符号，如SQL关键字、数据库对象名。 进行语法检查和语法分析，判断查询语句是否符合SQL语法规则。 查询处理步骤 查询检查 根据数据字典对合法的查询语句进行语义检查 根据数据字典中的用户权限和完整性约束定义对用户的查询请求进行检查 检查通过后把SQL查询语句转换成等价的关系代数表达式 RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式 查询处理步骤 查询优化 每个查询都会有多个可供选择的执行策略，查询优化就是选择一个高效率的执行策略 查询优化分类 ： 代数优化：指关系代数表达式的优化 物理优化：指存取路径和底层操作算法的选择 查询处理步骤 查询执行 依据优化器得到的执行策略生成查询计划 代码生成器(code generator)生成执行查询计划的代码 实现查询操作的算法示例 1. 选择操作的实现 SELECT * FROM Student where sno = 95006 2. 连接操作的实现 SELECT * FROM Student inner join SC on Student.Sno = SC.Sno； 选择操作的实现 1. 简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表 2. 索引(或散列)扫描方法 选择条件中的属性上有索引(例如B+树索引或Hash索引) 通过索引先找到满足条件的元组指针，再通过元组指针直接在查询的基本表中找到元组 选择操作的实现 连接操作的实现 连接操作是查询处理中最耗时的操作之一 SELECT * FROM Student inner join SC on Student.Sno = SC.Sno； 连接操作的实现 嵌套循环方法(nested loop) 对外层循环(Student)的每一个元组，检索内层循环(SC)中的每一个元组 检查这两个元组在连接属性(sno)上是否相等 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止 连接操作的实现 2. 排序-合并方法(sort-merge join 或merge join) 常用算法，尤其适合连接的诸表已经排好序的情况 连接操作的实现 3. 索引连接(index join)方法 步骤： ①如果SC表的属性Sno上原来没有索引，在SC表的属性Sno上建立索引， ② 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组 ③ 把这些SC元组和Student元组连接起来 循环执行②③，直到Student表中的元组处理完为止 连接操作的实现 4. Hash Join方法 把连接属性作为hash码，选用同一个hash函数 9.2 关系数据库系统的查询优化 关系数据库系统的查询优化 关系语言（关系代数，关系演算语言和SQL语言）是一个非过程化的语言，用户只要提出“干什么”，不必指出“怎么干”。 SELECT sname FROM Student inner join SC on Student.SNO=SC.SNO where SC.CNO=‘2’ 关系数据库系统的查询优化 (1) 优化器可以从数据字典中获取许多统计信息，而用户则难以获得这些信息 (2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。 (3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术 关系数据库系统的查询优化 RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案 查询执行方案的代价 集中式数据库 总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库 总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价 9.3 代数优化 代数优化 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 关系代数表达式的等价： 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 两个关系表达式E1和E2是等价的，可记为