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

1、第九章 關(guān)系查詢處理及其查詢優(yōu)化章節(jié)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)化課型新授課課時(shí)2節(jié)課班級(jí)2002級(jí)1、2班教學(xué)目標(biāo)重點(diǎn)掌握關(guān)系系統(tǒng)的查詢優(yōu)化。教學(xué)重點(diǎn)難點(diǎn)1. 重點(diǎn)掌握關(guān)系系統(tǒng)的查詢優(yōu)化。2. 畫出查詢的語法樹和優(yōu)化后的語法樹。3. 優(yōu)化算法，包括代數(shù)優(yōu)化算法和物理優(yōu)化算法。教學(xué)關(guān)鍵理解查詢處理的過程了解查詢優(yōu)化的方法教學(xué)方法講解和課件演示教具計(jì)算機(jī)大屏幕投影復(fù)習(xí)內(nèi)容引入內(nèi)容講解內(nèi)容9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟1查詢分析2查詢檢查3查詢優(yōu)化4查詢執(zhí)行9.1.2 實(shí)現(xiàn)查詢操作的算法示例一、選擇操作的實(shí)

2、現(xiàn)1簡單的全表掃描方法2索引（或散列）掃描方法二、連接操作的實(shí)現(xiàn)1循環(huán)嵌套方法2排序-合并方法3索引連接方法4Hash 連接方法9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1 查詢優(yōu)化概述n 系統(tǒng)選擇不同的策略對(duì)查詢時(shí)間影響很大。n 因此有必要對(duì)查詢優(yōu)化n 查詢優(yōu)化：為查詢選擇最有效的查詢計(jì)劃。n 查詢優(yōu)化極大地影響RDBMS的性能。n 查詢優(yōu)化的可能性n 關(guān)系數(shù)據(jù)語言的級(jí)別很高，使DBMS 可以從關(guān)系表達(dá)式 中分析查詢語義。 1.由DBMS進(jìn)行查詢優(yōu)化的好處n 用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率n 系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶

3、程序則難以獲得這些信息 (2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)2.查詢優(yōu)化目標(biāo)n 查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達(dá)式的值3.實(shí)際系統(tǒng)的查詢優(yōu)化步驟(1) 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹(2)根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式(3)選擇低層的操作算法n 對(duì)于語法樹中的每一個(gè)操作n 計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)n 選擇代價(jià)小

