第04章關系查詢處理和查詢優(yōu)化

1、第四章 關系查詢處理和查詢優(yōu)化4.1 關系數(shù)據(jù)庫系統(tǒng)的查詢處理4.2 關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.3 代數(shù)優(yōu)化4.4 物理優(yōu)化4.5 小結4.1 關系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行詞法分析語法分析語義轉換符號名轉換安全性檢查完整性檢查查詢樹代數(shù)優(yōu)化物理優(yōu)化等執(zhí)行策略描述代碼生成執(zhí)行查詢計劃的代碼數(shù)據(jù)庫數(shù)據(jù)字典查詢語句查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行圖4.1 查詢處理步驟4.1.1 查詢處理的步驟4.1.2 實現(xiàn)查詢操作的算法示例一、選擇操作的實現(xiàn) 例1 SELECT * FROM student WHERE C1：無條件；C2：Sno=200215121;C3:Sage2

2、0;C4:Sdept=CS AND Sage20方法:1.簡單的全表掃描2.索引或散列掃描二、連接操作的實現(xiàn)例2 SELECT * FROM student，SC WHERE student.Sno=SC.Sno方法：1.嵌套循環(huán)方法2.排序合并方法3.索引連接方法4.Hash Join方法嵌套循環(huán)法(NESTED-LOOP)兩重循環(huán)，外循環(huán)掃描表1，內循環(huán)掃描表2排序合并法(SORT-MERGE) 常用于=連接。首先按連接屬性對表1和表2排序，先掃描表1，當遇到表2中第一條大于表1連接字段值的元組時，對表2的查詢不再繼續(xù)。表1的第二條元組，從剛才的中斷處繼續(xù)掃描表2。索引連接(INDEX-J

3、OIN)對表2按連接字段建立索引對表1中的每個元組，依次根據(jù)其連接字段值查詢表2的索引，從中找到滿足條件的元組9500195002950039500495001 1 9295001 2 8595001 3 8895002 2 9095003 3 804.2 關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化4.2.1 查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。查詢優(yōu)化的可能性關系數(shù)據(jù)語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。 由DBMS進行查詢優(yōu)化的好處用戶不必考慮如何最好地表達查詢以獲得較好的效率，系統(tǒng)可以比用戶程序的優(yōu)化做得更好。優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程

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

