06-第六章关系系统及其优化-new.ppt

《06-第六章关系系统及其优化-new.ppt》由会员分享，可在线阅读，更多相关《06-第六章关系系统及其优化-new.ppt（51页珍藏版）》请在三一文库上搜索。

1、第六章: 关系系统及其查询优化,关系系统的定义和分类 查询处理 关系系统中的查询优化,关系系统的定义,关系系统: 支持关系数据模型的数据库管理系统(粗略) 关系系统(确切定义): 一个系统可以定义为一个关系系统, 当且仅当它: 支持关系数据库 支持选择、投影和连接运算(自然连接), 对这些运算不要求定义任何物理存取路径,关系系统的分类,许多关系系统的产品 按E.F.Codd的思想将关系系统分为: 表式系统(a) 最小关系系统(b) 关系完备的系统(c) 全关系系统(d),S,M,I,S,M,I,S,M,I,S,M,I,a,b,c,d,S: Structure I: Integrity M: M

2、anipulation,关系数据模型,集合级,关系系统的查询处理,查询处理的步骤:,查询,关系代数 表达式,执行计划,查询结果输出,数据,基于数据的统计分析,优 化 器,分析器 & 翻译器,评 价 引 擎,DBMS,为什么需要查询优化？,一个查询实例: 求选修2号课程的学生姓名 SQL表示: select Sname from Students, SC where Students.Sno=SC.Sno and Cno=2; 关系代数表示: Q1= sname(Students.Sno=SC.Sno and Cno=2(StudentsSC) Q2= sname(Cno=2(Students

3、SC) Q3= sname( Students Cno=2(SC),代价计算 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),10,100,SC,Students,5块,通过读取块数计算I/O代价 读取块数计算方法: Students

4、 1000个元组 SC 10000个元组 读取总块数: 若每秒读写20块, 则花费:,Q1 = sname(Students.Sno=SC.Sno and Cno=2(StudentsSC),Student 块数,SC 读入内存的次数,SC块数,10,100,SC,Students,5块,条件:Students 1000个元组， SC 10000个元组 迪卡尔集后的元组个数为: 103 104=107 连接后的中间结果内存放不下, 需暂时写到外存 若每块可装10个完成迪卡尔集后的元组, 则写这些元组需: (107 /10)/20=5 104s 选择操作: 读回需5 104s, 假设选择后剩50

5、个元组,均可放在内存 投影操作: 只需CPU时间 查询共花费: 105+2 5 104 105 s 28小时,Q1 = sname(Students.Sno=SC.Sno and Cno=2(StudentsSC),每秒读20块,Q2= sname(Cno=2(Students SC),Q2代价计算(仅考虑I/O代价) 计算自然连接代价 也要把数据读到内存进行连接, 但连接结果比笛卡尔积要小得多 读取块数依然为: 花费为2100/20105s 假设连接结果大小为104个元组, 写到外存需: (104 /10)/20=50s,每秒读20块,Q2= sname(Cno=2(Students SC)

6、 Q3= sname( Students Cno=2(SC),读取自然连接结果, 执行选择运算, 需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自然连接的 代价 需读Students到内存进行连 接运算 读Students块数为: 1000/1

7、0=100 花费为: 100/20=5s 连接结果为50个元组, 均可放在内存 投影运算:只需CPU时间 总花费: 5+5=10s,10,50,SC,Students,5块,关系系统的查询优化,关系系统的查询优化由系统完成, 而不是由用户完成 优化器可以从数据字典获取许多统计信息 如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划 优化器可以考虑数百种不同的执行计划 优化器包括了许多复杂的技术 优化目标: 寻求最优的执行计划, 使查询执行开销尽量小,查询执行开销主要包括: 总代价 = I/O代价 + CPU代价 多用户数据库执行开销: 总代价 = I/O代价 +

8、CPU代价 + 内存代价 查询优化的途径 代数优化 物理优化,关系系统的查询优化,代数优化,查询优化的一般步骤 将查询转化成内部表示-语法树 根据等价变化规则, 将语法树转化成优化形式 选择底层操作算法 生成查询计划,代数优化,查询优化的一般准则（启发式规则）: 下面的优化策略一般能提高查询效率, 但不一定是最优的 选择和投影运算尽可能先做, 降低中间结果大小 把投影运算和选择运算同时进行 sno (cno=2(SC) 把投影和其前或后的双目运算结合起来 Cname(Course SC) 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 Students.Sno=SC.Sno an

9、d Cno=2(StudentsSC) 找出公共子表达式,代数优化,关系代数等价变换规则: 给定 sname(Students.Sno=SC.Sno and Cno=2(StudentsSC) 如何将上述提到的运算先做, 即得到: sname( Students Cno=2(SC) 规则1: 连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2= E2 E1 E1 E2= E2 E1 E: 关系代数表达式 F: 连接条件,代数优化,规则2: 连接、笛卡尔积的结合律 (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E

10、2 E3) 规则3: 投影的串接定律 A1,A2,.,An( B1,B2,.,Bn (E) A1,A2,.,An(E),F1,F2,F1,F2,代数优化,规则4: 选择的串接定律 F1(F2(E) F1F2(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= F1F2 F(

11、E1 E2) F2(F1(E1)E2 ) F1-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 E2) A1,A2,.,An(E1) A1,A2,.,An(E2),代数优

12、化,关系代数表达式的优化算法: 应用关系代数等价变换规则来优化关系代数表达式, 使优化后的表达式能遵循查询优化的一般准则, 在语法树上进行优化,代数优化,关系代数表达式的优化算法 输入: 语法树 输出: 计算关系代数表达式的程序 1 利用规则4把形如F1F2Fn(E) 变换成 F1(F2( (Fn(E).) 2 对每一个选择, 利用规则49尽可能移到树的叶端 3 对于每个投影, 利用规则3, 5, 10, 11尽可能移到树的叶端 4 利用规则35把选择和投影的串接合并成单个选择, 单个投影, 或一个选择后跟一个投影,代数优化,5 把处理后的语法树内节点分组: 每一双目运算(, ,)和它的所有直

13、接祖先(,)为一组,后代直到叶子全是单目运算也并入该组; 若双目运算为,且其后的选择不能与它结合为等值连接时,这些单目运算单独为一组. 6 生成一个程序, 每组节点的计算是程序中的一步,代数优化,代数优化,优化的一般步骤: 因DBMS而不同 把查询转换成某种内部表示(例如关系代数语法树) 把语法树转化成标准(优化)形式 选择底层的存取路径 生成查询计划, 选择代价最小的 例子: 设有供应商S, 零件P和供应关系SP三个关系, 其关系模式: S(Snum, Sname, City) P(Pnum, Pname, Weight, Size) SP(Snum, Pnum, Dept, Quan),代

14、数优化,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.Quan1000; 原始语法树: select-投影 from-笛卡尔积 where-选择,代数优化,c: S.Snum=SP.Snum and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000,优化:,代数优化,Sname,c,S,SP,P,优化:,c: S.Snum=SP.Snum

15、and SP.Pnum=P.Pnum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000,代数优化,Sname,c,S,SP,P,优化:,c: S.Snum=SP.Snum and SP.Pnum=P.Pnum s: S.City=NANJING p: P.Pname=Bolt sp: SP.Quan1000,Sname,c,S,SP,P,s,sp,p,代数优化,Sname,c,S,SP,P,优化:,c: SP.Pnum=P.Pnum s: S.City=NANJING p: P.Pname=Bolt sp: SP.Quan1000,Snam

16、e,c,S,SP,P,s,sp,p,Sname,c,S,SP,P,s,sp,p,代数优化,Sname,c,S,SP,P,优化:,s: S.City=NANJING p: P.Pname=Bolt sp: SP.Quan1000,Sname,c,S,SP,P,s,sp,p,Sname,c,S,SP,P,s,sp,p,Sname,S,SP,P,s,sp,p,练习1,查询要求: 查询信息系学生选修的所有的课程的课程名称 写出关系代数及其原始语法树,并进行优化处理,画出优化后的语法树.,SELECT Cname FROM Students,Courses,SC WHERE Students.sno=S

17、C.sno and Co=SC.cno and Sdept=IS;,练习1: Cname( Students.sno=Sc.snoSC.cno=Co Sdept=IS (Students(SCCourse),SC,原始语法树:,c: Students.sno=Sc.snoSC.cno=Co Sdept=IS c: SC.cno=Co c1: Sdept=IS,练习2,查询要求: 一图书管理数据库，其关系如下： BOOKS(Title, Author, Pname, LC_No) PUBLISHERS(Pname, Paddr, Pcity) BORROWERS(Name, Addr, City

18、, Card_No) LOANS(Card_No, LC_No, Date) 要求： 1.列出2003年1月1日之后借出的所有书名和借书人姓名 2. 写出关系代数及其原始语法树,并进行优化处理,画出优化后的语法树. SELECT Title,Name FROM BOOKS,BORROWERS,LOANS WHERE 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 BORRO

19、WERS.Card_No=LOANS.Card_No Date01/01/2003(BOOKS BORROWERSLOANS), Title,Name,Date01/01/2003,BOOKS,BORROWERS,LOANS,语法树:,BOOKS.LC_No=LOANS.LC_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 BORROWERSLOANS),F Date01/01/2003(

20、BOOKS BORROWERSLOANS) = F (BOOKS) Date01/01/2003(BORROWERSLOANS) = F (BOOKS BORROWERS) Date01/01/2003(LOANS),增加两个投影： Title, BOOKS.LC_No Name, LOANS.LC_No,练习2: Title,Name(F Date01/01/2003(BOOKS BORROWERSLOANS),Title，BOOKS. LC_No,练习2: Title,Name(F Date01/01/2003(BOOKS BORROWERSLOANS), Title,Name, Date

21、01/01/2003,BOOKS,BORROWERS,LOANS,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 BORROWERSLOANS),物理优化,涉及底层的存取路径，不同的存取方案导致不同的执行效率 物理优化：选择高效合理的操作算法或存取路径 优化方法 基于启发式规则的存取路径选择优化 基于代价的优化 两者结合的优化方法,物理优化基于启发式规则的存取路径选择优化,选

22、择操作的启发式规则 小关系：全表顺序扫描(优点：简单有效),95001, 1, 85 95003, 1, 95 95003, 2, 88 95004, 1, 70 95004, 3, 62 ,SC,选择操作的启发式规则 大关系 选择条件是主码=值的查询，查询结果最多一个选择主码索引 (RDBMS会自动建立主码索引),95001, 1 95003, 1 95003, 2 95004, 1 . 95004, 3 .,SC,Sno, Cno是主码,物理优化基于启发式规则的存取路径选择优化,选择操作的启发式规则 大关系 选择条件是范围查询或非等值查询，或选择条件是非主属性=值的查询 查询结果数目不明确

23、估算查询结果的元组数量 如果查询结果的元组数量10%，且选择列上有索引 使用索引扫描 否则，使用全表顺序扫描,物理优化基于启发式规则的存取路径选择优化,索引扫描 B+树索引或Hash索引 如果选择条件的属性上有索引，则可以利用索引进行扫描 等值查询：使用索引得到符合等值条件的指针 范围查询：仅适用于B+树索引。例如Sage20，以Sage=20为索引项，以此为入口点找到Sage20的所有元组指针 合取选择查询：例如Sdept=CS AND Sage20。 分别找到符合各个条件的元组指针，取指针的交集；或者 找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足 析取选择查询：使用全表顺序

24、扫描,物理优化基于启发式规则的存取路径选择优化,物理优化预备知识,B+树索引,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,连接操作的启发式规则 如果两个表都已经按照连接属性排序排序合并连接 例如： Students SC,物理优化基于启发式规则的存取路径选择优化,两个表只要扫描一次就可以完成连接操作,连接操作的启发式规则 如果一个表的连接属性上有索引排序索引连接 例如： Students SC,物理优化基于启发式规则的存取路径选择优化,索引连接(在SC的连接列Sno上建立索引):,Students,95001 95003 95003 95004 9

25、5004 .,SC上建立Sno的索引,.,95004 95002. 95003. 95001 .,95003, 1 95003, 2 95004, 2 . 95004, 3 . 95001, 1 .,SC,连接操作的启发式规则 如果前两个规则不适用，且一个表较小Hash连接 例如： Students SC,物理优化基于启发式规则的存取路径选择优化,Hash连接(选用Hash函数散列连接属性值): 例如：Hash函数=将Sno后三位模除3,连接操作的启发式规则 最后可选用嵌套循环方法 例如： Students SC,物理优化基于启发式规则的存取路径选择优化,物理优化基于代价的优化,启发式规则适用于解释执行的系统 优化开销包含在查询总开销中 基于代价的优化适用于编译执行的系统 一次编译优化，多次执行 优化开销不包含在查询执行中 对代价进行估算，选择代价最小的查询计划 新教材274页,