第3章-分布式數(shù)據(jù)庫的查詢處理與優(yōu)化

第3章分布式數(shù)據(jù)庫的查詢處理與優(yōu)化2012.02長沙理工大學(xué)計(jì)通學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系李春芳2/14/20231內(nèi)容概要分布式數(shù)據(jù)查詢分布式數(shù)據(jù)查詢優(yōu)化2/14/20232集中式數(shù)據(jù)庫查詢總代價(jià)是以查詢期間的CPU代價(jià)和I/O代價(jià)來衡量的。分布式數(shù)據(jù)庫查詢優(yōu)化通常有兩個(gè)標(biāo)準(zhǔn)：一個(gè)是以總代價(jià)最小為標(biāo)準(zhǔn)。另一個(gè)是以每個(gè)查詢的響應(yīng)時(shí)間最短為標(biāo)準(zhǔn)。3.1分布式數(shù)據(jù)查詢2/14/20233分布式數(shù)據(jù)處理環(huán)境可分為：遠(yuǎn)程通訊網(wǎng)絡(luò)環(huán)境高速局域網(wǎng)

2/14/20234查詢分解數(shù)據(jù)本地化全局優(yōu)化局部優(yōu)化分布式數(shù)據(jù)查詢處理層次結(jié)構(gòu)

2/14/20235查詢分解數(shù)據(jù)本地化全局優(yōu)化局部優(yōu)化分布關(guān)系上的代數(shù)表達(dá)分段關(guān)系查詢表達(dá)帶有通訊操作的段查詢優(yōu)化優(yōu)化的局部查詢表達(dá)全局模式段模式片段統(tǒng)計(jì)局部模式分布式查詢問題全局查詢代數(shù)表達(dá)式片段查詢包括通信操作的優(yōu)化片段上查詢2/14/20236代價(jià)公式

QC=I/O代價(jià)+CPU代價(jià)+通訊代價(jià)通訊代價(jià)

TC（X）=C0+(X*C1)C0為兩站點(diǎn)間通信初始化一次所花費(fèi)的時(shí)間，由通信系統(tǒng)定，幾乎是一個(gè)常數(shù)，以秒為單位；C1為傳輸速度的倒數(shù)，單位是B/S，X為數(shù)據(jù)傳輸量，以Bit為單位。分布式數(shù)據(jù)查詢策略的重要性2/14/20237

例：數(shù)據(jù)庫S(s#,sname,age,sex)有104個(gè)元組，存放在SiteA，C(c#,cname,teacher)有105個(gè)元組，存放在SiteB，SC(s#,c#,grade)有106個(gè)元組，存放在SiteA。其中每個(gè)元組長度100Bit，通訊傳輸速度104bit/sec，通訊延遲為1sec。S,SCCSiteASiteB2/14/20238應(yīng)用：查出所有選修maths課的男生學(xué)號(hào)和姓名

SELECTs#,snameFROMS,C,SCWHERES.s#=SC.s#AND

C.c#=SC.c#ANDsex=‘男’AND

cname=‘maths’;2/14/20239策略1:

A傳CB

把關(guān)系C傳輸?shù)紸地,在A地處理查詢

○

○

T1=1+(10**5*100/10**4)S,SC

通信1次C≈10**3秒

≈16.7秒

A傳S,SCB

把關(guān)系S和SC傳輸?shù)紹地,在B地處理查詢

○

○

T2=(2+10**4+10**5)*100/10**4S,SC通信2次C≈10100秒

≈28小時(shí)

A問10**5B

先在A地求出男學(xué)生的成績?cè)M有10**5

○

○

再根據(jù)C#的值詢問B地,核實(shí)是否C=‘MATHS’S,SC答10**5CT3≈(2*10**5*1)=2*10**5秒

≈2.3天策略2:策略3:2/14/202310

A

問10

B

先在B地求出‘MATHS’的元組,有10個(gè)

○

○

再根據(jù)C#的值詢問A地的S，SC的連接，S,SC

答10

C

核實(shí)是否為選修‘MATHS’的男生

T4≈(2*10*1)=20秒

A傳輸10**5

B

先在A地求出男生選課元組，有10**5個(gè)

○

○

再把結(jié)果傳輸?shù)紹地,在B地執(zhí)行查詢，S,SC

通信1次CT5=1+(10**5*100)/10**4

≈1000秒

≈16.7分

A傳輸10

B

先在B地求出為‘MATHS’的元組，有10個(gè)

○

○

再把結(jié)果傳輸?shù)?/p>

A

地,在

A

地執(zhí)行查詢，S,SC

通信1次C

T6=1+(10*100)/10**4≈1秒策略

4：

策略

5：

策略