5、個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4. 生成查詢計劃(查詢執(zhí)行方案)查詢計劃是由一系列內部操作組成的。基于代價模型的優(yōu)化算法集中式數(shù)據(jù)庫總代價 = I/O代價 + CPU代價 + 內存代價分布式數(shù)據(jù)庫 總代價 = I/O代價 + CPU代價+ 內存代價 + 通信代價 代價模型4.2.2 一個實例 例3 求選修了課程2的學生姓名SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND o=2; 執(zhí)行策略1 name(Student.Sno=SC.Sno o=2 (StudentSC)2 name( o=

6、 2 (Student SC) 3 name(Student o=2 (SC)查詢優(yōu)化的必要性（四個假設） Student:1000條,SC:10000條, 選修2號課程:50條一個內存塊裝元組:10個Student, 或100個SC。內存中一次可以存放: 5塊Student元組, 1塊SC元組和若干塊連接結果元組讀寫速度：20塊/秒連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法執(zhí)行策略11name(Student.Sno=SC.Sno o=2(StudentSC)StudentSC讀取總塊數(shù)= 讀Student表塊數(shù) + 讀SC表遍數(shù)*每遍塊數(shù) =1000/10+(1000/(105) (10000/10

7、0) =100+20100=2100塊讀數(shù)據(jù)時間=2100/20=105秒中間結果大小 = 1000*10000 = 107 (1千萬條元組,每塊10個元組) 寫中間結果時間 = 10000000/10/20 = 50000秒 讀中間結果時間 = 50000秒，50個符合條件（主存） 主存中處理時間忽略總時間 =1055000050000秒 = 100105秒 = 27.8小時執(zhí)行策略22. 2 name( o= 2 (Student SC)讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時間=2100/20=105秒中間結果大小=10000 （減少1000倍）寫中間結果時間=10000/10/20=50秒讀中

8、間結果時間=50秒總時間1055050秒205秒=3.4分執(zhí)行策略33. 2 Sname(Student o= 2 (SC)讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時間=100/20=5秒中間結果大小=50條 不必寫入外存讀Student表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時間=100/20=5秒 總時間55秒10秒 執(zhí)行策略44. 2 name(Student o=2 (SC)假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些元組(50個)存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊若Student表在Sno上也有索引第二步也不必讀

9、取所有的Student元組涉及最多50個Student記錄讀取Student表的塊數(shù)也可大大減少 總的存取時間將進一步減少到數(shù)秒代數(shù)優(yōu)化：Q1=Sname(Student.Sno=SC.Sno o=2 (StudentSC)Q2=Sname( o=2 (Student SC)Q3=Sname(Student o=2(SC)物理優(yōu)化在Q3中，SC表的選擇操作算法有全表掃描和索引掃描2種方法，經過初步估算，索引掃描方法較優(yōu)代數(shù)優(yōu)化與物理優(yōu)化4.3 代數(shù)優(yōu)化基于關系代數(shù)等價變換規(guī)則的優(yōu)化方法為代數(shù)優(yōu)化；代數(shù)優(yōu)化策略是通過對關系代數(shù)表達式的等價變換來提高查詢效率；關系代數(shù)表達式的等價是指用相同的關系代

10、替兩個表達式中相應的關系所得到的結果是相同的；兩個表達式E1和E2是等價的,記為E1 E2。4.3.1 關系代數(shù)表達式等價變換規(guī)則設E1、E2等是關系代數(shù)表達式，F(xiàn)是條件表達式l. 連接、笛卡爾積交換律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 常用的等價變換規(guī)則2. 連接、笛卡爾積的結合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假設：1) E是關系代數(shù)表達式2)

11、 Ai(i=1，2，n), Bj(j=l，2，m)是屬性名3) A1, A2, , An構成Bl，B2，Bm的子集 4. 選擇的串接定律 F1 （ F2（E） F1 F2(E)選擇的串接律說明 選擇條件可以合并這樣一次就可檢查全部條件。 5. 選擇與投影的交換律 (1)假設: 選擇條件F只涉及屬性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假設: F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E)6. 選擇與笛卡爾積的交換律(1) 假設：F中涉及的

12、屬性都是E1中的屬性 F (E1E2)F (E1)E2(2) 假設：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 則由上面的等價變換規(guī)則1，4，6可推出： F(E1E2) F1(E1)F2 (E2)(3) 假設： F=F1F2，并且 F1只涉及E1中的屬性， F2涉及E1和E2兩者的屬性 F(E1E2) F2(F1(E1)E2) 它使部分選擇在笛卡爾積前先做 7. 選擇與并的分配律假設：E=E1E2，E1，E2有相同的屬性名F(E1E2) F(E1) F(E2)8. 選擇與差運算的分配律假設：E1與E2有相同的屬性名F(E1-E2) F(E1) - F(E2) 9. 選擇

13、對自然連接的分配律F(E1 E2) F(E1) F(E2) F只涉及E1與E2的公共屬性10. 投影與笛卡爾積的分配假設：E1和E2是兩個關系表達式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2)l1. 投影與并的分配假設：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2)A1,A2, ,An(E1)A1,A2, ,An(E2) 4.3.2 查詢樹的啟發(fā)式優(yōu)化 啟發(fā)式規(guī)則的代數(shù)優(yōu)化,是對關系代數(shù)表達式的查詢樹進行優(yōu)化,其典型的規(guī)則有:選擇運算應盡可能先做 目的：減

14、小中間關系投影運算和選擇運算同時做目的：避免重復掃描關系把投影運算與其前面或后面的雙目運算結合目的：減少掃描關系的遍數(shù)某些選擇運算在其前面執(zhí)行的笛卡爾積= 連接運算 例：Student.Sno=SC.Sno (StudentSC) Student SC提取公共子表達式關系代數(shù)表達式的優(yōu)化算法 算法：關系表達式的優(yōu)化。輸入：一個關系表達式的查詢樹。輸出：優(yōu)化的查詢樹。方法：(1) 分解選擇運算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) (2) 通過交換選擇運算，將其盡可能移到葉端 對每一個選擇，利用規(guī)則48盡可能把它移到樹的葉端。(3) 通過交換投影運算，

15、將其盡可能移到葉端對每一個投影利用規(guī)則3、5、l0、11中的一般形式盡可能把它移向樹的葉端。(4) 利用規(guī)則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成，盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。(5) 對內結點分組把上述得到的語法樹的內節(jié)點分組。每一雙目運算(， ，-)和它所有的直接祖先為一組(這些直接祖先是，運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組，但當雙目運算是笛卡爾積()，而且其后的選擇不能與它結合為等值連接時除外。把這些單目運算單獨分為一組。 例4 求選修了課程2的學生

16、姓名SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND o=2; Sname Student.Sno=SC.Sno o=2 StudentSC（2）關系代數(shù)語法樹Sname Student.Sno=SC.Sno o=2 StudentSC（3）優(yōu)化后的查詢樹結果project(Sname) select( o=2) join(Student.Sno=SC.Sno) StudentSC（1）把SQL語句轉換成查詢樹4.4 物理優(yōu)化代數(shù)優(yōu)化是改變查詢語句的次序和組合，不涉及底層的存取路徑，物理優(yōu)化就是要選擇高效合理的

17、操作算法或存取路徑，求的優(yōu)化的查詢計劃，達到查詢優(yōu)化的目標。具體方法有：基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結合的優(yōu)化方法4.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則對于小關系使用全表順序掃描，對大關系來說分情況處理：選擇條件是主碼值的查詢，查詢結果最多是一個元組，可以選擇主碼索引。選擇條件是非主屬性值的查詢，并且選擇列上有索引，要估算查詢結果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引，要估算查詢結果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序

18、掃描 用AND連接的合取選擇條件如果有涉及這些屬性的組合索引，優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引，則可以用例1-C4中介紹的索引掃描方法否則使用全表順序掃描。用OR連接的析取選擇條件，一般使用全表順序掃描4.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化二、連接操作的啟發(fā)式規(guī)則如果2個表都已經按照連接屬性排序 選用排序-合并方法 如果一個表在連接屬性上有索引 選用索引連接方法 如果上面2個規(guī)則都不適用，其中一個表較小 選用Hash join方法可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)較少的表，作為外表(外循環(huán)的表) 。一、統(tǒng)計信息基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價，與數(shù)據(jù)庫的狀態(tài)密切相關 。數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息：