第9章 數(shù)據(jù)庫.ppt

1、第9章 關(guān)系查詢處理和查詢優(yōu)化,本章主要內(nèi)容,關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 代數(shù)優(yōu)化 物理優(yōu)化,9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理,實現(xiàn)查詢操作的算法示例,一.選擇操作的實現(xiàn) Select * from student Select * from student where Sno200215121； Select * from student Where Sage20； Select * from student Where SdeptCS AND Sage20； Select * from student Where SdeptCS or Sage20；,1.Selec

2、t * from student 搜索方法： 全表掃描,2.Select * from student where Sno200215121； 搜索算法： 全表掃描 索引掃描 在聚集索引的屬性上的等值比較 在非聚集索引屬性上的等值比較 散列掃描,聚簇索引,非聚簇索引,3. Select * from student Where Sage20； 全表掃描 索引掃描 在聚集索引的屬性上比較 對于形如Av或Av的比較條件，首先通過主索引（如B+樹索引）搜索，定位在滿足Av或Av條件的第一個索引項，然后通過該指針到文件中搜索磁盤塊，并從該磁盤塊開始順序訪問所有的磁盤塊，直到文件結(jié)束。 對于形如Av或A

3、v的比較條件，沒有必要查找索引，直接從第一個葉節(jié)點讀取，直到Av 。,在非聚集索引屬性上比較 對于形如Av或Av的比較條件，首先通過輔助索引搜索定位在滿足Av或Av條件的第一個索引項，并通過該索引項中的指針搜索并訪問相應(yīng)文件塊；然后順序讀取葉結(jié)點鏈表中的下一個索引項，并通過該索引項中的指針搜索并訪問相應(yīng)文件塊直到葉結(jié)點鏈表結(jié)束。 對于形如Av或Av的比較條件，直接從索引的葉結(jié)點鏈表頭開始順序掃描每一個葉結(jié)點中的每一個索引項，并通過該索引項中的指針搜索并訪問相應(yīng)文件塊，直至遇到（但不包含）不滿足Av或Av條件的第一個索引項或葉結(jié)點鏈表尾為止。 如果滿足查詢條件的記錄數(shù)很多，使用非聚集索引的代價甚

4、至比線性搜索還要大。非聚集索引只適合于滿足查詢條件的記錄很少時使用。,4.Select * from student Where SdeptCS AND Sage20； 1) 全表掃描 2) 索引掃描 如果其中一個選擇屬性Ai上存在索引。則首先用索引選擇方式選擇；然后在內(nèi)存緩沖區(qū)中，通過測試每條檢索到的記錄是否滿足其余的選擇條件，所有滿足其余選擇條件的記錄都是該合取選擇操作的最后結(jié)果。,5.Select * from student Where SdeptCS or Sage20； 1)全表掃描 任一個析取選擇中無索引，則要全表掃描 2) 索引掃描 如果析取選擇中的每個簡單選擇謂詞i的屬性上都

5、存在相應(yīng)的索引，則首先通過索引來檢索指向滿足謂詞i的記錄的指針，并將這些記錄的指針列表記為Li；然后計算所有Li的并集列表L，要求并集列表L中的所有指針按升序排列；最后根據(jù)有序的并集列表L中的每一個指針到文件中去訪問磁盤塊并檢索相關(guān)記錄。,二、連接操作的實現(xiàn) Select * from student,sc Where student.sno=sc.sno 1) 嵌套循環(huán)方法（nested loop） 對外層循環(huán)（student）中的每一個元組，檢查內(nèi)層循環(huán)（sc）的元組,2) 排序-合并方法 將連接的表按連接屬性進行排序,3) 索引-連接方法 在sc表的sno上建立索引。 對student中

6、每個元組，由sno通過sc的索引查找相應(yīng)的sc元組 把這些sc元組與student元組連接起來 循環(huán)執(zhí)行，直到student表中元組處理完。,4) 散列連接方法 對于參與連接的兩個關(guān)系r和s，首先通過散列函數(shù)h把關(guān)系r和s的元組分別劃分成在連接屬性值上具有相同散列值的子集ri和si，然后分別計算ri si。,9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化,處理一個給定的查詢，尤其是復雜的查詢，通常會有許多種策略。 RDBMS能夠構(gòu)造并選擇出一個具有最小查詢執(zhí)行代價的查詢執(zhí)行計劃。 關(guān)系數(shù)據(jù)庫系統(tǒng)和非過程化的SQL語言能夠取得巨大成功關(guān)鍵是得益于查詢優(yōu)化技術(shù)的發(fā)展。查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素。,查

