【数据库技术】查询处理

1、第九章 查询处理,9.1 查询处理的过程 9.2 关系代数表达式的转换（重点） 9.3 查询代价的度量 9.4 实现关系运算的算法代价 9.5 表达式的求值方法 9.6 查询优化（重点）,9.1 查询处理的过程,查询处理进程的三个步骤（见教材P159）： (1)语法分析与翻译；(2)查询优化（重点）；(3)查询执行。,据,图9.1 查询处理过程,优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在

2、非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。,查询优化器 查询优化是影响RDBMS性能的关键因素。主要解决下面3个问题： 问题1：每个查询语句可以翻译成多个等价的关系代数表达式，应该选择哪一个表达式？ 例如有SQL语句： Select student_number from student where student_number“s000003” 等价表达式为： stud

3、ent_number“s000003”( student_number(student) student_number(student_number“s000003”(student),问题2：每个关系表达式中的关系运算可以用不同的算法来实现，且可以采用不同的索引，应该选择何种算法或索引？ 问题3：对于表达式的求值何种采用计算方法？ 以上三个问题的解决的方法形成执行计划。,9.2关系代数表达式的转换,引例：“请给出计算机系的教师所讲课程的课程名称和教师姓名”。用如下两个等价的关系代数表达式表达： course_name,teacher_name （department_name=“计算机系”(

4、teacherteaching)，其关系表达式树如下： course_name,teacher_name,teacher,teaching,department_name=“计算机系”,course_name,teacher_name （department_name=“计算机系”(teacher）teaching)，其关系表达式树如下： course_name,teacher_name,department_name=“计算机系“,teaching,teacher,9.2.1 等价规则 约定：用表示谓词，用L表示属性列表，用E表示关系代数表达式。 （1）的级联： 12(E)= 1(2(E)

5、（2）选择运算满足交换律：1(2(E)=2(1(E) （3）的级联： L1（ L2（ Ln（E）= L1(E) （4）选择可与笛卡儿积以及theta连接相结合： (E1 E2)= E1 E2 1(E1 2 E2)= E1 1 2 E2 （5） theta连接（包括自然连接）运算满足交换律： E1 E2 = E2 E1,（6）自然连接运算满足结合律： (E1 E2) E3 = E1 （ E2 E3） （7）选择运算在选定条件下对运算的分配律 （8）投影运算对运算具有分配律 （9）集合运算并与交运算满足交换律 （10）集合运算并与交运算满足结合律 （11）集合运算对并、交、差运算具有分配律 （12

6、）投影运算对并运算具有分配律,9.2.2 表达式转换举例 若有关系模式： 学生（学号，学生姓名，所在系） 选课（学号，课程名），有关系表达式： 例1：学生姓名（所在系=“计算机系”(学生选课)） 此关系代数表达式的含义？ 下面对此关系作等价变换： 利用规则7（1）可得如下等价表达式： 学生姓名（所在系=“计算机系”(学生）选课）,例2：学生姓名（所在系=“计算机系”课程名 like“数据库%“(学生选课)） 此关系代数表达式的含义？ 下面对此关系作等价变换： 利用规则7（2）可得如下等价表达式： 学生姓名（所在系=“计算机系”（学生） （课程名 like“数据库%“（选课）)）,关系表达式树分

7、别如下：,学生,选课,学生姓名,所在系=“计算机系”课程名 like“数据库%“,学生,例2关系代数表达式,例1关系代数表达式,9.3 查询代价的度量,9.3.1 查询处理的代价 查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。 在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价 + CPU代价 + 内存代价,9.3.2 处理模型 I/O代价用从磁盘向主存传送的物理块数来度量。 假定所有块传送

8、的代价相同。 忽略了最终查询结果写回磁盘的代价。 实现算法的代价考虑最坏情况下的代价。,9.4 实现关系运算(选择、连接)的算法代价,算法代价主要是计算磁盘存取代价，即在磁盘向主存传送的物理块数来。 9.4.1 选择运算 （1）不用索引的搜索算法-文件扫描： 线性搜索算法A1（？） 代价为：EA1=br 二分搜索算法A2（？） 代价为：EA2=log2(br) + SC(A,r)/fr -1,（2）使用索引的搜索算法-索引扫描： 在建立主索引的码属性上的等值比较算法： 代价为：EA3=HTi+1 在建立主索引的非码属性上的等值比较算法: 代价为：EA4=HTi+ SC(A,r)/fr,9.4.

9、2 连接运算 有嵌套循环连接算法、索引嵌套循环连接算法、归并连接算法等 。 1、嵌套循环连接算法 例：rs的嵌套循环连接算法表示如下： for 对于r是的每一个元组tr，do begin for 对于s是的每一个元组ts，do begin 检查元组对（）满足连接条件吗？ 若满足则把tr.ts加到结果集中 end end,嵌套循环连接算法代价分析： 最坏情况下，缓冲区只能装一个数据块，则： EJ=nr*bs+br，其中nr为关系r中的记录条数，bs为s中记录的块数，br为r中记录的块数。 最好情况下，两个关系都能放入缓冲区中，则： EJ=bs+br 2、索引嵌套循环连接算法 将嵌套循环连接算法中

10、嵌套于内层的文件扫描改为索引扫描。则 EJ=br+nr*c，其中c为使用连接条件并利用索引对关系s进行单个选择运算的代价。,9.5 表达式的求值方法,（1）实体化计算方法 （2）流水线计算方法 （3）上述两种方法的相互结合,9.5.1 实体化计算方法 实体化计算方法是以适当的顺序每次执行表达式中的一个运算，计算结果保存到一个临时关系（实体化）中备用。如查询： 课程名(（学号“s000003”(学生) 选课）的实体化计算方法执行过程为：,课程名,学号“s000003”,选课,学生,R1,R2,R3,9.5.2 流水线计算方法 流水线计算方法是将表达式中多个关系运算组合成一个操作流水线来实现，即将一个运算的结果作为下一个运算的输入，每条记录依次执行到底。如查询： 课程名(（学号“s000003”(学生) 选课）的实体化计算方法执行过程为：,课程名,学号“s000003”,选课,学生,T1,T2,T3,9.6 查询优化,查询优化器的工作目的：产生一个代价最小的查询执行计划。 查询优化方法包括： 基于代价的优化； 启发式优化。,9.6.1 基于代价的优化方法 基于代价的优化方法，其思想是将各种可能的查询执行计划全部产生出来，然后从中选择最小的一个。这样的做法花费非常多