关系系统及其优化

关系系统及其优化第一页，共三十二页，2022年，8月28日关系系统的定义关系系统:支持关系数据模型的数据库管理系统(粗略)关系系统(确切定义):一个系统可以定义为一个关系系统,当且仅当它:支持关系数据库支持选择、投影和连接运算(自然连接),对这些运算不要求定义任何物理存取路径第二页，共三十二页，2022年，8月28日关系系统的分类:许多关系系统的产品按的思想将关系系统分为:表式系统(a)最小关系系统(b)关系完备的系统(c)全关系系统(d)SMISMISMISMIabcdS:StructureI:IntegrityM:Manipulation关系数据模型集合操作第三页，共三十二页，2022年，8月28日关系系统的查询处理:查询处理的步骤:queryParser&translatorRelationalalgebraexpressionOptimizerExecutionplanEvaluationengineQueryoutputdataStatisticsaboutdataDBMS第四页，共三十二页，2022年，8月28日为什么需要查询优化？一个查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;关系代数表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))第五页，共三十二页，2022年，8月28日代价计算Q1代价计算(仅考虑I/O代价)计算广义笛卡尔积代价假定:在内存中,存放5块Students元组和一块SC元组,一块可以装10个Students元组或100个SC元组.假定:Students有1000个元组,SC有10000个元组,其中选2号课程的有50个元组数据只有读到内存才能进行连接Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))10100SCStudents5块第六页，共三十二页，2022年，8月28日通过读取块数计算I/O代价读取块数计算方法:Students1000个元组

SC10000个元组读取总块数:若每秒读写20块,则花费:10100SCStudents5块Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Student块数Student读入内存的次数SC块数第七页，共三十二页，2022年，8月28日条件:Students1000个元组，SC10000个元组迪卡尔集后后的元组个数为:103

104=107连接后的中间结果内存放不下,需暂时写到外存若每块可装10个完成迪卡尔集后的元组,则写这些元组需:(107/10)/20=5104s选择操作:读回需5104s,假设选择后剩50个元组,均可放在内存投影操作:查询共花费:105+25104

105s

28小时Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))10100SCStudents5块每秒读20块第八页，共三十二页，2022年，8月28日Q2=sname(Cno=‘2’(StudentsSC))Q2代价计算(仅考虑I/O代价)计算自然连接代价也要把数据读到内存进行连接,但连接结果比笛卡尔积要小得多读取块数依然为:花费为2100/20105s假设连接结果大小为104个元组,写到外存需:(104/10)/20=50s每秒读20块第九页，共三十二页，2022年，8月28日

Q2=sname(Cno=‘2’(StudentsSC))

Q3=sname(StudentsCno=‘2’(SC))读取自然连接结果,执行选择运算,需50s,选择结果均可放在内存投影运算:总花费为:105+50+50=205s3.4分钟Q3代价计算(仅考虑I/O代价)计算对SC做选择运算的代价需读SC到内存进行选择运算读SC块数为:10000/100=100花费为:100/20=5s选择结果为50个SC元组,均可放在内存第十页，共三十二页，2022年，8月28日Q3=sname(StudentsCno=‘2’(SC))计算和Students自然连接的代价需读Students到内存进行连接运算读Students块数为:1000/10=100花费为:100/20=5s连接结果为50个元组,均可放在内存投影运算:总花费:5+5=10s1050SCStudents5块第十一页，共三十二页，2022年，8月28日关系系统的查询优化:关系系统的查询优化由系统完成,而不是由用户完成优化器可以从数据字典获取许多统计信息如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术优化目标:寻求最优的执行计划,使查询执行开销尽量小第十二页，共三十二页，2022年，8月28日关系系统的查询优化:查询优化的一般步骤将查询转化成内部表示--语法树根据等价变化规则,将语法树转化成优化形式选择低层操作算法生成查询计划查询执行开销主要包括:

总代价=I/O代价+CPU代价多用户数据库执行开销:

总代价=I/O代价+CPU代价+内存代价第十三页，共三十二页，2022年，8月28日关系系统的查询优化:查询优化的一般准则:下面的优化策略一般能提高查询效率,但不一定是最优的选择运算尽可能先做,降低中间结果大小在连接前,对关系适当的进行预处理:对关系排序(排序合并连接方法)或在连接属性上建索引(索引连接方法)95004…95002...95003...95001…...Students950031…950032…950042...950043...950011…...SC循环嵌套连接(不做任何预处理):...第十四页，共三十二页，2022年，8月28日关系系统的查询优化:95001…95002...95003...95004…...Students95001,1…95003,1…95003,2…95004,2...95004,3...SC排序合并连接(连接的关系分别排序):...索引连接(在SC的连接列Sno上建立索引):Students9500195003950039500495004...SC索引...95004…95002...95003...95001…...95003,1…95003,2…95004,2...95004,3...95001,1…...SC第十五页，共三十二页，2022年，8月28日关系系统的查询优化:把投影运算和选择运算同时进行

sno(cno=‘2’(SC))把投影和其前或后的双目运算结合起来Cname(CourseSC)把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算Students.Sno=SC.SnoandCno=‘2’(StudentsSC)找出公共子表达式第十六页，共三十二页，2022年，8月28日关系系统的查询优化:关系代数等价变换规则:给定sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))如何将上述提到的运算先做,即得到:sname(StudentsCno=‘2’(SC))规则1:连接、笛卡尔积的交换律

