清华大学数据库access幻灯片-第09章：查询处理

2019/4/20,1,数据库系统设计与原理,第部分 DBMS的内核 (第章第11章),2019/4/20,2,第9章 查询处理,讲课内容： 查询处理是指从数据库中提取数据的一系列活动。这一系列活动包括：将用高层数据库语言表示的查询语句，如SQL，翻译成能在文件系统这一物理层上实现的表达式，如关系代数；为优化查询进行的各种转换；以及查询的实际执行。 查询处理的过程 表达式的求值方法 关系代数表达式的转换 查询优化的方法 查询代价的度量 查询优化器的构造 实现关系运算的算法代价本章总结,2019/4/20,3,DBMS总体结构回顾：查询处理器,2019/4/20,4,§9.1查询处理的过程,查询处理 是指对最终用户提交的查询进行： 解析 优化 执行 并最终给出查询结果的处理过程。,2019/4/20,5,§9.1查询处理的过程,查询优化器 问题的提出： 一个查询用SQL语言可以有多种表达方式； 而每个SQL语句又可以翻译成多个等价的关系代数表达式。例如： select student_number from student where student_number “s000003” 可以翻译成下面两个关系代数表达式： student_number”s000003”(student_number(student) student_number(student_number”s000003”(student) 表达式中的关系运算又可以用不同的算法和索引去实现。因此，查询优化器的任务就是要找出代价最小的计算给定查询的处理过程。,2019/4/20,6,§9.1查询处理的过程,查询优化器 输入？输出？ 查询执行计划？带注释！ 注释用于说明： 如何具体实施每个关系操作。例如： 关系运算所采用的算法 将要使用的索引 执行原语： 加上了有关“如何执行”的注释的关系代数运算 查询执行(计算)计划： 用于计算一个查询的原语序列。,2019/4/20,7,查询优化器 查询优化 为给定查询选择最有效的查询执行计划的过程： 在关系代数级进行优化，力图找出与给定表达式等价、但执行效率更高(?)的一个表达式； 查询语句处理的详细策略的选择。例如，确定算法与索引等。 本章的主要内容 什么是查询执行计划的代价？ 如何估计查询执行计划的代价？ 如何进行有效的查询优化？,§9.1查询处理的过程,2019/4/20,8,§9.1查询处理的过程,执行引擎 输入是查询执行计划 输出则是具体的查询结果,2019/4/20,9,§9.2关系代数表达式的转换,等价的关系代数表达式 它们的执行结果相同，但代价不同。例如： “请给出计算机系的教师所讲课程的课程名称和教师姓名”，就可以用如下两个等价的关系代数表达式来求值： course_name, teacher_name (department_name = “计算机系”(teacherteaching) course_name, teacher_name (department_name = “计算机系”(teacher)teaching) 从感觉上讲，哪个关系代数表达式的计算效率更高一些？为什么？,2019/4/20,10,§9.2关系代数表达式的转换,关系代数表达式树 为了更明显地看出上述两个表达式的差别，还可以用关系代数表达式树来描述它们：,2019/4/20,11,§9.2关系代数表达式的转换,表达式的转换与等价 通过等价规则进行关系代数表达式的转换； 等价规则顾名思义就是指两种不同形式的表达式可以相互转换，而又保持等价； 所谓保持等价是指两个表达式产生的结果关系具有相同的属性集和相同的元组集，但属性出现的次序可以不同。 等价规则 在下面的等价规则中，用、1、2等表示谓词；用L、L1、L2等表示属性列表；用E、E1、E2等表示关系代数表达式。,2019/4/20,12,§9.2关系代数表达式的转换,等价规则 合取选择运算可分解为单个选择运算的序列，该变换称为的级联： 12(E) = 1(2(E) 选择运算满足交换律： 1(2(E) = 2(1(E) 投影运算序列中只有最后一个运算是需要的，其余可省略。该转换称为的级联： L1(L2(Ln(E) = L1(E),2019/4/20,13,§9.2关系代数表达式的转换,等价规则 选择可与笛卡儿积以及theta连接相结合： (E1E2) = E1E2 1(E12E2) = E112E2 theta连接(包括自然连接)运算满足交换律： E1E2 = E2E1 自然连接运算满足结合律： (E1E2)E3 = E1(E2E3) theta连接具有以下方式的结合律： (E11E2)23E3 = E113(E22E3),2只涉及E2与E3的属性； 由于任意一个条件都可为空，因此笛卡儿积运算也满足结合率！,2019/4/20,14,§9.2关系代数表达式的转换,等价规则 选择运算在下面两个条件下对theta连接运算具有分配律： 当选择条件0的所有属性只涉及E1时： 0(E1E2) = (0(E1)E2 当选择条件1只涉及E1的属性，2只涉及E2时： 12(E1E2) = (1(E1)(2(E2) 投影运算对theta连接运算具有分配律： 令L1、L2分别是E1、E2的属性，而连接 条件只涉及L1L2中的属性，则： L1L2(E1E2) = (L1(E1)(L2(E2),2019/4/20,15,§9.2关系代数表达式的转换,等价规则 投影运算对theta连接运算具有分配律： 令L1、L2分别是E1、E2的属性，L3是E1里出现 在连接条件中但不在L1L2中的属性，而L4 是E2里出现在连接条件中但不在L1L2中的 属性，那么： L1L2(E1E2) = L1L2(L1L3(E1)(L2L4(E2) 集合运算并与交满足交换律： E1E2 = E2E1；E1E2 = E2E1 但是集合差运算不满足交换律！,2019/4/20,16,§9.2关系代数表达式的转换,等价规则 集合运算并与交满足结合律： (E1E2)E3 = E1(E2E3) (E1E2)E3 = E1(E2E3) 选择运算对并、交、差运算具有分配律： (E1E2) = (E1)(E2) (E1E2) = (E1)(E2) (E1-E2) = (E1)-(E2) 投影运算对并运算具有分配率： L(E1E2) = (L(E1)(L(E2),2019/4/20,17,§9.2关系代数表达式的转换,表达式转换举例 假设student和selecting是以下关系模式上的关系： Student_schema = (student_number, student_name, department_name) Selecting_schema = (student_number, course_name) 对于关系代数表达式： student_name(department_name = “计算机系” (studentselecting) ),2019/4/20,18,§9.2关系代数表达式的转换,表达式转换举例 利用前面介绍的规则，可以得到如下的等价表达式： student_name(department_name=“计算机系”(student) selecting) 如果将上述查询修改为： student_name(department_name=“计算机系” course_name like ”数据库%” (studentselecting) ) 那么，如何对上述表达式进行等价变换呢？,2019/4/20,19,§9.2关系代数表达式的转换,表达式转换举例 由于选择条件中属性department_name只涉及到关系student，而属性course_name只涉及到关系selecting，因此利用规则将表达式变换为： student_name( (department_name=“计算机系”(student) (course_name like ”数据库%”(selecting) ),2019/4/20,20,表达式转换举例 用关系代数表达式树可以更明显地看出上述两个表达式的差别：,§9.2关系代数表达式的转换,2019/4/20,21,§9.3查询代价的度量,查询处理的代价 查询处理的代价可以通过该查询对各种资源的使用情况进行衡量。资源包括： 磁盘存取(磁盘I/O) 执行查询所用的CPU时间 并行/分布式数据库系统中的通信开销 磁盘访问通常是最主要的代价，这是因为： 磁盘存取比内存操作(CPU)要慢得多； CPU速度的提升要比磁盘速度的提升快的多。 结论：磁盘存取代价是查询执行计划代价的合理度量。,2019/4/20,22,§9.3查询代价的度量,代价模型 为了简化磁盘存取代价的计算，需要构造一个简单的代价模型： 存取代价用从磁盘向主存传送的物理块数来度量 假定所有块传送的代价相同。该假定忽略了： 寻道时间(搜索时间)：将磁头移动到所期望的磁道或柱面的时间； 旋转等待时间：等待所需要的数据(扇区)旋转到读写头下的时间延迟。 忽略了将查询的最终结果写回磁盘的代价； 实现关系运算的算法代价是最坏情形下的代价： 即主存中缓冲区只能容纳数目不多的数据块，需要不断地访问外存。,2019/4/20,23,§9.3查询代价的度量,用于估计代价的统计信息 查询优化器利用存储在DBMS的系统目录中的统计信息来估计查询执行计划的代价，相关的统计信息包括： nr：关系r中元组的数目； br：关系r的元组所占用的块数目； sr：关系r中一个元组的大小； fr：关系r的块因子，即一个物理块中能存放的关系r的元组数目； V(A,r)：关系r中属性A所具有的不同值的数目： 该数目与A(r)的大小相同。若A为关系r的码，则V(A,r)=nr。,2019/4/20,24,§9.3查询代价的度量,用于估计代价的统计信息 查询优化器利用存储在DBMS的系统目录中的统计信息来估计查询执行计划的代价，相关的统计信息包括： SC(A,r)：关系r的属性A的选择基数。给定关系r及其属性A，假定至少有一条记录满足等值条件，那么SC(A,r)表示在属性A上满足某个等值条件的平均记录数： 若A为r的码，则SC(A,r)=1； 若A为非码属性，并假定V(A,r)个不同的值在多个元组中平均分配，则SC(A,r)=(nr/V(A,r)。 HTi：索引i的层数，即索引i的高度；对于散列索引，HTi=1。,2019/4/20,25,§9.3查询代价的度量,统计信息的维护与使用 这里提到的统计信息是经过简化的，实际系统的查询优化器通常包含更多的统计信息。这些统计信息： 在适当的时候，比如系统负载比较轻的时候，进行更新，而不是实时更新。 利用这些统计信息来估计实现各种关系代数运算的算法代价，并把算法A的代价估计记为EA。,2019/4/20,26,§9.4实现关系运算的算法代价,概述 在关系代数中，不同的关系运算有： 、和运算等等； 这些运算的实现都离不开对文件的扫描！ 实现这些运算的不同算法是数据结构这门课要讲的内容，包括算法的时间复杂性和空间复杂性分析； 本节的主要内容是以前面介绍的代价模型为基础，根据系统目录中的统计信息来分析实现关系运算的具体算法的磁盘存取代价，即在磁盘和主存储器之间传送的数据块数！,2019/4/20,27,§9.4实现关系运算的算法代价,选择