【數(shù)據(jù)庫技術】查詢處理

1、第九章 查詢處理,9.1 查詢處理的過程 9.2 關系代數(shù)表達式的轉(zhuǎn)換（重點） 9.3 查詢代價的度量 9.4 實現(xiàn)關系運算的算法代價 9.5 表達式的求值方法 9.6 查詢優(yōu)化（重點）,9.1 查詢處理的過程,查詢處理進程的三個步驟（見教材P159）： (1)語法分析與翻譯；(2)查詢優(yōu)化（重點）；(3)查詢執(zhí)行。,據(jù),圖9.1 查詢處理過程,優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，例如關系中的元組數(shù)、關系中每個屬性值的分布情況等。優(yōu)化器可以根據(jù)這些信息選擇有效的執(zhí)行計劃，而用戶程序則難以獲得這些信息。 如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢進行重新優(yōu)化以選擇相適應的執(zhí)行計劃。在

2、非關系系統(tǒng)中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。優(yōu)化器中包括了很多復雜的優(yōu)化技術，這些優(yōu)化技術往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當于使得所有人都擁有這些優(yōu)化技術。,查詢優(yōu)化器 查詢優(yōu)化是影響RDBMS性能的關鍵因素。主要解決下面3個問題： 問題1：每個查詢語句可以翻譯成多個等價的關系代數(shù)表達式，應該選擇哪一個表達式？ 例如有SQL語句： Select student_number from student where student_number“s000003” 等價表達式為： stud

