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

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

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

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

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

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

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

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

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

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

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