第九章关系查询处理和查询优化精选PPT.ppt
第九章关系查询处理和第九章关系查询处理和查询优化查询优化第1页，本讲稿共25页关系系统的定义qq关系系统关系系统:支持关系数据模型的数据库管支持关系数据模型的数据库管理系统理系统(粗略粗略)qq关系系统关系系统(确切定义确切定义):一个系统可以定一个系统可以定义为一个关系系统义为一个关系系统,当且仅当它当且仅当它:支持关系数据库支持关系数据库支持选择、投影和连接运算支持选择、投影和连接运算(自然连接自然连接),),对对这些运算不要求定义任何物理存取路径这些运算不要求定义任何物理存取路径第2页，本讲稿共25页关系系统的分类:qq许多关系系统的产品许多关系系统的产品qq按按E.F.Codd的思想将关系系统分为的思想将关系系统分为:表式系统表式系统表式系统表式系统(a)(a)最小关系系统最小关系系统最小关系系统最小关系系统(b)(b)关系完备的系统关系完备的系统关系完备的系统关系完备的系统(c)(c)全关系系统全关系系统全关系系统全关系系统(d)(d)SMISMISMISMIabcd第3页，本讲稿共25页关系系统的查询处理:qq查询处理的步骤查询处理的步骤:queryParser&translatorRelational algebra expressionOptimizerExecution planEvaluationengineQuery outputdataStatisticsabout dataDBMS第4页，本讲稿共25页关系系统的查询优化:qq为什么需要查询优化为什么需要查询优化qq关系系统的查询优化由系统完成关系系统的查询优化由系统完成,而不是而不是由用户完成由用户完成优化器可以数据字典获取许多统计信息优化器可以数据字典获取许多统计信息如果数据库的物理统计信息改变了如果数据库的物理统计信息改变了,优化器优化器可以对查询进行重新优化以选择适应的执行可以对查询进行重新优化以选择适应的执行计划计划优化器可以考虑数百种不同的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术优化器包括了许多复杂的技术qq优化目标优化目标:寻求最优的执行计划寻求最优的执行计划,使查询使查询执行开销尽量小执行开销尽量小第5页，本讲稿共25页关系系统的查询优化:qq查询优化的一般步骤查询优化的一般步骤将查询转化成内部表示将查询转化成内部表示-语法树语法树根据等价变化规则根据等价变化规则,将语法树转化成优化形将语法树转化成优化形式式选择低层操作算法选择低层操作算法生成查询计划生成查询计划qq查询执行开销主要包括查询执行开销主要包括:总代价总代价=I/O代价代价+CPU代价代价qq多用户数据库执行开销多用户数据库执行开销:总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价第6页，本讲稿共25页关系系统的查询优化:qq一个查询实例一个查询实例:求选修求选修2号课程的学生姓名号课程的学生姓名SQLSQL表示表示:select Snameselect Snamefrom Students,SCfrom Students,SCwhere Students.Sno=SC.Sno and Cno=2;where Students.Sno=SC.Sno and Cno=2;关系代数表示关系代数表示:Q1Q1=snamesname(Students.Sno=SC.Sno and Cno=2Students.Sno=SC.Sno and Cno=2(Students(Students SC)SC)Q2Q2=snamesname(Cno=2Cno=2(Students SC)(Students SC)Q3Q3=snamesname(Students (Students Cno=2Cno=2(SC)(SC)第7页，本讲稿共25页qq代价计算代价计算 Q1代价计算代价计算(仅考虑仅考虑I/O代价代价)计算广义笛卡尔积代价计算广义笛卡尔积代价假定假定:在内存中在内存中,存放存放5 5块块StudentsStudents元组和一元组和一块块SCSC元组元组,一块可以装一块可以装1010个个StudentsStudents元组或元组或100100个个SCSC元组元组.假定假定:Students:Students有有10001000个元组个元组,SC,SC有有1000010000个元个元组组,其中选其中选2 2号课程的有号课程的有5050个元组个元组数据只有读到内存才能进行连接数据只有读到内存才能进行连接Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)第8页，本讲稿共25页通过读取块数计算通过读取块数计算I/OI/O代价代价 读取块数计算方法读取块数计算方法:Students 1000 Students 1000个元组个元组 SC 10000 SC 10000个元组个元组读取总块数读取总块数:若每秒读写若每秒读写2020块块,则花费则花费:10100SCStudents5块块Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)第9页，本讲稿共25页连接后的元组个数为连接后的元组个数为:10:103 3 10104 4=10=107 7连接后的中间结果内存放不下连接后的中间结果内存放不下,需暂时写到外存需暂时写到外存若每块可装若每块可装1010个元组个元组,则写出这些元组需则写出这些元组需:(10 (107 7/10)/20=5 /10)/20=5 10 104 4s s选择操作选择操作:读回需读回需5 104s,选择后剩选择后剩50个元组个元组,假定均可放在内存假定均可放在内存投影操作投影操作:查询共花费查询共花费:105+2 5 104 105 sQ1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)第10页，本讲稿共25页Q2Q2=snamesname(Cno=2Cno=2(Students SC)(Students SC)Q2代价计算代价计算(仅考虑仅考虑I/O代价代价)计算自然连接代价计算自然连接代价也要把数据读到内存进行连接也要把数据读到内存进行连接,但连接结果比笛但连接结果比笛卡尔积要小得多卡尔积要小得多读取块数依然为读取块数依然为:花费为花费为2100/202100/20 105s105s连接结果大小为连接结果大小为10104 4个元组个元组,写到外存需写到外存需:(10104 4/10)/20=50s/10)/20=50s第11页，本讲稿共25页 Q2=sname(Cno=2(Students SC)Q3=sname(Students (Students Cno=2(SC)读取自然连接结果读取自然连接结果,执行选择运算执行选择运算,需需50s,50s,选择结选择结果均可放在内存果均可放在内存投影运算投影运算:总花费为总花费为:105+50+50=205s:105+50+50=205sQ3代价计算代价计算(仅考虑仅考虑I/O代价代价)计算对计算对SCSC做选择运算的代价做选择运算的代价需读需读SCSC到内存进行选择运算到内存进行选择运算读读SCSC块数为块数为:10000/100=100:10000/100=100花费为花费为:100/20=5s:100/20=5s选择结果为选择结果为5050个个SCSC元组元组,均可放在内存均可放在内存第12页，本讲稿共25页Q3Q3=snamesname(Students (Students Cno=2Cno=2(SC)(SC)计算和计算和StudentsStudents自然连接的自然连接的 代价代价需读需读StudentsStudents到内存进行连到内存进行连 接运算接运算读读StudentsStudents块数为块数为:1000/10=100 1000/10=100花费为花费为:100/20=5s:100/20=5s连接结果为连接结果为5050个元组个元组,均可放在内存均可放在内存投影运算投影运算:总花费总花费:5+5=10s:5+5=10s1050SCStudents5块块第13页，本讲稿共25页关系系统的查询优化:qq查询优化的一般准则查询优化的一般准则:下面的优化策略一般下面的优化策略一般能提高查询效率能提高查询效率,但不一定是最优的但不一定是最优的选择运算尽可能先做选择运算尽可能先做,降低中间结果大小降低中间结果大小在连接前在连接前,对关系适当的进行预处理对关系适当的进行预处理:对关对关系排序系排序(排序合并连接方法排序合并连接方法)或在连接属性或在连接属性上建索引上建索引(索引连接方法索引连接方法)9500495002.95003.95001.Students95003 1 95003 2 95004 2.95004 3.95001 1.SC循环嵌套连接循环嵌套连接(不不做任何预处理做任何预处理):.第14页，本讲稿共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第15页，本讲稿共25页关系系统的查询优化:把投影运算和选择运算同时进行把投影运算和选择运算同时进行 sno(cno=2cno=2(SC)把投影和其前或后的双目运算结合起来把投影和其前或后的双目运算结合起来 Cname(Course SC)把某些选择同在它前面要执行的笛卡尔积把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算结合起来成为一个连接运算 Students.Sno=SC.Sno and Cno=2Students.Sno=SC.Sno and Cno=2(StudentsSC)找出公共子表达式找出公共子表达式第16页，本讲稿共25页关系系统的查询优化:qq关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则:给定给定给定给定 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 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)F1FFF2F1F2第17页，本讲稿共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,A2,.,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(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第18页，本讲稿共25页关系系统的查询优化:规则规则规则规则7:7:选择与并的交换选择与并的交换选择与并的交换选择与并的交换 F F(E E1 1 E E2 2)F F(E E1 1)F F(E(E2 2)规则规则规则规则8:8:选择与差的交换选择与差的交换选择与差的交换选择与差的交换 F F(E E1 1-E-E2 2)F F(E E1 1)-)-F F(E(E2 2)规则规则规则规则9:9:投影与笛卡尔积的交换投影与笛卡尔积的交换投影与笛卡尔积的交换投影与笛卡尔积的交换 A1,A2,.,An,B1,B2,.,BmA1,A2,.,An,B1,B2,.,Bm(E(E1 1 E E2 2)A1,A2,.,AnA1,A2,.,An(E(E1 1)B1,B2,.,BmB1,B2,.,Bm(E(E2 2)规则规则规则规则10:10:投影与并的交换投影与并的交换投影与并的交换投影与并的交换 A1,A2,.,An A1,A2,.,An(E(E1 1 E E2 2)A1,A2,.,AnA1,A2,.,An(E(E1 1)A1,A2,.,AnA1,A2,.,An(E(E2 2)20第19页，本讲稿共25页关系系统的查询优化:qq关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法:应用应用应用应用关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则关系代数等价变换规则来优化关系代数表达式来优化关系代数表达式来优化关系代数表达式来优化关系代数表达式,使优化后的表达式能遵循使优化后的表达式能遵循使优化后的表达式能遵循使优化后的表达式能遵循查询查询查询查询优化的一般准则优化的一般准则优化的一般准则优化的一般准则,在语法树上进行优化在语法树上进行优化在语法树上进行优化在语法树上进行优化关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法输入输入输入输入:语法树语法树语法树语法树 1 1 利用利用利用利用规则规则规则规则4 4把形如把形如把形如把形如 F1F1 F2FnF2Fn(E)(E)变换成变换成变换成变换成 F1F1(F2F2(FnFn(E).)(E).)2 2 对每一个选择对每一个选择对每一个选择对每一个选择,利用利用利用利用规则规则规则规则4848尽可能移到树的叶端尽可能移到树的叶端尽可能移到树的叶端尽可能移到树的叶端 3 3 对于每个投影对于每个投影对于每个投影对于每个投影,利用利用利用利用规则规则规则规则3 3,9,109,10,5 5尽可能移到树尽可能移到树尽可能移到树尽可能移到树 的叶端的叶端的叶端的叶端20页页第20页，本讲稿共25页关系系统的查询优化:4 4 利用利用利用利用规则规则规则规则3535把选择和投影的串接合并成单个选择把选择和投影的串接合并成单个选择把选择和投影的串接合并成单个选择把选择和投影的串接合并成单个选择,单单单单个投影个投影个投影个投影,或一个选择后跟一个投影或一个选择后跟一个投影或一个选择后跟一个投影或一个选择后跟一个投影 5 5 把处理后的语法树内节点分组把处理后的语法树内节点分组把处理后的语法树内节点分组把处理后的语法树内节点分组:n n每一双目运算每一双目运算每一双目运算每一双目运算(,)和它的所有直接祖先和它的所有直接祖先和它的所有直接祖先和它的所有直接祖先(,)为一组为一组为一组为一组,后代直到叶子全是单目运算也并入该组后代直到叶子全是单目运算也并入该组后代直到叶子全是单目运算也并入该组后代直到叶子全是单目运算也并入该组;n n若双目运算为若双目运算为若双目运算为若双目运算为 ,且其后的选择不能与它结合为等值连且其后的选择不能与它结合为等值连且其后的选择不能与它结合为等值连且其后的选择不能与它结合为等值连接时接时接时接时,这些单目运算单独为一组这些单目运算单独为一组这些单目运算单独为一组这些单目运算单独为一组.6 6 生成一个程序生成一个程序生成一个程序生成一个程序,每组节点的计算是程序中的一步每组节点的计算是程序中的一步每组节点的计算是程序中的一步每组节点的计算是程序中的一步输出输出输出输出:计算关系代数表达式的程序计算关系代数表达式的程序计算关系代数表达式的程序计算关系代数表达式的程序第21页，本讲稿共25页关系系统的查询优化:SSPP不能结不能结合成等合成等值连接值连接 S.Sno=SC.SnoSCS能结合能结合成等值成等值连接连接第22页，本讲稿共25页关系系统的查询优化:qq优化的一般步骤优化的一般步骤优化的一般步骤优化的一般步骤:因因因因DBMSDBMS不同不同不同不同把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示把查询转换成某种内部表示(例如关系代数语法树例如关系代数语法树例如关系代数语法树例如关系代数语法树)把语法树转化成标准把语法树转化成标准把语法树转化成标准把语法树转化成标准(优化优化优化优化)形式形式形式形式选择底层的存取路径选择底层的存取路径选择底层的存取路径选择底层的存取路径生成查询计划生成查询计划生成查询计划生成查询计划,选择代价最小的选择代价最小的选择代价最小的选择代价最小的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)SP(Snum,Pnum,Dept,Quan)23页页第23页，本讲稿共25页关系系统的查询优化:select Snameselect Sname from S,SP,P from S,SP,P where S.Snum=SP.Snum where S.Snum=SP.Snum and SP.Snum=P.Snum and SP.Snum=P.Snum and S.City=NANJING and S.City=NANJING and P.Pname=Bolt and P.Pname=Bolt and SP.Quan1000;and SP.Quan1000;原始语法树原始语法树:select-:select-投影投影 from-from-笛卡尔积笛卡尔积 where-where-选择选择第24页，本讲稿共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页，本讲稿共25页
