第8章关系查询处理及其查询优化.ppt

《第8章关系查询处理及其查询优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章关系查询处理及其查询优化数据库系统概论AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem第八章关系查询处理及其查询优化8.1关系数据库系统的查询处理8.2关系数据库系统的查询优化8.3代数优化8.4物理优化8.3小结AnIntroductiontoDatabaseSystem8.1.1查询处理步骤查询分析查询检查检查通过后把SQL语句转换成等价的关系代数表达式；一般用查询树（语法分析树）来表示扩展的关系代数表达式；把数据库

2、对象的外部名称转换为内部表示。查询优化查询执行AnIntroductiontoDatabaseSystem8.1.2实现查询操作的算法示例一、选择操作的实现1.简单的全表扫描方法对小表而言简单有效。2.索引（或散列）扫描方法通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。AnIntroductiontoDatabaseSystem8.1.2实现查询操作的算法示例（续）二、连接操作的实现1.嵌套循环法(NESTED-LOOP)首先在表1中找到第一个元组，然后

3、从头开始扫描表2，逐一查找满足连接件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组；表2全部查找完后，再找表1中第二个元组，然后再从头开始扫描表2，逐一查找满足连接条件的元组，找到后就将表1中的第二个元组与该元组拼接起来，形成结果表中一个元组；重复上述操作，直到表1中的全部元组都处理完毕。AnIntroductiontoDatabaseSystem8.1.2实现查询操作的算法示例（续）2.排序合并法(SORT-MERGE)首先按连接属性对表1和表2排序；对表1的第一个元

4、组，从头开始扫描表2，顺序查找满足连接条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组。当遇到表2中第一条“大于”表1连接字段值的元组时，对表2的查询不再继续；AnIntroductiontoDatabaseSystem排序合并法(SORT-MERGE)找到表1的第二条元组，然后从刚才的中断点处继续顺序扫描表2，查找满足连接条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组。直接遇到表2中“大于”表1连接字段值的元组时，对表2的查询不再继续

5、；重复上述操作，直到表1或表2中的全部元组都处理完毕为止。注：常用于等值连接。AnIntroductiontoDatabaseSystem8.1.2实现查询操作的算法示例（续）3.索引连接(INDEX-JOIN)对表2按连接字段建立索引；对表1中的每个元组，依次根据其连接字段值查询表2的索引，从中找到满足条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组；重复上述操作，直到表1中的全部元组都处理完毕为止。AnIntroductiontoDatabaseSystem8.1

6、.2实现查询操作的算法示例（续）3.Hash-Join方法划分阶段，对包含较少元组的表（比如表2）进行一遍处理，把它的元组按hash函数分散列到hash表的桶中；试探阶段（也称为连接阶段），将另一个表（表1）的元组散列到hash桶中，并把元组与桶中来自表2与之相匹配的元组连接起来。注：上面算法假定较小的表在第一阶段后可以完全放入内存的hash桶中。AnIntroductiontoDatabaseSystem8.2关系数据库系统的查询优化8.2.1查询优化概述8.2.2查询优化的必要性AnIntro

7、ductiontoDatabaseSystem8.2.1查询优化概述查询优化的必要性查询优化极大地影响RDBMS的性能。查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。AnIntroductiontoDatabaseSystem由DBMS进行查询优化的好处用户不必考虑如何最好地表达查询以获得较好的效率。系统可以比用户程序的优化做得更好(1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息；AnIntroductiontoDatabaseSyst

8、em由DBMS进行查询优化的好处(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术。AnIntroductiontoDatabaseSystem查询优化目标查询优化的总目标选择有效策略，求得给定关系表达式的值实际系统的查询优化步骤1.将查询转换成某种内部表示，通