第九章關(guān)系查詢處理和查詢優(yōu)化.ppt.ConvertorVIP

1、數(shù)據(jù)庫原理咸陽師范學(xué)院信息工程學(xué)院第九章 關(guān)系查詢處理和查詢優(yōu)化本章主要教學(xué)內(nèi)容: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)化重點及難點：了解查詢處理步驟；了解查詢處理的四個階段；掌握優(yōu)化的方法；關(guān)系查詢處理和查詢優(yōu)化查詢優(yōu)化一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關(guān)系代數(shù)表達式的優(yōu)化。物理優(yōu)化是指存取路徑和底層操作算法的選擇。9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟9.1.2 實現(xiàn)查詢操作的算法示例9.1.1 查詢處理步驟查詢處理的任務(wù)是把用戶提交給RDBMS的查詢語句轉(zhuǎn)換為高效的執(zhí)行計劃。RDBMS查詢處理可以分為4個階段：查詢

2、分析、查詢檢查、查詢優(yōu)化和查詢執(zhí)行。查詢分析對查詢語句進行掃描、詞法分析和語法分析。從查詢語句中識別出語言符號，如SQL關(guān)鍵字、屬性名和關(guān)系名等，進行語法檢查和語法分析，即判斷查詢語句是否符合SQL語法規(guī)則。查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進行語義檢查，即檢查語句中的數(shù)據(jù)庫對象，如屬性名、關(guān)系名、是否存在和是否有效。根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進行檢查。檢查通過后便把SQL查詢語句轉(zhuǎn)換成等價的關(guān)系代數(shù)表達式。查詢檢查RDBMS一般都用查詢樹(query tree)，也稱為語法分析法(syntax tree)，來表示擴展的關(guān)系代數(shù)表達式。這個過程中要把數(shù)據(jù)庫對象的

3、外部名稱轉(zhuǎn)換為內(nèi)部表示。查詢優(yōu)化每個查詢都會有許多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化就是選擇一個高效執(zhí)行的查詢處理策略。查詢優(yōu)化有多種方法，按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。查詢優(yōu)化選擇的規(guī)則：基于規(guī)則的基于代價的基于語義的查詢執(zhí)行依據(jù)優(yōu)化器得到執(zhí)行策略生成查詢計劃，由代碼生成器(code generator)生成執(zhí)行這個查詢計劃的代碼。9.1.2 實現(xiàn)查詢操作的算法示例選擇操作連接操作選擇操作的實現(xiàn)例1 Select * from student where <條件表達式>考慮<條件表達式>的幾種情況：C1：無條件C2：Sno=C3: Sage>2

4、0C4: Sdept=CS AND Sage>201.簡單的全表掃描方法2.索引（或散列）掃描方法連接操作的實現(xiàn)連接操作是查詢處理中最耗時的操作之一。例2 Select * from Student ，SC where Student.Sno=SC.Sno;1.嵌套循環(huán)方法2.排序-合并方法3.索引連接方法4.Hash Join方法9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1 查詢優(yōu)化概述9.2.2 一個實例9.2.1 查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。 查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高，使DBMS可以從關(guān)系表達式中分析查詢語義。 由DBMS進

5、行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息 由DBMS進行查詢優(yōu)化的好處(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo) 選擇有效策略，求得給定關(guān)系表達式的值實際系統(tǒng)的查詢優(yōu)化步驟1. 將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常

6、是語法樹2. 根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn) （優(yōu)化）形式實際系統(tǒng)的查詢優(yōu)化步驟3. 選擇低層的操作算法對于語法樹中的每一個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4. 生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內(nèi)部操作組成的。代價模型集中式數(shù)據(jù)庫單用戶系統(tǒng)總代價 = I/O代價 + CPU代價多用戶系統(tǒng)總代價 = I/O代價 + CPU代價 + 內(nèi)存代價分布式數(shù)據(jù)庫 總代價 = I/O代價 + CPU代價+ 內(nèi)存代價 + 通信代價 4.2.2 查詢優(yōu)化的必要性 例：求選修了課程2的學(xué)生姓名 SELECT Student.SnameFROM Student,

