《06第六章关系系统及其优化new》由会员分享，可在线阅读，更多相关《06第六章关系系统及其优化new（51页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章: 关系系统及其查询优化关系系统及其查询优化q关系系统的定义和分类关系系统的定义和分类q查询处理查询处理q关系系统中的查询优化关系系统中的查询优化关系系统的定义关系系统的定义q关系系统关系系统: 支持关系数据模型的数据库管理系支持关系数据模型的数据库管理系统统(粗略粗略)q关系系统关系系统(确切定义确切定义): 一个系统可以定义为一一个系统可以定义为一个关系系统个关系系统, 当且仅当它当且仅当它:支持关系数据库支持关系数据库支持选择、投影和连接运算支持选择、投影和连接运算(自然连接自然连接), 对对这些运算不要求定义任何物理存取路径这些运算不要求定义任何物理存取路径关系系统的分类关
2、系系统的分类q许多关系系统的产品许多关系系统的产品q按按E.F.Codd的思想将关系系统分为的思想将关系系统分为:表式系统表式系统(a)最小关系系统最小关系系统(b)关系完备的系统关系完备的系统(c)全关系系统全关系系统(d)SMISMISMISMIabcdS: StructureI: IntegrityM: Manipulation关系数据模型关系数据模型集合级集合级关系系统的查询处理关系系统的查询处理q查询处理的步骤查询处理的步骤: 查询查询关系代数关系代数表达式表达式执行计划执行计划查询结查询结果输出果输出数据数据基于数据的基于数据的统计分析统计分析优优 化化 器器分析器分析器 &翻译器
3、翻译器 评评 价价 引引 擎擎 DBMS为什么需要查询优化？为什么需要查询优化？q一个查询实例一个查询实例: 求选修求选修2号课程的学生姓名号课程的学生姓名SQL表示表示:select Snamefrom Students, SCwhere Students.Sno=SC.Sno and Cno=2;关系代数表示关系代数表示:Q1= sname( Students.Sno=SC.Sno and Cno=2(Students SC)Q2= sname( Cno=2(Students SC)Q3= sname( Students Cno=2(SC)q代价计算代价计算 Q1代价计算代价计算(仅考虑仅
4、考虑I/O代价代价)计算广义笛卡尔积代价计算广义笛卡尔积代价假定假定: 在内存中在内存中, 存放存放5块块Students元组和元组和一块一块SC元组元组, 一块可以装一块可以装10个个Students元元组或组或100个个SC元组元组. 假定假定: Students有有1000个元组个元组,SC有有10000个元组个元组, 其中选其中选2号课程的有号课程的有50个元组个元组数据只有读到内存才能进行连接数据只有读到内存才能进行连接Q1 = sname( Students.Sno=SC.Sno and Cno=2(Students SC)10100SCStudents5块块通过读取块数计算通过读
5、取块数计算I/O代价代价 读取块数计算方法读取块数计算方法: Students 1000个元组个元组 SC 10000个元组个元组读取总块数读取总块数:若每秒读写若每秒读写20块块, 则花费则花费:Q1 = sname( Students.Sno=SC.Sno and Cno=2(Students SC)Student块数块数SC读入内存读入内存的次数的次数SC块数块数10100SCStudents5块块条件条件:Students 1000个元组，个元组， SC 10000个元组个元组迪卡尔集后的元组个数为迪卡尔集后的元组个数为: 103 104=107连接后的中间结果内存放不下连接后的中间结
6、果内存放不下, 需暂时写到外存需暂时写到外存若每块可装若每块可装10个完成迪卡尔集后的元组个完成迪卡尔集后的元组, 则写这则写这些元组需些元组需: (107 /10)/20=5 104s选择操作选择操作: 读回需读回需5 104s, 假设假设选择后剩选择后剩50个元组个元组,均可放在内存均可放在内存投影操作投影操作: 只需只需CPU时间时间查询共花费查询共花费: 105+2 5 104 105 s 28小时小时Q1 = sname( Students.Sno=SC.Sno and Cno=2(Students SC)10100SCStudents5块块每秒读每秒读20块块Q2= sname(
7、Cno=2(Students SC)Q2代价计算代价计算(仅考虑仅考虑I/O代价代价)计算自然连接代价计算自然连接代价也要把数据读到内存进行连接也要把数据读到内存进行连接, 但连接结果比笛但连接结果比笛卡尔积要小得多卡尔积要小得多读取块数依然为读取块数依然为:花费为花费为2100/20 105s假设连接结果大小为假设连接结果大小为104个元组个元组, 写到外存需写到外存需: (104 /10)/20=50s每秒读每秒读20块块 Q2= sname( Cno=2(Students SC) Q3= sname( Students Cno=2(SC)读取自然连接结果读取自然连接结果, 执行选择运算执
8、行选择运算, 需需50s, 选择结选择结果均可放在内存果均可放在内存投影运算投影运算:只需只需CPU时间时间总花费为总花费为: 105+50+50=205s 3.4分钟分钟Q3代价计算代价计算(仅考虑仅考虑I/O代价代价)计算对计算对SC做选择运算的代价做选择运算的代价需读需读SC到内存进行选择运算到内存进行选择运算读读SC块数为块数为: 10000/100=100花费为花费为: 100/20=5s选择结果为选择结果为50个个SC元组元组, 均可放在内存均可放在内存Q3= sname( Students Cno=2(SC)计算和计算和Students自然连接的自然连接的 代价代价需读需读Stu
9、dents到内存进行连到内存进行连 接运算接运算读读Students块数为块数为: 1000/10=100花费为花费为: 100/20=5s连接结果为连接结果为50个元组个元组, 均可放在内存均可放在内存投影运算投影运算:只需只需CPU时间时间总花费总花费: 5+5=10s1050SCStudents5块块关系系统的查询优化关系系统的查询优化q关系系统的查询优化由系统完成关系系统的查询优化由系统完成, 而不是由用户完而不是由用户完成成优化器可以从数据字典获取许多统计信息优化器可以从数据字典获取许多统计信息如果数据库的物理统计信息改变了如果数据库的物理统计信息改变了,优化器可优化器可以对查询进行
10、重新优化以选择适应的执行计划以对查询进行重新优化以选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术优化器包括了许多复杂的技术q优化目标优化目标: 寻求最优的执行计划寻求最优的执行计划, 使查询执行开销使查询执行开销尽量小尽量小q查询执行开销主要包括查询执行开销主要包括: 总代价总代价 = I/O代价代价 + CPU代价代价q多用户数据库执行开销多用户数据库执行开销: 总代价总代价 = I/O代价代价 + CPU代价代价 + 内存代价内存代价q查询优化的途径查询优化的途径代数优化代数优化物理优化物理优化关系系统的查询优化关系系统的查
11、询优化代数优化代数优化q查询优化的一般步骤查询优化的一般步骤将查询转化成内部表示将查询转化成内部表示-语法树语法树根据等价变化规则根据等价变化规则, 将语法树转化成优化形式将语法树转化成优化形式选择底层操作算法选择底层操作算法生成查询计划生成查询计划代数优化代数优化q查询优化的查询优化的一般准则（启发式规则）一般准则（启发式规则）: 下面的优化下面的优化策略一般能提高查询效率策略一般能提高查询效率, 但不一定是最优的但不一定是最优的选择和投影运算尽可能先做选择和投影运算尽可能先做, 降低中间结果大小降低中间结果大小把投影运算和选择运算同时进行把投影运算和选择运算同时进行 sno ( cno=2
12、(SC)把投影和其前或后的双目运算结合起来把投影和其前或后的双目运算结合起来 Cname(Course SC)把某些选择同在它前面要执行的笛卡尔积结合起把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算来成为一个连接运算 Students.Sno=SC.Sno and Cno=2(Students SC)找出公共子表达式找出公共子表达式代数优化代数优化q关系代数等价变换规则关系代数等价变换规则: 给定给定 sname( Students.Sno=SC.Sno and Cno=2(Students SC)如何如何将上述提到的运算先做将上述提到的运算先做, 即得到即得到: sname(
13、Students Cno=2(SC)规则规则1: 连接、笛卡尔积的交换律连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2= E2 E1 E1 E2= E2 E1 E: 关系代数表达式关系代数表达式 F: 连接条件连接条件FF代数优化代数优化规则规则2: 连接、笛卡尔积的结合律连接、笛卡尔积的结合律 (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3)规则规则3: 投影的串接定律投影的串接定律 A1,A2,.,An( B1,B2,.,Bn (E) A1,A2,.,An(E) F1F2F1F2代数优化代数优
14、化规则规则4: 选择的串接定律选择的串接定律 F1( F2(E) F1 F2(E) 规则规则5: 选择和投影的交换律选择和投影的交换律 F( A1,A2,.,An(E) = A1,A2,.,An( F(E) 特殊情况特殊情况 A1,A2,.,An( F(E) A1,A2,.,An( F( A1,A2,.,An, B1,B2,.,Bm (E)代数优化代数优化规则规则6: 选择与笛卡尔积的交换律选择与笛卡尔积的交换律 F(E1 E2) F(E1) E2 F仅和仅和E1有关有关 F(E1 E2) F1(E1) F2( E2 ) F= F1 F2 F(E1 E2) F2( F1(E1) E2 ) F1
15、-E1 F2-E1E2规则规则7: 选择与并的分配律选择与并的分配律 F(E1 E2) F(E1) F(E2) 代数优化代数优化规则规则8: 选择与差的分配律选择与差的分配律 F(E1- E2) F(E1)- F(E2)规则规则9: 选择对自然连接的分配律选择对自然连接的分配律 F(E1 E2) F(E1) F(E2) 代数优化代数优化规则规则10: 投影与笛卡尔积的分配律投影与笛卡尔积的分配律 A1,A2,.,An, B1,B2,.,Bm(E1 E2) A1,A2,.,An(E1) B1,B2,.,Bm(E2) 规则规则11: 投影与并的分配律投影与并的分配律 A1,A2,.,An (E1
16、E2) A1,A2,.,An(E1) A1,A2,.,An(E2) 代数优化代数优化q关系代数表达式的优化算法关系代数表达式的优化算法:q应用应用关系代数等价变换规则关系代数等价变换规则来优化关系代数来优化关系代数表达式表达式, 使优化后的表达式能遵循使优化后的表达式能遵循查询优化的查询优化的一般准则一般准则, 在语法树上进行优化在语法树上进行优化代数优化代数优化关系代数表达式的优化算法关系代数表达式的优化算法输入输入: 语法树语法树输出输出: 计算关系代数表达式的程序计算关系代数表达式的程序 1 利用利用规则规则4把形如把形如 F1 F2Fn(E) 变换成变换成 F1( F2( ( Fn(E
17、).) 2 对每一个选择对每一个选择, 利用利用规则规则49尽可能移到树的叶端尽可能移到树的叶端 3 对于每个投影对于每个投影, 利用利用规则规则3, 5, 10, 11尽可能移到尽可能移到树的叶端树的叶端 4 利用利用规则规则35把选择和投影的串接合并成单个选把选择和投影的串接合并成单个选择择, 单个投影单个投影, 或一个选择后跟一个投影或一个选择后跟一个投影代数优化代数优化 5 把处理后的语法树内节点分组把处理后的语法树内节点分组:每一双目运算每一双目运算( , , , )和它的所有直接祖先和它的所有直接祖先( , )为一组为一组,后代直到叶子全是单目运算也并入该后代直到叶子全是单目运算也
18、并入该组组;若双目运算为若双目运算为 ,且其后的选择不能与它结合为等值且其后的选择不能与它结合为等值连接时连接时,这些单目运算单独为一组这些单目运算单独为一组. 6 生成一个程序生成一个程序, 每组节点的计算是程序中的一步每组节点的计算是程序中的一步代数优化代数优化 SSPP不能结不能结合成等合成等值连接值连接 S.Sno=SC.Sno SCS能结合能结合成等值成等值连接连接代数优化代数优化q优化的一般步骤优化的一般步骤: 因因DBMS而不同而不同把查询转换成某种内部表示把查询转换成某种内部表示(例如关系代数语法树例如关系代数语法树)把语法树转化成标准把语法树转化成标准(优化优化)形式形式选择
19、底层的存取路径选择底层的存取路径生成查询计划生成查询计划, 选择代价最小的选择代价最小的q例子例子: 设有供应商设有供应商S, 零件零件P和供应关系和供应关系SP三个关系三个关系, 其关系模式其关系模式:S(Snum, Sname, City) P(Pnum, Pname, Weight, Size) SP(Snum, Pnum, Dept, Quan)代数优化代数优化select Sname from S, SP, P where S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan
20、1000;原始语法树原始语法树: select-投影投影 from-笛卡尔积笛卡尔积 where-选择选择代数优化代数优化 Sname c SSPP c: S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000优化优化:代数优化代数优化 Sname c SSPP 优化优化: Sname c SSPP c: S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000代数优
21、化代数优化 Sname c SSPP 优化优化: Sname c SSPP c: S.Snum=SP.Snum and SP.Pnum=P.Pnums: S.City=NANJING p: P.Pname=Boltsp: SP.Quan1000 Sname c SSPP s sp p代数优化代数优化 Sname c SSPP 优化优化: Sname c SSPP c: SP.Pnum=P.Pnums: S.City=NANJING p: P.Pname=Boltsp: SP.Quan1000 Sname c SSPP s sp p Sname c SSPP s sp p代数优化代数优化 Sna
22、me c SSPP 优化优化: Sname c SSPP s: S.City=NANJING p: P.Pname=Boltsp: SP.Quan1000 Sname c SSPP s sp p Sname c SSPP s sp p SnameSSPP s sp p练习练习1查询要求查询要求:l查询信息系学生选修的所有的课程的课程名称查询信息系学生选修的所有的课程的课程名称l写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处理并进行优化处理,画出优化后的语法树画出优化后的语法树.SELECT Cname FROM Students,Courses,SCWHERE Studen
23、ts.sno=SC.sno and Co=SC.cno and Sdept=IS;练习练习1: Cname( Students.sno=Sc.sno SC.cno=Co Sdept=IS(Students (SC Course)SC原始语法树原始语法树: Cname c StudentsCourses c: Students.sno=Sc.sno SC.cno=Co Sdept=ISc: SC.cno=Coc1: Sdept=IS Cname c1 StudentsSCCourses c CnameCourses c1StudentsSC练习练习2查询要求查询要求:l一图书管理数据库，其关系如
24、下：一图书管理数据库，其关系如下：BOOKS(Title, Author, Pname, LC_No)PUBLISHERS(Pname, Paddr, Pcity)BORROWERS(Name, Addr, City, Card_No)LOANS(Card_No, LC_No, Date)要求：要求：1.列出列出2003年年1月月1日之后借出的所有书名和借书人姓名日之后借出的所有书名和借书人姓名2. 写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处理并进行优化处理,画出优化画出优化后的语法树后的语法树.SELECT Title,Name FROM BOOKS,BORROWER
25、S,LOANSWHERE BOOKS. LC_No = LOANS. LC_No AND BORROWERS. Card_No= LOANS. Card_No AND Date01/01/2003图书编号图书编号图书证号图书证号练习练习2: Title,Name( BOOKS.LC_No=LOANS.LC_No BORROWERS.Card_No=LOANS.Card_No Date01/01/2003(BOOKS BORROWERS LOANS) Title,Name Date01/01/2003 BOOKSBORROWERSLOANS 语法树语法树: BOOKS.LC_No=LOANS.L
26、C_No BORROWERS.Card_No=LOANS.Card_No Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date练习练习2: Title,Name( F Date01/01/2003(BOOKS BORROWERS LOANS)sF Date01/01/2003(BOOKS BORROWERS LOANS)= F (BOOKS) Date01/01/2003(BORROWERS LOANS)= F (BOOKS BORROWERS) Date01/01/2003(LOANS) Title,Name Date01/01/2003
27、BOOKSBORROWERSLOANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No 增加两个投影：增加两个投影： Title, BOOKS.LC_No Name, LOANS.LC_No Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS.LC_No = LOANS. LC_No BORROWERS.Card_No= LOANS.Card_No Title, BOOKS.LC_No Name, LOANS.LC_No练习练习2: Title,Name( F Da
28、te01/01/2003(BOOKS BORROWERS LOANS) Title，BOOKS. LC_No练习练习2: Title,Name( F Date01/01/2003(BOOKS BORROWERS LOANS) LOANS.LC_No,LOANS. Card_No Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS. LC_No = LOANS. LC_No BORROWERS. Card_No= LOANS. Card_No Name, LOANS. LC_No Name，BORROWERS. CARD_No Title,Na
29、me Date01/01/2003BOOKSBORROWERSLOANS Title，BOOKS. LC_No Name， LOANS. LC_No Name, BORROWERS.CARD_No LOANS.LC_No,LOANS. Card_No最后语法树：最后语法树：练习练习2: Title,Name( F Date01/01/2003(BOOKS BORROWERS LOANS)物理优化物理优化q涉及底层的存取路径，不同的存取方案导致不同涉及底层的存取路径，不同的存取方案导致不同的执行效率的执行效率物理优化：选择高效合理的操作算法或存取路径物理优化：选择高效合理的操作算法或存取路径q优
30、化方法优化方法基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化基于代价的优化基于代价的优化两者结合的优化方法两者结合的优化方法物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化选择操作的启发式规则选择操作的启发式规则小关系：全表顺序扫描(优点：简单有效)95001, 1, 8595003, 1, 9595003, 2, 8895004, 1, 7095004, 3, 62SC选择操作的启发式规则选择操作的启发式规则大关系选择条件是主码=值的查询，查询结果最多一个选择主码索引 (RDBMS会自动建立主码索引)95001, 1 95003, 1 95003,
31、2 95004, 1 . 95004, 3 .SCSno, Cno是主码是主码物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化选择操作的启发式规则选择操作的启发式规则大关系选择条件是范围查询或非等值查询，或选择条件是非主属性=值的查询查询结果数目不明确估算查询结果的元组数量如果查询结果的元组数量20，以，以Sage=20为索引项，以此为入口点找到为索引项，以此为入口点找到Sage20的的所有元组指针所有元组指针合取选择查询合取选择查询：例如：例如Sdept=CS AND Sage20。分别找到符合各个条件的元组指针，取指针的交集；或者分别找到符合各个条件的元组指针，取指
32、针的交集；或者找到符合第一个条件的元组指针，在此范围内检查另一条找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足件是否满足析取选择查询析取选择查询：使用全表顺序扫描：使用全表顺序扫描物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化物理优化预备知识lB+树索引树索引10 1518 20 2223 3133 4548 5218 233333连接操作的启发式规则连接操作的启发式规则如果两个表都已经按照连接属性排序排序合并连接例如： Students SC物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化9500195002. 95003. 9
33、5004.Students95001, 1 95003, 1 95003, 2 95004, 2 . 95004, 3 .SC排序合并连接排序合并连接(连连接的关系分别排接的关系分别排序序):.两个表只要扫描一次就可以完成连接操作两个表只要扫描一次就可以完成连接操作连接操作的启发式规则连接操作的启发式规则如果一个表的连接属性上有索引排序索引连接例如： Students SC物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化索引连接索引连接(在在SC的连接列的连接列Sno上上建立索引建立索引):Students95001 9500395003 95004 95004.SC上
34、建立上建立Sno的索引的索引.9500495002. 95003. 95001.95003, 1 95003, 2 95004, 2 . 95004, 3 . 95001, 1 .SC连接操作的启发式规则连接操作的启发式规则如果前两个规则不适用，且一个表较小Hash连接例如： Students SC物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化Hash连接连接(选用选用Hash函数散列连接属函数散列连接属性值性值):例如：例如：Hash函数函数=将将Sno后三位模除后三位模除3Students9500495002. 95003. 9500195003, 1 95004
35、, 2 95001, 2 . 95002, 3 . 95001, 1 .SC9500195004(1)95002(2)95003(3)1. 划分阶段划分阶段为小表建立为小表建立hash桶桶2. 连接阶段连接阶段*对大表顺序扫描对大表顺序扫描*在匹配的在匹配的hash桶桶内做顺序扫描内做顺序扫描连接操作的启发式规则连接操作的启发式规则最后可选用嵌套循环方法例如： Students SC物理优化基于启发式规则的存取路径选择优化基于启发式规则的存取路径选择优化9500495002. 95003. 95001.Students95003 1 95003 2 95004 2 . 95004 3 . 95001 1 .SC循环嵌套连接循环嵌套连接(不不做任何预处理做任何预处理)对外层循环表对外层循环表（外表）的每个（外表）的每个元组，扫描一遍元组，扫描一遍内层循环表内层循环表.选择占用内存块较少的表作为外表选择占用内存块较少的表作为外表外循环表外循环表内循环表内循环表物理优化基于代价的优化基于代价的优化l启发式规则适用于解释执行的系统启发式规则适用于解释执行的系统优化开销包含在查询总开销中l基于代价的优化适用于编译执行的系统基于代价的优化适用于编译执行的系统一次编译优化，多次执行优化开销不包含在查询执行中对代价进行估算，选择代价最小的查询计划l新教材274页
