第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化

1、第九章 關(guān)系查詢處理及其查詢優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小 結(jié) 關(guān)系查詢處理及其查詢優(yōu)化（續(xù)） o 本章目的： n RDBMS的查詢處理步驟 n 查詢優(yōu)化的概念 n 基本方法和技術(shù) o 查詢優(yōu)化分類 ： n 代數(shù)優(yōu)化 n 物理優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.1.1 查詢處理步驟 9.1.2 實(shí)現(xiàn)查詢操作的算法示例 9.1.1 查詢處理步驟 RDBMS查詢處理階段 ： 1. 查詢分析 2. 查詢檢查 3. 查詢優(yōu)化 4. 查詢執(zhí)行 查詢處理步驟（續(xù)） 查詢處理步驟 1. 查詢分析 o 對查詢語句

2、進(jìn)行掃描、詞法分析和語法分析 o 從查詢語句中識別出語言符號 o 進(jìn)行語法檢查和語法分析 2. 查詢檢查 o 根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查 o 根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用 戶的存取權(quán)限進(jìn)行檢查 o 檢查通過后把SQL查詢語句轉(zhuǎn)換成等價的關(guān)系代數(shù) 表達(dá)式 o RDBMS一般都用查詢樹(語法分析樹)來表示擴(kuò)展的 關(guān)系代數(shù)表達(dá)式 o 把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換為內(nèi)部表示 3. 查詢優(yōu)化 o 查詢優(yōu)化：選擇一個高效執(zhí)行的查詢處理策略 o 查詢優(yōu)化分類 ： n代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化 n物理優(yōu)化：指存取路徑和底層操作算法的選擇 o 查詢優(yōu)化方法選擇的依據(jù)： n基于規(guī)

3、則(rule based) n基于代價(cost based) n基于語義(semantic based) 4. 查詢執(zhí)行 o 依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計劃 o 代碼生成器(code generator)生成執(zhí)行查詢 計劃的代碼 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.1.1 查詢處理步驟 9.1.2 實(shí)現(xiàn)查詢操作的算法示例 9.1.2 實(shí)現(xiàn)查詢操作的算法示例 一、 選擇操作的實(shí)現(xiàn) 二、 連接操作的實(shí)現(xiàn) 一、 選擇操作的實(shí)現(xiàn) 例1: Select * from student where ；考 慮的幾種情況： C1：無條件； C2：Sno200215121； C3：Sage20； C4：

4、SdeptCS AND Sage20； 選擇操作的實(shí)現(xiàn)（續(xù)） o 選擇操作典型實(shí)現(xiàn)方法： n1. 簡單的全表掃描方法 對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇 條件，把滿足條件的元組作為結(jié)果輸出 適合小表，不適合大表 n2. 索引(或散列)掃描方法 適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引) 通過索引先找到滿足條件的元組主碼或元組指針，再通過元 組指針直接在查詢的基本表中找到元組 選擇操作的實(shí)現(xiàn)（續(xù)） o例1-C2 以C2為例，Sno200215121，并且Sno上有索 引(或Sno是散列碼) n使用索引(或散列)得到Sno為200215121元組的指針 n通過元

5、組指針在student表中檢索到該學(xué)生 o例1-C3 以C3為例，Sage20，并且Sage上有B+樹索引 n使用B+樹索引找到Sage20的索引項(xiàng)，以此為入口點(diǎn)在 B+樹的順序集上得到Sage20的所有元組指針 n通過這些元組指針到student表中檢索到所有年齡大于20 的學(xué)生。 選擇操作的實(shí)現(xiàn)（續(xù)） o例1-C4 以C4為例，SdeptCSAND Sage20，如果Sdept和 Sage上都有索引： n算法一：分別用上面兩種方法分別找到SdeptCS的一組 元組指針和Sage20的另一組元組指針 求這2組指針的交集 到student表中檢索 得到計算機(jī)系年齡大于20的學(xué)生 n算法二：找到

