關(guān)系系統(tǒng)及其優(yōu)化

關(guān)系系統(tǒng)及其優(yōu)化第一頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的定義關(guān)系系統(tǒng):支持關(guān)系數(shù)據(jù)模型的數(shù)據(jù)庫(kù)管理系統(tǒng)(粗略)關(guān)系系統(tǒng)(確切定義):一個(gè)系統(tǒng)可以定義為一個(gè)關(guān)系系統(tǒng),當(dāng)且僅當(dāng)它:支持關(guān)系數(shù)據(jù)庫(kù)支持選擇、投影和連接運(yùn)算(自然連接),對(duì)這些運(yùn)算不要求定義任何物理存取路徑第二頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的分類:許多關(guān)系系統(tǒng)的產(chǎn)品按的思想將關(guān)系系統(tǒng)分為:表式系統(tǒng)(a)最小關(guān)系系統(tǒng)(b)關(guān)系完備的系統(tǒng)(c)全關(guān)系系統(tǒng)(d)SMISMISMISMIabcdS:StructureI:IntegrityM:Manipulation關(guān)系數(shù)據(jù)模型集合操作第三頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢處理:查詢處理的步驟:queryParser&translatorRelationalalgebraexpressionOptimizerExecutionplanEvaluationengineQueryoutputdataStatisticsaboutdataDBMS第四頁(yè)，共三十二頁(yè)，2022年，8月28日為什么需要查詢優(yōu)化？一個(gè)查詢實(shí)例:求選修2號(hào)課程的學(xué)生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;關(guān)系代數(shù)表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))第五頁(yè)，共三十二頁(yè)，2022年，8月28日代價(jià)計(jì)算Q1代價(jià)計(jì)算(僅考慮I/O代價(jià))計(jì)算廣義笛卡爾積代價(jià)假定:在內(nèi)存中,存放5塊Students元組和一塊SC元組,一塊可以裝10個(gè)Students元組或100個(gè)SC元組.假定:Students有1000個(gè)元組,SC有10000個(gè)元組,其中選2號(hào)課程的有50個(gè)元組數(shù)據(jù)只有讀到內(nèi)存才能進(jìn)行連接Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))10100SCStudents5塊第六頁(yè)，共三十二頁(yè)，2022年，8月28日通過(guò)讀取塊數(shù)計(jì)算I/O代價(jià)讀取塊數(shù)計(jì)算方法:Students1000個(gè)元組

SC10000個(gè)元組讀取總塊數(shù):若每秒讀寫20塊,則花費(fèi):10100SCStudents5塊Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Student塊數(shù)Student讀入內(nèi)存的次數(shù)SC塊數(shù)第七頁(yè)，共三十二頁(yè)，2022年，8月28日條件:Students1000個(gè)元組，SC10000個(gè)元組迪卡爾集后后的元組個(gè)數(shù)為:103

104=107連接后的中間結(jié)果內(nèi)存放不下,需暫時(shí)寫到外存若每塊可裝10個(gè)完成迪卡爾集后的元組,則寫這些元組需:(107/10)/20=5104s選擇操作:讀回需5104s,假設(shè)選擇后剩50個(gè)元組,均可放在內(nèi)存投影操作:查詢共花費(fèi):105+25104

105s

28小時(shí)Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))10100SCStudents5塊每秒讀20塊第八頁(yè)，共三十二頁(yè)，2022年，8月28日Q2=sname(Cno=‘2’(StudentsSC))Q2代價(jià)計(jì)算(僅考慮I/O代價(jià))計(jì)算自然連接代價(jià)也要把數(shù)據(jù)讀到內(nèi)存進(jìn)行連接,但連接結(jié)果比笛卡爾積要小得多讀取塊數(shù)依然為:花費(fèi)為2100/20105s假設(shè)連接結(jié)果大小為104個(gè)元組,寫到外存需:(104/10)/20=50s每秒讀20塊第九頁(yè)，共三十二頁(yè)，2022年，8月28日

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

