重郵版第七章

第七章關(guān)系查詢優(yōu)化

本章要點

關(guān)系查詢優(yōu)化的基本概念關(guān)系查詢優(yōu)化的一般準則7.1查詢優(yōu)化的基本概念同一個關(guān)系查詢可以有多種等價表達形式，但由于計算、磁盤訪問、中間結(jié)果存儲、通信傳輸?shù)拳h(huán)節(jié)都會產(chǎn)生不同的CPU、內(nèi)存、磁盤I/O等代價，不同表達形式的查詢效率可能存在明顯差異。例：求5號客戶購買的服裝品牌，系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達式來完成這一查詢：假定數(shù)據(jù)庫中有l(wèi)000件服裝，l0000個購買記錄，其中5號客戶的購買記錄為50個。同時，假設讀取表的策略為：一個塊能裝10條服裝記錄或100條購買記錄，在內(nèi)存中存放5塊服裝記錄和1塊購買記錄，每秒讀寫20塊。Q1的時間代價1.計算笛卡爾積讀取所有數(shù)據(jù)庫記錄到內(nèi)存所需時間=需讀取總塊數(shù)/20。其中，需讀取總塊數(shù)為1000/10+1000/(10*5)*10000/100=2100，則讀取數(shù)據(jù)的時間是105秒。設每塊能裝10條笛卡爾積所得到的記錄，則將積結(jié)果從內(nèi)存寫到中間文件的時間是1000*10000/10/20=50000秒。2.選擇操作需要將笛卡爾積的結(jié)果從中間文件讀入內(nèi)存，其時間為1000*10000/10/20=50000秒。3.投影運算由于選擇操作后得到的結(jié)果僅50條記錄，最后在此基礎上作投影運算，其時間可以忽略。另外，忽略內(nèi)存代價，執(zhí)行Q1的總時間約為100105秒。Q2的時間代價1.計算自然連接讀取數(shù)據(jù)的時間和Q1相同是105秒。將自然連接的計算結(jié)果寫到中間文件的時間為10000/10/20＝50秒。2.選擇操作需要將連接后的結(jié)果從中間文件讀入內(nèi)存，所需要的時間和寫入的時間相同是50秒。3.投影運算對上一步所得的結(jié)果進行投影運算，其時間可忽略。同樣忽略內(nèi)存代價，執(zhí)行Q2的總時間約為205秒。Q3的時間代價1.選擇運算現(xiàn)對購買記錄表作選擇運算，只需讀一遍服裝記錄表，其讀取時間為10000/100/20=5秒。因為滿足條件的記錄僅50條，不必使用中間文件。2.自然連接讀取服裝記錄表，把讀入的服裝記錄和內(nèi)存中的購買記錄作連接，也只需讀一遍服裝記錄表，其讀取時間為1000/10/20=5秒。3.投影運算對第二步得到的結(jié)果進行投影運算，其時間可忽略。同時忽略內(nèi)存代價，執(zhí)行Q3的總時間約為10秒。關(guān)系查詢優(yōu)化的目的關(guān)系查詢優(yōu)化的目標是根據(jù)用戶輸入的查詢語句，選擇有效的查詢計劃并求得給定關(guān)系表達式的值。關(guān)系查詢優(yōu)化對提高RDBMS的查詢效率是非常必要的，是影響RDBMS性能的關(guān)鍵因素。查詢優(yōu)化是由RDBMS中自動完成的，用戶不必考慮如何最好地表達查詢才能獲得較好的效率。查詢處理過程7.2關(guān)系代數(shù)表達式的變換關(guān)系代數(shù)表達式的優(yōu)化是關(guān)系查詢優(yōu)化的基礎。兩個關(guān)系表達式El和E2是等價的，是指用相同的關(guān)系代替兩個表達式中的關(guān)系變量所得到的結(jié)果是相同的，并記為E1≡E2。常用的等價變換規(guī)則①連接、笛卡爾積交換律常用的等價變換規(guī)則②連接、笛卡爾積的結(jié)合律常用的等價變換規(guī)則③投影的串接定律④選擇的串接定律常用的等價變換規(guī)則⑤選擇與投影的交換律這里，選擇條件F只涉及屬性A1,...,An。若F中有不屬于Al,...,An的屬性B1,…,Bm則有更一般的規(guī)則：常用的等價變換規(guī)則⑥選擇與笛卡爾積的交換律如果F中涉及的屬性都是El中的屬性，則如果F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1、4、6可推出：若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有常用的等價變換規(guī)則⑦選擇與并的交換⑧選擇與差運算的交換常用的等價變換規(guī)則⑨投影與笛卡爾積的交換⑩投影與并的交換7.3查詢優(yōu)化的一般準則利用等價變換規(guī)則可以得到查詢的所有等價式，但在實際應用中不可能也沒有必要計算一個查詢的所有等價式，而是使用一些優(yōu)化準則進行關(guān)系表達式的變換。利用查詢優(yōu)化策略一般能提高查詢效率，但不一定是所有策略中最優(yōu)的。7.3查詢優(yōu)化的一般準則（1）選擇運算應盡可能先做。選擇運算一般使計算的中間結(jié)果大大變小，提前處理常?？墒共樵兇鷥r降低幾個數(shù)量級。（2）在執(zhí)行連接前對關(guān)系適當?shù)仡A處理。如執(zhí)行連接前事先在連接屬性上建立索引，可以減少對表的掃描次數(shù)，從而大大減少連接處理的時間。（3）投影運算和選擇運算同時進行。如有若干投影和選擇運算，并且它們都對同一個關(guān)系操作，則可以在掃描此關(guān)系的同時完成所有的這些運算以避免重復掃描關(guān)系。7.3查詢優(yōu)化的一般準則（4）把投影同其前或其后的雙目運算結(jié)合起來。沒有必要為了去掉某些字段而掃描一遍關(guān)系。（5）把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算，連接特別是等值連接運算要比同樣關(guān)系上的笛卡爾積省很多時間。（6）找出公共子表達式。對那些重復出現(xiàn)且結(jié)果不是很大的子表達式，可以先計算一次并把結(jié)果寫入中間文件，需要時從外存中讀入。7.4查詢優(yōu)化的處理步驟實際系統(tǒng)對查詢優(yōu)化的具體實現(xiàn)一般可以歸納為四個步驟：將