补充查询处理和查询优化

《补充查询处理和查询优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章内容：§1关系数据库系统的查询处理§2关系数据库系统的查询优化§3代数优化§4物理优化第九章关系查询处理和查询优化11、了解查询处理的一般步骤2、了解为什么必须进行查询优化？3、掌握关系代数的等价变换规则4、掌握代数优化的算法和优化的一般步骤5、了解物理优化的内容和方法本章要求：2一、查询处理步骤查询处理分为4个阶段，在处理过程中，一旦发现问题，则报告错误，中止处理。§1关系数据库系统的查询处理查询处理的任务：将用户提交给RDBMS的查询语句转换为高效的执行计划（方案）。3词法分析：识别出语句中的SQL关键字、属性名、关系名、运算符、常量等语

2、言符号。语法分析：检查语句是否符合SQL语法规则。(1)查询分析4语义检查：根据数据字典，检查语句中的数据库对象，如属性名、关系名等，是否有效。符号名转换：将外部名转换为内部名。安全性检查：检查用户是否有请求的存取权限。完整性检查：检查是否违反完整性约束。查询树转换：用基于关系代数的查询树来表示查询，查询树也叫语法分析树。(2)查询检查5(3)查询优化从多个可能的执行方案中选择一个执行效率较高的方案。分为两个层次。6(4)查询执行依据查询优化得到的结果，生成执行代码，执行之。代数优化：按照一定的规则，改变代数表达式中关系操作的次序和组合，使执行效

3、率更高，又称逻辑优化。物理优化：依据事先确定的策略，选择底层存取路径和算法。7二、实现查询操作的算法举例1.选择操作的实现Select*fromstudentwhere<条件表达式>；考虑<条件表达式>的几种情况：C1:无条件；C2:Sno=‘200215121’；C3：Sage>20;C4:Sdept=‘CS’ANDSage>20;8二、实现查询操作的算法举例1.选择操作的实现(1)简单的全表扫描方法对查询基本表顺序扫描，逐一检查每个元组是否满足选择的条件，对满足条件的元组作为结果输出。对于小表，简单有效。对于大表，费时。(2)索引或散列扫描方

4、法如果选择条件中的属性上有索引（B+树索引或Hash索引），可以用索引扫描方法。通过索引先找到满足条件的元组的主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。9二、实现查询操作的算法举例2.连接操作的实现Select*fromStudent,ScWhereStudent.Sno=SC.sno(1)嵌套循环方法对于外层循环(Student)的每个元组(s),检索内层循环(SC)中的每个元组(sc)，并检查这两个元组在连接属性(sno)上是否相等。如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。10二、实现查询操

5、作的算法举例(2)排序-合并方法①如果连接的表没有排好序，则将Student和SC表按连接属性Sno排序；②取Student表中的第一个Sno，依次扫描SC表中具有相同Sno的元组，把它们连接起来；③当扫描到Sno不相同的第一个SC元组时，返回Student表扫描下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。重复上述步骤直到Student表扫描完。11二、实现查询操作的算法举例(3)索引连接方法①在SC表上建立属性Sno的索引，如果原来没有的话；②对Student表中的每一个元组，由Sno的值通过SC的索引查找相应的SC元组；③

6、把这些SC元组和Student元组连接起来。循环执行②、③；直到Student表中的元组处理完为止。12二、实现查询操作的算法举例(4)HashJoin方法把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中。划分阶段：对包含较少元组的表(比如R)进行一遍处理，把它的元组按hash函数分散到hash表的桶中；试探阶段：对另一个表(S)进行一遍处理，把S的元组散列到适当的hash桶中，并将元组与桶中所有来自R并与之匹配的元组连接起来。13§2关系数据库系统的查询优化关系数据语言只需用户提出“做什么”，不必指出“怎

7、么做”，为什么能做到这一点？一个重要原因就是系统能自动进行查询优化。系统自动优化比用户自己优化会做得更好，见P267。在集中式数据库中，查询执行的总代价(开销)为：总代价=I/O代价+CPU代价+内存代价三者中，I/O代价是最主要的。查询优化的总目标：选择有效的策略，求得给定的关系表达式的值，使得查询代价较小。14例：求选修了2号课程的学生姓名。其SQL语句为：SELECT姓名FROMStudent,SCWHEREStudent.学号=SC.学号AND课号=‘2’;为什么要进行查询优化？也可用SQL语言如下实现:SELECT姓名FROMStude

8、ntWHERE学号IN(SELECT学号FROMSCWHERE课号=‘2’);15对于一个复杂的查询，不同用户可能会写出各种不同的查询方