6、SdeptCS的一組元組指針， 通過這些元組指針到student表中檢索 對得到的元組檢查另一些選擇條件(如Sage20)是否滿足 把滿足條件的元組作為結(jié)果輸出。 二、 連接操作的實(shí)現(xiàn) o 連接操作是查詢處理中最耗時的操作之一 o 本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法 例2 SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno； 連接操作的實(shí)現(xiàn)（續(xù)） 1. 嵌套循環(huán)方法(nested loop) 2. 排序-合并方法(sort-merge join 或merge join) 3. 索引連接(index join)方法 4. Hash J

7、oin方法 連接操作的實(shí)現(xiàn)（續(xù)） 1. 嵌套循環(huán)方法(nested loop) n 對外層循環(huán)(Student)的每一個元組(s)，檢索 內(nèi)層循環(huán)(SC)中的每一個元組(sc) n 檢查這兩個元組在連接屬性(sno)上是否相等 n 如果滿足連接條件，則串接后作為結(jié)果輸出， 直到外層循環(huán)表中的元組處理完為止 連接操作的實(shí)現(xiàn)（續(xù)） 2. 排序-合并方法(sort-merge join 或merge join) n 適合連接的諸表已經(jīng)排好序的情況 n 排序合并連接方法的步驟： 如果連接的表沒有排好序，先對Student表和SC表按連 接屬性Sno排序 取Student表中第一個Sno，依次掃描SC表

8、中具有相同 Sno的元組 連接操作的實(shí)現(xiàn)（續(xù)） 200215121200215121 200215122200215122 200215123200215123 200215124200215124 . . . . . . 200215121 1 92200215121 1 92 200215121 2 85200215121 2 85 200215121 3 88200215121 3 88 200215122 2 90200215122 2 90 200215122 3 80200215122 3 80 . . . . . . 排序-合并連接方法示意圖 連接操作的實(shí)現(xiàn)（續(xù)） n 排序合并連

9、接方法的步驟（續(xù)）： 當(dāng)掃描到Sno不相同的第一個SC元組時，返回 Student表掃描它的下一個元組，再掃描SC表中具 有相同Sno的元組，把它們連接起來 重復(fù)上述步驟直到Student 表掃描完 連接操作的實(shí)現(xiàn)（續(xù)） o Student表和SC表都只要掃描一遍 o 如果2個表原來無序，執(zhí)行時間要加上對兩個表的 排序時間 o 對于2個大表，先排序后使用sort-merge join方法 執(zhí)行連接，總的時間一般仍會大大減少 連接操作的實(shí)現(xiàn)（續(xù)） 3. 索引連接(index join)方法 o 步驟： 在SC表上建立屬性Sno的索引，如果原來沒有該索引 對Student中每一個元組，由Sno值通

10、過SC的索引查找相 應(yīng)的SC元組 把這些SC元組和Student元組連接起來 循環(huán)執(zhí)行，直到Student表中的元組處理完為止 連接操作的實(shí)現(xiàn)（續(xù)） 4. Hash Join方法 o把連接屬性作為hash碼，用同一個hash函數(shù)把R和S中的元組散列到 同一個hash文件中 o步驟： n劃分階段(partitioning phase)： 對包含較少元組的表(比如R)進(jìn)行一遍處理 把它的元組按hash函數(shù)分散到hash表的桶中 n試探階段(probing phase)：也稱為連接階段(join phase) 對另一個表(S)進(jìn)行一遍處理 把S的元組散列到適當(dāng)?shù)膆ash桶中 把元組與桶中所有來自R并

11、與之相匹配的元組連接起來 連接操作的實(shí)現(xiàn)（續(xù)） o 上面hash join算法前提：假設(shè)兩個表中較 小的表在第一階段后可以完全放入內(nèi)存的 hash桶中 o 以上的算法思想可以推廣到更加一般的多個 表的連接算法上 第九章 關(guān)系查詢處理及其查詢優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小結(jié) 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 o 查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要 的地位 o 關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素 o 由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系 統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供 了執(zhí)行查詢優(yōu)化的可

