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

會(huì)計(jì)學(xué)1第關(guān)系查詢處理和查詢優(yōu)化關(guān)系查詢處理和查詢優(yōu)化主要內(nèi)容：查詢處理步驟查詢的優(yōu)化理論基礎(chǔ)——代數(shù)優(yōu)化物理優(yōu)化——存儲(chǔ)和結(jié)構(gòu)第1頁/共35頁4.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理RDBMS進(jìn)行查詢處理的目的是什么？提高計(jì)算機(jī)系統(tǒng)的執(zhí)行效率——優(yōu)化。查詢過程如下：第2頁/共35頁查詢語句詞法分析語法分析語義分析符號(hào)名轉(zhuǎn)換檢查安全性和完整性代數(shù)優(yōu)化物理優(yōu)化生成代碼查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行數(shù)據(jù)庫中的相關(guān)信息從另一個(gè)角度描述第3頁/共35頁查詢語法分析器與翻譯器關(guān)系代數(shù)表達(dá)式優(yōu)化器執(zhí)行計(jì)劃執(zhí)行引擎查詢結(jié)果數(shù)據(jù)有關(guān)數(shù)據(jù)的統(tǒng)計(jì)信息在實(shí)際操作過程中上述過程如何進(jìn)行？第4頁/共35頁4.2實(shí)現(xiàn)查詢操作的分析RDBMS有哪些基本類型的查詢操作？選擇，連接4.2.1RDBMS應(yīng)該怎樣進(jìn)行選擇操作？例如選擇語句Select*fromstudentwheresno=‘94545’最簡(jiǎn)單的方法：搜索全部相應(yīng)的表，查找符合條件的記錄或記錄集合。第5頁/共35頁利用數(shù)據(jù)結(jié)構(gòu)課程中的知識(shí)分析下列算法的特性,適用的情況。順序搜索法；二分搜索法；散列搜索法。第6頁/共35頁在一個(gè)關(guān)系數(shù)據(jù)庫的表中，RDBMS應(yīng)該如何進(jìn)行搜索(查詢)？1、簡(jiǎn)單的搜索：在沒有排序的情況下——順序搜索；已經(jīng)排序了——二分搜索；如果使用散列存儲(chǔ)(或B+樹)，可不可提高效率，如果可以該如何做？添加鍵信息(指向數(shù)據(jù)存儲(chǔ)的位置)。—索引第7頁/共35頁2、索引搜索法：B+樹的結(jié)構(gòu)：59971544597297101521374451596372859197rootsqtRoot和sqt指針的作用是什么，非葉子節(jié)點(diǎn)中的數(shù)據(jù)的作用是什么？針對(duì)某一個(gè)數(shù)據(jù)，可以采取哪幾種搜索方法？第8頁/共35頁利用B+樹建立的索引進(jìn)行搜索比簡(jiǎn)單的搜索性能如何？下面選擇語句應(yīng)該如何操作？1：select*fromstudentwheresno<‘023231’利用B+樹的索引功能，在Sno屬性上添加索引就可以提高操作效率。2：select*fromstudent,

