第关系查询处理和查询优化

会计学1第关系查询处理和查询优化关系查询处理和查询优化主要内容：查询处理步骤查询的优化理论基础——代数优化物理优化——存储和结构第1页/共35页4.1关系数据库系统的查询处理RDBMS进行查询处理的目的是什么？提高计算机系统的执行效率——优化。查询过程如下：第2页/共35页查询语句词法分析语法分析语义分析符号名转换检查安全性和完整性代数优化物理优化生成代码查询分析查询检查查询优化查询执行数据库中的相关信息从另一个角度描述第3页/共35页查询语法分析器与翻译器关系代数表达式优化器执行计划执行引擎查询结果数据有关数据的统计信息在实际操作过程中上述过程如何进行？第4页/共35页4.2实现查询操作的分析RDBMS有哪些基本类型的查询操作？选择，连接4.2.1RDBMS应该怎样进行选择操作？例如选择语句Select*fromstudentwheresno=‘94545’最简单的方法：搜索全部相应的表，查找符合条件的记录或记录集合。第5页/共35页利用数据结构课程中的知识分析下列算法的特性,适用的情况。顺序搜索法；二分搜索法；散列搜索法。第6页/共35页在一个关系数据库的表中，RDBMS应该如何进行搜索(查询)？1、简单的搜索：在没有排序的情况下——顺序搜索；已经排序了——二分搜索；如果使用散列存储(或B+树)，可不可提高效率，如果可以该如何做？添加键信息(指向数据存储的位置)。—索引第7页/共35页2、索引搜索法：B+树的结构：59971544597297101521374451596372859197rootsqtRoot和sqt指针的作用是什么，非叶子节点中的数据的作用是什么？针对某一个数据，可以采取哪几种搜索方法？第8页/共35页利用B+树建立的索引进行搜索比简单的搜索性能如何？下面选择语句应该如何操作？1：select*fromstudentwheresno<‘023231’利用B+树的索引功能，在Sno属性上添加索引就可以提高操作效率。2：select*fromstudent,

s_cwherestudent.sno=s_c.snoRDBMS如何实现该操作？连接第9页/共35页4.2.2RDBMS应该怎样实现连接操作？法1.涉及到几个表，就用几层嵌套循环——该怎样做？例如：Selectsnamefromstudent,s_cwherestudent.sno=s_c.snofor(每个元组tsinstudent){for(每个元组trins_c){if(每个(ts

,tr

)对满足条件)把ts的sname放到结果中；}}第10页/共35页法2.先排序，然后再搜索——该怎样做？法3.使用索引(建立索引)；进行搜索——该怎样做？问题：连接操作与简单的选择操作，哪个执行速度高？在一个复杂查询中，用户使用的查询语句一定完全一样吗，若不一样，各种语句的执行速度都一样吗？看下例：Sfromstudent,s_cwherestudent.sno=s_c.snoands_o=‘2’操作方法有如下几种：具体方法类似于《数据结构》中介绍的相应的方法。注意：该处的排序是外部排序。第11页/共35页步1：先求两个表的笛卡尔积；步2：然后找到两个学号相同且s_o=‘2’的元组；步3：查找出姓名。法1法2步1：先求两个表的自然连接；步2：然后找到s_o=‘2’的元组；步3：查找出姓名。法3步1：先找到s_o=‘2’的元组；步2：然后student表和s_o=‘2’的元组自然连接；步3：查找出姓名。在相同条件下，哪种方法效率高，为什么？考查产生的中间结果的数量，法3应该最少，法2次之，法1最多，因此……第12页/共35页对于用户编写的查询语句，RDBMS有必要对其进行语法分析，采取最优的执行方法，以提高效率。对上面的查询的3种方法分别写出关系代数式是什么？上面3个关系代数实现的是同一个功能，因此它们是等价的。针对用户的查询请求，RDBMS如何选择高效的处理方式？第13页/共35页4.3代数优化RDBMS选择最优操作的依据是什么？4.3.1关系代数表达式等价变换规则1、下列关系代数表达式是否成立？因此有第14页/共35页1.连接、笛卡尔积的交换律设E1和E2是关系代数表达式，F是连接运算的条件，则有：第15页/共35页2、下列关系代数表达式是否成立？等值连接和连接呢？第16页/共35页2.连接、笛卡尔积的结合律没有先后次序的区别第17页/共35页3、下列关系代数表达式是否成立，执行效率是否一样？第18页/共35页3.投影的串接定律4.选择的串接定律第19页/共35页4、下列关系代数表达式是否成立，执行效率是否一样？5.选择与投影操作的交换律F与Ai的关系是什么？F只涉及到Ai(i=1,2,…,n)，若F还涉及到其他呢？假设F还涉及到属性Bj(j=1,2,…,n)，第20页/共35页5、下列关系代数表达式是否成立，执行效率是否一样？6.选择与笛卡尔积的交换律第21页/共35页问题：第22页/共35页下面每个等式是否成立，等式两面的执行效率是否一样？第23页/共35页RDBMS如何利用这些变换规则来提高效率？第24页/共35页4.3.2查询树的启发式优化RDBMS对用户的一个查询请求的处理过程是什么？查询请求语法/语义分析查询树主要是利用关系代数式的变换来降低运算的规模。代数优化物理优化执行计划/策略执行引擎结果什么是查询树？第25页/共35页例如：selectstudent.SnameFromStudent,s_cwhereStudent.Sno=s_c.Snoands_c.Cno=‘2’前面3种查询方法分别对应的关系代数式是各自的查询树如下：第26页/共35页1：students_c2：students_c3：students_c第3种要比前两种的查询效率高，为什么？第27页/共35页查询树优化的经典启发式规则：1、选择操作应尽可能先做。——Why?2、把投影运算和选择运算同时进行。——避免重复搜索(扫描)。3、把投影同其前或其后的双目运算结合起来。——避免重复扫描。4、把选择同其前面的笛卡尔积结合起来——减小规模。5、找出表达式中的公共子表达式——避免重复操作。问题：给出一个查询如何利用上述规则实现优化？第28页/共35页关系表达式的优化算法输入：一个关系表达式的查询树输出：优化的查询树步骤1：步骤2：将步骤1的结果利用变换尽可能移到树的叶端——why?步骤3：将投影运算分解并尽可能移到树的叶端——why?步骤4：把选择和投影的串接合并成一个选择后跟一个投影——why?第29页/共35页4.4物理优化代数优化的主要目的是什么，涉及没涉及到底层数据的存取？物理优化的主要目的是提高底层数据的存取效率。主要方法：4.4.1、基于启发式规则的存取选择优化一、选择操作的启发式规则：1、对于小关系，应该如何进行选择操作？全表顺序搜索。对于大关系，又如何？第30页/共35页2、若选择的条件是主码=值的查询，有多少个结果，应该怎样进行操作？1个，使用主码索引——百里挑一3、若选择的条件是非主属性=值的查询，有多少个结果，应该怎样进行操作？多个，需要根据具体情况来选择，例如在student表中，选择条件是：姓名=‘…’，应该怎样进行操作，选择条件是：专业=‘…’呢？在选择条件是：姓名=‘…’中，结果不会很多，可以使用索引搜索。在选择条件是：专业=‘…’中，结果会很多，需要使用顺序搜索。Why?索引搜索和顺序搜索的特点第31页/共35页4、若选择是属性上的非等值查询或范围查询，并且选择列上有索引，应该如何操作？同样要根据结果的规模决定使用索引搜索，还是顺序搜索。5、对于用AND连接的合取选择条件，有索引就用，否则使用顺序搜索。6、对于用OR连接的选择条件，一般顺