关系查询和查询优化.ppt

《关系查询和查询优化.ppt》由会员分享，可在线阅读，更多相关《关系查询和查询优化.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系查询和查询优化现在学习的是第1页，共24页9.1 关系数据库系统的查询处理关系数据库系统的查询处理v查询分析查询分析v查询检查查询检查v查询优化查询优化v查询执行查询执行词法分析词法分析语法分析语法分析语义转换语义转换符号名转换符号名转换安全性检查安全性检查完整性检查完整性检查查询树查询树代数优化代数优化物理优化等物理优化等执行策略描述执行策略描述代码生成代码生成执行查询计划的代码执行查询计划的代码数据库数据库数据字典数据字典查询语句查询语句查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行图图9.1 查询处理步骤查询处理步骤9.1.1 查询处理的步骤查询处理的步骤现在学习的

2、是第2页，共24页9.1.2 实现查询操作的算法示例实现查询操作的算法示例一、选择操作的实现一、选择操作的实现 例例1 SELECT * FROM student WHERE C1：无条件；：无条件；C2：Sno=200215121;C3:Sage20;C4:Sdept=CS AND Sage20方法方法: :1.1.简单的全表扫描简单的全表扫描2.2.索引或散列扫描索引或散列扫描二、连接操作的实现二、连接操作的实现例例2 SELECT * FROM student，SC WHERE student.Sno=SC.Sno方法：方法：1.1.嵌套循环方法嵌套循环方法2.2.排序合并方法排序合并方

3、法3.3.索引连接方法索引连接方法4.Hash Join4.Hash Join方法方法现在学习的是第3页，共24页9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.2.1 查询优化概述查询优化概述v查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响RDBMS的性能。的性能。v查询优化的可能性查询优化的可能性关系数据语言的关系数据语言的级别很高级别很高，使，使DBMS可以从关系表达式中分析查询可以从关系表达式中分析查询语义语义。 现在学习的是第4页，共24页由由DBMS进行查询优化的好处进行查询优化的好处用户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用户用

4、户不必考虑如何最好地表达查询以获得较好的效率，系统可以比用户程序的程序的优化优化做得更好。做得更好。优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 。如果数据库的物理统计信息改变了，系统可以自动对查询如果数据库的物理统计信息改变了，系统可以自动对查询重新优化重新优化以选择相适应以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。能的。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限

5、的几种可能性。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术。这些技术往往只有最好的程序员才能掌握。系优化器中包括了很多复杂的优化技术。这些技术往往只有最好的程序员才能掌握。系统的自动优化相当于使的所有人都拥有这些优化技术。统的自动优化相当于使的所有人都拥有这些优化技术。现在学习的是第5页，共24页查询优化目标查询优化目标v查询优化的总目标查询优化的总目标选择有效策略，求得给定关系表达式的值选择有效策略，求得给定关系表达式的值v实际系统的查询优化步骤实际系统的查询优化步骤1. 将查询转换成某种内部表示，通常是语法树将查询转换成某种内部

6、表示，通常是语法树2. 根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准 （优化）形式（优化）形式3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作计算各种执行算法的执行代价计算各种执行算法的执行代价选择代价小的执行算法选择代价小的执行算法4. 生成查询计划生成查询计划(查询执行方案查询执行方案)查询计划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。现在学习的是第6页，共24页基于代价模型的优化算法基于代价模型的优化算法v集中式数据库集中式数据库单用户系统单用户系统总代价总代价 = I/O代价代价 + CPU代