s_cwherestudent.sno=s_c.snoRDBMS如何實(shí)現(xiàn)該操作？連接第9頁/共35頁4.2.2RDBMS應(yīng)該怎樣實(shí)現(xiàn)連接操作？法1.涉及到幾個(gè)表，就用幾層嵌套循環(huán)——該怎樣做？例如：Selectsnamefromstudent,s_cwherestudent.sno=s_c.snofor(每個(gè)元組tsinstudent){for(每個(gè)元組trins_c){if(每個(gè)(ts

,tr

)對(duì)滿足條件)把ts的sname放到結(jié)果中；}}第10頁/共35頁法2.先排序，然后再搜索——該怎樣做？法3.使用索引(建立索引)；進(jìn)行搜索——該怎樣做？問題：連接操作與簡(jiǎn)單的選擇操作，哪個(gè)執(zhí)行速度高？在一個(gè)復(fù)雜查詢中，用戶使用的查詢語句一定完全一樣嗎，若不一樣，各種語句的執(zhí)行速度都一樣嗎？看下例：Sfromstudent,s_cwherestudent.sno=s_c.snoands_o=‘2’操作方法有如下幾種：具體方法類似于《數(shù)據(jù)結(jié)構(gòu)》中介紹的相應(yīng)的方法。注意：該處的排序是外部排序。第11頁/共35頁步1：先求兩個(gè)表的笛卡爾積；步2：然后找到兩個(gè)學(xué)號(hào)相同且s_o=‘2’的元組；步3：查找出姓名。法1法2步1：先求兩個(gè)表的自然連接；步2：然后找到s_o=‘2’的元組；步3：查找出姓名。法3步1：先找到s_o=‘2’的元組；步2：然后student表和s_o=‘2’的元組自然連接；步3：查找出姓名。在相同條件下，哪種方法效率高，為什么？考查產(chǎn)生的中間結(jié)果的數(shù)量，法3應(yīng)該最少，法2次之，法1最多，因此……第12頁/共35頁對(duì)于用戶編寫的查詢語句，RDBMS有必要對(duì)其進(jìn)行語法分析，采取最優(yōu)的執(zhí)行方法，以提高效率。對(duì)上面的查詢的3種方法分別寫出關(guān)系代數(shù)式是什么？上面3個(gè)關(guān)系代數(shù)實(shí)現(xiàn)的是同一個(gè)功能，因此它們是等價(jià)的。針對(duì)用戶的查詢請(qǐng)求，RDBMS如何選擇高效的處理方式？第13頁/共35頁4.3代數(shù)優(yōu)化RDBMS選擇最優(yōu)操作的依據(jù)是什么？4.3.1關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則1、下列關(guān)系代數(shù)表達(dá)式是否成立？因此有第14頁/共35頁1.連接、笛卡爾積的交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有：第15頁/共35頁2、下列關(guān)系代數(shù)表達(dá)式是否成立？等值連接和連接呢？第16頁/共35頁2.連接、笛卡爾積的結(jié)合律沒有先后次序的區(qū)別第17頁/共35頁3、下列關(guān)系代數(shù)表達(dá)式是否成立，執(zhí)行效率是否一樣？第18頁/共35頁3.投影的串接定律4.選擇的串接定律第19頁/共35頁4、下列關(guān)系代數(shù)表達(dá)式是否成立，執(zhí)行效率是否一樣？5.選擇與投影操作的交換律F與Ai的關(guān)系是什么？F只涉及到Ai(i=1,2,…,n)，若F還涉及到其他呢？假設(shè)F還涉及到屬性Bj(j=1,2,…,n)，第20頁/共35頁5、下列關(guān)系代數(shù)表達(dá)式是否成立，執(zhí)行效率是否一樣？6.選擇與笛卡爾積的交換律第21頁/共35頁問題：第22頁/共35頁下面每個(gè)等式是否成立，等式兩面的執(zhí)行效率是否一樣？第23頁/共35頁RDBMS如何利用這些變換規(guī)則來提高效率？第24頁/共35頁4.3.2查詢樹的啟發(fā)式優(yōu)化RDBMS對(duì)用戶的一個(gè)查詢請(qǐng)求的處理過程是什么？查詢請(qǐng)求語法/語義分析查詢樹主要是利用關(guān)系代數(shù)式的變換來降低運(yùn)算的規(guī)模。代數(shù)優(yōu)化物理優(yōu)化執(zhí)行計(jì)劃/策略執(zhí)行引擎結(jié)果什么是查詢樹？第25頁/共35頁例如：selectstudent.SnameFromStudent,s_cwhereStudent.Sno=s_c.Snoands_c.Cno=‘2’前面3種查詢方法分別對(duì)應(yīng)的關(guān)系代數(shù)式是各自的查詢樹如下：第26頁/共35頁1：students_c2：students_c3：students_c第3種要比前兩種的查詢效率高，為什么？第27頁/共35頁查詢樹優(yōu)化的經(jīng)典啟發(fā)式規(guī)則：1、選擇操作應(yīng)盡可能先做?！猈hy?2、把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。——避免重復(fù)搜索(掃描)。3、把投影同其前或其后的雙目運(yùn)算結(jié)合起來?！苊庵貜?fù)掃描。4、把選擇同其前面的笛卡爾積結(jié)合起來——減小規(guī)模。5、找出表達(dá)式中的公共子表達(dá)式——避免重復(fù)操作。問題：給出一個(gè)查詢?nèi)绾卫蒙鲜鲆?guī)則實(shí)現(xiàn)優(yōu)化？第28頁/共35頁關(guān)系表達(dá)式的優(yōu)化算法輸入：一個(gè)關(guān)系表達(dá)式的查詢樹輸出：優(yōu)化的查詢樹步驟1：步驟2：將步驟1的結(jié)果利用變換盡可能移到樹的葉端——why?步驟3：將投影運(yùn)算分解并盡可能移到樹的葉端——why?步驟4：把選擇和投影的串接合并成一個(gè)選擇后跟一個(gè)投影——why?第29頁/共35頁4.4物理優(yōu)化代數(shù)優(yōu)化的主要目的是什么，涉及沒涉及到底層數(shù)據(jù)的存??？物理優(yōu)化的主要目的是提高底層數(shù)據(jù)的存取效率。主要方法：4.4.1、基于啟發(fā)式規(guī)則的存取選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則：1、對(duì)于小關(guān)系，應(yīng)該如何進(jìn)行選擇操作？全表順序搜索。對(duì)于大關(guān)系，又如何？第30頁/共35頁2、若選擇的條件是主碼=值的查詢，有多少個(gè)結(jié)果，應(yīng)該怎樣進(jìn)行操作？1個(gè)，使用主碼索引——百里挑一3、若選擇的條件是非主屬性=值的查詢，有多少個(gè)結(jié)果，應(yīng)該怎樣進(jìn)行操作？多個(gè)，需要根據(jù)具體情況來選擇，例如在student表中，選擇條件是：姓名=‘…’，應(yīng)該怎樣進(jìn)行操作，選擇條件是：專業(yè)=‘…’呢？在選擇條件是：姓名=‘…’中，結(jié)果不會(huì)很多，可以使用索引搜索。在選擇條件是：專業(yè)=‘…’中，結(jié)果會(huì)很多，需要使用順序搜索。Why?索引搜索和順序搜索的特點(diǎn)第31頁/共35頁4、若選擇是屬性上的非等值查詢或范圍查詢，并且選擇列上有索引，應(yīng)該如何操作？同樣要根據(jù)結(jié)果的規(guī)模決定使用索引搜索，還是順序搜索。5、對(duì)于用AND連接的合取選擇條件，有索引就用，否則使用順序搜索。6、對(duì)于用OR連接的選擇條件，一般順