7、詢優(yōu)化步驟,邏輯優(yōu)化，即產(chǎn)生邏輯上與給定關(guān)系代數(shù)表達式等價的表達式； 物理優(yōu)化，選擇高效合理的操作算法或存取路徑，產(chǎn)生不同的查詢執(zhí)行計劃。 代價估計，即估計每個執(zhí)行計劃的代價；,代價估算,訪問外存的開銷. 存儲中間文件的開銷。 計算開銷（ CPU開銷）。 通信開銷：數(shù)據(jù)在各結(jié)點之間傳輸?shù)拈_銷。 對于大型數(shù)據(jù)庫系統(tǒng)而言，在磁盤上存取數(shù)據(jù)的代價通常是最重要的代價。,一個實例,例：求選修了2號課程的學生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,假設(shè)1：外存： Student:1000

8、條,SC:10000條, 選修2號課程:50條 假設(shè)2： 一個內(nèi)存塊裝元組:10個Student,或100個SC,或者10個連接結(jié)果元組。 內(nèi)存中一次可以存放:5塊Student元組,1塊SC 元組和1塊結(jié)果元組 假設(shè)3：讀寫速度：20塊/秒 假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法。,執(zhí)行策略1,1 sname (Student.Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 讀取總塊數(shù)=讀Student表塊數(shù) + 讀SC表遍數(shù) *每遍塊數(shù) =1000/10+(1000/(105)(10000/100) =100+20100=2100,讀數(shù)據(jù)時間=2100

9、/20=105秒 中間結(jié)果大小=1000*10000 = 107 寫中間結(jié)果時間=10000000/10/20 = 50000秒, 讀數(shù)據(jù)時間 = 50000秒 滿足條件的元組個數(shù)為50個，放在內(nèi)存，不需要往中間文件寫。, 投影不需要I/O讀寫。,總時間 =1055000050000秒 = 100105秒 = 27.8小時,執(zhí)行策略2, Student SC 讀取總塊數(shù)= 2100塊 讀數(shù)據(jù)時間=2100/20=105秒 中間結(jié)果大小=10000（SC表的大?。?寫中間結(jié)果時間=10000/10/20=50秒, 讀數(shù)據(jù)時間=50秒 滿足條件的元組個數(shù)為50個，放在內(nèi)存，不需要往中間文件寫。,投

10、影不需要I/O讀寫。,總時間1055050秒205秒3.4分,2 name(SC.Cno= 2 (Student SC),執(zhí)行策略3,3Sname(Student SC.Cno= 2 (SC) 讀SC表總塊數(shù)= 10000/100=100塊 讀數(shù)據(jù)時間=100/20=5秒 中間結(jié)果大小=50條 不必寫入外存 讀Student表總塊數(shù)= 1000/10=100塊 讀數(shù)據(jù)時間=100/20=5秒 投影不需要I/O讀寫。 總時間55秒10秒,總結(jié),選擇運算應(yīng)盡可能先做 由于選擇運算可能大大減少元組的數(shù)量，同時選擇運算還可以使用索引存取元組。 把某些選擇與其前的笛卡爾積操作結(jié)合形成連接操作 投影運算與

11、其前的選擇運算一起做，避免重復掃描關(guān)系,9.3 代數(shù)優(yōu)化,9.3.1 關(guān)系代數(shù)等價變換規(guī)則,設(shè)E1、E2等是關(guān)系代數(shù)表達式，F(xiàn)是條件表達式 1） 連接、笛卡爾積交換律 E1 E2 E2E1 E1 E2 E2 E1 E1 F E2 E2 F E1,3） 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,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的子集,4） 選擇的串接定律 F1（ F2（E） F1 F2(E) 選擇的串接律說明選擇條件可以合并 這樣一

12、次就可檢查全部條件。,5） 選擇與投影的交換律 (1)假設(shè): 選擇條件F只涉及屬性A1，An F (A1,A2, ,An（E) A1,A2, ,An(F(E) (2)假設(shè): F中有不屬于A1, ,An的屬性B1,Bm A1,A2, ,An ( F(E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),6） 選擇與笛卡爾積的交換律 (1) 假設(shè)：F中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 (2) 假設(shè)：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 F(E1E2) F1(E1)F2 (E2),(3) 假設(shè)： F=F1F2，

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

14、：E1和E2 有相同的屬性名 A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2),9.3.2 查詢樹的啟發(fā)式優(yōu)化,選擇運算應(yīng)盡可能先做 由于選擇運算可能大大減少元組的數(shù)量，同時選擇運算還可以使用索引存取元組。 投影運算和選擇運算同時做 避免重復掃描關(guān)系 將投影運算與其前面或后面的雙目運算結(jié)合 減少掃描關(guān)系的遍數(shù),某些選擇運算在其前面執(zhí)行的笛卡爾積 = 連接運算 例：Student.Sno=SC.Sno (StudentSC) Student SC 提取公共子表達式 定義視圖的表達式,9.3.3 關(guān)系代數(shù)表達式的優(yōu)化算法,算法：關(guān)系表達式的優(yōu)化 輸入：一

15、個關(guān)系表達式的語法樹。 輸出：計算該表達式的程序。,方法： （1）分解選擇運算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) （2）通過交換選擇運算，將其盡可能移到葉端 （3）通過交換投影運算，將其盡可能移到葉端 （4）合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成,（5）對內(nèi)結(jié)點分組 把上述得到的語法樹的內(nèi)節(jié)點(非根結(jié)點和非葉結(jié)點)分組。 每一雙目運算(， ，-)和它所有的直接父結(jié)點為一組(這些直接祖先是，運算)。 如果其子孫結(jié)點一直到葉子全是單目運算（，運算），則也將它們并入該組. 但當雙目運算是笛卡爾積()，而且其子結(jié)點的選擇不能與它結(jié)合為等值

16、連接時，這樣的選擇子結(jié)點不與該結(jié)點同組。把這些單目運算單獨分為一組。,（6）生成程序 生成一個程序，每組結(jié)點的計算是程序中的一步。 各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。,優(yōu)化實例,例：求選修了2號課程的學生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,（1）把查詢轉(zhuǎn)換成某種內(nèi)部表示,（2）把語法樹轉(zhuǎn)換成標準（優(yōu)化）形式 用選擇串接定律 Student.Sno=SC.Sno SC.Cno=2 Student.Sno=SC.S（SC.Cno=2） 將語法

17、樹變換為如圖示,使用選擇與笛卡兒運算的交換律 SC.Cno=2 (StudentSC) Student（ SC.Cno=2(SC)）,將選擇運算與笛卡兒乘積轉(zhuǎn)換為連接運算公式,9.4 物理優(yōu)化,9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 一、選擇操作的啟發(fā)式規(guī)則 1. 對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引。 對于大關(guān)系，啟發(fā)式規(guī)則有： 2. 對于選擇條件是主碼值的查詢.查詢結(jié)果最多是一個元組，可以選擇主碼索引。 3. 對于選擇條件是非主屬性值的查詢，并且選擇列上有索引.要估算查詢結(jié)果的元組數(shù)目.如果比例較小(10%)可以使用索引掃描,否則還是使用全表順序掃描。,4. 對于選擇條件

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

19、3. 如果上面2個規(guī)則都不適用，其中一個表較小.選用Hash join方法 4. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。,9.4.2 基于代價的優(yōu)化,一、統(tǒng)計信息 1. 對每個基本表 .該表的元組總數(shù)(N) .元組長度(l) .占用的塊數(shù)(B) .占用的溢出塊數(shù)(BO) 2. 對基表的每個列.該列不同值的個數(shù)(m) .選擇率(f)（如果不同值的分布是均勻的，f1/m.如果不同值的分布不均勻，則每個值的選擇率具有該值的元組數(shù)/N ）.該列最大值.該列最小值.該列上是否已經(jīng)建立了索引.索引類型(B+樹索引、Hash索引、聚集索引) 3. 對索引(如B+樹索引) .索引的層數(shù)(L).不同索引值的個數(shù).索引的選擇基數(shù)S(有S個元組具有某個索引值).索引的葉結(jié)點數(shù)(Y)。,二、代價估算示例,1.全表掃描算法的代價估算公式 .如果基本表大小為B塊，全表掃描算法的代價costB .如果選擇條件是碼值，那么平均搜索代價costB/2,2. 索