7、价代价多用户系统多用户系统总代价总代价 = I/O代价代价 + CPU代价代价 + 内存代价内存代价v分布式数据库分布式数据库 总代价总代价 = I/O代价代价 + CPU代价代价+ 内存代价内存代价 + 通信代价通信代价 代价模型代价模型现在学习的是第7页，共24页9.2.2 一个实例一个实例 例例3 求选修了课程求选修了课程2的学生姓名的学生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; 执行策略执行策略1 n a m e(S t u d e n t . S n o = S C

8、. S n o S C . C n o = 2 (StudentSC)2 name(SC.Cno= 2 (Student SC) 3 name(Student SC.Cno=2 (SC)现在学习的是第8页，共24页9.3 代数优化代数优化v基于关系代数等价变换规则的优化方法为基于关系代数等价变换规则的优化方法为代数优化；代数优化；v代数优化策略是通过对关系代数表达式的等价变换来提高查代数优化策略是通过对关系代数表达式的等价变换来提高查询效率；询效率；v关系代数表达式的等价是指用相同的关系代替两个表达式中关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的；相应的关

9、系所得到的结果是相同的；v两个表达式两个表达式E1和和E2是等价的是等价的,记为记为E1 E2。现在学习的是第9页，共24页9.3.1 关系代数表达式等价变换规则关系代数表达式等价变换规则设设E1、E2等是关系代数表达式，等是关系代数表达式，F是条件表达式是条件表达式l. 连接、笛卡尔积交换律连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 常用的等价变换规则常用的等价变换规则现在学习的是第10页，共24页 2. 连接、笛卡尔积的结合律连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E

10、2) E3 E1 (E2 E3) F F F F现在学习的是第11页，共24页3. 投影的串接定律投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假设：假设：1) E是关系代数表达式是关系代数表达式2) Ai(i=1，2，n), Bj(j=l，2，m)是属性名是属性名3) A1, A2, , An构成构成Bl，B2，Bm的子集的子集 现在学习的是第12页，共24页4. 选择的串接定律选择的串接定律 F1 （ F2（E） F1 F2(E)选择的串接律说明选择的串接律说明 选择条件可以合并选择条件可以合并这样一次就可检查全部条件。这样一次就可检查全部

11、条件。 5. 选择与投影的交换律选择与投影的交换律 (1)假设假设: 选择条件选择条件F只涉及属性只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假设假设: F中有不属于中有不属于A1, ,An的属性的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E)现在学习的是第13页，共24页6. 选择与笛卡尔积的交换律选择与笛卡尔积的交换律(1) 假设：假设：F中涉及的属性都是中涉及的属性都是E1中的属性中的属性 F (E1E2)F (E1)E2 (2) 假设：假设：F=F1F2

12、，并且，并且F1只涉及只涉及E1中的属性，中的属性， F2只涉及只涉及E2中的属性中的属性 则由上面的等价变换规则则由上面的等价变换规则1，4，6可推出：可推出： F(E1E2) F1(E1)F2 (E2) (3) 假设：假设： F=F1F2，并且，并且 F1只涉及只涉及E1中的属性，中的属性， F2涉及涉及E1和和E2两者的属性两者的属性 F(E1E2) F2(F1(E1)E2) 它使部分选择在笛卡尔积前先做它使部分选择在笛卡尔积前先做 现在学习的是第14页，共24页7. 选择与并的分配律选择与并的分配律假设：假设：E=E1E2，E1，E2有相同的属性名有相同的属性名F(E1E2) F(E1

13、) F(E2) 8. 选择与差运算的分配律选择与差运算的分配律假设：假设：E1与与E2有有相同的属性名相同的属性名F(E1-E2) F(E1) - F(E2) 9. 选择对自然连接的分配律选择对自然连接的分配律F(E1 E2) F(E1) F(E2) F只涉及只涉及E1与与E2的的公共属性公共属性现在学习的是第15页，共24页10. 投影与笛卡尔积的分配投影与笛卡尔积的分配假设：假设：E1和和E2是两个关系表达式，是两个关系表达式， A1，An是是E1的属性，的属性， B1，Bm是是E2的属性的属性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,

14、B2, ,Bm(E2)l1. 投影与并的分配投影与并的分配假设：假设：E1和和E2 有有相同的属性名相同的属性名 A1,A2, ,An(E1E2)A1,A2, ,An(E1)A1,A2, ,An(E2) 现在学习的是第16页，共24页9.3.2 查询树的启发式优化查询树的启发式优化 启发式规则的代数优化启发式规则的代数优化,是对关系代数表达式的查询树进行优化是对关系代数表达式的查询树进行优化,其典型的规则有其典型的规则有:选择运算应尽可能先做选择运算应尽可能先做 目的：减小中间关系目的：减小中间关系投影运算和选择运算同时做投影运算和选择运算同时做目的：避免重复扫描关系目的：避免重复扫描关系把投

