1、第五章 分布查詢的存取優(yōu)化,1,2,分布式查詢處理概述,2,2020/7/29,查詢存取優(yōu)化 輸入：片段查詢 找到好的（不必最優(yōu)的）全局調度 最小代價函數(shù) 分布Join處理 稠密樹與線性樹 需要傳輸?shù)年P系 全部傳輸與按需傳輸 確定使用半連接 使用半連接可減少通信代價 Join方法 嵌套循環(huán)與順序join（合并join與hash join）,分布式查詢處理概述,3,2020/7/29,基于代價的優(yōu)化 搜索空間（Solution space） 等價的代數(shù)表達式 (query trees). 代價函數(shù)（Cost function） I/O 代價 + CPU 代價+ communication代價 不

2、同的分布環(huán)境中各因素權重不同 (LAN vs WAN). 最大吞吐量 搜索算法（Search algorithm） 如何在解決空間中移動 窮舉搜索，啟發(fā)式算法 (遞歸改進、模擬退火、遺傳法等）,分布式查詢處理概述,4,2020/7/29,查詢優(yōu)化 最小化查詢代價,查詢優(yōu)化過程,分布式查詢處理概述,5,2020/7/29,分布式查詢處理概述,搜索空間(Search Space) 搜索空間由可選擇的執(zhí)行計劃描述 側重Join樹 若存在n個關系，有O(N!)等價的Join樹 例如， select ENAME,RESP From EMP,ASG,PROJ Where EMP.ENO=ASG.ENO A

3、nd ASG.PNO=PROJ.PNO,6,2020/7/29,分布式查詢處理概述,搜索空間(Search Space) 由啟發(fā)式規(guī)則約束 如一元操作先于二元操作執(zhí)行 約束join樹的形狀 只考慮線性樹而忽略了稠密樹,線性join樹：,稠密join樹：,7,2020/7/29,搜索策略(Search Strategy) 如何在搜索空間中構建查詢計劃 確定的（Deterministic） 開始于基關系，每步加一個關系構建執(zhí)行計劃 動態(tài)規(guī)劃法：寬度優(yōu)先（breadth-first） 貪婪法: 深度優(yōu)先（depth-first）（只構造一個計劃） 隨機的（Randomized） 從一個特定的點起始搜

4、索最優(yōu)執(zhí)行計劃 (首先應用貪婪法構建一個或多個執(zhí)行計劃，接著通過鄰居關系替換來改進執(zhí)行計劃) 綜合考慮優(yōu)化時間和執(zhí)行時間 適合大于 5-6 個關系 模擬退化（Simulated annealing） 遞歸改進（Iterative improvement）,構造所有可能的執(zhí)行計劃； 盡早剪裁不是優(yōu)化的計劃； Is also exhaustive; 關系數(shù)少時，優(yōu)化代價可接受;,分布式查詢處理概述,8,2020/7/29,隨機的（Randomized） 隨機交換操作關系,搜索策略(Search Strategy) 確定的（Deterministic） 從基關系開始，每步聯(lián)接一個或多個關系，直到獲得

5、全部的計劃,分布式查詢處理概述,9,2020/7/29,分布查詢的存取優(yōu)化,基本概念 優(yōu)化的理論基礎 半聯(lián)接優(yōu)化方法 SDD-1 系統(tǒng)優(yōu)化技術 枚舉法優(yōu)化技術 集中的查詢優(yōu)化(CENTRALIZED QUERY OPTIMIZATION),10,2020/7/29,基本概念,分布執(zhí)行過程實際上就是從查詢場地發(fā)出查詢命令、從數(shù)據(jù)源獲取數(shù)據(jù)、確定最佳的執(zhí)行場地和返回執(zhí)行結果的過程。,查詢場地：指發(fā)出查詢命令和存儲最終查詢結果的場地。查詢場地也稱最終結果文件。 源數(shù)據(jù)場地：指查詢命令需要訪問的數(shù)據(jù)副本所在的場地，可能涉及到一個或一個以上的場地。源數(shù)據(jù)場地也稱源數(shù)據(jù)文件。 執(zhí)行場地：指查詢操作執(zhí)行所在

6、的場地。執(zhí)行場地可以和查詢場地或源數(shù)據(jù)場地處于同一場地，也可不處于同一場地。執(zhí)行場地也稱中間結果文件。,11,2020/7/29,基本概念,分布執(zhí)行策略舉例 有關系EMP和DEPT。 EMPENO，ENAME，BIRTH，SALARY，DNO （ENO為主鍵） ENO，ENAME，BIRTH，SALARY，DNO分別為雇員編號 雇員姓名 出生日期 工資 部門號 DEPTDNO，DNAME （ ENO為主鍵） DNO，DNAME分別為部門號，部門名稱 假設： （1）EMP：元組數(shù)：10000，元組大?。?00B，關系大?。?00*10000=1000KB （2）DEPT：元組數(shù)：100，元組大小

7、：35B，關系大?。?5*100=3.5KB,12,2020/7/29,假設：結果元組大小40字節(jié)，S3為查詢場地 結果關系大小：40*10000=400KB,基本概念,(3) 存在三個場地，S1、S2和S3。如圖： 查詢要求：查詢每個雇員的姓名及所在單位。 則：（1）SQL語句：SELECT ENAME，DNAME FROM EMP，DEPT WHERE EMP.DNO=DEPT.DNO （2）關系表達式：ENAME，DNAME（EMPDEPT）,分布執(zhí)行策略舉例,13,2020/7/29,分布執(zhí)行策略舉例-1 策略（設結果為R，以傳輸代價為主） 策略1： S3為執(zhí)行場地，則需傳輸EMP、D

8、EPT 傳輸量=1000K+3.5K=1003.5K 策略2： S2為執(zhí)行場地，則需傳輸EMP到S2，結果R傳 輸?shù)絊3。 傳輸量=1000K+400K=1400K 策略3： S1為執(zhí)行場地，則需傳輸DEPT到S1，結果R傳輸?shù)絊3。 傳輸量=3.5K +400K=403.5K 從上面三個策略看，選擇不同的執(zhí)行場地，傳輸代價差別很大。應選擇最低的傳輸代價。但組成系統(tǒng)的環(huán)境不同，優(yōu)化的側重點也不同。,基本概念,14,2020/7/29,基本概念,分布查詢的存取優(yōu)化的目標 對于遠程網(wǎng)，主要考慮通信開銷，使通信代價最小。 對于局域網(wǎng)，需同時考慮通信代價和本地處理代價，使綜合代價最小。 優(yōu)化的內容 優(yōu)

