数据库第九章关系查询优化幻灯片.ppt

* * * * * * An Introduction to Database System （8）投影与乘积交换。设E1、E2是两个关系代数表达式，A1，A2，…，An是E1的属性，B1，B2，…，Bm是E2的属性，则有 Home An Introduction to Database System （9）结合律。设E1、E2、E3是关系代数表达式，F1、F2是连接条件，则有 Home An Introduction to Database System （10）交换律。设E1、E2是关系代数表达式，F是连接条件，则有： Home * * * * * * * * * * * * * * * * * * * * * * * * * * * * * An Introduction to Database System 连接操作的实现（续） 4. Hash Join方法 把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中 步骤： 划分阶段(partitioning phase)： 对包含较少元组的表(比如R)进行一遍处理 把它的元组按hash函数分散到hash表的桶中 试探阶段(probing phase)：也称为连接阶段(join phase) 对另一个表(S)进行一遍处理 把S的元组散列到适当的hash桶中 把元组与桶中所有来自R并与之相匹配的元组连接起来 An Introduction to Database System 连接操作的实现（续） 上面hash join算法前提：假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中 以上的算法思想可以推广到更加一般的多个表的连接算法上 An Introduction to Database System 第九章 关系系统及其查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代 数 优 化 9.4 物 理 优 化 9.5 小 结 An Introduction to Database System 9.2 关系数据库系统的查询优化 查询优化在关系数据库系统中有着非常重要的地位 关系查询优化是影响RDBMS性能的关键因素 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性 An Introduction to Database System 9.2 关系数据库系统的查询优化 9.2.1 查询优化概述 9.2.2 一个实例 An Introduction to Database System 9.2.1 查询优化概述 关系系统的查询优化 非关系系统 An Introduction to Database System 查询优化概述（续） 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好 (1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 (2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 An Introduction to Database System 查询优化概述（续） (3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术 An Introduction to Database System 查询优化概述（续） RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案 集中式数据库 执行开销主要包括： 磁盘存取块数(I/O代价) 处理机时间(CPU代价) 查询的内存开销 I/O代价是最主要的 An Introduction to Database System 分布式数据库 总代价=I/O代价+CPU代价+内存代价＋通信代价 An Introduction to Database System 查询优化概述（续） 查询优化的总目标： 选择有效的策略 求得给定关系表达式的值 使得查询代价最小(实际上是较小) An Introduction to Database System 9.2 关系数据库系统的查询优化 9.2.1 查询优化概述 9.2.2 一个实例 An Introduction to Database System 一个实例 首先来看一个简单的例子，说明为什么要进行查询