第5章查詢處和優(yōu)化ppt課件

1、第5章 查詢處理和優(yōu)化5.1 引言5.2 代數(shù)優(yōu)化5.3 依賴于存取路徑的規(guī)則優(yōu)化5.4 代價估算優(yōu)化*5.1 引言1. 概述查詢是數(shù)據(jù)庫系統(tǒng)中最基本、最常見和最復雜的操作。對數(shù)據(jù)庫的查詢一般都是以查詢語言（如sql）表示。從查詢請求出發(fā)，直到得到查詢結果，這一過程稱為查詢處理。關系數(shù)據(jù)庫系統(tǒng)的查詢語言一般是“非過程語言”，它減輕了用戶選擇存取路徑的負擔。用戶只要提出干什么，不必指出怎么干。即用戶不必關心查詢的具體執(zhí)行過程，而由dbms確定合理的、有效的執(zhí)行策略。dbms在這方面的作用稱為查詢優(yōu)化 。對于使用非過程查詢語言的rdbms，查詢優(yōu)化是查詢處理中非常重要的一環(huán)，對系統(tǒng)性能會產(chǎn)生很大的

2、影響。5.1 引言2.查詢處理的一般過程查詢處理的一般過程 先做詞法和語法分析，把查詢語句變成語法樹或語法圖；然后進行查詢優(yōu)化，形成執(zhí)行計劃，生成可執(zhí)行代碼，交系統(tǒng)執(zhí)行。具體處理過程也可分為解釋和編譯兩種實現(xiàn)方式。解釋方式如圖61所示。編譯方式如圖62所示。對于常用的例行事務，編譯方式可以顯著地提高數(shù)據(jù)庫性能。對于那些不怎么重復使用的偶然查詢，解釋也不失為一種簡單、實用的實現(xiàn)方式。這兩種實現(xiàn)方式在現(xiàn)有的商用dbms中都有應用。 5.1 引言3. 例子首先看一個簡單的例子，說明為什么要進行查詢優(yōu)化。 例：求選修了2號課程的學生姓名。用sql語言表達： select sname from s，sc

3、 where s.sno=sc.sno and sc.cno=2； 假定學生-課程數(shù)據(jù)庫中有l(wèi)000個學生記錄,l0000個選課記錄，其中選修2號課程的選課記錄為50個。 系統(tǒng)可以用多種等價的關系代數(shù)表達式來完成這一查詢 1.q1= sname( s.sno=o=2(ssc) 2.q2= sname( o=2 (s |10000;5.2 代數(shù)優(yōu)化 圖6-3(a) q的原始查詢樹(p125) 圖6-3(b) 將選擇操作盡量下推 圖6-3(c) 將連接條件與笛卡兒積組合成連接操作 圖6-3(d) 另一種查詢執(zhí)行方案 圖6-3(e) 用投影操作消除對查詢無用的屬性5.3 依賴于存取路徑的優(yōu)化1. 選

4、擇操作的實現(xiàn)和優(yōu)化選擇操作的執(zhí)行策略與選擇條件、可用的存取路徑以及滿足選擇條件的元組數(shù)在整個關系中所占的比例有關。選擇條件可分為：等值(=)、范圍(,=,between )和集合(in)等幾種。復合選擇條件由簡單選擇條件通過and、or連接而成。選擇操作的實現(xiàn)方法包括：(1) 順序掃描：適用于小的關系，滿足條件的元組比例較大或無其他存取路徑。(2) 利用各種存取路徑：包括索引（b+樹），動態(tài)散列 對于選擇操作可按照下列啟發(fā)式規(guī)則選取存取路徑：(1) (8) p128-1295.3 依賴于存取路徑的優(yōu)化2.連接操作的實現(xiàn)和優(yōu)化主要考慮二元連接(two-way join)。多元連接(multi-m

5、ay join)則以二元連接為基礎。實現(xiàn)連接操作一般有下列4種方法：1)嵌套循環(huán)法(nested loop) 順序掃描外關系的每一個元組，然后與內關系的每一個元組進行匹配 具體算法見p129 圖6-4 設 br ，bs分別表示r和s的物理塊數(shù)，nb為可用的內存緩沖塊數(shù)，并以其中(nb 1)塊存放外關系，剩余的1塊存放內關系。 若以r為外關系，s為內關系，用嵌套循環(huán)法進行連接需要訪問的物理塊數(shù)為： br+br/(nb-1) bs 若以s為外關系，r為內關系，用嵌套循環(huán)法進行連接需要訪問的物理塊數(shù)為： bs+bs/(nb-1) br 比較上面2個式子，可以看出選擇占用物理塊少的關系作為外關系 5.

6、3 依賴于存取路徑的優(yōu)化2.連接操作的實現(xiàn)和優(yōu)化(續(xù))2)利用索引或散列尋找匹配元組法 可有效減少i/o次數(shù) 3)排序歸并(sort-merge)法 首先按連接屬性對關系排序，然后進行歸并連接 具體算法見p131 圖6-64)散列連接法(hash join) 首先用散列函數(shù)將連接屬性散列至文件中，然后對散列到同一個桶(bucket)中的元組進行匹配。有關連接操作實現(xiàn)策略的啟發(fā)式規(guī)則：(1) (4) p131-1325.3 依賴于存取路徑的優(yōu)化3.投影操作的實現(xiàn) 投影操作一般可與選擇、連接等操作同時進行，不再需要附加的i/o開銷。 重復值的消除：排序，散列 具體實現(xiàn)算法見 p132 圖6-74.