6：2/14/202311結(jié)論：一個(gè)好的查詢處理應(yīng)該使數(shù)據(jù)的傳輸量和通信次數(shù)最少，這樣才能使查詢所花費(fèi)的數(shù)據(jù)傳輸和/或通信時(shí)間最少，從而減少查詢的總代價(jià)。2/14/202312

SQL語句

SQL是關(guān)系型數(shù)據(jù)庫的標(biāo)準(zhǔn)查詢語言，如：SELECTsnameFROMS,SCWHERES.s#=SC.s#andSC.c#=‘c03’;

關(guān)系代數(shù)式

sname(s.s#=SC.s#andSC.c#=‘c03’(S×SC))

查詢樹

對(duì)一個(gè)關(guān)系代數(shù)表達(dá)式表示的查詢進(jìn)行語法分析，可以得到一棵語法樹。分布式數(shù)據(jù)查詢表達(dá)

2/14/202313E2SELECTsnameFROMSWHERES.s#in(SELECTSC.s#FROMSCWHEREc#=‘c03’);代數(shù)描述

sname(s.s#=SC.s#(S×SC.c#=‘c03’SC))E3SELECTsnameFROMS,(SELECTSC.s#FROMSCWHEREc#=‘c03’)SCCWHERES.s#=SCC.s#;代數(shù)描述

sname(S∞

SC.c#=‘c03’SC)例：

2/14/202314局部查詢遠(yuǎn)程查詢?nèi)植樵兎植际綌?shù)據(jù)查詢分類

2/14/2023153.2分布式數(shù)據(jù)庫查詢優(yōu)化基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化處理基于半連接算法的查詢優(yōu)化處理基于直接連接算法的查詢優(yōu)化處理2/14/202316基本原理查詢問題——〉關(guān)系代數(shù)表達(dá)式分析得到查詢樹獲取基于片段的查詢樹盡可能先執(zhí)行選擇和投影操作

基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化處理2/14/202317實(shí)現(xiàn)步驟轉(zhuǎn)換一：查詢問題——〉關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換二：關(guān)系代數(shù)表達(dá)式——〉查詢樹轉(zhuǎn)換三：全局查詢樹分拆成片段查詢樹優(yōu)化：利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，優(yōu)化查詢樹，進(jìn)而優(yōu)化查詢2/14/202318優(yōu)化算法連接和合并盡可能上提（樹根方向）選擇和投影操作盡可能下移（葉子方向）2/14/202319全局關(guān)系S(S#,SNAME,AGE,SEX)和SC(S#,C#,GRADE)被水平分片hhSSCS1:SEX=‘M’男學(xué)生全體S2:SEX=‘F’女學(xué)生全體SC1：C#<=20課程號(hào)<=20SC2：C#>20課程號(hào)>20查詢問題：查找至少有一門功課成績?cè)?0分以上的男生姓名SNAME(SEX=‘M’andGRADE>90(S.S#=SC.C#(S×SC)))2/14/202320SNAMES.S#=SC.S#S.S#=SC.S#S#,SNAMES#,SNAMEGRADE>90GRADE>90SNAMESEX=‘M’

SSCSEX=‘M’US1[SEX=‘M’]S2[SEX=‘F’]USC1[C#‘C20’]SC1[C#>’C20’](a)全局關(guān)系上的查詢樹(b)對(duì)應(yīng)片段上的查詢樹

變換∞∞2/14/202321SNAMES.S#=SC.S#S.S#=SC.S#S#,SNAMES#,SNAMEGRADE>90SNAMESEX=‘M’USC1[C#‘C20’（c）把投影和選擇下移后的查詢樹(d)一個(gè)簡化的查詢樹產(chǎn)生矛盾去掉一支S#,SNAMEGRADE>90S2[SEX=‘F’]SEX=‘M’SC1[C#‘C20’]SC2[C#‘C20’]S1[SEX=‘M’]SC2[C#‘C20’S1[SEX=‘M’]UUGRADE>90]GRADE>90]∞∞2/14/202322基于水平分片的查詢優(yōu)化基本思想：盡量把選擇條件下移到分片的限定關(guān)系處再把分片的限定關(guān)系與選擇條件進(jìn)行比較去掉它們之間存在矛盾的相應(yīng)片段如果最后剩下一個(gè)水平片段，則重構(gòu)全局關(guān)系的操作中，就可去掉“并”操作（至少可以減少“并”操作的次數(shù)）2/14/202323vSE1E2:查詢問題：雇員的姓名和工資情況ENAME,SALARY(EMP)全局關(guān)系EMP(EMP#,ENAME,SALARY,DEPT#,DNAME)垂直分片：E1(EMP#,DEPT#,DNAME)EMP2(EMP#,ENAME,SALARY)2/14/202324ENAME,SALARYENAMEEMP#,DEPT#,EMP#,ENAME,DEPTNAMESALARYENAME,SALARYEMP#,ENAME,SALARYENAME,SALARYEMPE2:EMP#,ENAME,SALARY去掉無關(guān)的片段

移植到片段上去掉連接E1：E2：E1.EMP#=E2.EMP#∞∞2/14/202325基于垂直分片的查詢優(yōu)化的基本思想：把垂直分片所用到的屬性集，與查詢條件中的投影操作所涉及的屬性相比較，去掉無關(guān)的垂直片段。如果最后只剩下一個(gè)垂直片斷與查詢有關(guān)時(shí)，去掉重構(gòu)全局關(guān)系的“連接”操作（至少可以減少“連接”操作的次數(shù)）2/14/202326假定有兩個(gè)關(guān)系R,S,在屬性R.A=S.B上做半連接操作，可表示為：R∝A=BS=R(R∞A=BS)=R∞A=B(B(S))S∝A=BR=S(S∞A=BR)=S∞A=B(A(R))用半連接表示連接操作R∞A=BS=(R∝A=BS)∞A=BS=R∞A=B(B(S))∞A=BSR∞A=BS=(S∝A=BR)∞A=BR=(S∞A=B(A(R))∞A=BR

基于半連接算法的查詢優(yōu)化處理2/14/202327RS網(wǎng)絡(luò)

站點(diǎn)1

站點(diǎn)2

(1)

B(S)(3)R’=R∝A=BB(S)(2)B(S)(4)R’=R∝A=B

B(S)(5)R’∞A=BS采用半連接方法表示連接操作過程圖2/14/202328直接把R送到站點(diǎn)2上執(zhí)行連接操作（假定關(guān)系R的數(shù)據(jù)量小于關(guān)系S的數(shù)據(jù)量），其代價(jià)為：

T全=C0+C1*size(B)*card(R)基本原理是在傳到另一個(gè)站點(diǎn)做連接前，消除與連接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價(jià)。2/14/202329結(jié)論：采用半連接實(shí)現(xiàn)連接操作需要兩次傳輸：連接屬性投影結(jié)果和半連接結(jié)果。但在通常情況下，T半<<T全。半連接的得益：當(dāng)card（R）>>card（R’），可減少站點(diǎn)間的數(shù)據(jù)傳輸量半連接的損失：傳輸B(S)=C0+C1*size(B)*val(B[S])2/14/202330采用半連接優(yōu)化算法的步驟計(jì)算每種半連接方案的代價(jià)，并從中選擇一種最佳方案選擇傳輸代價(jià)最小的站點(diǎn)，計(jì)算采用全連接的方案的代價(jià)比較兩種方案，確定最優(yōu)方案2/14/202331采用半連接將會(huì)導(dǎo)致通信次數(shù)的增加和本地處理時(shí)間的增加。如果傳輸費(fèi)用是主要的，采用半連接方案處理策略比較有利。如果本地費(fèi)用是主要的，采用直接連接方案處理策略比較有利。

基于直接連接算法的查詢優(yōu)化處理2/14/202332四種基于直接連接的優(yōu)化算法利用站點(diǎn)依賴信息的算法分片與復(fù)制算法站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合算法Hash劃分算法2/14/202333

R1

R2

站點(diǎn)

關(guān)系S1S2

F11F12F21F22∪∞∞利用站點(diǎn)依賴信息的算法2/14/202334站點(diǎn)依賴設(shè)關(guān)系Ri分片F(xiàn)i1和Fi2,Rj分片F(xiàn)j1和Fj2關(guān)系Ri和Rj在屬性A上滿足條件

Fis∞AFjt=,其中st,則稱Ri和Rj在屬性A上站點(diǎn)依賴也就是說:

Ri∞ARj=U(Fis∞AFjs),對(duì)于包含著兩個(gè)關(guān)系的片段的每個(gè)站點(diǎn)s都成立此時(shí)關(guān)系的連接操作無站點(diǎn)間數(shù)據(jù)傳輸R1∞R2（F11∞F21）U（F12∞F22）=？2/14/202335推論若Ri和Rj在屬性A上站點(diǎn)依賴，則Ri和Rj在任何包含A的屬性集B上也站點(diǎn)依賴。若Ri和Rj在屬性A上站點(diǎn)依賴，另一屬性（或?qū)傩越M）B函數(shù)決定A，且A，則Ri和Rj在B上也站點(diǎn)依賴。若Ri和Rj在屬性A上站點(diǎn)依賴，且若Rj和Rk在屬性B上站點(diǎn)依賴，則（Ri∞ARj∞BRk）=（Fis∞AFjs∞BFks)查詢Ri∞ARj∞BRk的連接操作能夠以無數(shù)據(jù)傳輸?shù)姆绞教幚怼?/p>

2/14/202336

站點(diǎn)

關(guān)系S1S2

F11F12R2

R2

R1

R2分片和復(fù)制算法2/14/202337在該算法中，選擇一組站點(diǎn)，把查詢引用某個(gè)關(guān)系