第九章关系查询处理和查询优化优秀PPT.ppt

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

1、第九章关系查询处理第九章关系查询处理和查询优化和查询优化第一页，本课件共有25页关系系统的定义qq关系系统关系系统:支持关系数据模型的数据库管支持关系数据模型的数据库管理系统理系统(粗略粗略)qq关系系统关系系统(确切定义确切定义):一个系统可以定一个系统可以定义为一个关系系统义为一个关系系统,当且仅当它当且仅当它:支持关系数据库支持选择、投影和连接运算(自然连接),对这些运算不要求定义任何物理存取路径第二页，本课件共有25页关系系统的分类:qq许多关系系统的产品许多关系系统的产品qq按按E.F.Codd的思想将关系系统分为的思想将关系系统分为:表式系统表式系统(a)最小关系系统最小关系系统(

2、b)关系完备的系统关系完备的系统(c)全关系系统全关系系统(d)SMISMISMISMIabcd第三页，本课件共有25页关系系统的查询处理:qq查询处理的步骤查询处理的步骤:queryParser&translatorRelational algebra expressionOptimizerExecution planEvaluationengineQuery outputdataStatisticsabout dataDBMS第四页，本课件共有25页关系系统的查询优化:qq为什么需要查询优化为什么需要查询优化qq关系系统的查询优化由系统完成关系系统的查询优化由系统完成,而不是而不是由用户完

3、成由用户完成优化器可以数据字典获取许多统计信息如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术qq优化目标优化目标:寻求最优的执行计划寻求最优的执行计划,使查询使查询执行开销尽量小执行开销尽量小第五页，本课件共有25页关系系统的查询优化:qq查询优化的一般步骤查询优化的一般步骤将查询转化成内部表示-语法树根据等价变化规则,将语法树转化成优化形式选择低层操作算法生成查询计划qq查询执行开销主要包括查询执行开销主要包括:总代价总代价=I/O代价代价+CPU代价代价qq多用户数据库执行开销多用户数据库执行开销

