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

1、第9章 關系查詢處理和查詢優(yōu)化,本章主要內(nèi)容,關系數(shù)據(jù)庫系統(tǒng)的查詢處理 關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 代數(shù)優(yōu)化 物理優(yōu)化,9.1 關系數(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條件的第一個索引項，然后通過該指針到文件中搜索磁盤塊，并從該磁盤塊開始順序訪問所有的磁盤塊，直到文件結束。 對于形如Av或A

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

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

5、存在相應的索引，則首先通過索引來檢索指向滿足謂詞i的記錄的指針，并將這些記錄的指針列表記為Li；然后計算所有Li的并集列表L，要求并集列表L中的所有指針按升序排列；最后根據(jù)有序的并集列表L中的每一個指針到文件中去訪問磁盤塊并檢索相關記錄。,二、連接操作的實現(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的索引查找相應的sc元組 把這些sc元組與student元組連接起來 循環(huán)執(zhí)行，直到student表中元組處理完。,4) 散列連接方法 對于參與連接的兩個關系r和s，首先通過散列函數(shù)h把關系r和s的元組分別劃分成在連接屬性值上具有相同散列值的子集ri和si，然后分別計算ri si。,9.2 關系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化,處理一個給定的查詢，尤其是復雜的查詢，通常會有許多種策略。 RDBMS能夠構造并選擇出一個具有最小查詢執(zhí)行代價的查詢執(zhí)行計劃。 關系數(shù)據(jù)庫系統(tǒng)和非過程化的SQL語言能夠取得巨大成功關鍵是得益于查詢優(yōu)化技術的發(fā)展。查詢優(yōu)化是影響RDBMS性能的關鍵因素。,查

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

8、條,SC:10000條, 選修2號課程:50條 假設2： 一個內(nèi)存塊裝元組:10個Student,或100個SC,或者10個連接結果元組。 內(nèi)存中一次可以存放:5塊Student元組,1塊SC 元組和1塊結果元組 假設3：讀寫速度：20塊/秒 假設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秒 中間結果大小=1000*10000 = 107 寫中間結果時間=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秒 中間結果大小=10000（SC表的大?。?寫中間結果時間=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秒 中間結果大小=50條 不必寫入外存 讀Student表總塊數(shù)= 1000/10=100塊 讀數(shù)據(jù)時間=100/20=5秒 投影不需要I/O讀寫。 總時間55秒10秒,總結,選擇運算應盡可能先做 由于選擇運算可能大大減少元組的數(shù)量，同時選擇運算還可以使用索引存取元組。 把某些選擇與其前的笛卡爾積操作結合形成連接操作 投影運算與

11、其前的選擇運算一起做，避免重復掃描關系,9.3 代數(shù)優(yōu)化,9.3.1 關系代數(shù)等價變換規(guī)則,設E1、E2等是關系代數(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) 假設： 1)E是關系代數(shù)表達式 2)Ai(i=1，2，n), Bj(j=l，2，m)是屬性名 3)A1, A2, , An構成Bl，B2，Bm的子集,4） 選擇的串接定律 F1（ F2（E） F1 F2(E) 選擇的串接律說明選擇條件可以合并 這樣一

12、次就可檢查全部條件。,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中涉及的屬性都是E1中的屬性 F (E1E2)F (E1)E2 (2) 假設：F=F1F2，并且F1只涉及E1中的屬性， F2只涉及E2中的屬性 F(E1E2) F1(E1)F2 (E2),(3) 假設： F=F1F2，

13、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） 投影與笛卡爾積的交換 假設：E1和E2是兩個關系表達式， A1，An是E1的屬性， B1，Bm是E2的屬性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2),10） 投影與并的交換 假設

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

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

16、連接時，這樣的選擇子結點不與該結點同組。把這些單目運算單獨分為一組。,（6）生成程序 生成一個程序，每組結點的計算是程序中的一步。 各步的順序是任意的，只要保證任何一組的計算不會在它的后代組之前計算。,優(yōu)化實例,例：求選修了2號課程的學生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;,（1）把查詢轉換成某種內(nèi)部表示,（2）把語法樹轉換成標準（優(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)）,將選擇運算與笛卡兒乘積轉換為連接運算公式,9.4 物理優(yōu)化,9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 一、選擇操作的啟發(fā)式規(guī)則 1. 對于小關系，使用全表順序掃描，即使選擇列上有索引。 對于大關系，啟發(fā)式規(guī)則有： 2. 對于選擇條件是主碼值的查詢.查詢結果最多是一個元組，可以選擇主碼索引。 3. 對于選擇條件是非主屬性值的查詢，并且選擇列上有索引.要估算查詢結果的元組數(shù)目.如果比例較小(10%)可以使用索引掃描,否則還是使用全表順序掃描。,4. 對于選擇條件

18、是屬性上的非等值查詢或者范圍查詢，并且選擇列上有非聚集索引.要估算查詢結果的元組數(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個元組具有某個索引值).索引的葉結點數(shù)(Y)。,二、代價估算示例,1.全表掃描算法的代價估算公式 .如果基本表大小為B塊，全表掃描算法的代價costB .如果選擇條件是碼值，那么平均搜索代價costB/2,2. 索