《查詢處理和優(yōu)化 》PPT課件.pptVIP

第5章 查詢處理和優(yōu)化,5.1 引言 5.2 代數(shù)優(yōu)化 5.3 依賴于存取路徑的規(guī)則優(yōu)化 5.4 代價估算優(yōu)化*,5.1 引言,概述 查詢是數(shù)據(jù)庫系統(tǒng)中最基本、最常見和最復(fù)雜的操作。對數(shù)據(jù)庫的查詢一般都是以查詢語言（如SQL）表示。從查詢請求出發(fā)，直到得到查詢結(jié)果，這一過程稱為查詢處理。 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢語言一般是“非過程語言”，它減輕了用戶選擇存取路徑的負擔(dān)。用戶只要提出干什么，不必指出怎么干。即用戶不必關(guān)心查詢的具體執(zhí)行過程，而由DBMS確定合理的、有效的執(zhí)行策略。DBMS在這方面的作用稱為查詢優(yōu)化 。 對于使用非過程查詢語言的RDBMS，查詢優(yōu)化是查詢處理中非常重要的一環(huán)，對系統(tǒng)性能會產(chǎn)生很大的影響。,5.1 引言,2.查詢處理的一般過程 先做詞法和語法分析，把查詢語句變成語法樹或語法圖；然后進行查詢優(yōu)化，形成執(zhí)行計劃，生成可執(zhí)行代碼，交系統(tǒng)執(zhí)行。 具體處理過程也可分為解釋和編譯兩種實現(xiàn)方式。 解釋方式如圖61所示。 編譯方式如圖62所示。 對于常用的例行事務(wù)，編譯方式可以顯著地提高數(shù)據(jù)庫性能。 對于那些不怎么重復(fù)使用的偶然查詢，解釋也不失為一種簡單、實用的實現(xiàn)方式。這兩種實現(xiàn)方式在現(xiàn)有的商用DBMS中都有應(yīng)用。,5.1 引言,3. 例子 首先看一個簡單的例子，說明為什么要進行查詢優(yōu)化。 例：求選修了2號課程的學(xué)生姓名。用SQL語言表達： SELECT Sname FROM S，SC WHERE S.SNO=SC.SNO AND SC.CNO=2； 假定學(xué)生-課程數(shù)據(jù)庫中有l(wèi)000個學(xué)生記錄,l0000個選課記錄，其中選修2號課程的選課記錄為50個。 系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達式來完成這一查詢 1.Q1= Sname( S.sno=o=2(SSC) 2.Q2= Sname( o=2 (S | o= 2 (SC) 我們將看到由于查詢執(zhí)行的策略不同,查詢時間相差很大。,5.1 引言,查詢執(zhí)行策略Q1代價分析 計算廣義笛卡爾積的代價 把S和SC的每個元組連接起來。一般連接的做法是：在內(nèi)存中盡可能多地裝人某個表(如Student表)的若干塊元組，留出一塊存放另一個表(如SC表)的元組。然后把SC中的每個元組和S中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上，再從SC中讀入一塊和內(nèi)存中的S元組連接，直到SC表處理完。這時再一次讀入若干塊S元組，讀入一塊SC元組，重復(fù)上述處理過程，直到把S表處理完。 設(shè)一個塊能裝l0個Student元組或l00個SC元組，在內(nèi)存中存放5塊Student元組 和l塊SC元組，則讀取總塊數(shù)為： 1000/10+1000/(10 5) (10000/100)=2100塊 其中讀Student表l00塊。讀SC表20遍，每遍l00塊。若每秒讀寫20塊，則總計要花105(秒)。 連接后的元組數(shù)為100010000。設(shè)每塊能裝l0個元組，則寫出這些塊要花1000000/20=50000( 秒)。,5.1 引言,查詢執(zhí)行策略Q1代價分析(續(xù)) 選擇操作的代價 依次讀入連接后的元組，按照選擇條件選取滿足要求的的記錄。假定內(nèi)存處理時間忽略。這一步讀取中間文件花費的時間(同寫中間文件一樣)需50000 秒。滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存。 3) 投影操作的代價 把第2步的結(jié)果在Sname上作投影輸出,得到最終結(jié)果。 因此第一種情況下執(zhí)行查詢的總時間約為105+2510000秒。這里，所有內(nèi)存處理時間均忽略不計。,5.1 引言,查詢執(zhí)行策略Q2代價分析 計算自然連接的代價 為了執(zhí)行自然連接，讀取Student和SC表的策略不變,總的讀取塊數(shù)仍為2100塊，花費l05秒。但自然連接的結(jié)果比第一種情況大大減少，為 10000個。因此寫出這些元組時間為 10000/10/20=50秒。僅為第一種情況的千分之一。 讀取中間文件塊，執(zhí)行選擇運算，花費時間也為50秒。 將第2步結(jié)果投影輸出。 因此，第二種情況總的執(zhí)行時間105+50+50205秒。,5.1 引言,查詢執(zhí)行策略Q3代價分析 先對SC表作選擇運算，只需讀一遍SC表，存取l00塊花費時間為5秒，因為滿足條件的元組僅50個，不必使用中間文件。 讀取STUDENT表，把讀入的STUDENT元組和內(nèi)存中的SC元組作連接。也只需讀一遍STUDENT表共l00塊花費時間為5秒。 把連接結(jié)果投影輸出。 第三種情況總的執(zhí)行時間5+510秒。,5.1 引言,假如SC表的Cno字段上有索引，第l步就不必讀取所有的SC元組而只需讀取CNO=2的那些元組(50個)。 存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊。若STUDENT表在Sno上也有索引，則第2步也不必讀取所有的STUDENT元組，因為滿足條件的SC記錄僅50個，涉及最多50個STUDENT記錄，因此讀取STUDENT表的塊數(shù)也可大大減少。總的存取時間將進一步減少到數(shù)秒。 這個簡單的例子充分說明了查詢優(yōu)化的必要性，同時也給了我們一些查詢優(yōu)化方法的初步概念。如當(dāng)有選擇和連接操作時，應(yīng)當(dāng)先做選擇操作，這樣參加連接的元組就可以大大減少。,5.1 引言,查詢優(yōu)化 代數(shù)優(yōu)化：對查詢語句進行變換 。 依賴于存取路徑的優(yōu)化（物理優(yōu)化）：根據(jù)系統(tǒng)所提供的存取路徑，選擇合理的存取策略。 規(guī)則優(yōu)化：僅根據(jù)啟發(fā)式規(guī)則，選擇執(zhí)行的策略。 代價估算優(yōu)化：對可供選擇的執(zhí)行策略進行代價估算，從中選用代價最小的執(zhí)行策略。,5.2 代數(shù)優(yōu)化,5.2.1 關(guān)系代數(shù)等價變換規(guī)則 上面的優(yōu)化策略大部分都涉及到代數(shù)表達式的變換。關(guān)系代數(shù)表達式的優(yōu)化是查詢優(yōu)化的基本課題。而研究關(guān)系代數(shù)表達式的優(yōu)化最好從研究關(guān)系表達式的等價變換規(guī)則開始。 兩個關(guān)系表達式El和E2是等價的，可記為E1E2。 常用的等價變換規(guī)則有： (1)選擇的串接 F1(F2(R)F1 F2(R) (2) 選擇的交換 F1(F2(R)F2(F1(R),5.2 代數(shù)優(yōu)化,(3)投影的串接. L1(L2(Ln(R) L1(R) 條件：L1 L2 Ln (4)選擇與投影的交換. L(F(R)F(L(R) 條件：Attr(F)是L的子集 (5)連接笛卡兒積的交換律 R| R RSSR,5.2 代數(shù)優(yōu)化,(6)選擇對連接笛卡兒積的分配律 F(R|L2 (R) F F 條件： Attr(L1)Attr(S)=NULL, Attr(L2)Attr(R)=NULL Attr(F) Attr(L1L2),5.2 代數(shù)優(yōu)化,(8)選擇對、的分配律 F(RS) F(R) F(S) F(RS) F(R)F(S) F(RS) F(R)F(S) (9)投影對的分配率. L (RS) L (R) L (S) (10) |T),5.2 代數(shù)優(yōu)化,5.2.2查詢優(yōu)化的一般策略 (1)優(yōu)先 (2)使用頻率高的屬性建索引 (3)連接屬性索引/排序 (4)、同時進行 (5)+ | (6)公共子表達式,5.2 代數(shù)優(yōu)化,5.2.3 代數(shù)優(yōu)化算法 步驟： SELECT子句對應(yīng)，F(xiàn)ROM子句對應(yīng)，WHERE子句對應(yīng)，生成查詢語法樹 利用規(guī)則(2)，(6)，(8)盡可能將選擇操作移到樹的葉端 利用投影的串接規(guī)則(3)，合并投影,5.2 代數(shù)優(yōu)化,利用連接、笛卡兒積的結(jié)合率，按照小關(guān)系先執(zhí)行原則，調(diào)整連接、笛卡兒積的執(zhí)行順序* 將笛卡兒積與相關(guān)選擇操作轉(zhuǎn)換為連接操作 對葉節(jié)點加必要的 ，以消除對查詢無用的屬性。,5.2 代數(shù)優(yōu)化,5.2.4 例子 例 設(shè)有Shop(商店)，Customer(顧客)，SC(購物關(guān)系)三個關(guān)系，關(guān)系模式如下： Shop (S#,Sname,Address) Customer (C#,Cname,Address) SC(S#,C#, Item, Quantity,Price) 查詢是“找出西安銷售給顧客“張立”彩電的商店編號和名稱”，用SQL語句表達如下： SELECT S#,Sname FROM Shop，SC ，Customer WHERE Shop.Address=西安 AND Cname=張立 AND Item=彩 電 AND Shop.S# SC.S# AND Customer.C#=SC.C#,5.2 代數(shù)優(yōu)化,假設(shè)該查詢變換成的關(guān)系代數(shù)表達式如下： S#,Sname(Shop.Address=西安 Cname=張立 Item=彩電 Shop.S# SC.S# Customer.C#=SC.C# (ShopSC Customer) 該表達式可轉(zhuǎn)換為下圖所示的原始查詢樹表示。以SELECT子句對應(yīng)投影操作，F(xiàn)ROM子句對應(yīng)笛卡兒積操作，WHERE子句對應(yīng)選擇操作，生成原始查詢樹。,5.2 代數(shù)優(yōu)化,5.2 代數(shù)優(yōu)化,現(xiàn)在使用優(yōu)化算法對語法樹進行優(yōu)化。 應(yīng)用規(guī)則變換選擇條件C，可得到單獨的五個選擇操作： Shop.Address=西安 Cname=張立 Item=彩電 Shop.S# SC.S# Customer.C#=SC.C# 根據(jù)涉及選擇的規(guī)則，盡可能將選擇操作沿查詢樹下移。 由于操作Shop.Address=西安、Cname=張立、Item=彩電 分別只涉及關(guān)系Shop、Customer、SC，經(jīng)過一系列變換，可以作為葉子結(jié)點的直接祖先。,5.2 代數(shù)優(yōu)化,而操作Shop.S# SC.S#分別涉及到兩個關(guān)系Shop和SC，可向下移動，與笛卡兒積交換位置。操作Customer.C#=SC.C#分別涉及到兩個關(guān)系Customer和SC，不能再向下移向樹葉方向。得到表達式： S#,Sname(Customer.C#=SC.C# (Shop.S# SC.S# (Shop.Address=西安(Shop)Item=彩電(SC) Cname=張立(Customer) 經(jīng)過這一步，原始語法樹變成下圖的形式。,5.2 代數(shù)優(yōu)化,5.2 代數(shù)優(yōu)化,將選擇與笛卡兒積合并為連接,5.2 代數(shù)優(yōu)化,利用規(guī)則(3)、(7)下移。,5.2 代數(shù)優(yōu)化,例：設(shè)有下列關(guān)系： S(SNUM,SNAME,CITY) P(PNUM,PNAME,WEIGHT,SIZE) SP(SNUM,PNUM,DEPT,QUAN) 和如下查詢： SELECT SNAME FROM S,SP,P WHERE S.SNUM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=NJ AND P.PNAME=BLOT AND SP.QUAN10000;,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)化,選擇操作的實現(xiàn)和優(yōu)化 選擇操作的執(zhí)行策略與選擇條件、可用的存取路徑以及滿足選擇條件的元組數(shù)在整個關(guān)系中所占的比例有關(guān)。 選擇條件可分為：等值(=)、范圍(,=,Between )和集合(IN)等幾種。 復(fù)合選擇條件由簡單選擇條件通過AND、OR連接而成。 選擇操作的實現(xiàn)方法包括： (1) 順序掃描：適用于小的關(guān)系，滿足條件的元組比例較大或無其他存取路徑。 (2) 利用各種存取路徑：包括索引（B+樹），動態(tài)散列 對于選擇操作可按照下列啟發(fā)式規(guī)則選取存取路徑： (8) P128-129,5.3 依賴于存取路徑的優(yōu)化,連接操作的實現(xiàn)和優(yōu)化 主要考慮二元連接(two-way join)。 多元連接(multi-may join)則以二元連接為基礎(chǔ)。 實現(xiàn)連接操作一般有下列4種方法： 嵌套循環(huán)法(nested loop) 順序掃描外關(guān)系的每一個元組，然后與內(nèi)關(guān)系的每一個元組進行匹配 具體算法見P129 圖6-4 設(shè) bR ，bS分別表示R和S的物理塊數(shù)，nB為可用的內(nèi)存緩沖塊數(shù)，并以其中(nB 1)塊存放外關(guān)系，剩余的1塊存放內(nèi)關(guān)系。 若以R為外關(guān)系，S為內(nèi)關(guān)系，用嵌套循環(huán)法進行連接需要訪問的物理塊數(shù)為： bR+bR/(nB-1) bS 若以S為外關(guān)系，R為內(nèi)關(guān)系，用嵌套循環(huán)法進行連接需要訪問的物理塊數(shù)為： bS+bS/(nB-1) bR 比較上面2個式子，可以看出選擇占用物理塊少的關(guān)系作為外關(guān)系,5.3 依賴于存取路徑的優(yōu)化,連接操作的實現(xiàn)和優(yōu)化(續(xù)) 利用索引或散列尋找匹配元組法 可有效減少I/O次數(shù) 排序歸并(sort-merge)法 首先按連接屬性對關(guān)系排序，然后進行歸并連接 具體算法見P131 圖6-6 散列連接法(hash join) 首先用散列函數(shù)將連接屬性散列至文件中，然后對散列到同一個桶(Bucket)中的元組進行匹配。 有關(guān)連接操作實現(xiàn)策略的啟發(fā)式規(guī)則： (1) (4) P131-132,5.3 依賴于存取路徑的優(yōu)化,投影操作的實現(xiàn) 投影操作一般可與選擇、連接等操作同時進行，不再需要附加的I/O開銷。 重復(fù)值的消除：排序，散列 具體實現(xiàn)算法見 P132 圖6-7 集合操作的實現(xiàn) 對于笛卡兒積()一般可采用嵌套循環(huán)法； 對于、等操作需要發(fā)現(xiàn)共同元組 ； 具體算法見P133 圖6-8 圖6-9 圖6-10 組合操作 減少臨時文件，盡可能同時執(zhí)行操作。,5.4 代價估算優(yōu)化*,查詢執(zhí)行代價的組成與代價統(tǒng)計參數(shù) 查詢執(zhí)行代價主要包括3個方面： I/O代價(*) CPU代價 通信代價 訪問磁盤1次所需的代價可表示為： CI/O=D0 + xD1 其中：x 存取數(shù)據(jù)的大小，以字節(jié)表示 D0 與x無關(guān)的I/O代價，包括尋道時間和等待時間 D1 每個字節(jié)所需的傳輸時間 一般D0 xD1 故 I/O代價=I/O次數(shù) D0,5.4 代價估算優(yōu)化,查詢執(zhí)行代價的組成與代價統(tǒng)計參數(shù)(續(xù)) 下面給出進行代價估算時將要用到的統(tǒng)計參數(shù)： nR：R中的元組數(shù)； PR ： R塊因子，即每個物理塊中包含的元組數(shù)； Na： 屬性A在一個關(guān)系中出現(xiàn)的不同值的個數(shù)； Fa： 屬性A的選擇因子，即屬性A為某一個值的概率，一般假定屬性值均勻分布， FA=1/ Na ； Ma：屬性A的值域大小|DOM(A)|； L：索引的級數(shù)；,5.4 代價估算優(yōu)化,選擇操作的代價估算 (1) 順序掃描 最多選取一個元組的I/O代價：Csa=0.5n/p=0.5 b 選取多個元組的I/O代價： Csb = b (2) 利用主鍵上的索引或散列進行等值查詢 通過索引訪問的I/O代價：Cik = L+1 通過散列訪問的I/O代價：Chk = 1 (假定散列沒有溢出) (3) 利用非主鍵上的無序索引進行等值查詢 分析表明幾乎每取一個元組都需要訪問一個物理塊，故 CINK = L + s 其中 s 為滿足選擇條件的元組數(shù) (4) 利用聚簇索引進行等值查詢 CCI = L + s/p (5) 利用聚簇索引進行范圍查詢 CCIR=L + b/2,5.4 代價估算優(yōu)化,例：設(shè)有關(guān)系STUDENT，其統(tǒng)計數(shù)據(jù)及存取路徑如下： n=10000 b=2000 即 p=5 在屬性DEPT上建有聚簇索引：NDEPT = 25， L=2 在屬性SNO上建有主鍵索引：NSNO = 10000， L=4 在屬性DNO上建有輔助索引：NDNO = 20， L=3 在屬性AGE上建有輔助索引：NAGE = 15， L=2 設(shè)有下列查詢： 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īng)優(yōu)先采用主索引，其執(zhí)行代價可估 算為： CQ1=L+1=4+1=5 Q2：DEPT=CS(STUDENT) DEPT上建有聚簇索引，故可不考慮順序掃描。滿足Q2的元組數(shù)s估計為: s=10000/25=400 由于STUDENT關(guān)系對DEPT是聚簇的，故I/O代價可估算為： CQ2=L + s/p = 2 + 400/5 = 82 Q3：AGE=20(STUDENT) 是范圍查詢。雖然在AGE上建有輔助(二次)索引，但不是聚簇索引。如果取一半元組，則使用索引還不如使用順序掃描，故： CQ3 = b = 2000 Q4：查詢條件是合取式。由于沒有適當(dāng)?shù)亩鄬傩运饕捎?，只?種 可能的策略：,5.4 代價估算優(yōu)化,策略1：預(yù)查詢法DEPT=CSAND DNO=108 AND AGE=20(STUDENT) 滿足條件 DNO=108 的元組數(shù)估算為： n/NDNO = 10000/20 = 500