4、的執(zhí)行算法(4)生成查詢計(jì)劃(查詢執(zhí)行方案)n 查詢計(jì)劃是由一系列內(nèi)部操作組成的。9.代價(jià)模型n 一般DBMS采用基于代價(jià)的優(yōu)化算法：n 集中式數(shù)據(jù)庫n 單用戶系統(tǒng)總代價(jià) = I/O代價(jià) + CPU代價(jià)n 多用戶系統(tǒng)總代價(jià) = I/O代價(jià) + CPU代價(jià) + 內(nèi)存代價(jià)n 分布式數(shù)據(jù)庫 總代價(jià) = I/O代價(jià) + CPU代價(jià)+ 內(nèi)存代價(jià) + 通信代價(jià) 9.2.2 一個(gè)實(shí)例 例：求選修了2號(hào)課程的學(xué)生姓名 SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno='2' 1 name(S

5、tudent.Sno=SC.Sno SC.Cno='2' (Student×SC) 2 name(SC.Cno=' 2' (Student SC)3 Sname(Student SC.Cno= 2 (SC) 三種不同的執(zhí)行策略，查詢時(shí)間差別很大。假設(shè)1：外存：Student:1000條,SC:10000條, 選修2號(hào)課程:50條假設(shè)2：一個(gè)內(nèi)存塊裝元組:10個(gè)Student, 或100個(gè)SC, 內(nèi)存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法

6、。 執(zhí)行策略1Q1 name (Student.Sno=SC.SnoSC.Cno='2' (Student×SC)  計(jì)算笛卡爾積Student×SC 讀取總塊數(shù)= 讀Student表塊數(shù) + 讀SC表遍數(shù)*每遍塊數(shù) =1000/10+(1000/(10×5) ×(10000/100) =100+20×100=2100 讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組)寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒 做選擇運(yùn)算

7、讀數(shù)據(jù)時(shí)間 = 50000秒 做投影運(yùn)算 總時(shí)間 =1055000050000秒 = 100105秒= 27.8小時(shí)執(zhí)行策略22. 2 name(SC.Cno=' 2' (Student SC)計(jì)算自然連接讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大小=10000 （減少1000倍）寫中間結(jié)果時(shí)間=10000/10/20=50秒 執(zhí)行選擇運(yùn)算讀數(shù)據(jù)時(shí)間=50秒 執(zhí)行投影  總時(shí)間1055050秒205秒=3.4分 執(zhí)行策略33. 2 Sname(StudentSC.Cno=' 2' (S

8、C) 讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存  連接運(yùn)算讀Student表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒  投影  總時(shí)間55秒10秒 執(zhí)行策略49. 2 name(Student SC.Cno='2' (SC)假設(shè)SC表在Cno上有索引，Student表在Sno上有索引  讀SC表索引Cno=2的元組。讀SC表總塊數(shù)= 50/100<1塊讀數(shù)據(jù)時(shí)間更小。中間結(jié)果大小=50條 不必寫入外存 讀Student

9、表索引讀Student表總塊數(shù)= 50/10=5塊讀數(shù)據(jù)時(shí)間大大減少。 總時(shí)間<10秒9.3 代數(shù)優(yōu)化9.3.1 關(guān)系代數(shù)等價(jià)變換規(guī)則 n 關(guān)系代數(shù)表達(dá)式等價(jià)n 指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的n 兩個(gè)關(guān)系表達(dá)式E1 和E2 是等價(jià)的，記為： E1E2 常用的等價(jià)變化規(guī)則有：1. 連接、笛卡爾積交換律E1× E2 E2×E1E1 E2E2 E1 E1 F E2E2 F E1 F為連接條件。2. 連接、笛卡爾積的結(jié)合律 (E1×E2) × E3 E1 × (E2×E3) (E1 E2) E3 E1 (E

10、2 E3) (E1 E2) E3 E1 (E2 E3) F F F F3. 投影的串接定律 A1,A2, L,An( B1,B2, L,Bm(E) A1,A2, L,An (E)假設(shè)：1)E是關(guān)系代數(shù)表達(dá)式2)Ai(i=1，2，n), Bj(j=l，2，m)是屬性名3)A1, A2, , An構(gòu)成Bl，B2，Bm的子集 9. 選擇的串接定律 F1 （ F2（E） F1 F2(E)n 選擇的串接律說明 選擇條件可以合并 n 這樣一次就可檢查全部條件。 5. 選擇與投影的交換律(1)假設(shè): 選擇條件F只涉及屬性A1，An F (A1,A2, L,An(E) A1,A2, L,An(F(E)(2)假

11、設(shè): F中有不屬于A1, ,An的屬性B1,Bm A1,A2, L,An ( F (E) A1,A2, L,An(F (A1,A2, L,An,B1,B2, L,Bm(E)6. 選擇與笛卡爾積的交換律(1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1×E2)F (E1)×E2 (2) 假設(shè)：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出： F(E1×E2) F1(E1)×F2 (E2) (3) 假設(shè)： F=F1F2， F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬

12、性 F(E1×E2) F2(F1(E1)×E2) 它使部分選擇在笛卡爾積前先做 7. 選擇與并的交換假設(shè)：E=E1E2，E1，E2有相同的屬性名F(E1E2) F(E1) F(E2)8. 選擇與差運(yùn)算的交換假設(shè)：E1與E2有相同的屬性名F(E1-E2) F(E1) - F(E2) 9. 投影與笛卡爾積的交換假設(shè)：E1和E2是兩個(gè)關(guān)系表達(dá)式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1×E2) A1,A2, ,An（E1)× B1,B2, ,Bm(E2)l0. 投影與并的交換假設(shè)：E1和E2 有相同

13、的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2)9.3.2 查詢數(shù)的啟發(fā)式優(yōu)化典型的啟發(fā)式規(guī)則有：1. 選擇運(yùn)算應(yīng)盡可能先做  n 目的：減小中間關(guān)系2. 在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理n (1)在連接屬性上建立索引 n (2)按連接屬性排序n Student SCn 索引連接方法的步驟：(1)在SC上建Sno索引；(2)對(duì)Student中的每一元組，由Sno的值通過SC的索引查找SC的元組； (3)把這些SC的元組與Student的元組連接起來。對(duì)Student和SC表只掃描一遍。n 用排序合并方法的步驟：(1)

14、先對(duì)Student表和SC表在Sno上排序；(2)取Student中的第1個(gè)Sno，依次掃描SC表中具有相同Sno的元組；把它們連接起來。(3)當(dāng)掃描到Sno不相同的第1個(gè)SC的元組時(shí)，返回Student表掃描它的下一個(gè)元組，再掃描SC表中具有相同Sno的元組，把它們連接起來。直到Student表掃描完。這樣，Student表和SC表也只掃描一遍。2.把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。 可以避免重復(fù)掃描關(guān)系。3. 把投影同其前或其后的雙目運(yùn)算結(jié)合起來，沒有必為去掉某些字段而掃描一遍關(guān)系。4. 把某些選擇同它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算。 例：Student.Sno=SC.Sno (

15、Student×SC) Student SCn 連接特別是等值連接比笛卡爾積節(jié)省時(shí)間。5. 找出公共子表達(dá)式 重復(fù)出現(xiàn)的表達(dá)式，結(jié)果寫到中間文件。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的語法樹。輸出：計(jì)算該表達(dá)式的程序。方法：（1）分解選擇運(yùn)算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) （2）通過交換選擇運(yùn)算，將其盡可能移到葉端 對(duì)每一個(gè)選擇，利用規(guī)則48盡可能把它移到樹的葉端。（3）通過交換投影運(yùn)算，將其盡可能移到葉端對(duì)每一個(gè)投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。 （4）合并串接的選擇和

16、投影，以便能同時(shí)執(zhí)行或在一次掃描中完成n 利用規(guī)則3 5 把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。 n 使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成 n 盡管這種變換似乎違背“ 投影盡可能早做” 的原則，但這樣做效率更高。 （5）對(duì)內(nèi)結(jié)點(diǎn)分組n 把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。 n 每一雙目運(yùn)算( × ， ， ，-) 和它所有的直接祖先為一組( 這些直接祖先是， 運(yùn)算) 。 n 如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積( ×) ，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。 （6）生成程序n 生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。 n 各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。 9.4 物理優(yōu)化（3）物理優(yōu)化：選擇低層的存取路徑- 優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫狀態(tài)信息 選擇字段上是否有索引 連接的兩個(gè)表是否有序 連接字段上是否有索引 然后根據(jù)一定的優(yōu)