第04章关系查询处理和查询优化.ppt

,*,第四章 关系查询处理和查询优化,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,问题,关系数据库的操作对象和操作结果分别是什么？,SQL,语言是过程化的？还是非过程化的？,SQL,语言的特点是什么？,方便了用户，计算机系统在执行时是否也具有较高的效率？,C,源程序,语法检查,语句结构分析,生成目标文件,编译,将多个目标文件连接,起来生成可执行程序,运行,计算机系统如何处理,SQL,语句？,计算机系统如何处理,c,语言程序？,过程如下：,关系查询处理和查询优化,主要内容：,查询处理步骤,查询的优化,理论基础代数优化,物理优化存储和结构,4.1关系数据库系统的查询处理,RDBMS,进行查询处理的目的是什么？,提高计算机系统的执行效率,优化。,查询过程如下：,查询语句,词法分析,语法分析,语义分析,符号名转换,检查安全性,和完整性,代数优化,物理优化,生成代码,查询分析,查询检查,查询优化,查询执行,数据库中的,相关信息,从另一个角度描述,查询,语法分析器,与翻译器,关系代数表达式,优化器,执行计划,执行引擎,查询结果,数据,有关数据的统计信息,在实际操作过程中上述过程如何进行？,4.2实现查询操作的分析,RDBMS,有哪些基本类型的查询操作？,选择，连接,4.2.1RDBMS,应该怎样进行,选择操作,？例如选择语句,Select*from student where,sno,=94545,最简单的方法：,搜索全部相应的表，查找符合条件的记录或记录集合。,利用数据结构课程中的知识分析下列算法的特性,适用的情况。,顺序搜索法；,二分搜索法；,散列搜索法。,在一个关系数据库的表中，,RDBMS,应该如何进行搜索(查询)？,1、简单的搜索：,在没有排序的情况下,顺序搜索,；,已经排序了,二分搜索,；,如果使用散列存储(或,B+,树)，可不可提高效率，如果可以该如何做？,添加键信息(指向数据存储的位置,)。,索引,2、索引搜索法：,B+,树的结构：,59,97,15,44,59,72 97,10 15,21 37,44,51,59,63 72,85 91 97,root,sqt,Root,和,sqt,指针的作用是什么，非叶子节点中的数据的作用是什么？,针对某一个数据，可以采取哪几种搜索方法？,利用,B+,树建立的索引,进行搜索比简单的搜索性能如何？,下面选择语句应该如何操作？,1：,select*from student where,sno,023231,利用,B+,树的索引功能，在,Sno,属性上添加索引就可以提高操作效率,。,2：,select*from student,s_c where,student.,sno,=s_c.,sno,RDBMS,如何实现该操作？,连接,4.2.2RDBMS,应该怎样实现,连接操作？,法,1.,涉及到几个表，就用几层嵌套循环该怎样做？,例如：,Select,sname,from student,s_c where student.,sno,=s_c.,sno,for(,每个元组,t,s,in student),for(,每个元组,t,r,in s_c),if(,每个(,t,s,t,r,)对满足条件),把,t,s,的,sname,放到结果中；,法,2.,先排序，然后再搜索该怎样做？,法3.,使用索引(建立索引,)；,进行搜索该怎样做？,问题：连接操作与简单的选择操作，哪个执行速度高？,在一个复杂查询中，用户使用的查询语句一定完全一样吗，若不一样，各种语句的执行速度都一样吗？看下例：,Select student.name from student,s_c,where student.,sno,=s_c.,sno,and s_c.,cno,=2,操作方法有如下几种：,具体方法类似于数据结构中介绍的相应的方法。,注意：,该处的排序是外部排序,。,步1：先求两个表的笛卡尔积；,步2：然后找到两个学号相同且,s_c.,cno,=2,的元组；,步3：查找出姓名。,法1,法2,步1：先求两个表的自然连接；,步2：然后找到,s_c.,cno,=2,的元组；,步3：查找出姓名。,法3,步1：先找到,s_c.,cno,=2,的元组；,步2：然后,student,表和,s_c.,cno,=2,的元组自然连接；,步3：查找出姓名。,在相同条件下，哪种方法效率高，为什么？,考查产生的中间结果的数量，法3应该最少，法2次之，法1最多，因此,对于用户编写的查询语句，,RDBMS,有必要对其进行语法分析，采取最优的执行方法，以提高效率,。,对上面的查询的3种方法分别写出关系代数式是什么？,上面3个关系代数实现的是同一个功能，,因此它们是等价的,。,针对用户的查询请求，,RDBMS,如何选择高效的处理方式？,4.3代数优化,RDBMS,选择最优操作的依据是什么？,4.3.1关系代数表达式等价变换规则,1、下列关系代数表达式是否成立？,因此有,1.,连接、笛卡尔积的交换律,设,E,1,和,E,2,是关系代数表达式，,F,是连接运算的条件，则有：,2、下列关系代数表达式是否成立？,等值连接和 连接呢？,2.,连接、笛卡尔积的结合律,没有先后次序的区别,3、下列关系代数表达式是否成立，执行效率是否一样？,3.,投影的串接定律,4.,选择的串接定律,4、下列关系代数表达式是否成立，执行效率是否一样？,5.,选择与投影操作的交换律,F,与,A,i,的关系是什么？,F,只涉及到,A,i,(,i=1,2,n)，,若,F,还涉及到其他呢？,假设,F,还涉及到属性,B,j,(j=1,2,n)，,5,、下列关系代数表达式是否成立，执行效率是否一样？,6.,选择与笛卡尔积的交换律,问题：,下面每个等式是否成立，等式两面的执行效率是否一样？,RDBMS,如何利用这些变换规则来提高效率？,4.3.2查询树的启发式优化,RDBMS,对用户的一个查询请求的处理过程是什么？,查询请求,语法/语义分析,查询树,主要是利用关系代数式的变换来降低运算的规模。,代数优化,物理优化,执行计划,/策略,执行引擎,结果,什么是查询树？,例如：,select student.,Sname,From Student,s_c,where Student.,Sno,=s_c.,Sno,and s_c.,Cno,=2,前面3种查询方法分别对应的关系代数式是,各自的查询树如下：,1：,student,s_c,2：,student,s_c,3：,student,s_c,第3种要比前两种的查询效率高，为什么？,查询树优化的经典启发式规则：,1、选择操作应尽可能先做。,Why?,2、把投影运算和选择运算同时进行。避免重复搜索(扫描)。,3、把投影同其前或其后的双目运算结合起来。避免重复扫描。,4、把选择同其前面的笛卡尔积结合起来减小规模。,5、找出表达式中的公共子表达式避免重复操作。,问题：给出一个查询如何利用上述规则实现优化？,关系表达式的优化算法,输入：一个关系表达式的查询树,输出：优化的查询树,步骤1：,步骤2：将步骤1的结果利用变换尽可能移到树的叶端,why?,步骤3：将投影运算分解并尽可能移到树的叶端,why?,步骤4：把选择和投影的串接合并成一个选择后跟一个投影,why?,4.4物理优化,代数优化的主要目的是什么，涉及没涉及到底层数据的存取？,物理优化的主要目的是,提高底层数据的存取效率,。,主要方法：,4.4.1、基于启发式规则的存取选择优化,一、选择操作的启发式规则：,1、对于小关系，应该如何进行选择操作？,全表顺序搜索。,对于大关系，又如何？,2、若选择的条件是主码=值的查询，有多少个结果，应该怎样进行操作？,1个，使用,主码索引,百里挑一,3、若选择的条件是非主属性=值的查询，有多少个结果，应该怎样进行操作？,多个，需要根据具体情况来选择，例如在,student,表中，选择条件是：姓名=，应该怎样进行操作，选择条件是：专业=呢？,在选择条件是：姓名=中，结果不会很多，可以使用,索引搜索,。,在选择条件是：专业=中，结果会很多，需要使用,顺序搜索,。,Why?,索引搜索和顺序搜索的特点,4、若选择是属性上的非等值查询或范围查询，并且选择列上有索引，应该如何操作？,同样要根据结果的规模决定使用索引搜索，还是顺序搜索。,5、对于用,AND,连接的合取选择条件，有索引就用，否则使用顺序搜索。,6、对于用,OR,连接的选择条件，一般顺序搜索。,二、连接操作的启发式规则：,1、已经对连接的属性排序，采用排序合并方法。,2、如果一个表在连接属性上有索引，则可以选用索引连接。,3、前2条都行不通，且一个表较小，将较小的表作为外循环的表，进行嵌套循环方法。,本章小结,代数优化的目的是什么？,物理优化的目的是什么？,谁负责进行查询优化？,作业：,P275 T2,3,4,