Q3=sname(StudentsCno=‘2’(SC))讀取自然連接結(jié)果,執(zhí)行選擇運(yùn)算,需50s,選擇結(jié)果均可放在內(nèi)存投影運(yùn)算:總花費(fèi)為:105+50+50=205s3.4分鐘Q3代價(jià)計(jì)算(僅考慮I/O代價(jià))計(jì)算對(duì)SC做選擇運(yùn)算的代價(jià)需讀SC到內(nèi)存進(jìn)行選擇運(yùn)算讀SC塊數(shù)為:10000/100=100花費(fèi)為:100/20=5s選擇結(jié)果為50個(gè)SC元組,均可放在內(nèi)存第十頁(yè)，共三十二頁(yè)，2022年，8月28日Q3=sname(StudentsCno=‘2’(SC))計(jì)算和Students自然連接的代價(jià)需讀Students到內(nèi)存進(jìn)行連接運(yùn)算讀Students塊數(shù)為:1000/10=100花費(fèi)為:100/20=5s連接結(jié)果為50個(gè)元組,均可放在內(nèi)存投影運(yùn)算:總花費(fèi):5+5=10s1050SCStudents5塊第十一頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系系統(tǒng)的查詢優(yōu)化由系統(tǒng)完成,而不是由用戶完成優(yōu)化器可以從數(shù)據(jù)字典獲取許多統(tǒng)計(jì)信息如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了,優(yōu)化器可以對(duì)查詢進(jìn)行重新優(yōu)化以選擇適應(yīng)的執(zhí)行計(jì)劃優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃優(yōu)化器包括了許多復(fù)雜的技術(shù)優(yōu)化目標(biāo):尋求最優(yōu)的執(zhí)行計(jì)劃,使查詢執(zhí)行開(kāi)銷盡量小第十二頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:查詢優(yōu)化的一般步驟將查詢轉(zhuǎn)化成內(nèi)部表示--語(yǔ)法樹(shù)根據(jù)等價(jià)變化規(guī)則,將語(yǔ)法樹(shù)轉(zhuǎn)化成優(yōu)化形式選擇低層操作算法生成查詢計(jì)劃查詢執(zhí)行開(kāi)銷主要包括:

總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶數(shù)據(jù)庫(kù)執(zhí)行開(kāi)銷:

總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)第十三頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:查詢優(yōu)化的一般準(zhǔn)則:下面的優(yōu)化策略一般能提高查詢效率,但不一定是最優(yōu)的選擇運(yùn)算盡可能先做,降低中間結(jié)果大小在連接前,對(duì)關(guān)系適當(dāng)?shù)倪M(jìn)行預(yù)處理:對(duì)關(guān)系排序(排序合并連接方法)或在連接屬性上建索引(索引連接方法)95004…95002...95003...95001…...Students950031…950032…950042...950043...950011…...SC循環(huán)嵌套連接(不做任何預(yù)處理):...第十四頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:95001…95002...95003...95004…...Students95001,1…95003,1…95003,2…95004,2...95004,3...SC排序合并連接(連接的關(guān)系分別排序):...索引連接(在SC的連接列Sno上建立索引):Students9500195003950039500495004...SC索引...95004…95002...95003...95001…...95003,1…95003,2…95004,2...95004,3...95001,1…...SC第十五頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行

sno(cno=‘2’(SC))把投影和其前或后的雙目運(yùn)算結(jié)合起來(lái)Cname(CourseSC)把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算Students.Sno=SC.SnoandCno=‘2’(StudentsSC)找出公共子表達(dá)式第十六頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系代數(shù)等價(jià)變換規(guī)則:給定sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))如何將上述提到的運(yùn)算先做,即得到:sname(StudentsCno=‘2’(SC))規(guī)則1:連接、笛卡爾積的交換律

E1E2E2E1E1E2=E2E1E1E2=E2E1E:關(guān)系代數(shù)表達(dá)式F:連接條件規(guī)則2:連接、笛卡爾積的結(jié)合律(E1E2)E3=E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)F1FFF2F1F2第十七頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:規(guī)則3:投影的串接定律

A1,A2,...,An(B1,B2,...,Bn(E))A1,A2,...,An(E)規(guī)則4:選擇的串接定律F1(F2(E))F1F2(E)規(guī)則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)))規(guī)則6:選擇與笛卡爾積的交換律F(E1E2)F(E1)E2

F僅和E1有關(guān)F(E1E2)F1(E1)F2(E2)F=F1F2

F(E1E2)F2(F1(E1)E2)F1--E1F2--E1E22021第十八頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:規(guī)則7:選擇與并的交換

F(E1E2)F(E1)F(E2)規(guī)則8:選擇與差的交換F(E1-E2)F(E1)-F(E2)規(guī)則9:投影與笛卡爾積的交換

A1,A2,...,An,B1,B2,...,Bm(E1E2)A1,A2,...,An(E1)B1,B2,...,Bm(E2)規(guī)則10:投影與并的交換A1,A2,...,An(E1E2)A1,A2,...,An(E1)A1,A2,...,An(E2)

第十九頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系代數(shù)表達(dá)式的優(yōu)化算法:應(yīng)用關(guān)系代數(shù)等價(jià)變換規(guī)則來(lái)優(yōu)化關(guān)系代數(shù)表達(dá)式,使優(yōu)化后的表達(dá)式能遵循查詢優(yōu)化的一般準(zhǔn)則,在語(yǔ)法樹(shù)上進(jìn)行優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入:語(yǔ)法樹(shù)