7、SCWHERE Student.Sno=SC.SnoAND SC.Cno='2' 查詢優(yōu)化的必要性假設(shè)1：外存：Student:1000條,SC:10000條, 選修2號課程:50條假設(shè)2：一個內(nèi)存塊裝元組:10個Student, 或100個SC, 內(nèi)存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結(jié)果元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法執(zhí)行策略11=name(Student.Sno=SC.Sno SC.Cno='2' (Student×SC)  Student×SC 讀取總

8、塊數(shù)= 讀Student表塊數(shù) + 讀SC表遍數(shù) *每遍塊數(shù) =1000/10+(1000/(10×5) ×(10000/100) =100+20×100=2100 讀數(shù)據(jù)時間=2100/20=105秒不同的執(zhí)行策略,考慮I/O時間中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組)寫中間結(jié)果時間 = 10000000/10/20 = 50000秒 讀數(shù)據(jù)時間 = 50000秒 總時間 =1055000050000秒 = 100105秒 = 27.8小時查詢優(yōu)化的必要性2. 2 name(SC.Cno=' 2&

9、#39; (Student SC) 讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時間=2100/20=105秒中間結(jié)果大小=10000 （減少1000倍）寫中間結(jié)果時間=10000/10/20=50秒 讀數(shù)據(jù)時間=50秒  總時間1055050秒205秒=3.4分查詢優(yōu)化的必要性3. 2 Sname(Student SC.Cno=' 2' (SC) 讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀 Student表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時

10、間=100/20=5秒   總時間55秒10秒 查詢優(yōu)化的必要性4. 2 name(Student SC.Cno='2' (SC)假設(shè)SC表在Cno上有索引，Student表在Sno上有索引  讀SC表索引=讀SC表總塊數(shù)= 50/100<1塊讀數(shù)據(jù)時間 中間結(jié)果大小=50條 不必寫入外存查詢優(yōu)化的必要性 讀Student表索引=讀Student表總塊數(shù)= 50/10=5塊讀數(shù)據(jù)時間 總時間<10秒9.3代數(shù)優(yōu)化9.3.1 關(guān)系代數(shù)表達式等價變換規(guī)則9.3.2 查詢樹的啟發(fā)式優(yōu)化9.3.1 關(guān)系代數(shù)表達式等價變換規(guī)則關(guān)系代數(shù)表

11、達式等價指用相同的關(guān)系代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達式的變換常用的等價變換規(guī)則設(shè)E1、E2等是關(guān)系代數(shù)表達式，F(xiàn)是條件表達式 l. 連接、笛卡爾積交換律E1× E2 E2×E1E1 E2E2 E1 E1 F E2E2 F E1關(guān)系代數(shù)等價變換規(guī)則2. 連接、笛卡爾積的結(jié)合律 (E1×E2) × E3 E1 × (E2×E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F關(guān)系代數(shù)等價變換規(guī)則3. 投影的串接定律 A1,A2, L

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

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

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

15、與并的交換假設(shè)：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2) 9.3.2 查詢樹的啟發(fā)式優(yōu)化選擇運算應(yīng)盡可能先做  目的：減小中間關(guān)系在執(zhí)行連接操作前對關(guān)系適當(dāng)進行預(yù)處理按連接屬性排序在連接屬性上建立索引 投影運算和選擇運算同時做目的：避免重復(fù)掃描關(guān)系將投影運算與其前面或后面的雙目運算結(jié)合目的：減少掃描關(guān)系的遍數(shù)9.3.2 查詢樹的啟發(fā)式優(yōu)化某些選擇運算在其前面執(zhí)行的笛卡爾積 => 連接運算 例：Student.Sno=SC.Sno (Student×SC)  

16、Student SC提取公共子表達式關(guān)系代數(shù)表達式的優(yōu)化算法 算法：關(guān)系表達式的優(yōu)化輸入：一個關(guān)系表達式的語法樹。輸出：計算該表達式的程序。方法：（1）分解選擇運算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) 關(guān)系代數(shù)表達式的優(yōu)化算法（2）通過交換選擇運算，將其盡可能移到葉端 對每一個選擇，利用規(guī)則48盡可能把它移到樹的葉端。 （3）通過交換投影運算，將其盡可能移到葉端對每一個投影利用規(guī)則3，9，l0，5中的一般形式盡可能把它移向樹的葉端。 關(guān)系代數(shù)表達式的優(yōu)化算法（4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成利用規(guī)則35把選擇和投

17、影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。 關(guān)系代數(shù)表達式的優(yōu)化算法（5）對內(nèi)結(jié)點分組把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×， ，-)和它所有的直接祖先為一組(這些直接祖先是，運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當(dāng)雙目運算是笛卡爾積(×)，而且其后的選擇不能與它結(jié)合為等值連接時除外。把這些單目運算單獨分為一組。 關(guān)系代數(shù)表達式的優(yōu)化算法（6）生成程序生成一個程序，每組結(jié)點的計算是程序中的一步。各步的順序是任意的，

18、只要保證任何一組的計算不會在它的后代組之前計算。 優(yōu)化的一般步驟 1把查詢轉(zhuǎn)換成某種內(nèi)部表示2代數(shù)優(yōu)化：把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化） 形式3物理優(yōu)化：選擇低層的存取路徑4生成查詢計劃，選擇代價最小的 優(yōu)化的一般步驟（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示例4：求選修了課程2的學(xué)生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno='2' （1）把查詢轉(zhuǎn)換成某種內(nèi)部表示語法樹 結(jié)果project(Sname) select(SC.Cno=¢2¢) join(Student.Sno=SC.Sno) StudentSC關(guān)系代數(shù)語法樹（2）代數(shù)優(yōu)化利用優(yōu)化算法把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式9.4 物理優(yōu)化9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2 基于代價的優(yōu)化9