12、能性 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.2.1 查詢優(yōu)化概述 9.2.2 一個實(shí)例 9.2.1 查詢優(yōu)化概述 o 關(guān)系系統(tǒng)的查詢優(yōu)化 o 非關(guān)系系統(tǒng) 查詢優(yōu)化概述（續(xù)） o 查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢 以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化 ”做得更好 (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則 難以獲得這些信息 (2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新 優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序 ，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。 查詢優(yōu)化概述（續(xù)） (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃

13、，程序員一 般只能考慮有限的幾種可能性。 (4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技 術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu) 化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù) 查詢優(yōu)化概述（續(xù)） o RDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代 價，然后選取代價最小的執(zhí)行方案 n集中式數(shù)據(jù)庫 執(zhí)行開銷主要包括： 磁盤存取塊數(shù)(I/O代價) 處理機(jī)時間(CPU代價) 查詢的內(nèi)存開銷 I/O代價是最主要的 n分布式數(shù)據(jù)庫 總代價=I/O代價+CPU代價+內(nèi)存代價通信代價 查詢優(yōu)化概述（續(xù)） o 查詢優(yōu)化的總目標(biāo)： n 選擇有效的策略 n 求得給定關(guān)系表達(dá)式的值 n 使得查詢代價最小(

14、實(shí)際上是較小) 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.2.1 查詢優(yōu)化概述 9.2.2 一個實(shí)例 9.2.2 一個實(shí)例 例3 求選修了2號課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； n假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選 課記錄 n其中選修2號課程的選課記錄為50個 一個實(shí)例（續(xù)） o 系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達(dá)式來完成這一查詢 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2(StudentSC) Q2=

15、Sname(Sc.Cno=2 (Student SC) Q3=Sname(Student Sc.Cno=2(SC) 一個實(shí)例（續(xù)） o一、第一種情況一、第一種情況 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC) 1. 計算廣義笛卡爾積 o把Student和SC的每個元組連接起來的做法： n在內(nèi)存中盡可能多地裝入某個表(如Student表)的若干塊，留出一 塊存放另一個表(如SC表)的元組。 n把SC中的每個元組和Student中每個元組連接，連接后的元組裝滿 一塊后就寫到中間文件上 n從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理

16、完。 n再讀入若干塊Student元組，讀入一塊SC元組 n重復(fù)上述處理過程，直到把Student表處理完 一個實(shí)例（續(xù)） o 設(shè)一個塊能裝10個Student元組或100個SC元組，在內(nèi)存中存 放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為 =100+20100=2100塊 o 其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒 讀寫20塊，則總計要花105s o 連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個元組，則寫 出這些塊要用106/20=5104s 10 1000 510 1000 100 10000 一個實(shí)例（續(xù)） 2. 作選擇操作 n 依次讀

17、入連接后的元組，按照選擇條件選取滿 足要求的記錄 n 假定內(nèi)存處理時間忽略。讀取中間文件花費(fèi)的 時間(同寫中間文件一樣)需5104s n 滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存 一個實(shí)例（續(xù)） 3. 作投影操作 n 把第2步的結(jié)果在Sname上作投影輸出，得到最 終結(jié)果 n 第一種情況下執(zhí)行查詢的總時間 105+25104105s n 所有內(nèi)存處理時間均忽略不計 一個實(shí)例（續(xù)） 二、 第二種情況 Q2=Sname(Sc.Cno=2 (Student SC) 1. 計算自然連接 執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為 2100塊花費(fèi)105 s 自然連接的結(jié)果比第一

18、種情況大大減少，為104個 寫出這些元組時間為104/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時間也為50s。 3. 把第2步結(jié)果投影輸出。 第二種情況總的執(zhí)行時間105+50+50205s 一個實(shí)例（續(xù)） 三、 第三種情況 Q3=Sname(Student Sc.Cno=2(SC) 1. 先對SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時 間為5s，因?yàn)闈M足條件的元組僅50個，不必使用中間文件。 2. 讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作 連接。也只需讀一遍Student表共100塊，花費(fèi)時間為5s。 3.

19、把連接結(jié)果投影輸出 第三種情況總的執(zhí)行時間5+510s 一個實(shí)例（續(xù)） o 假如SC表的Cno字段上有索引 n第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些 元組(50個) n存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊 o 若Student表在Sno上也有索引 n第二步也不必讀取所有的Student元組 n因?yàn)闈M足條件的SC記錄僅50個，涉及最多50個Student記錄 n讀取Student表的塊數(shù)也可大大減少 o 總的存取時間將進(jìn)一步減少到數(shù)秒 一個實(shí)例（續(xù)） o 把代數(shù)表達(dá)式Q1變換為Q2、 Q3， n即有選擇和連接操作時，先做選擇操作，這樣參加連接的 元組就可以大大減少

20、，這是代數(shù)優(yōu)化 o 在Q3中 nSC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過 初步估算，索引掃描方法較優(yōu) n對于Student和SC表的連接，利用Student表上的索引，采 用index join代價也較小，這就是物理優(yōu)化 第九章 關(guān)系查詢處理及其查詢優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小結(jié) 9.3 代數(shù)優(yōu)化 9.3.1 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化 9.3.1 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則 o 代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等 價變換來提高查詢效率 o 兩個關(guān)系表達(dá)

21、式E1和E2是等價的，可記為 E1E2 o常用的等價變換規(guī)則： 1. 連接、笛卡爾積交換律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運(yùn)算的條件，則有 E1 E2E2 E1 E1 E2E2 E1 E1 E2E2 E1 2. 連接、笛卡爾積的結(jié)合律 設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運(yùn)算的條件，則有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 3. 投影的串接定律 ( (E) (E) 這里，E是關(guān)系代數(shù)表達(dá)式，Ai(i=1，2，n)，

22、Bj(j=1，2， ，m)是屬性名且A1，A2，An構(gòu)成B1，B2，Bm的子 集。 4. 選擇的串接定律 ( (E) (E) 這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2是選擇條件。 選擇的串接律說明選擇條件可以合并。這樣一次就可檢查全部 條件。 n AAA, 21 m BBB, 21 n AAA, 21 1 F 2 F 2 1 FF 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 5. 選擇與投影操作的交換律 F( (E) (F(E) 選擇條件F只涉及屬性A1，An。 若F中有不屬于A1，An的屬性B1，Bm則有更 一般的規(guī)則： (F(E) (F( (E) n AAA, 21 n AAA, 21 n AAA, 2

23、1 n AAA, 21 mn BBBAAA, 2121 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 6. 選擇與笛卡爾積的交換律 如果F中涉及的屬性都是E1中的屬性，則 (E1E2) (E1)E2 如果F=F1F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性， 則由上面的等價變換規(guī)則1，4，6可推出： (E1E2) (E1) (E2) 若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有 (E1E2) ( (E1)E2) 它使部分選擇在笛卡爾積前先做。 1 F 2 F 2 F 1 F F F F F 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 7. 選擇與并的分配律 設(shè)E=E1E2，E1，E2有

24、相同的屬性名，則 F(E1E2)F(E1)F(E2) 8. 選擇與差運(yùn)算的分配律 若E1與E2有相同的屬性名，則 F(E1-E2)F(E1)-F(E2) 9. 選擇對自然連接的分配律 F(E1 E2)F(E1) F(E2) F只涉及E1與E2的公共屬性 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)） 10. 投影與笛卡爾積的分配律 設(shè)E1和E2是兩個關(guān)系表達(dá)式，A1，An是E1的屬性，B1， Bm是E2的屬性，則 (E1E2) (E1) (E2) 11. 投影與并的分配律 設(shè)E1和E2有相同的屬性名，則 (E1E2) (E1) (E2) mn BBBAAA, 2121 n AAA, 21 m BBB, 21

25、 n AAA, 21 n AAA, 21 n AAA, 21 9.3 代 數(shù) 優(yōu) 化 9.3.1 關(guān)系代數(shù)表達(dá)式等價變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化 9.3.2 查詢樹的啟發(fā)式優(yōu)化 o 典型的啟發(fā)式規(guī)則： 1. 選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最 重要、最基本的一條 2. 把投影運(yùn)算和選擇運(yùn)算同時進(jìn)行 如有若干投影和選擇運(yùn)算，并且它們都對同一個關(guān) 系操作，則可以在掃描此關(guān)系的同時完成所有的這 些運(yùn)算以避免重復(fù)掃描關(guān)系 查詢樹的啟發(fā)式優(yōu)化（續(xù)） 3. 把投影同其前或其后的雙目運(yùn)算結(jié)合起來 4. 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來 成為一個連接運(yùn)算 5. 找出公共子表達(dá)式

26、如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系, 并且從外存中讀入這個關(guān)系比計算該子表達(dá)式的時間少 得多，則先計算一次公共子表達(dá)式并把結(jié)果寫入中間文 件是合算的 當(dāng)查詢的是視圖時，定義視圖的表達(dá)式就是公共子表達(dá) 式的情況 查詢樹的啟發(fā)式優(yōu)化（續(xù)） o遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價變換公式來優(yōu)化關(guān)系表達(dá) 式的算法。 算法：關(guān)系表達(dá)式的優(yōu)化 輸入：一個關(guān)系表達(dá)式的查詢樹 輸出：優(yōu)化的查詢樹 方法： (1) 利用等價變換規(guī)則4把形如F1F2Fn(E)變換為 F1(F2(Fn(E)。 (2) 對每一個選擇，利用等價變換規(guī)則49盡可能把它移到樹的 葉端。 查詢樹的啟發(fā)式優(yōu)化（續(xù)） (3) 對每

27、一個投影利用等價變換規(guī)則3，5，10，11中的一般形式盡可 能把它移向樹的葉端。 n注意： 等價變換規(guī)則3使一些投影消失 規(guī)則5把一個投影分裂為兩個，其中一個有可能被移向 樹的葉端 (4) 利用等價變換規(guī)則35把選擇和投影的串接合并成單個選擇 、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時 執(zhí)行，或在一次掃描中全部完成 查詢樹的啟發(fā)式優(yōu)化（續(xù)） (5) 把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(， 運(yùn)算)。 n如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該 組 n但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成 等值連接的選擇

28、時，則不能把選擇與這個雙目運(yùn)算組成 同一組，把這些單目運(yùn)算單獨(dú)分為一組 查詢樹的啟發(fā)式優(yōu)化（續(xù)） 例4 下面給出例3中 SQL語句的代數(shù)優(yōu)化示例。 (1) 把SQL語句轉(zhuǎn)換成查詢樹，如下圖所示 查詢樹 查詢樹的啟發(fā)式優(yōu)化（續(xù)） 為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān) 系代數(shù)語法樹，則上面的查詢樹如下圖所示。 關(guān)系代數(shù)語法樹 查詢樹的啟發(fā)式優(yōu)化（續(xù)） (2) 對查詢樹進(jìn)行優(yōu)化 利用規(guī)則4、6把選擇SC.Cno=2移到葉端，查詢樹便轉(zhuǎn)換成下圖 所示的優(yōu)化的查詢樹。這就是9.2.2節(jié)中Q3的查詢樹表示 優(yōu)化后的查詢樹 第九章 關(guān)系查詢處理及其查詢優(yōu)化 9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.

29、2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小結(jié) 9.4 物理優(yōu)化 o 代數(shù)優(yōu)化改變查詢語句中操作的次序和組合 ，不涉及底層的存取路徑 o 對于一個查詢語句有許多存取方案，它們的 執(zhí)行效率不同， 僅僅進(jìn)行代數(shù)優(yōu)化是不夠 的 o 物理優(yōu)化就是要選擇高效合理的操作算法或 存取路徑，求得優(yōu)化的查詢計劃 物理優(yōu)化（續(xù)） o 選擇的方法： n 基于規(guī)則的啟發(fā)式優(yōu)化 n 基于代價估算的優(yōu)化 n 兩者結(jié)合的優(yōu)化方法 9.4 物理優(yōu)化 9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 9.4.2 基于代價的優(yōu)化 9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 一、 選擇操作的啟發(fā)式規(guī)則

30、 二、 連接操作的啟發(fā)式規(guī)則 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 一、 選擇操作的啟發(fā)式規(guī)則: 1. 對于小關(guān)系，使用全表順序掃描，即使選擇 列上有索引 對于大關(guān)系，啟發(fā)式規(guī)則有： 2. 對于選擇條件是主碼值的查詢 查詢結(jié)果最多是一個元組，可以選擇主碼索引 一般的RDBMS會自動建立主碼索引。 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 3. 對于選擇條件是非主屬性值的查詢， 并且選擇列上有索引 n要估算查詢結(jié)果的元組數(shù)目 如果比例較小(10%)可以使用索引掃描方法 否則還是使用全表順序掃描 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 4. 對于選擇條件是屬性上的非等值查詢或 者范圍查詢，并且選擇

31、列上有索引 n要估算查詢結(jié)果的元組數(shù)目 如果比例較小(10%)可以使用索引掃描方法 否則還是使用全表順序掃描 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 5. 對于用AND連接的合取選擇條件 n如果有涉及這些屬性的組合索引 優(yōu)先采用組合索引掃描方法 n如果某些屬性上有一般的索引 則可以用例1-C4中介紹的索引掃描方法 否則使用全表順序掃描。 6. 對于用OR連接的析取選擇條件，一般使用全表順序 掃描 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 二、 連接操作的啟發(fā)式規(guī)則： 1. 如果2個表都已經(jīng)按照連接屬性排序 n 選用排序-合并方法 2. 如果一個表在連接屬性上有索引 n 選用索引連接方法 3. 如

32、果上面2個規(guī)則都不適用，其中一個表較小 n 選用Hash join方法 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 4. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地 講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。 n理由： 設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs 連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K 分配K-1塊給外表 如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+( Br/K-1)Bs 顯然應(yīng)該選塊數(shù)小的表作為外表 9.4 物理優(yōu)化（續(xù)） 9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 9.4.2 基于代價的優(yōu)化 9.4.2 基于代價的優(yōu)化 o 啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行

33、的系 統(tǒng) n解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中 o 編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的 n可以采用精細(xì)復(fù)雜一些的基于代價的優(yōu)化方法 基于代價的優(yōu)化（續(xù)） 一、 統(tǒng)計信息 二、 代價估算示例 基于代價的優(yōu)化（續(xù)） 一、 統(tǒng)計信息 o 基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價， 與數(shù)據(jù)庫的狀態(tài)密切相關(guān) o 數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息： 1. 對每個基本表 n該表的元組總數(shù)(N) n元組長度(l) n占用的塊數(shù)(B) n占用的溢出塊數(shù)(BO) 基于代價的優(yōu)化（續(xù)） 2. 對基表的每個列 n該列不同值的個數(shù)(m) n選擇率(f) 如果不同值的分布是均勻的，f1/m 如果不同值的分布不均勻，則每個值的選擇率具有該 值的元組數(shù)/N n該列最大值 n該列最小值 n該列上是否已經(jīng)建立了索引 n索引類型(B+樹索引、Hash索引、聚集索引) 基于代價的優(yōu)化（續(xù)） 3. 對索引(如B+樹索引) n索引的層數(shù)(L) n不同索引值的個數(shù) n索引的選