3、ent_number“s000003”( student_number(student) student_number(student_number“s000003”(student),問題2：每個關系表達式中的關系運算可以用不同的算法來實現(xiàn)，且可以采用不同的索引，應該選擇何種算法或索引？ 問題3：對于表達式的求值何種采用計算方法？ 以上三個問題的解決的方法形成執(zhí)行計劃。,9.2關系代數(shù)表達式的轉(zhuǎn)換,引例：“請給出計算機系的教師所講課程的課程名稱和教師姓名”。用如下兩個等價的關系代數(shù)表達式表達： course_name,teacher_name （department_name=“計算機系”(

4、teacherteaching)，其關系表達式樹如下： course_name,teacher_name,teacher,teaching,department_name=“計算機系”,course_name,teacher_name （department_name=“計算機系”(teacher）teaching)，其關系表達式樹如下： course_name,teacher_name,department_name=“計算機系“,teaching,teacher,9.2.1 等價規(guī)則 約定：用表示謂詞，用L表示屬性列表，用E表示關系代數(shù)表達式。 （1）的級聯(lián)： 12(E)= 1(2(E)

5、（2）選擇運算滿足交換律：1(2(E)=2(1(E) （3）的級聯(lián)： L1（ L2（ Ln（E）= L1(E) （4）選擇可與笛卡兒積以及theta連接相結合： (E1 E2)= E1 E2 1(E1 2 E2)= E1 1 2 E2 （5） theta連接（包括自然連接）運算滿足交換律： E1 E2 = E2 E1,（6）自然連接運算滿足結合律： (E1 E2) E3 = E1 （ E2 E3） （7）選擇運算在選定條件下對運算的分配律 （8）投影運算對運算具有分配律 （9）集合運算并與交運算滿足交換律 （10）集合運算并與交運算滿足結合律 （11）集合運算對并、交、差運算具有分配律 （12

6、）投影運算對并運算具有分配律,9.2.2 表達式轉(zhuǎn)換舉例 若有關系模式： 學生（學號，學生姓名，所在系） 選課（學號，課程名），有關系表達式： 例1：學生姓名（所在系=“計算機系”(學生選課)） 此關系代數(shù)表達式的含義？ 下面對此關系作等價變換： 利用規(guī)則7（1）可得如下等價表達式： 學生姓名（所在系=“計算機系”(學生）選課）,例2：學生姓名（所在系=“計算機系”課程名 like“數(shù)據(jù)庫%“(學生選課)） 此關系代數(shù)表達式的含義？ 下面對此關系作等價變換： 利用規(guī)則7（2）可得如下等價表達式： 學生姓名（所在系=“計算機系”（學生） （課程名 like“數(shù)據(jù)庫%“（選課）)）,關系表達式樹分

7、別如下：,學生,選課,學生姓名,所在系=“計算機系”課程名 like“數(shù)據(jù)庫%“,學生,例2關系代數(shù)表達式,例1關系代數(shù)表達式,9.3 查詢代價的度量,9.3.1 查詢處理的代價 查詢計劃也稱查詢執(zhí)行方案，是由一系列內(nèi)部操作組成的。這些內(nèi)部操作按一定的次序構成查詢的一個執(zhí)行方案。通常這樣的執(zhí)行方案有多個，需要對每個執(zhí)行計劃計算代價，從中選擇代價最小的一個。 在集中式數(shù)據(jù)庫中，查詢的執(zhí)行開銷主要包括： 總代價 = I/O代價 + CPU代價 在多用戶環(huán)境下： 總代價 = I/O代價 + CPU代價 + 內(nèi)存代價,9.3.2 處理模型 I/O代價用從磁盤向主存?zhèn)魉偷奈锢韷K數(shù)來度量。 假定所有塊傳送

8、的代價相同。 忽略了最終查詢結果寫回磁盤的代價。 實現(xiàn)算法的代價考慮最壞情況下的代價。,9.4 實現(xiàn)關系運算(選擇、連接)的算法代價,算法代價主要是計算磁盤存取代價，即在磁盤向主存?zhèn)魉偷奈锢韷K數(shù)來。 9.4.1 選擇運算 （1）不用索引的搜索算法-文件掃描： 線性搜索算法A1（？） 代價為：EA1=br 二分搜索算法A2（？） 代價為：EA2=log2(br) + SC(A,r)/fr -1,（2）使用索引的搜索算法-索引掃描： 在建立主索引的碼屬性上的等值比較算法： 代價為：EA3=HTi+1 在建立主索引的非碼屬性上的等值比較算法: 代價為：EA4=HTi+ SC(A,r)/fr,9.4.

9、2 連接運算 有嵌套循環(huán)連接算法、索引嵌套循環(huán)連接算法、歸并連接算法等 。 1、嵌套循環(huán)連接算法 例：rs的嵌套循環(huán)連接算法表示如下： for 對于r是的每一個元組tr，do begin for 對于s是的每一個元組ts，do begin 檢查元組對（）滿足連接條件嗎？ 若滿足則把tr.ts加到結果集中 end end,嵌套循環(huán)連接算法代價分析： 最壞情況下，緩沖區(qū)只能裝一個數(shù)據(jù)塊，則： EJ=nr*bs+br，其中nr為關系r中的記錄條數(shù)，bs為s中記錄的塊數(shù)，br為r中記錄的塊數(shù)。 最好情況下，兩個關系都能放入緩沖區(qū)中，則： EJ=bs+br 2、索引嵌套循環(huán)連接算法 將嵌套循環(huán)連接算法中

10、嵌套于內(nèi)層的文件掃描改為索引掃描。則 EJ=br+nr*c，其中c為使用連接條件并利用索引對關系s進行單個選擇運算的代價。,9.5 表達式的求值方法,（1）實體化計算方法 （2）流水線計算方法 （3）上述兩種方法的相互結合,9.5.1 實體化計算方法 實體化計算方法是以適當?shù)捻樞蛎看螆?zhí)行表達式中的一個運算，計算結果保存到一個臨時關系（實體化）中備用。如查詢： 課程名(（學號“s000003”(學生) 選課）的實體化計算方法執(zhí)行過程為：,課程名,學號“s000003”,選課,學生,R1,R2,R3,9.5.2 流水線計算方法 流水線計算方法是將表達式中多個關系運算組合成一個操作流水線來實現(xiàn)，即將一個運算的結果作為下一個運算的輸入，每條記錄依次執(zhí)行到底。如查詢： 課程名(（學號“s000003”(學生) 選課）的實體化計算方法執(zhí)行過程為：,課程名,學號“s000003”,選課,學生,T1,T2,T3,9.6 查詢優(yōu)化,查詢優(yōu)化器的工作目的：產(chǎn)生一個代價最小的查詢執(zhí)行計劃。 查詢優(yōu)化方法包括： 基于代價的優(yōu)化； 啟發(fā)式優(yōu)化。,9.6.1 基于代價的優(yōu)化方法 基于代價的優(yōu)化方法，其思想是將各種可能的查詢執(zhí)行計劃全部產(chǎn)生出來，然后從中選擇最小的一個。這樣的做法花費非常多