数据库技术讲义 第4章 查询优化.pptVIP

第四章 关系系统及其查询优化 4.1 关系系统 关系模型的三个基本要素：关系数据结构、关系的完整性和关系操作。 关系系统和关系模型是两个密切相关而又不同的概念。支持关系模型的数据库管理系统统称为关系系统，但关系模型中并非每一部分都同等重要，所有并不苛求数据库管理系统必须完全支持关系模型，也不苛求完全支持关系模型的系统才称为关系系统。因此，可以给出一个关系系统的最要要求及分类的定义。 4.1.1 关系系统的定义 一个系统可定义为关系系统，当且仅当它： 支持关系数据库(关系数据结构) 支持选择、投影和连接运算，对这些运算不必要求定义任何存取路径。 4.1.2 关系系统的分类 可以按照对数据结构、数据操作和完整性的支持把关系系统分为4类： 表式系统：只支持关系数据结构 最小关系系统：支持数据结构和基本的三类操作 关系完备的系统：支持数据结构和所有关系操作 全关系系统：支持关系模型的所有特性 全关系系统的十二条基本准则。 4.2 关系数据库系统的查询优化 查询优化在关系数据库系统中有着非常重要的地位，是影响数据库系统性能的关键因素。因为SQL是非过程化的语言，用户只需要指出做什么，具体的操作由数据库完成因此必须对用户的查询要求进行优化，达到一个较高的效率。 4.2.1 关系系统及其查询优化 SQL只需要用户指出做什么，而不需要指出怎么做。而非关系数据库要用户自己完成全部查询操作，用户必须了解存取路径等信息，查询效率由用户的存取策略决定。这要求用户有较高的数据库技术和程序设计技术。 4.2.1 关系系统及其查询优化 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做的更好： 优化器可以从数据字典中获得许多统计信息 如果数据库的物理统计信息变了，系统可以自动对查询进行重新优化 优化器可以考虑很多种不同的执行计划 优化器中包括了很多复杂的优化技术 4.2.1 关系系统及其查询优化 查询优化一般可分为4个步骤： 将查询转换成某种内部表示，通常是语法树 根据一定的等价变换规则把语法树转换成优化形式 选择底层的操作算法 生成查询计划 4.2.1 关系系统及其查询优化 目前的商品化数据库大都采用了基于代价的优化算法。这种算法要求优化器充分考虑系统中的各种参数，计算出各种查询执行方案的代价，选择代价最小的执行方案。查询代价主要包括： 总代价＝I/O代价＋CPU代价 在多用户系统中还有考虑内存代价。 4.2.2 实例 例：查询选修了2号课程的学生姓名 SELECT Student.Sname FROM Student,SC WHERE Student.Sno=SC.Sno AND SC.Cno=‘2’; 可以有很多种等价的关系代数表达式完成该查询。 4.2.3 查询优化的一般准则 1.选择运算尽可能先做。 2.在执行连接欠对关系做适当预处理，主要包括在连接属性上建立索引和对关系排序。 3.把投影运算和选择运算同时进行。 4.把投影同其前或其后的双目运算结合起来进行，没有必要为了投影扫描一遍关系。 5.把某些选择同在它前面要执行的笛卡儿积结合起来形成一个连接运算。 6.找出公共子表达式。 4.2.4 关系代数等价变换规则 所谓关系代数表达式的等价是指用相同的关系代替表达式中相应的关系所得到的结果是相同的。常用的等价变换有： 1.连接、笛卡儿积交换律 2.连接笛卡儿积结合律 3.投影的串接定律 4.选择的串接定律 5.选择与投影的交换律 4.2.4 关系代数等价变换规则 6.选择与笛卡儿积的交换律 7.选择与并的交换 8.选择与差的交换 9.投影与笛卡儿积的交换 10.投影与并的交换 4.2.5 关系代数表达式的优化算法 优化算法一般为： 1.利用规则4把选择分解 2.对于每一个选择利用规则4～8尽可能下移 3.对于每一个投影利用规则尽可能下移 4.把投影和选择的串接合并 5.把语法树的内节点分组 6.生成一个程序，每组节点的计算是程序中的一步。 4.2.6 优化的一般步骤 优化的一般步骤如下： 1.把查询转换为内部表示 2.把语法树转换为优化形式 3.选择底层的存取路径 4.生成查询计划，选择代价最小的 * *