第九章關(guān)系查詢處理和查詢優(yōu)化

第九章關(guān)系查詢處理和查詢優(yōu)化第1頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(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)算不要求定義任何物理存取路徑第2頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的分類:許多關(guān)系系統(tǒng)的產(chǎn)品按E.F.Codd的思想將關(guān)系系統(tǒng)分為:表式系統(tǒng)(a)最小關(guān)系系統(tǒng)(b)關(guān)系完備的系統(tǒng)(c)全關(guān)系系統(tǒng)(d)SMISMISMISMIabcd第3頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢處理:查詢處理的步驟:

queryParser&translatorRelationalalgebraexpressionOptimizerExecutionplanEvaluationengineQueryoutputdataStatisticsaboutdataDBMS第4頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:為什么需要查詢優(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í)行開銷盡量小第5頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:查詢優(yōu)化的一般步驟將查詢轉(zhuǎn)化成內(nèi)部表示--語(yǔ)法樹根據(jù)等價(jià)變化規(guī)則,將語(yǔ)法樹轉(zhuǎn)化成優(yōu)化形式選擇低層操作算法生成查詢計(jì)劃查詢執(zhí)行開銷主要包括:總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶數(shù)據(jù)庫(kù)執(zhí)行開銷:總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)第6頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(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))第7頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月代價(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))第8頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月通過讀取塊數(shù)計(jì)算I/O代價(jià)讀取塊數(shù)計(jì)算方法:Students1000個(gè)元組SC10000個(gè)元組讀取總塊數(shù):若每秒讀寫20塊,則花費(fèi):10100SCStudents5塊Q1=

sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))第9頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月連接后的元組個(gè)數(shù)為:103

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

105sQ1=

sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))第10頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月Q2=sname(Cno=‘2’(StudentsSC))Q2代價(jià)計(jì)算(僅考慮I/O代價(jià))計(jì)算自然連接代價(jià)也要把數(shù)據(jù)讀到內(nèi)存進(jìn)行連接,但連接結(jié)果比笛卡爾積要小得多讀取塊數(shù)依然為:花費(fèi)為2100/20

105s連接結(jié)果大小為104個(gè)元組,寫到外存需:(104/10)/20=50s第11頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月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=205sQ3代價(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)存第12頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月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塊第13頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(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ù)處理):...第14頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:95001…95002...95003...95004…...Students950011…950031…950032…950042...950043......SC排序合并連接(連接的關(guān)系分別排序):...索引連接(在SC的連接列Sno上建立索引):Students9500195003950039500495004...SC索引...95004…95002...95003...95001…...950031…950032…950042...950043...950011…...SC第15頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行

sno(cno=‘2’(SC))把投影和其前或后的雙目運(yùn)算結(jié)合起來

Cname(CourseSC)把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算

Students.Sno=SC.SnoandCno=‘2’(StudentsSC)找出公共子表達(dá)式第16頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(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第17頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(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--E1E2第18頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(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)

20第19頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:關(guān)系代數(shù)表達(dá)式的優(yōu)化算法:應(yīng)用關(guān)系代數(shù)等價(jià)變換規(guī)則來優(yōu)化關(guān)系代數(shù)表達(dá)式,使優(yōu)化后的表達(dá)式能遵循查詢優(yōu)化的一般準(zhǔn)則,在語(yǔ)法樹上進(jìn)行優(yōu)化關(guān)系代數(shù)表達(dá)式的優(yōu)化算法輸入:語(yǔ)法樹1利用規(guī)則4把形如F1F2…Fn(E)變換成

F1(F2(…(Fn(E))...))2對(duì)每一個(gè)選擇,利用規(guī)則4~8盡可能移到樹的葉端3對(duì)于每個(gè)投影,利用規(guī)則3,9,10,5盡可能移到樹的葉端20頁(yè)第20頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:

4利用規(guī)則3~5把選擇和投影的串接合并成單個(gè)選擇,單個(gè)投影,或一個(gè)選擇后跟一個(gè)投影5把處理后的語(yǔ)法樹內(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è)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:

SSPP不能結(jié)合成等值連接

S.Sno=SC.Sno

SCS能結(jié)合成等值連接第22頁(yè)，課件共25頁(yè)，創(chuàng)作于2023年2月關(guān)系系統(tǒng)的查詢優(yōu)化:優(yōu)化的一般步驟:因DBMS不同把查詢轉(zhuǎn)換成某種內(nèi)部表示(例如關(guān)系代數(shù)語(yǔ)法樹)把語(yǔ)法樹轉(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