9、化是在片段查詢的基礎上進行的實際物理副本查詢操作的優(yōu)化。具體如下： 輸入：片段查詢表達式 輸出：分布執(zhí)行計劃,15,2020/7/29,查詢存取優(yōu)化 內容： 確定片段查詢需訪問的物理副本。通常：本場地上的物理副本優(yōu)先；若二元運算存在盡量選擇本場地上的二元運算；數(shù)據(jù)最小的物理關系應被優(yōu)先選中；網(wǎng)絡通信代價小的應優(yōu)先選中 確定片段查詢表達式操作執(zhí)行的最優(yōu)順序。包括從葉到根的執(zhí)行和同一層葉子上表達式執(zhí)行的先后，特別是對查詢樹上的并操作和聯(lián)接操作的執(zhí)行次序的確定，其代價差別很大。 選擇執(zhí)行每個操作的方法。如：盡量將同一場地上的、同一物理副本的全部操作組合在一起統(tǒng)一考慮完成。,基本概念,16,2020/

10、7/29,存取優(yōu)化的理論基礎,代價函數(shù)(the total time or the response time) 總的時間（Total Time）-所有時間組件的和 減少每一個組件的時間代價 盡可能減少每個代價組件的代價 優(yōu)化資源利用率，增加系統(tǒng)吞吐率 響應時間（Response Time）-從查詢開始到執(zhí)行結束所用的時間 盡可能并行執(zhí)行（Do as many things as possible in parallel） 增加總的活動（activity）可能會增加總時間,17,2020/7/29,例子:,存取優(yōu)化的理論基礎,假設只考慮通信代價 總時間=2*消息啟動時間+單位傳輸代價*(x+y

11、) 響應時間=max(從1傳輸x到3的時間，從2傳輸x到3的時間),18,2020/7/29,存取優(yōu)化的理論基礎,代價模型 主要指傳輸代價（Ccom）、I/O代價（CIO）和CPU代價（Ccpu）Total cost = Ccom+CIO+Ccpu 傳輸代價 費用和延遲。其中費用起決定作用。 傳輸費用是指使通信中的整個傳輸開銷，即傳輸?shù)臄?shù)據(jù)量。 模型為：CCOM（X）=C0+C1*X 其中：C0：場地間傳輸數(shù)據(jù)的啟動所需的固定費用（啟動一次），簡稱啟動代價； C1：網(wǎng)絡單位傳輸數(shù)據(jù)費用，簡稱單位傳輸代價； X：需傳輸?shù)臄?shù)據(jù)量。,19,2020/7/29,存取優(yōu)化的理論基礎,I/O代價 模型為：

12、CIO（X）=X/P*CIO 其中：P：頁面的大??；CIO：為每頁平均訪問代價； X：數(shù)據(jù)量大小。 CPU代價 模型：CCPU（X）=X*CCPU 其中：CCPU：單位指令代價；X：為指令數(shù)。 通常具有下面的統(tǒng)計值： 廣域網(wǎng)環(huán)境：CCOM/ CIO=20：1； 局域網(wǎng)環(huán)境：CCOM/ CIO=1.6：1。 可見，在廣域網(wǎng)環(huán)境，以傳輸代價為主；在局域網(wǎng)環(huán)境，需綜合考慮傳輸代價和局部代價。,20,2020/7/29,查詢模型 主要代價因素:中間關系大小 數(shù)據(jù)庫特征參數(shù) 假設R為一關系 關系的基：指關系R包含的元組個數(shù)，記為Card(R) 屬性的長度：指屬性A定義的取值字節(jié)數(shù)，記為Length(A)

13、 元組的長度：關系R中每個元組的字節(jié)數(shù)，記為Length(R), Length(R)=Length(Ai) 關系的大?。宏P系R所包含的字節(jié)數(shù)，記為Size(R) Size(R)= Card(R)* Length(R) 屬性的特征值：指關系R中屬性A取值不同的屬性值個數(shù)，記為Val(A) 屬性A的值域：記為Dom(A) 屬性A的最大值和最小值：記為Max(A)和Min(A),存取優(yōu)化的理論基礎,21,2020/7/29,關系運算的特征參數(shù) 假設：R、S為關系。 選擇運算 （S=F（R） 選擇度： 滿足選擇謂詞F的元組與R元組總數(shù)之比，記為 基數(shù)： Card（S）=* Card（R） 關系的寬度：