7、集合操作的實現(xiàn) 對于笛卡兒積()一般可采用嵌套循環(huán)法； 對于、等操作需要發(fā)現(xiàn)共同元組 ； 具體算法見p133 圖6-8 圖6-9 圖6-105.組合操作 減少臨時文件，盡可能同時執(zhí)行操作。 5.4 代價估算優(yōu)化*1. 查詢執(zhí)行代價的組成與代價統(tǒng)計參數(shù)查詢執(zhí)行代價主要包括3個方面：1) i/o代價(*)2) cpu代價3) 通信代價訪問磁盤1次所需的代價可表示為： ci/o=d0 + xd1 其中：x 存取數(shù)據(jù)的大小，以字節(jié)表示 d0 與x無關的i/o代價，包括尋道時間和等待時間 d1 每個字節(jié)所需的傳輸時間一般d0 xd1 故 i/o代價=i/o次數(shù) d05.4 代價估算優(yōu)化1. 查詢執(zhí)行代價

8、的組成與代價統(tǒng)計參數(shù)(續(xù))下面給出進行代價估算時將要用到的統(tǒng)計參數(shù)： nr：r中的元組數(shù)； pr ： r塊因子，即每個物理塊中包含的元組數(shù)； na： 屬性a在一個關系中出現(xiàn)的不同值的個數(shù)； fa： 屬性a的選擇因子，即屬性a為某一個值的概率，一般假定屬性值均勻分布， fa=1/ na ； ma：屬性a的值域大小|dom(a)|； l：索引的級數(shù)；5.4 代價估算優(yōu)化2. 選擇操作的代價估算(1) 順序掃描最多選取一個元組的i/o代價：csa=0.5n/p=0.5 b選取多個元組的i/o代價： csb = b(2) 利用主鍵上的索引或散列進行等值查詢通過索引訪問的i/o代價：cik = l+1通

9、過散列訪問的i/o代價：chk = 1 (假定散列沒有溢出)(3) 利用非主鍵上的無序索引進行等值查詢分析表明幾乎每取一個元組都需要訪問一個物理塊，故 cink = l + s 其中 s 為滿足選擇條件的元組數(shù)(4) 利用聚簇索引進行等值查詢 cci = l + s/p(5) 利用聚簇索引進行范圍查詢 ccir=l + b/25.4 代價估算優(yōu)化例：設有關系student，其統(tǒng)計數(shù)據(jù)及存取路徑如下：n=10000b=2000 即 p=5在屬性dept上建有聚簇索引：ndept = 25， l=2在屬性sno上建有主鍵索引：nsno = 10000， l=4在屬性dno上建有輔助索引：ndno

10、= 20， l=3在屬性age上建有輔助索引：nage = 15， l=2設有下列查詢：q1：sno=992311(student)q2：dept=cs(student)q3：age=20(student)q4：dept=csand dno=108 and age=20(student)試用代價估算優(yōu)化選取存取策略，并估算其執(zhí)行代價。5.4 代價估算優(yōu)化解：q1：sno=992311(student) 由于sno上建有主索引，應優(yōu)先采用主索引，其執(zhí)行代價可估算為： cq1=l+1=4+1=5q2：dept=cs(student) dept上建有聚簇索引，故可不考慮順序掃描。滿足q2的元組數(shù)s估

11、計為: s=10000/25=400由于student關系對dept是聚簇的，故i/o代價可估算為： cq2=l + s/p = 2 + 400/5 = 82q3：age=20(student) 是范圍查詢。雖然在age上建有輔助(二次)索引，但不是聚簇索引。如果取一半元組，則使用索引還不如使用順序掃描，故： cq3 = b = 2000q4：查詢條件是合取式。由于沒有適當?shù)亩鄬傩运饕捎?，只?種可能的策略：5.4 代價估算優(yōu)化策略1：預查詢法dept=csand dno=108 and age=20(student)滿足條件 dno=108 的元組數(shù)估算為： n/ndno = 10000/

12、20 = 500設順序集每塊可容納200個tid，則從dno輔助索引的順序集中取500個tid所需的i/o代價為 cdno = l + 500/200 = 3+3 =6滿足條件 age= 20 的元組數(shù)估算為：n/2 = 10000/2 = 5000則從age輔助索引的順序集中取5000個tid所需的i/o代價為 cage = l + 5000/200 = 2+25 = 272個tid集的交集的大小應小于或等于500。由于取500個隨機存放的元組一般需要500次i/o，故預查詢法的i/o代價估算為： ca = cdno + cage + 500 = 5335.4 代價估算優(yōu)化策略2：用其中代價

13、最小的一個條件選出元組，再用其他 條件對這些元組進行篩選應從3個條件中選出i/o代價最小的條件：dept=csand dno=108 and age=20(student)dept=cs：同q2，cq2 = 82dno=108：s = 10000/20= 500 cdno=108 = cdno+500 = 6 + 500=506age=20：同q3，cq3 = 2000在3個條件中，以dept=cs的代價最小，故可先按此條件選取出滿足條件dept=cs的學生的元組并同時檢查每個元組是否滿足其他2個條件，其i/o代價為 cb = 82由于cacb，故cq4=cb=825.4 代價估算優(yōu)化3. 連接操作的代價估算(1) 連接結果大小的估算為估算連接操作的代價，首先需要估算連接結果的大小。為此，引入連接