E1E2E2E1E1E2=E2E1E1E2=E2E1E:关系代数表达式F:连接条件规则2:连接、笛卡尔积的结合律(E1E2)E3=E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)F1FFF2F1F2第十七页，共三十二页，2022年，8月28日关系系统的查询优化:规则3:投影的串接定律

A1,A2,...,An(B1,B2,...,Bn(E))A1,A2,...,An(E)规则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(E1E2)F(E1)E2

F仅和E1有关F(E1E2)F1(E1)F2(E2)F=F1F2

F(E1E2)F2(F1(E1)E2)F1--E1F2--E1E22021第十八页，共三十二页，2022年，8月28日关系系统的查询优化:规则7:选择与并的交换

F(E1E2)F(E1)F(E2)规则8:选择与差的交换F(E1-E2)F(E1)-F(E2)规则9:投影与笛卡尔积的交换

A1,A2,...,An,B1,B2,...,Bm(E1E2)A1,A2,...,An(E1)B1,B2,...,Bm(E2)规则10:投影与并的交换A1,A2,...,An(E1E2)A1,A2,...,An(E1)A1,A2,...,An(E2)

第十九页，共三十二页，2022年，8月28日关系系统的查询优化:关系代数表达式的优化算法:应用关系代数等价变换规则来优化关系代数表达式,使优化后的表达式能遵循查询优化的一般准则,在语法树上进行优化关系代数表达式的优化算法输入:语法树

1

利用规则4把形如F1F2…Fn(E)变换成F1(F2(…(Fn(E))...))

2

对每一个选择,利用规则4~8尽可能移到树的叶端

3

对于每个投影,利用规则3,9,10,5尽可能移到树的叶端

4

利用规则3~5把选择和投影的串接合并成单个选择,单个投影,或一个选择后跟一个投影第二十页，共三十二页，2022年，8月28日关系系统的查询优化:

5把处理后的语法树内节点分组:每一双目运算(,,,)和它的所有直接祖先(,)为一组,后代直到叶子全是单目运算也并入该组;若双目运算为,且其后的选择不能与它结合为等值连接时,这些单目运算单独为一组.

6

生成一个程序,每组节点的计算是程序中的一步输出:计算关系代数表达式的程序21页SSPP不能结合成等值连接S.Sno=SC.SnoSCS能结合成等值连接第二十一页，共三十二页，2022年，8月28日关系系统的查询优化:优化的一般步骤:因DBMS不同把查询转换成某种内部表示(例如关系代数语法树)把语法树转化成标准(优化)形式选择底层的存取路径生成查询计划,选择代价最小的例子:设有供应商S,零件P和供应关系SP三个关系,其关系模式:S(Snum,Sname,City)P(Pnum,Pname,Weight,Size)SP(Snum,Pnum,Dept,Quan)第二十二页，共三十二页，2022年，8月28日关系系统的查询优化:selectSnamefromS,SP,PwhereS.Snum=SP.SnumandSP.Pnum=P.PnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000;原始语法树:select--投影

from--笛卡尔积

where--选择第二十三页，共三十二页，2022年，8月28日关系系统的查询优化:SnamecSSPPC=S.Snum=SP.SnumandSP.Pnum=P.PnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000SnamecSSPPSnamec’SSPPssppSnamec’’SSPPssppSnameSSPPssppspspc’c’’优化:第二十四页，共三十二页，2022年，8月28日练习1查询要求:查询信息系学生选修的所有的课程的课程名称写出关系代数及其原始语法树,并进行优化处理,画出优化后的语法树.SELECTCnameFROMStudents,Course,SCWHEREStudents.sno=SC.snoandCo=SC.cnoandSdept=‘IS’;第二十五页，共三十二页，2022年，8月28日练习1:

Cname(Sdept=‘IS’(StudentsSCCourse))CnamecStudentsSCCourse原始语法树:Cnamec1StudentsSCCourseC:Students.sno=Sc.snoSC.cno=CoSdept=‘IS’C’:

SC.cno=Co,C1:Sdept=‘IS’Cnamec1StudentsSCCoursec’第二十六页，共三十二页，2022年，8月28日练习2查询要求:一图书管理数据库，其关系如下：BOOKS(Title,Author,Pname,LC_No)PUBLISHERS(Pname,Paddr,Pcity)BORROWERS(Name,Addr,City,Card_No)LOANS(Card_No,LC_No,Date)要求：1.列出1999年1月1日前借出的所有书名和借书人姓名2.写出关系代数及其原始语法树,并进行优化处理,画出优化后的语法树.SELECTTitle,NamefromBOOKS,BORROWERS,LOANSWHEREBOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_NoANDDate>’01/01/2003’图书编号图书证号第二十七页，共三十二页，2022年，8月28日练习2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLOANS))Title,NameDate>’01/01/2003’BOOKSBORROWERSLOANS原始语法树:BOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_No

Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date第二十八页，共三十二页，2022年，8月28日练习2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLOANS))Date>’01/01/2003’(BOOKSBORROWERSLOANS)=BOOKSDate>’01/01/2003’(BORROWERSLOANS)=BOOKSBORROWERSDate>’01/01/2003’(LOANS)Title,NameDate>’01/01/2003’BOOKSBORROWERSLOANSBOOKS.LC_No=LOANS.LC_NoBORROWERS.Card_No=LOANS.Card_No

第二十九页，共三十二页，2022年，8月28日练习2:

Title,Name(Date>