4、:总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价第六页，本课件共有25页关系系统的查询优化:qq一个查询实例一个查询实例:求选修求选修2号课程的学生姓名号课程的学生姓名SQL表示:select Snamefrom Students,SCwhere Students.Sno=SC.Sno and Cno=2;关系代数表示:Q1=sname(Students.Sno=SC.Sno and Cno=2Students.Sno=SC.Sno and Cno=2(StudentsSC)Q2=sname(Cno=2Cno=2(Students SC)Q3=sname(Students Cn

5、o=2Cno=2(SC)第七页，本课件共有25页qq代价计算代价计算 Q1代价计算代价计算(仅考虑仅考虑I/O代价代价)计算广义笛卡尔积代价计算广义笛卡尔积代价假定:在内存中,存放5块Students元组和一块SC元组,一块可以装10个Students元组或100个SC元组.假定:Students有1000个元组,SC有10000个元组,其中选2号课程的有50个元组数据只有读到内存才能进行连接Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)第八页，本课件共有25页通过读取块数计算I/O代价 读取块数计算方法:Students 1000个元组

6、SC 10000个元组读取总块数:若每秒读写20块,则花费:10100SCStudents5块块Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)第九页，本课件共有25页连接后的元组个数为:103 104=107连接后的中间结果内存放不下,需暂时写到外存若每块可装10个元组,则写出这些元组需:(107/10)/20=5 104s选择操作选择操作:读回需读回需5 104s,选择后剩选择后剩50个元组个元组,假定均可放在内存假定均可放在内存投影操作投影操作:查询共花费查询共花费:105+2 5 104 105 sQ1=sname(Students.

7、Sno=SC.Sno and Cno=2(StudentsSC)第十页，本课件共有25页Q2=sname(Cno=2(Students SC)Q2代价计算代价计算(仅考虑仅考虑I/O代价代价)计算自然连接代价也要把数据读到内存进行连接,但连接结果比笛卡尔积要小得多读取块数依然为:花费为2100/20 105s连接结果大小为104个元组,写到外存需:(104/10)/20=50s第十一页，本课件共有25页 Q2=sname(Cno=2(Students SC)Q3=sname(Students Cno=2(SC)读取自然连接结果,执行选择运算,需50s,选择结果均可放在内存投影运算:总花费为:1

8、05+50+50=205sQ3代价计算代价计算(仅考虑仅考虑I/O代价代价)计算对SC做选择运算的代价需读SC到内存进行选择运算读SC块数为:10000/100=100花费为:100/20=5s选择结果为50个SC元组,均可放在内存第十二页，本课件共有25页Q3Q3=sname(Students Cno=2Cno=2(SC)(SC)计算和Students自然连接的 代价需读Students到内存进行连 接运算读Students块数为:1000/10=100花费为:100/20=5s连接结果为50个元组,均可放在内存投影运算:总花费:5+5=10s1050SCStudents5块块第十三页，本课

9、件共有25页关系系统的查询优化:qq查询优化的一般准则查询优化的一般准则:下面的优化策略一般下面的优化策略一般能提高查询效率能提高查询效率,但不一定是最优的但不一定是最优的选择运算尽可能先做选择运算尽可能先做,降低中间结果大小降低中间结果大小在连接前在连接前,对关系适当的进行预处理对关系适当的进行预处理:对关对关系排序系排序(排序合并连接方法排序合并连接方法)或在连接属性或在连接属性上建索引上建索引(索引连接方法索引连接方法)9500495002.95003.95001.Students95003 1 95003 2 95004 2.95004 3.95001 1.SC循环嵌套连接循环嵌套连接

10、(不不做任何预处理做任何预处理):.第十四页，本课件共有25页关系系统的查询优化:9500195002.95003.95004.Students95001 1 95003 1 95003 2 95004 2.95004 3.SC排序合并连接排序合并连接(连连接的关系分别排接的关系分别排序序):.索引连接索引连接(在在SC的连接列的连接列Sno上上建立索引建立索引):Students95001 9500395003 95004 95004.SC索引索引.9500495002.95003.95001.95003 1 95003 2 95004 2.95004 3.95001 1.SC第十五页，本课

11、件共有25页关系系统的查询优化:把投影运算和选择运算同时进行把投影运算和选择运算同时进行 sno(cno=2cno=2(SC)把投影和其前或后的双目运算结合起来把投影和其前或后的双目运算结合起来 Cname(Course SC)把某些选择同在它前面要执行的笛卡尔积把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算结合起来成为一个连接运算 Students.Sno=SC.Sno and Cno=2(StudentsSC)找出公共子表达式找出公共子表达式第十六页，本课件共有25页关系系统的查询优化:qq关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则:给定

12、给定给定给定 snamesname(Students.Sno=SC.SnoStudents.Sno=SC.Sno and and Cno=2Cno=2(Students(Students SC)SC)如何如何如何如何将上述提到的运算先做将上述提到的运算先做将上述提到的运算先做将上述提到的运算先做,即得到即得到即得到即得到:snamesname(Students (Students Cno=2Cno=2(SC)(SC)规则规则规则规则1:1:连接、笛卡尔积的交换律连接、笛卡尔积的交换律连接、笛卡尔积的交换律连接、笛卡尔积的交换律 E E1 1 E E2 2 E E2 2 E E1 1 E E1

13、1 E E2 2=E=E2 2 E E1 1 E E1 1 E E2 2=E=E2 2 E E1 1 E:E:关系代数表达式关系代数表达式关系代数表达式关系代数表达式 F:F:连接条件连接条件连接条件连接条件规则规则规则规则2:2:连接、笛卡尔积的结合律连接、笛卡尔积的结合律连接、笛卡尔积的结合律连接、笛卡尔积的结合律 (E (E1 1 E E2 2)E E3 3=E=E1 1 (E(E2 2 E E3 3)(E (E1 1 E E2 2)E)E3 3 E E1 1 (E (E2 2 E E3 3)(E (E1 1 E E2 2)E)E3 3 E E1 1 (E (E2 2 E E3 3)F1

14、FFF2F1F2第十七页，本课件共有25页关系系统的查询优化:规则规则规则规则3:3:投影的串接定律投影的串接定律投影的串接定律投影的串接定律 A1,A2,.,AnA1,A2,.,An(B1,B2,.,Bn B1,B2,.,Bn(E)(E)A1,A2,.,AnA1,A2,.,An(E)(E)规则规则规则规则4:4:选择的串接定律选择的串接定律选择的串接定律选择的串接定律 F1F1(F2F2(E)(E)F1F1 F2F2(E)(E)规则规则规则规则5:5:选择和投影的交换律选择和投影的交换律选择和投影的交换律选择和投影的交换律 F F(A1,A2,.,AnA1,A2,.,An(E)(E)A1,A

15、2,.,AnA1,A2,.,An(F F(E)(E)特殊情况特殊情况特殊情况特殊情况 A1,A2,.,AnA1,A2,.,An(F F(E)(E)A1,A2,.,AnA1,A2,.,An(F F(A1,A2,.,An,B1,B2,.,BmA1,A2,.,An,B1,B2,.,Bm(E)(E)规则规则规则规则6:6:选择与笛卡尔积的交换律选择与笛卡尔积的交换律选择与笛卡尔积的交换律选择与笛卡尔积的交换律 F F(E(E1 1 E E2 2)F F(E(E1 1)E E2 2 F F仅和仅和仅和仅和E E1 1有关有关有关有关 F F(E(E1 1 E E2 2)F1F1(E(E1 1)F2F2(

16、E(E2 2)F=F1F=F1 F2F2 F F(E(E1 1 E E2 2)F2F2(F1F1(E(E1 1)E E2 2)F1-E1 F2-E1E2F1-E1 F2-E1E2第十八页，本课件共有25页关系系统的查询优化:规则规则7:选择与并的交换选择与并的交换 F F(E E1 E2)F(E1)F F(E(E2 2)规则规则规则规则8:8:选择与差的交换选择与差的交换选择与差的交换选择与差的交换 F(E1-E2)F(E E1)-)-F(E2)规则规则规则规则9:9:投影与笛卡尔积的交换投影与笛卡尔积的交换投影与笛卡尔积的交换投影与笛卡尔积的交换 A1,A2,.,An,B1,B2,.,Bm(

17、E1 1 E2)A1,A2,.,An(E1 1)B1,B2,.,Bm(E(E2 2)规则规则10:投影与并的交换投影与并的交换 A1,A2,.,An(E1 E2)A1,A2,.,AnA1,A2,.,An(E1)A1,A2,.,An(E2)20第十九页，本课件共有25页关系系统的查询优化:qq关系代数表达式的优化算法关系代数表达式的优化算法:应用应用关系代数等价变换关系代数等价变换关系代数等价变换关系代数等价变换规则规则规则规则来优化关系代数表达式来优化关系代数表达式,使优化后的表达式能遵循使优化后的表达式能遵循查询优化的一般准则查询优化的一般准则,在语法树上进行优化在语法树上进行优化在语法树上

18、进行优化在语法树上进行优化关系代数表达式的优化算法关系代数表达式的优化算法输入输入输入输入:语法树语法树语法树语法树 1 1 利用利用规则规则4把形如把形如 F1F1 F2FnF2Fn(E)变换成变换成 F1F1(F2(Fn(E).)2 对每一个选择对每一个选择,利用利用规则规则48尽可能移到树的叶端尽可能移到树的叶端尽可能移到树的叶端尽可能移到树的叶端 3 对于每个投影对于每个投影,利用利用规则规则规则规则3 3,9,109,10,5尽可能移到树尽可能移到树 的叶的叶端端20页页第二十页，本课件共有25页关系系统的查询优化:4 利用利用规则规则35把选择和投影的串接合并成单个选择把选择和投影

19、的串接合并成单个选择,单个投影单个投影,或一个选择后跟一个投影或一个选择后跟一个投影 5 把处理后的语法树内节点分组把处理后的语法树内节点分组:n n每一双目运算每一双目运算(,)和它的所有直接祖先和它的所有直接祖先(,)为一组为一组,后代直到叶子全是单目运算也并入后代直到叶子全是单目运算也并入该组该组;n n若双目运算为若双目运算为,且其后的选择不能与它结合为等值且其后的选择不能与它结合为等值连接时连接时,这些单目运算单独为一组这些单目运算单独为一组.6 生成一个程序生成一个程序,每组节点的计算是程序中的一步每组节点的计算是程序中的一步输出输出:计算关系代数表达式的程序计算关系代数表达式的程

20、序第二十一页，本课件共有25页关系系统的查询优化:SSPP不能结不能结合成等合成等值连接值连接 S.Sno=SC.SnoSCS能结合能结合成等值成等值连接连接第二十二页，本课件共有25页关系系统的查询优化:qq优化的一般步骤优化的一般步骤优化的一般步骤优化的一般步骤:因因因因DBMSDBMS不同不同不同不同把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示(例如关系代数语法树例如关系代数语法树例如关系代数语法树例如关系代数语法树)把语法树转化成标准把语法树转化成标准把语法树转化成标准把语法树转化成标准(优化优化优化优化)形式形式形式形式选择底层的存

21、取路径选择底层的存取路径选择底层的存取路径选择底层的存取路径生成查询计划生成查询计划生成查询计划生成查询计划,选择代价最小的选择代价最小的选择代价最小的选择代价最小的qq例子例子例子例子:设有供应商设有供应商设有供应商设有供应商S,S,零件零件零件零件P P和供应关系和供应关系和供应关系和供应关系SPSP三个关系三个关系三个关系三个关系,其关系模式其关系模式其关系模式其关系模式:S(Snum,Sname,City)S(Snum,Sname,City)P(Pnum,Pname,Weight,Size)P(Pnum,Pname,Weight,Size)SP(Snum,Pnum,Dept,Quan)

22、SP(Snum,Pnum,Dept,Quan)23页页第二十三页，本课件共有25页关系系统的查询优化:select Sname from S,SP,P where S.Snum=SP.Snum and SP.Snum=P.Snum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000;原始语法树:select-投影 from-笛卡尔积 where-选择第二十四页，本课件共有25页关系系统的查询优化:Sname cSSPPC=S.Snum=SP.Snum and SP.Snum=P.Snum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000Sname cSSPPSname cSSPP s sp pSname cSSPP s sp pSnameSSPP s sp p s p sp c c优化优化:第二十五页，本课件共有25页