15、影运算与其前面或后面的双目运算结合把投影运算与其前面或后面的双目运算结合目的：减少扫描关系的遍数目的：减少扫描关系的遍数现在学习的是第17页，共24页v某些选择运算某些选择运算在其前面执行的笛卡尔积在其前面执行的笛卡尔积= 连接运算连接运算 例：例：Student.Sno=SC.Sno (StudentSC) Student SC提取公共子表达式提取公共子表达式现在学习的是第18页，共24页关系代数表达式的优化算法关系代数表达式的优化算法 算法：关系表达式的优化。算法：关系表达式的优化。输入：一个关系表达式的查询树。输入：一个关系表达式的查询树。输出：优化的查询树。输出：优化的查询树。方法：方

16、法：(1) 分解选择运算分解选择运算 利用规则利用规则4把形如把形如F1 F2 Fn (E)变换为变换为 F1 (F2( (Fn(E) ) (2) 通过交换选择运算，将其尽可能移到叶端通过交换选择运算，将其尽可能移到叶端 对每一个选择，利用规则对每一个选择，利用规则48尽可能把它移到树的叶端。尽可能把它移到树的叶端。(3) 通过交换投影运算，将其尽可能移到叶端通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则对每一个投影利用规则3、5、l0、11中的一般形式尽可能把它移向树的叶端。中的一般形式尽可能把它移向树的叶端。现在学习的是第19页，共24页(4) 利用规则利用规则35把选择和投影的

17、串接合并成单个选择、单个投影或一个选择后跟一个投把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换似乎影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换似乎违背违背“投影尽可能早做投影尽可能早做”的原则，但这样做效率更高。的原则，但这样做效率更高。(5) 对内结点分组对内结点分组把上述得到的语法树的内节点分组。把上述得到的语法树的内节点分组。每一双目运算每一双目运算(， ，-)和它所有的直接祖先为一组和它所有的直接祖先为一组(这些直接祖先是这些直接祖先是，运算运算)。如果其后代直到叶子全是单目运算

18、，则也将它们并入该组，但当双目运算是如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积笛卡尔积()，而且其后的选择不能与它结合为等值连接时除外。把这些单目，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。运算单独分为一组。 现在学习的是第20页，共24页例例4 求选修了课程求选修了课程2的学生姓名的学生姓名SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2; Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSC（

19、2）关系代数语法树）关系代数语法树Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSC（3）优化后的查询树）优化后的查询树结果结果project(Sname) select(SC.Cno= 2 ) join(Student.Sno=SC.Sno) StudentSC（1）把）把SQL语句转换成查询树语句转换成查询树现在学习的是第21页，共24页9.4 物理优化物理优化代数优化是改变查询语句的次序和组合，不涉及底层的存取代数优化是改变查询语句的次序和组合，不涉及底层的存取路径，路径，物理优化物理优化就是要选择高效合理的操作算法或存取路径，求的优化就是要选择高效

20、合理的操作算法或存取路径，求的优化的查询计划，达到查询优化的目标。具体方法有：的查询计划，达到查询优化的目标。具体方法有：v基于规则的启发式优化基于规则的启发式优化v基于代价估算的优化基于代价估算的优化v两者结合的优化方法两者结合的优化方法现在学习的是第22页，共24页9.4.1 基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化一、选择操作的启发式规则（一、选择操作的启发式规则（P273）对于小关系使用全表顺序扫描。对于小关系使用全表顺序扫描。对大关系来说分情况处理对大关系来说分情况处理二、连接操作的启发式规则（二、连接操作的启发式规则（P273）9.4.2 基于代价的优化基于代价的优化一、统计信息一、统计信息二、代价估算示例二、代价估算示例全表扫描算法的代价估算公式全表扫描算法的代价估算公式索引扫描算法的代价估算公式索引扫描算法的代价估算公式嵌套循环连接算法的代价估算公式嵌套循环连接算法的代价估算公式1.排序排序合并连接算法的代价估算公式合并连接算法的代价估算公式现在学习的是第23页，共24页第九章作业题：第九章作业题：第275页习题 第2、3、4题。 现在学习的是第24页，共24页