《关系查询处理及其查询优化.doc》由会员分享，可在线阅读，更多相关《关系查询处理及其查询优化.doc（7页珍藏版）》请在金锄头文库上搜索。
1、关系查询处理及其查询优化第九章 关系查询处理及其查询优化章节9。1 关系数据库系统的查询处理9。2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化课型新授课课时2节课班级2002级1、2班教学目标重点掌握关系系统的查询优化。教学重点难点1. 重点掌握关系系统的查询优化.2. 画出查询的语法树和优化后的语法树。3。 优化算法，包括代数优化算法和物理优化算法。教学关键理解查询处理的过程了解查询优化的方法教学方法讲解和课件演示教具计算机大屏幕投影复习内容引入内容讲解内容9.1 关系数据库系统的查询处理9。1.1 查询处理步骤1查询分析2查询检查3查询优化4查询执行9.1.2 实现查询操作的
2、算法示例一、选择操作的实现1简单的全表扫描方法2索引（或散列）扫描方法二、连接操作的实现1循环嵌套方法2排序-合并方法3索引连接方法4Hash 连接方法9。2 关系数据库系统的查询优化9。2.1 查询优化概述n 系统选择不同的策略对查询时间影响很大。n 因此有必要对查询优化n 查询优化:为查询选择最有效的查询计划.n 查询优化极大地影响RDBMS的性能。n 查询优化的可能性n 关系数据语言的级别很高，使DBMS 可以从关系表达式 中分析查询语义。 1。由DBMS进行查询优化的好处n 用户不必考虑如何最好地表达查询以获得较好的效率n 系统可以比用户程序的优化做得更好(1） 优化器可以从数据字典中
3、获取许多统计信息,而用户程序则难以获得这些信息 （2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的.（3）优化器可以考虑数百种不同的执行计划,而程序员一般只能考虑有限的几种可能性.(4）优化器中包括了很多复杂的优化技术2。查询优化目标n 查询优化的总目标 选择有效策略，求得给定关系表达式的值3.实际系统的查询优化步骤（1） 将查询转换成某种内部表示，通常是语法树（2)根据一定的等价变换规则把语法树转换成标准（优化)形式（3）选择低层的操作算法n 对于语法树中的每一个操作n 计算各种执行算法
4、的执行代价n 选择代价小的执行算法（4）生成查询计划(查询执行方案）n 查询计划是由一系列内部操作组成的。9.代价模型n 一般DBMS采用基于代价的优化算法：n 集中式数据库n 单用户系统总代价 = I/O代价 + CPU代价n 多用户系统总代价 = I/O代价 + CPU代价 + 内存代价n 分布式数据库 总代价 = I/O代价 + CPU代价+ 内存代价 + 通信代价 9.2.2 一个实例 例：求选修了2号课程的学生姓名SELECT Student。SnameFROM Student, SCWHERE Student。Sno=SC。Sno AND SC.Cno=2； 1 name(Stud
5、ent。Sno=SC.Sno SC。Cno=2 (StudentSC）2 name(SC.Cno= 2 (Student SC）)3 Sname（Student SC。Cno= 2 (SC） 三种不同的执行策略，查询时间差别很大。假设1：外存:Student:1000条,SC：10000条, 选修2号课程:50条假设2:一个内存块装元组：10个Student, 或100个SC， 内存中一次可以存放: 5块Student元组， 1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法 . 执行策略1Q1 name （Student.Sno=SC.Sno
6、SC.Cno=2 (StudentSC) 计算笛卡尔积StudentSC 读取总块数= 读Student表块数 + 读SC表遍数每遍块数=1000/10+（1000/(105） (10000/100） =100+20100=2100 读数据时间=2100/20=105秒中间结果大小 = 100010000 = 107 (1千万条元组）写中间结果时间 = 10000000/10/20 = 50000秒做选择运算读数据时间 = 50000秒做投影运算 总时间 =1055000050000秒 = 100105秒= 27.8小时执行策略22. 2 name(SC.Cno= 2 (Student SC）
7、计算自然连接读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒执行选择运算读数据时间=50秒执行投影 总时间1055050秒205秒=3。4分执行策略33。 2 Sname（StudentSC。Cno= 2 (SC）读SC表总块数= 10000/100=100块读数据时间=100/20=5秒中间结果大小=50条 不必写入外存 连接运算读Student表总块数= 1000/10=100块读数据时间=100/20=5秒 投影 总时间55秒10秒 执行策略49. 2 name(Student SC。C
8、no=2 （SC)）假设SC表在Cno上有索引,Student表在Sno上有索引 读SC表索引Cno=2的元组。读SC表总块数= 50/1001块读数据时间更小。中间结果大小=50条 不必写入外存 读Student表索引读Student表总块数= 50/10=5块读数据时间大大减少。 总时间10秒9。3 代数优化9.3.1 关系代数等价变换规则 n 关系代数表达式等价n 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的n 两个关系表达式E1 和E2 是等价的，记为： E1E2 常用的等价变化规则有：1。 连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E
9、2 F E1 F为连接条件。2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 （E2E3) （E1 E2) E3 E1 (E2 E3） （E1 E2) E3 E1 (E2 E3) F F F F3。 投影的串接定律 A1，A2, L,An（ B1,B2， L,Bm（E）) A1，A2， L，An （E)假设：1)E是关系代数表达式2)Ai（i=1，2，n)， Bj(j=l,2，m）是属性名3)A1， A2, ， An构成Bl，B2，Bm的子集 9. 选择的串接定律 F1 （ F2（E）) F1 F2（E）n 选择的串接律说明 选择条件可以合并 n 这样一次就可检查全部条件. 5。 选择与
10、投影的交换律(1）假设： 选择条件F只涉及属性A1,，An F （A1,A2, L，An(E)） A1,A2, L,An(F(E)）（2)假设: F中有不属于A1, ，An的属性B1，Bm A1，A2, L，An ( F (E）) A1,A2， L,An(F （A1,A2, L,An，B1,B2, L,Bm（E）)6。 选择与笛卡尔积的交换律（1) 假设：F中涉及的属性都是E1中的属性 F （E1E2)F (E1）E2（2） 假设：F=F1F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性 则由上面的等价变换规则1，4，6可推出： F（E1E2) F1(E1)F2 （E2)（3） 假设
11、： F=F1F2， F1只涉及E1中的属性， F2涉及E1和E2两者的属性 F（E1E2) F2（F1（E1)E2） 它使部分选择在笛卡尔积前先做 7. 选择与并的交换假设：E=E1E2,E1，E2有相同的属性名F（E1E2） F(E1) F(E2)8。 选择与差运算的交换假设：E1与E2有相同的属性名F（E1-E2) F（E1) - F(E2) 9. 投影与笛卡尔积的交换假设：E1和E2是两个关系表达式, A1,，An是E1的属性， B1，Bm是E2的属性 A1，A2， ,An，B1,B2, ,Bm （E1E2) A1，A2, ，An（E1） B1,B2, ，Bm(E2)l0。 投影与并的交
12、换假设：E1和E2 有相同的属性名 A1，A2, ,An（E1E2） A1，A2， ，An(E1） A1,A2, ，An（E2)9。3.2 查询数的启发式优化典型的启发式规则有：1。 选择运算应尽可能先做 n 目的：减小中间关系2. 在执行连接操作前对关系适当进行预处理n （1)在连接属性上建立索引n （2）按连接属性排序n Student SCn 索引连接方法的步骤：(1）在SC上建Sno索引；(2)对Student中的每一元组，由Sno的值通过SC的索引查找SC的元组； （3)把这些SC的元组与Student的元组连接起来。对Student和SC表只扫描一遍。n 用排序合并方法的步骤：(1）先对Student表和SC表在Sno上排序；（2)取Student中的第1个Sno，依次扫描SC表中具有相同Sno的元组；把它们连接起来。(3）当扫描到Sno不相同的第1个SC的元组时,返回Student表扫描它的下一个元组,再扫描SC表中具有相同Sno的元组，把它们连接起来。直到Student表扫描完。这样,Student表和SC表也只扫描一遍.