14、 Length（S）= Length（R） Length（S.A）= Length（R.A）,存取優(yōu)化的理論基礎,22,2020/7/29,存取優(yōu)化的理論基礎,選擇運算(中間關系大小) 選擇度的具體計算方法: 等值比較 S=A=X(R)，其中A是R的屬性，X是常數(shù)。 則=1/Val(R, A) 非等值比較 S=AX(R)時： = (Max(A)-X)/(Max(A)-Min(A) S=AX(R)時： = (X-Min(A)/(Max(A)-Min(A) 不等比較 S=AX(R)時: = ( Val(R, A)-1)/ Val(R, A) 多屬性選擇條件 S= Ci AND Cj (R)時: =

15、 i*j S= Ci OR Cj (R)時: =1-(1-i)(1-j)=( i+j -i *j),23,2020/7/29,選擇運算 （S= F（R） 不同值的個數(shù)： a.設B不屬于選擇謂詞F，其值均勻分布。,存取優(yōu)化的理論基礎,Card(S) 當Card(S)Val(R, B)/2時 Val(S, B)= (Card(S)+Val(R, B)/3 當Val(R, B)/2Card(S)2Val(R, B)時 Val(R, B) 當Card(S)2Val(R, B)時,b.設B屬于選擇謂詞F 若B=X（值），則：Val（S，B）=1 若B與選擇謂詞F相關且為關鍵字， 則：Val（S，B）=*

16、 Val（R，B）,24,2020/7/29,令=0.1 則：Card(S)=* Card(R) =0.1*100=10 Card(S)=10, Val(R,B)/2=35 Card(S) Val(R,B)/2, Val(S,B)=Card(S)=10,存取優(yōu)化的理論基礎,選擇運算 （S= F（R） 舉例：設Card（R）=100，Val（R，B）=70,令=0.5 則：Card(S)=* Card(R) =0.5*100=50 Card(S)=50 , Val(R,B)/2=70/2=35 Val(R,B)/2Card(S)2* Val(R,B), Val(S,B)=(Card(S)+ Va

17、l(R,B)/3=40,25,2020/7/29,投影運算 (S=A(R) 基數(shù)： 如果投影涉及單個屬性A：Card（S）= Val（R，A） 如果A中包含關鍵字：Card（S）= Card（R） 投影涉及多個屬性： 關系的寬度： Length（S）=Length（Ai）（AiA） Size（S）= Card（S）* Length（S） Size（S） Size（R） 不同值的個數(shù)： Val(S,A)= Val(R,A),存取優(yōu)化的理論基礎,26,2020/7/29,并、交與差(如果結果關系執(zhí)行消除重復操作，則都只能計算出結果關系基數(shù)的上限和下限，因此通常采用平均值作為基數(shù)的估計值。) 基數(shù)：

18、 并運算 如果不消除重復，則結果關系基數(shù)等于兩個關系基數(shù)之和： Card(T)= Card(R)+ Card(S) 如果消除重復，則結果關系基數(shù)最大可大至兩個關系基數(shù)之和，最小可小至兩個關系基數(shù)的大者，因此有： MaxCard(R), Card(S)Card(T)Card(R)+ Card(S) 在估計中使用中間值作為結果關系基數(shù): (MaxCard(R), Card(S)+Card(R)+ Card(S)/2,存取優(yōu)化的理論基礎,27,2020/7/29,并、交與差 基數(shù)： 交運算 交運算的結果關系最小可以是空，最大可以等于兩個關系的較小者，因此按取區(qū)間中間值的方法估計結果關系的基數(shù)為較小關

19、系基數(shù)的一半： Card(T)= MinCard(R), Card(S)/2 差運算 對于兩個關系的差運算R-S，其結果關系基數(shù)的區(qū)間為： Card(R)-Card(S)Card(T)Card(R) 其中Card(R)-Card(S)在S包含R中所有元組時Card(R)-Card(S)=0。 結果關系基數(shù)：Card(T)=(2Card(R)-Card(S)/2,存取優(yōu)化的理論基礎,28,2020/7/29,聯(lián)接運算 S=RT，（R.a=T.b） 基數(shù)：存在Card（S） Card（R） Card（T） 具體分下面幾種情況： 基本計算形式（為聯(lián)接選擇度） Card（S）=* Card（R）* C

20、ard（T） 若b為關鍵字，a為外來關鍵字 Card（S）= Card（R） 關系的寬度： Length（S）= Length（R）+ Length（T） Length（S.a）= Length（R.a）,存取優(yōu)化的理論基礎,通常：Card(RT)=Card(R)*Card(T)/max(Val(R,a),Val(T,a),R中1個元組可能有T中的Card(T)/VAL(T,a)個元組聯(lián)接,29,2020/7/29,聯(lián)接運算 S=RT，（R.a=T.b） 不同值的個數(shù)： 設a為聯(lián)接屬性 Val(S,a)Min(Val(R,a), Val(T,b) 若c不為聯(lián)接屬性 Val（S，c）Val（R，

21、c）(c為R的屬性 ) Val（S，c）Val（T，c）(c為T的屬性 ),存取優(yōu)化的理論基礎,30,2020/7/29,半聯(lián)接運算 S=RT，（R.a=T.b） 半聯(lián)接操作是全聯(lián)接操作的一種縮減。是一種導出操作，且具有不對稱性。如：半聯(lián)接操作（RT）是R與T自然連接后在R上的投影，描述為：RT=Attr（R）(R T) 存在：Card（RT）Card（R） RT TR 基數(shù)： Card（S）=* Card（R）為半聯(lián)接選擇度 關系的寬度：Length（S）= Length（R） 不同值的個數(shù)： a.設a為聯(lián)接屬性 Val（S，a）=* Val（R，a） b.若c不為聯(lián)接屬性 Val（S，c）

22、Val（R，c）,存取優(yōu)化的理論基礎,(RaT)=,31,2020/7/29,存取優(yōu)化的理論基礎,笛卡爾積 基數(shù): Card(T)= Card(R)* Card(S) 元組的長度: Length(T)=Length(R)+ Length(S) 屬性不同值的數(shù)量: 笛卡爾積結果關系中屬性不同值的數(shù)量等于其原關系中 對應屬性的不同取值的數(shù)量： Val(T, A)= Val(R, A) 或者 Val(T, A)= Val(S, A),32,2020/7/29,對聯(lián)接操作的優(yōu)化有兩種趨勢，一種為采用半聯(lián)接技術，減少聯(lián)接操作的操作數(shù)，以降低傳輸費用；另一種為采用全聯(lián)接技術，主要考慮局部代價。一個系統(tǒng)需根

23、據(jù)其目標綜合確定其優(yōu)化算法。 半聯(lián)接的作用-1 采用半聯(lián)接技術的優(yōu)化目標是減少聯(lián)接操作的操作數(shù)，以降低傳輸費用。,半聯(lián)接優(yōu)化方法,33,2020/7/29,半聯(lián)接的作用,半聯(lián)接優(yōu)化方法,假設有雇員關系EMP和部門關系DEPT， EMP：Card（EMP）=10000；DEPT：Card（DEPT）=100 其中，關系EMP保存在場地S1，關系DEPT保存在場地S2，如下圖所示。 現(xiàn)有查詢要求：在場地S2上查詢部門名稱和部門經(jīng)理姓名，選擇最優(yōu)的執(zhí)行策略，這里只考慮數(shù)據(jù)傳輸代價。查詢的SQL語句如下： SELECT DNAME, ENAME FROM DEPT, EMP WHERE DEPT.Mg

24、rNO =EMP.ENO 關系代數(shù)表達式為： Q=DNAME，ENAME(DEPTEMP),34,2020/7/29,半聯(lián)接的作用 下面通過三種查詢策略分析其代價評估（COST） 策略1：執(zhí)行場地設在S2 需將EMP的Eno和Ename屬性傳送到S2場地 COST = (Length(Eno)+Length(Ename)* Card(EMP) = 39*10000=39KB,半聯(lián)接優(yōu)化方法,35,2020/7/29,半聯(lián)接的作用 策略2：執(zhí)行場地設在S1 需將DEPT的Dname和Mgno屬性傳送到S1場地，操作 后，再將結果傳回場地S2。設R為結果。 COST1=(Length(Dname)

25、+Length(Mgno)*Card(DEPT) =39*100=3.9KB COST2=(Length(Dname)+Length(Ename)* Card(R) =70*100=7KB COST= COST1+ COST2=10.9KB,半聯(lián)接優(yōu)化方法,36,2020/7/29,半聯(lián)接的作用 策略3：采用半聯(lián)接 將DEPT的Mgno屬性傳送到S1場地， 即將D1=Mgno（DEPT）傳送到S1場地。 COST1=Length(Mgno)*Card(DEPT)=4*100=0.4KB 在場地S1。完成EMP與D1的聯(lián)接，即實現(xiàn)E1=EMPD1， 則：Card（E1）=100。 將E1的屬性E

26、no和Ename傳到S2， 即將E2=Eno，Ename（E1）傳到S2。 COST2=(Length(Eno)+Length(Ename)* Card(E1) =39*100=3.9KB 在場地S2上計算： R=DEPT E2。 COST= COST1+ COST2=0.4+3.9=4.3 KB。 策略3相當于：EMP DEPT=（EMP DEPT）DEPT。 實現(xiàn) 實現(xiàn),半聯(lián)接優(yōu)化方法,查詢場地,37,2020/7/29,半聯(lián)接優(yōu)化算法 輸入信息：位于不同場地上的兩個關系R和S 輸出信息：實現(xiàn)RS（R.A=S.B） 算法：（設S的尺寸小于R） （1）在S所在場地上計算S=B（S）; （2）

27、傳送S到R場地 （3）在R場地上計算R=RS=RS （4）將R傳到S所在場地 （5）在S所在場地上計算 RS =（RS）S= RS,半聯(lián)接優(yōu)化方法,38,2020/7/29,傳輸代價的比較 假設： 關系R和S分別在不同的場地上，C0為啟動代價，C1為單位傳輸代價。 設：在S所在的場地上執(zhí)行，則傳輸關系R實現(xiàn)RS的代價 C=C0+C1*(Length(R)* Card(R) ) = C0+C1*Size(R),半聯(lián)接優(yōu)化方法,39,2020/7/29,傳輸代價的比較 采用半聯(lián)接的傳輸代價（見半聯(lián)接優(yōu)化算法：需傳輸S和R） C= CS+ CR = C0+C1*(Length(S)* Card(S)

28、+ C0+C1*(Length(R)* Card(R) =2 C0+C1*(Length(S)* Card(S)+ Length(R)* Card(R) =2 C0+C1*(Size(S)+ Size(R) 分析：如果有：CC 則：C0+C1*Size(R)2 C0+C1*(Size(S)+ Size(R) C0/C1+ Size(S)+ Size(R)Size(R),半聯(lián)接優(yōu)化方法,40,2020/7/29,SDD-1是美國采用ARPANET遠程網(wǎng)建立的世界上第一個分布式數(shù)據(jù)庫管理系統(tǒng)。該系統(tǒng)為人們進一步理解和解決分布式數(shù)據(jù)庫中的一些問題做出了很大貢獻。SDD-1的查詢優(yōu)化就是對片段數(shù)據(jù)使用

29、選擇、投影、半聯(lián)接操作來最大限度地縮減。SDD-1具體算法由兩部分組成：一是根據(jù)評估縮減算法確定一個收益最大的執(zhí)行策略，但此執(zhí)行策略的效率可能不一定高；二是進行后優(yōu)化處理，將基本算法得到的解進行修正，以得到更合理的執(zhí)行策略。,SDD-1系統(tǒng)優(yōu)化技術,41,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,優(yōu)化模型 在SDD-1算法中，分別使用連接圖（join graph）和概要圖來描述查詢中的條件限制和在關系上的特征參數(shù)。 例如： SELECT S.SNAME FROM SUPPLIER S, PARTS P, SUPPLY SP WHERE S.S#=SP.S# AND SP.P#=P.P# AN

30、D S.CITY=”Shanghai” 連接圖 圖的節(jié)點表示關系，邊表示連接運算，邊上標號表示連接條件，節(jié)點上標號表示關系名和場地。如下圖表示形式。,42,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,優(yōu)化模型 關系的概要圖 主要用于表示一個關系上的特征參數(shù)，其中數(shù)據(jù)包括關系中元組數(shù)量Card(R)、每個關系屬性的長度Length(A)和屬性不同值的數(shù)量Val(R,A)。 如：關系SUPPLYS#, P# , QUANTITY ，Card(R)=30000，則關系SUPPLY的概要圖表示為：,43,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,查詢代價與收益估計 SDD-1算法的基本優(yōu)化思想： 聯(lián)

31、接圖中的每個關系都用一元運算進行局部縮減； 對受益半聯(lián)接集合中的所有半聯(lián)接進行操作，逐個找出最優(yōu)的操作； 選擇一個要求最少傳輸代價的場地，執(zhí)行操作。 受益半連接集：對于一個給定的半連接集合，所有利益超過代價的半聯(lián)接操作的集合，稱為受益半聯(lián)接集，記為P。,44,2020/7/29,比傳輸R減少了（1）倍的數(shù)據(jù),SDD-1系統(tǒng)優(yōu)化技術,查詢代價與收益估計（利益代價模型） 半連接的代價：傳輸關系在連接屬性上的投影關系的代價。 假設關系R和S在不同場地上，連接屬性為A，使用半連接算法將增加傳輸Size (A(S)的通信代價，則半連接RAS的代價計算如下： Cost(RAS) = C0+C1*Val(S

32、, A)* Length(S.A) 其中C0是通信啟動代價，C1是傳輸單位數(shù)據(jù)的代價。 如果兩個連接關系在同一場地，則傳輸代價為0。 半連接的利益：半連接的利益是因半連接而節(jié)省了不需要傳輸?shù)脑M所對應的傳輸代價。 對于半連接RAS，其利益可以看作是由原來傳輸關系R減少到傳輸R的差值，計算公式如下： Benefit(RAS)= C1*(1-)*Card(R)* Length(R) 其中，為連接的選擇度，Length(R)為關系R的一個元組的長度。,45,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,查詢代價與收益估計（利益代價模型）,代價： SR,獲益： RS,R,S,S1,S2,R.A=S.A,

33、直接連接,（1）Size (R),半連接,（1）Size (A(S),R=RS,（2）Size (R),RS=RS,46,2020/7/29,基本優(yōu)化算法 輸入信息：查詢聯(lián)接圖及關系概要圖 輸出信息：半聯(lián)接執(zhí)行序列集合P及最后的執(zhí)行場地 Begin /*初始化*/ 包含所有可執(zhí)行的一元操作和局部操作，構成執(zhí)行策略集P； 計算所有的半聯(lián)接的代價和利益，構成受益半聯(lián)接集P。 /*選擇半聯(lián)接*/ While （存在滿足（Benefit（） Cost（） ） P= P|為最大受益半聯(lián)接 修改概要圖（最大受益半聯(lián)接執(zhí)行結果的概要圖）； 重新估計執(zhí)行后的各個半聯(lián)接的代價和利益； /*選擇執(zhí)行場地*/ FO

34、R I=1，n 計算在場地Si上執(zhí)行聯(lián)接運算的網(wǎng)絡傳輸代價Cost（Si） SR=Min Cost（S1），Cost（S2），Cost（Sn） End,SDD-1系統(tǒng)優(yōu)化技術,47,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例: 已知有三個關系（供應商Supplier、供應關系Supply和部門Dept），分別存在場地S1、S2和S3上，其模式信息、查詢連接圖和概要圖如下： 關系模式 供應商Supplier S(Sno, Sname, City) 供應關系Supply Y(Sno, Dno) 部門Dept D(Dno, Dname, Type) 連接圖（SupplierSupplyDept

35、）,48,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例: 概要圖：,查詢要求：找出部門名稱為“產(chǎn)品開發(fā)”、供應商城市在“紐約”的供應商的編碼和名稱，對應SQL語句如下： SELECT S.Sno，S.Sname FROM Supplier S，Supply Y，Dept D WHERE S.Sno=Y.Sno AND Y.Dno=D.Dno AND D.Dname=”產(chǎn)品開發(fā)” AND S.City=”紐約”,49,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例 步驟1：初始化 (1) 處理一元操作局部約減 執(zhí)行一元選擇操作Dname=”產(chǎn)品開發(fā)”，有Card( Dept)= Card(

36、Dname=“產(chǎn)品開發(fā)“(Dept)=Card(Dept)/Val(Dept, Dname) =100/5=20 選擇度 D = 1/ Val(Dept, Dname)=1/5 由于Dno 為關鍵字，因此有Val(Dept, Dno)= *Val(Dept, Dno)=20 執(zhí)行一元選擇操作City=”紐約”，有Card(Supplier)= Card( Supplier.City=”紐約” (Supplier) = Card(Supplier)/Val(Supplier, City)=2000/10=200 選擇度 S = 1/ Val(Supplier, City)=1/10 同理，Val

37、(Supplier, Sno)= *Val(Supplier, Sno)=200 關系Supplier和Dept參與連接操作的概要圖修改為：,50,2020/7/29,舉例 (2) 初始的利益代價表 假設：C0=0，C1=1 DOM（Supply.Sno） DOM （Supplier.Sno） DOM（Supply.Dno） DOM（Dept.Dno） 求可能的半聯(lián)接集合 P1= SupplySupplier，P2= SupplyDept P3= SupplierSupply，P4= DeptSupply 初始的利益代價表 對于： P1= SupplySupplier 因為DOM(SUPPLY

38、.SNO) DOM(SUPPLIER.SNO)。 1=s=0.1 Benefit1=(1- 1)*Card(Supply)*length(Supply)=0.9*5000*(2+4)=27K Cost1= Val（Supplier,Sno）*length(Supplier,Sno) =200*4=0.8K,SDD-1系統(tǒng)優(yōu)化技術,51,2020/7/29,舉例 對于：P2= SupplyDept 2=20/100=0.2 Benefit2=(1-2)*Card(Supply)*length(Supply)=0.8*5000*6=24K Cost2= Val(Dept,Dno)*length(D

39、ept,Dno) =20*2=0.04K 對于： P3= SupplierSupply 3=Val(SUPPLY, SNO)/Card(DOM(SUPPLIER.SNO) = 1000/2000 =0.5 ， Cost3= Val(SUPPLY, SNO)* Length (SUPPLY, SNO)=1000*4=4K Benefit3=(1-3)*200*24=2.4K 對于： P4= DeptSupply 4=Val(DeptSupply,Dno)/Val(Dept,Dno) 均勻分布下，4近似為1， Benefit4近似為0； Cost4=100*2=0.2K 因此，初始的利益代價表如下

40、：,根據(jù)初始的利益代價表，得到受益半聯(lián)接集P=P1，P2,SDD-1系統(tǒng)優(yōu)化技術,P1= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSupply,52,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,P1= SupplySupplier,舉例 步驟2：選擇半連接 循環(huán)1：選擇利益代價最好者 重新計算概要圖 Card(SUPPLY)=1* Card(SUPPLY) = 0.1*5000=500 SUPPLY中SNO不同值的個數(shù)，SNO屬于連接謂詞且均勻分布： Val(SUPPLY, SNO)=* Val(SUPPLY, SNO)

41、 = 0.1*1000=100 SUPPLY中DNO的不同值個數(shù)，DNO不屬于連接謂詞： Val(SUPPLY, DNO)=100，由于Card(SUPPLY)2Val(SUPPLY, DNO)，因此：Val(SUPPLY, DNO)= Val(SUPPLY, DNO)=100 三個關系的概要圖更新為如下 ：,53,2020/7/29,舉例 重新計算利益代價表 P2= SupplyDEPT Val(SUPPLY,DNO)與Val(DEPT,DNO)同比例縮減，因此2=0.2 Benefit2=(1-2)*Card(SUPPLY)*Length (SUPPLY) = 0.8*500*6=2.4K

42、 Cost2= Val(DEPT,DNO)* Length (DEPT,DNO)= 20*2=0.04K P3= SupplierSupply 由于DOM(SUPPLY.SNO) DOM(SUPPLIER.SNO)，因此3 = Val(SUPPLY, SNO)/ Val(SUPPLIER, SNO)= 100/200 =0.5 Benefit3=(1-3)*Card(SUPPLIER)*Length (SUPPLIER) =0.5*200*24=2.4K Cost3= Val(SUPPLY, SNO)* Length (SUPPLY, SNO)=100*4=0.4K P4= DeptSuppl

43、y 近似為1 ，Benefit4近似為0,SDD-1系統(tǒng)優(yōu)化技術,P1= SupplySupplier= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSupply,54,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例 循環(huán)2 從受益半聯(lián)接集P中選擇利益代價最小者P2， 將P2加到策略集P中，得：P=，P2，P1。 重新計算概要圖 對于外連接SUPPLY DEPT，需要更新SUPPLY 的概要圖內容，假設外連接后結果為SUPPLY(SNO,DNO)，則對于SUPPLY有： Card(SUPPLY)=* Card(SUPPLY

44、) = 0.2*500=100 DNO屬于連接謂詞： Val(SUPPLY, DNO)= * Val(SUPPLY, DNO) = 0.2*100=20 SNO不屬于連接謂詞： Val(SUPPLY, SNO)=100， 由于1/2(SUPPLY, SNO)Card(SUPPLY)2Val(SUPPLY, SNO)，因此：Val(SUPPLY, SNO)= 1/3*(Val(SUPPLY, SNO)+ Card(SUPPLY)=1/3*(100+100)=200/3,P1= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSup

45、ply,55,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例 循環(huán)2 三個關系的概要圖更新為如下,P1= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSupply,56,2020/7/29,舉例 重新計算利益代價表 P3= SUPPLIER SUPPLY 由于DOM(SUPPLY.SNO) DOM(SUPPLIER.SNO)，選擇度為： 3=Val(SUPPLY, SNO)/Val(SUPPLIER, SNO)=200/3/200 =1/3 Benefit3=(1-3)*Card(SUPPLIER)*Length (SUP

46、PLIER) =0.67*200*24=3.2K Cost3= Val(SUPPLY, SNO)* Length (SUPPLY, SNO)=200/3*4=0.27K P4= DEPT SUPPLY，4近似為1 ，Benefit4近似為0。,SDD-1系統(tǒng)優(yōu)化技術,P1= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSupply,57,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,P1= SupplySupplier P2= SupplyDept P3= SupplierSupply P4= DeptSupply,舉例 循環(huán)

47、3 從受益半聯(lián)接集P中選擇P3添加到策略集P中，得：P=，P3，P2，P1。 重新計算概要圖 對于外連接SUPPLIER SUPPLY，需要更新SUPPLIER的概要圖內容，假設外連接后結果為SUPPLIER(SNO,SNAME)，則對于SUPPLIER有： Card(SUPPLIER)=* Card(SUPPLIER) = 1/3*200=200/3 SNO屬于連接謂詞，因此： Val(SUPPLIER, SNO)= * Val(SUPPLIER, SNO) = 1/3*200=200/3 SNAME不屬于連接謂詞，因此： Card(SUPPLIER)=200/3 Val(SUPPLIER,

48、 SNO)/2=100 所以val(supplier,sno)=Card(SUPPLIER)=200/3 三個關系的概要圖更新為如下：,58,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,舉例 重新計算利益代價表 P4= DEPT SUPPLY 4近似為1；Benefit4近似為0； 此時已經(jīng)沒有受益半連接，循環(huán)結束。,步驟3：選擇執(zhí)行場地 根據(jù)最終的概要圖計算各場地上的數(shù)據(jù)量： Size(S1) =Size(SUPPLIER)=200/3*24=1.6K Size(S2) =Size(SUPPLY)=100*6=0.6K Size(S3) =Size(DEPT)=20*4=0.08K 可以看出

49、場地S1包含的數(shù)據(jù)量最多，因此選擇S1作為執(zhí)行場地能夠獲得最小的傳輸代價。查詢的最終傳輸代價為：Cost = Cost(Semijoin)+Cost(assembly)=(0.8+0.04+0.27)+(0.6+0.08)=1.79K 其中Cost(Semijoin)表示半連接所需要的傳輸代價，Cost(assembly)表示最后執(zhí)行連接時所需的傳輸代價。,59,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,SDD-1 后優(yōu)化處理 SDD-1算法的后優(yōu)化處理的目的是通過考慮半連接的間接影響對優(yōu)化后的執(zhí)行策略進行修改，以進一步減少通信代價。后優(yōu)化處理主要基于以下兩個規(guī)則對執(zhí)行策略優(yōu)化： 準則1 在

50、執(zhí)行策略集中，消去用于縮減處于執(zhí)行場地上的關系的半連接操作。 本例中，最終的執(zhí)行場地為S1，在得到執(zhí)行策略集P=P3，P2，P1中，在執(zhí)行策略集中半連接P3= SUPPLIER SUPPLY為縮減S1上關系SUPPLIER，根據(jù)準則1可以將P3從策略集中消去以減少優(yōu)化代價。,總代價= Cost = Cost(半連接)+Cost(全連接) = Cost(P2)+ Cost(P1)+ Cost(遷移supply和DEPT至S1場地) =(0.8+0.04)+(0.6+0.08)=1.52K,60,2020/7/29,SDD-1系統(tǒng)優(yōu)化技術,SDD-1 后優(yōu)化處理 準則2 延遲執(zhí)行代價高的半聯(lián)接，以

51、盡可能利用已縮減的關系。,例：有關系R、S、T，分別存在場地S1、S2和S3上，聯(lián)接圖如下：,求：實現(xiàn)RST。假設：實現(xiàn)如下，,方法1,示意,T= TS S= S R S= S T,61,2020/7/29,從優(yōu)化實現(xiàn)可知， 方法2中的步的實現(xiàn)同方法1的步實現(xiàn)順序不同，其目的是方法2中第步可以利用第步的已縮減的S。即盡可能利用已縮減的關系，使整體傳輸代價降低。,SDD-1系統(tǒng)優(yōu)化技術,SDD-1 后優(yōu)化處理 準則2 延遲執(zhí)行代價高的半聯(lián)接，以盡可能利用已縮減的關系。,方法2, S = S R T = T S S= S T,示意,方法1,62,2020/7/29,半聯(lián)接技術的不足 半聯(lián)接技術是通

52、過局部縮減操作縮減關系的數(shù)據(jù)量，發(fā)送縮減的關系到執(zhí)行場地，在執(zhí)行場地對縮減后的關系進行查詢處理。 優(yōu)點是大大降低了場地間傳遞的信息量，減少了整個系統(tǒng)的傳輸代價。 不足是增加了系統(tǒng)的局部處理代價： （1） 沒有考慮局部代價； 如 ：RS= （RS）S= RB（S） B（S）的代價 RB（S）的代價 （2）當選擇度較低時，半聯(lián)接技術才可行。 因此，在應用半聯(lián)接技術時，要考慮其適應的環(huán)境。,SDD-1系統(tǒng)優(yōu)化技術,63,2020/7/29,查詢操作的代價評估：綜合考慮局部代價和傳輸代價。 若側重傳輸代價，局部代價可以忽略不計時，采用半聯(lián)接技術較好； 側重局部代價時，采用直接聯(lián)接比采用半聯(lián)接優(yōu)越。 枚

53、舉法是基于直接聯(lián)接的實現(xiàn)方法。,枚舉法優(yōu)化技術,64,2020/7/29,常見的直接連接算法主要有： 嵌套循環(huán)連接算法(nest-loop) 歸并排序連接算法（merge-scan） 哈希連接算法（Hash） 基于索引的連接算法 對每種直接連接算法進行代價估計：考慮執(zhí)行連接操作所需的磁盤I/O代價。 對磁盤I/O代價的估計主要依賴于數(shù)據(jù)庫的特征參數(shù)。,枚舉法優(yōu)化技術,65,2020/7/29,嵌套循環(huán)連接算法 是一種最簡單的連接算法，原理是對連接操作的兩個關系中的一個僅讀取其元組一次，而對另一個關系中的元組將多次讀取。 特點是可以用于任何大小的關系間的連接操作，不必受連接操作所分配的內存空間大

54、小的限制。,枚舉法優(yōu)化技術,假設有關系R(A,B)和S(B,C)，Card(R)=n，Card(S)=m，現(xiàn)在要執(zhí)行兩個關系在屬性B上的連接操作.,66,2020/7/29,基于元組的嵌套循環(huán)連接 循環(huán)以關系中的元組為單位進行操作，具體的執(zhí)行算法如下： Result= /*初始化結果集合*/ For each tuple s in S For each tuple r in R If r.B=s.B Then /*元組r和元組s滿足連接條件*/ Join r and s as tuple t； Output t into Result；/*輸出連接結果元組*/ End If End For E

55、nd For Return Result,枚舉法優(yōu)化技術,外關系S,內關系R,67,2020/7/29,基于元組的嵌套循環(huán)連接 在執(zhí)行嵌套循環(huán)連接時，僅對外關系進行1次讀取操作，而對內關系則需要進行多次讀取。 如果不進行優(yōu)化的話，執(zhí)行代價很大，以磁盤IO代價計算最多可能多達Card(S)*Card(R) =mn次。 通常對這種算法進行修改，一種方法是通過盡可能多地使用內存以減少磁盤IO次數(shù)；另一種方法是使用連接屬性上的索引，以減小參與連接元組的數(shù)量。,枚舉法優(yōu)化技術,68,2020/7/29,基于塊的嵌套循環(huán)連接 通過盡可能多的使用內存，減少讀取元組所需的I/O次數(shù)。 對連接操作的兩個關系的訪

56、問均按塊（也稱為頁面）進行，同時使用盡可能多的內存來存儲嵌套循環(huán)中外關系的塊。 假設：為連接操作分配的內存緩沖區(qū)大小為M個塊，有Block(R)Block(S)M， 實現(xiàn)過程：首先選取較小的關系作為外關系，本例即關系S。將1到M-1塊分配給關系S,第M塊分配給關系R。 將外關系S按照M-1個塊的大小分為多個子表，并重復地將這些子表讀取到內存緩沖區(qū)中，用于重復地依次讀取關系R的每一個塊。 對于內存緩沖區(qū)中元組的連接操作，先在M-1個塊的外關系S元組的連接屬性上構建查找結構，再從內關系R在內存中的塊中取元組，通過查找結構與S中的元組連接。,枚舉法優(yōu)化技術,69,2020/7/29,基于塊的嵌套循環(huán)

57、連接 算法： Result= /*初始化結果集合*/ Buffer=M /*內存緩沖區(qū)*/ For each M-1 in Block(S) /*每次從外關系S中讀取M-1個塊到內存緩沖區(qū)*/ Read M-1 of Block(S) into Buffer； For each block in Block(R) /*每次從內關系R中讀取1個塊到內存緩沖區(qū)*/ Join M-1 of Block(S) and 1 of Block(R) in Buffer;/*在內存中對元組執(zhí)行連接*/ Output t into Result; End For End For Return Result,枚

58、舉法優(yōu)化技術,70,2020/7/29,基于塊的嵌套循環(huán)連接方法的代價估計 假設R和S占用的塊分別為Block(R)和Block(S)，M為內存緩沖區(qū)大小（塊數(shù)）。一次I/O可讀取一個數(shù)據(jù)塊。則共需讀取關系S的塊數(shù)為Block(S)，共需讀取R的塊數(shù)為Block(R)* Block(S)/(M-1)。,枚舉法優(yōu)化技術,說明： 如果連接關系Block(R)*Block(S)的值遠遠大于內存緩沖區(qū)大小M時，認為連接的代價近似等于Block(R)*Block(S)。 這種算法能夠適用于任意大小的關系之間的連接執(zhí)行，因此基于塊的嵌套循環(huán)連接算法依然廣泛應用于現(xiàn)有的數(shù)據(jù)庫系統(tǒng)中。,71,2020/7/2

59、9,嵌套循環(huán)連接方法舉例 假設連接的兩個關系R和S，Block(R)=2000，Block(S)=500，內存緩沖區(qū)M=51。則： 外關系為S 內存分配：M-1=50分配給S，再循環(huán)讀取關系R的2000個塊。 根據(jù)公式： 連接的執(zhí)行代價為： 500/(51-1)*2000+500=20500次磁盤IO。,枚舉法優(yōu)化技術,72,2020/7/29,基于排序的連接算法 首先將兩個關系按照連接屬性進行排序(分段排序+歸并) 然后按照連接屬性的順序掃描兩個關系，同時對兩個關系中的元組執(zhí)行連接操作。 簡單的歸并排序算法的執(zhí)行過程,枚舉法優(yōu)化技術,73,2020/7/29,簡單基于排序的連接算法 對已經(jīng)按照連接屬性排序的兩個關系，按照順序讀取關系中的塊到內存中執(zhí)行連接操作。,枚舉法優(yōu)化技術,執(zhí)行代價