第4章查询处理与优化（Times版）11.26..doc

第4章 关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“做什么”，不必指出“怎么做”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。这是因为： (1) 优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 (2) 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 (3) 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 (4) 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。关系数据库查询优化的总目标是选择有效的策略，求得给定关系表达式的值。系统的自动优化相当于使得所有人都拥有这些优化技术。 实际系统对查询优化的具体实现不尽相同，但一般来说，可以归纳为四个步骤； (1) 将查询转换成某种内部表示，通常是语法树。 (2) 根据一定的等价变换规则把语法树转换成标准（优化）形式。 (3) 选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 (4) 生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。在集中式关系数据库中，计算代价时主要考虑磁盘读写的I/O次数，也有一些系统还考虑了CPU的处理时间。 步骤(3)和(4)实际上没有清晰的界限，有些系统是作为一个步骤处理的。对于一个查询可能会有很多候选的查询计划，因此应采取适当的启发式技术来缩减查询计划的有哪些信誉好的足球投注网站空间。另外由于统计信息的不精确性，中间结果的大小难以预计等因素使得代价的精确估计常常比较困难。 本章讨论的查询实例都是基于一个学生课程数据库，其关系模式如下： Student(Sno, Sname, Ssex, Sage, Sdept)； COURSE(Cno, Cname, Cpno, Ccredit)； SC(Sno, Cno, Grade)。 其中各属性的含义如表4.1所示。 表4.1 学生课程数据库中各属性的含义 属性名 类型 含义 Sno 字符串 学生的学号 Sname 字符串 学生的姓名 Ssex 字符串 学生的性别 Sage 数值 学生的年龄 Sdept 字符串 学生所在系部（缩写） Cno 字符串 课程编号 Cname 字符串 课程名 Cpno 字符串 每门课程的先修课（课程编号） Ccredit 数值 每门课程的学分 Grade 数值 某个学生选修某门课程所获得的成绩 4.1 SQL查询与关系代数式的转换 对查询块进行优化的第1步是将查询块表示成关系代数表达式。SQL查询块转换为关系代数表达式可以由以下三个步骤完成。 (1) FROM子句对应于关系的笛卡尔积； (2) WHERE子句对应于选择操作； (3) SELECT子句对应于投影操作。 下面举例说明上述三个步骤。 【例1】在学生课程数据库中，查询选修了2号课程的学生姓名。 用SQL语言表示为： SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 现将其转换为关系代数表达式。 (1) FROM子句对应于关系的笛卡尔积，得。 (2) WHERE子句对应于选择操作，得。 (3) SELECT子句对应于投影操作，得。 综合上述三个步骤，得到。 【例5】在学生课程数据库中，查询成绩不及格学生的姓名和相应课程名。 用SQL语言表示为： SELECT Sname, Cname FROM Student, Course, SC WHERE Student.Sno=SC.Sno AND Course.Cno=SC.Cno AND Grade60; 现将其转换为关系代数表达式。 (1) FROM子句对应于关系的笛卡尔积，得。 (2) WHERE子句对应于选择操作，得。 (3) SELECT子句对应于投影操作，得。 综合上述三个步骤，得到 。 4.2 关系代数的等价变换规则 关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化最好从研究关系表达式的等价变换规则开始。所谓关系代数表达式的等价是指用相同的关系实例代替表达式中相应的关系时所得到的结果相同。两个关系表达式E1和E2是等价的，可记为