1

利用規(guī)則4把形如F1F2…Fn(E)變換成F1(F2(…(Fn(E))...))

2

對(duì)每一個(gè)選擇,利用規(guī)則4~8盡可能移到樹(shù)的葉端

3

對(duì)于每個(gè)投影,利用規(guī)則3,9,10,5盡可能移到樹(shù)的葉端

4

利用規(guī)則3~5把選擇和投影的串接合并成單個(gè)選擇,單個(gè)投影,或一個(gè)選擇后跟一個(gè)投影第二十頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:

5把處理后的語(yǔ)法樹(shù)內(nèi)節(jié)點(diǎn)分組:每一雙目運(yùn)算(,,,)和它的所有直接祖先(,)為一組,后代直到葉子全是單目運(yùn)算也并入該組;若雙目運(yùn)算為,且其后的選擇不能與它結(jié)合為等值連接時(shí),這些單目運(yùn)算單獨(dú)為一組.

6

生成一個(gè)程序,每組節(jié)點(diǎn)的計(jì)算是程序中的一步輸出:計(jì)算關(guān)系代數(shù)表達(dá)式的程序21頁(yè)SSPP不能結(jié)合成等值連接S.Sno=SC.SnoSCS能結(jié)合成等值連接第二十一頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:優(yōu)化的一般步驟:因DBMS不同把查詢轉(zhuǎn)換成某種內(nèi)部表示(例如關(guān)系代數(shù)語(yǔ)法樹(shù))把語(yǔ)法樹(shù)轉(zhuǎn)化成標(biāo)準(zhǔn)(優(yōu)化)形式選擇底層的存取路徑生成查詢計(jì)劃,選擇代價(jià)最小的例子:設(shè)有供應(yīng)商S,零件P和供應(yīng)關(guān)系SP三個(gè)關(guān)系,其關(guān)系模式:S(Snum,Sname,City)P(Pnum,Pname,Weight,Size)SP(Snum,Pnum,Dept,Quan)第二十二頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:selectSnamefromS,SP,PwhereS.Snum=SP.SnumandSP.Pnum=P.PnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000;原始語(yǔ)法樹(shù):select--投影

from--笛卡爾積

where--選擇第二十三頁(yè)，共三十二頁(yè)，2022年，8月28日關(guān)系系統(tǒng)的查詢優(yōu)化:SnamecSSPPC=S.Snum=SP.SnumandSP.Pnum=P.PnumandS.City=‘NANJING’andP.Pname=‘Bolt’andSP.Quan>1000SnamecSSPPSnamec’SSPPssppSnamec’’SSPPssppSnameSSPPssppspspc’c’’優(yōu)化:第二十四頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)1查詢要求:查詢信息系學(xué)生選修的所有的課程的課程名稱寫出關(guān)系代數(shù)及其原始語(yǔ)法樹(shù),并進(jìn)行優(yōu)化處理,畫出優(yōu)化后的語(yǔ)法樹(shù).SELECTCnameFROMStudents,Course,SCWHEREStudents.sno=SC.snoandCo=SC.cnoandSdept=‘IS’;第二十五頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)1:

Cname(Sdept=‘IS’(StudentsSCCourse))CnamecStudentsSCCourse原始語(yǔ)法樹(shù):Cnamec1StudentsSCCourseC:Students.sno=Sc.snoSC.cno=CoSdept=‘IS’C’:

SC.cno=Co,C1:Sdept=‘IS’Cnamec1StudentsSCCoursec’第二十六頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)2查詢要求:一圖書管理數(shù)據(jù)庫(kù)，其關(guān)系如下：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.寫出關(guān)系代數(shù)及其原始語(yǔ)法樹(shù),并進(jìn)行優(yōu)化處理,畫出優(yōu)化后的語(yǔ)法樹(shù).SELECTTitle,NamefromBOOKS,BORROWERS,LOANSWHEREBOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_NoANDDate>’01/01/2003’圖書編號(hào)圖書證號(hào)第二十七頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)2:

Title,Name(Date>’01/01/2003’(BOOKSBORROWERSLOANS))Title,NameDate>’01/01/2003’BOOKSBORROWERSLOANS原始語(yǔ)法樹(shù):BOOKS.LC_No=LOANS.LC_NoANDBORROWERS.Card_No=LOANS.Card_No

Title,Author,Pname,LC_No,Name,Addr,City,Card_No,Date第二十八頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)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

第二十九頁(yè)，共三十二頁(yè)，2022年，8月28日練習(xí)2:

Title,Name(Date>