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

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

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

,tr

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