分布式數(shù)據(jù)查詢處理與優(yōu)化

分布式數(shù)據(jù)查詢處理與優(yōu)化第一頁，共三十六頁，2022年，8月28日4.1問題的提出假設(shè)葡萄酒WINE(YEAR

,NAME,PRODUCT,AREA,COUNTRY)和天氣WEATHER(YEAR，AREA，COUNTRY,SUN,RAIN)的有關(guān)數(shù)據(jù)存放為：WINE-F存放在巴黎，WINE-I存放在羅馬，WINE-U存放在舊金山，WEATHER-R存放在奧斯陸，WEATHER-S存放在羅馬。另外，還在紐約存放WEATHER整個數(shù)據(jù)，現(xiàn)在的查詢?yōu)椋涸诎⒛匪固氐z索RAIN>800mm的葡萄酒的NAME，YEAR和SUN，可選的查詢方案：第二頁，共三十六頁，2022年，8月28日

調(diào)度1在紐約對WEATHER處理

WEATHER1=∏YEAR，AREA，SUN（σRAIN>

800(WEATHER)）把WEATHER發(fā)送到巴黎，羅馬，舊金山，分別在這些節(jié)點對WINE-F，WINE-I,WINE-U進行連接

RESULT1=∏NAME，YEAR，SUN(WINE-F∞WEATHER1）

RESULT2=∏NAME，YEAR，SUN(WINE-I∞WEATHER1）

RESULT3=∏NAME，YEAR，SUN(WINE-U∞WEATHER1）把RESULT1，RESULT2，RESULT3傳回阿姆斯特丹。第三頁，共三十六頁，2022年，8月28日調(diào)度2：把WINE-F，WINT-I，WINE-U發(fā)到紐約，合并成整個關(guān)系WINE。在紐約：RESULT=∏NAME，YEAR，SUN(σRAIN

>800(WEATHER)∞WINE)把結(jié)果RESULT傳到阿姆斯特丹。如何評價這兩個方案？第四頁，共三十六頁，2022年，8月28日衡量分布式查詢處理的效率是一個綜合指標，涉及下面的主要目標。系統(tǒng)的處理代價：CPU、I/O、通信。一個優(yōu)化的分布式查詢處理算法需要控制數(shù)據(jù)傳輸費用。他與數(shù)據(jù)分片策略及其單位的大小有直接關(guān)系。系統(tǒng)直接響應(yīng)時間：由于數(shù)據(jù)的分布和重復(fù)，使得查詢處理的路徑增多和并行性增大，不同的調(diào)度方案對系統(tǒng)的響應(yīng)時間有很大影響。第五頁，共三十六頁，2022年，8月28日4.2關(guān)系代數(shù)的等價變換一、算符樹用算符樹來表示對應(yīng)地查詢：例如，對關(guān)系供應(yīng)商S（S#，SNAME），產(chǎn)品P（P#，PNAME），采購B（B#，P#，S#，NUM）作如下查詢：

Q1：∏PNAME，SNAME，NUM(σNUM

>20(B)∞(S∞P));

Q2：∏PNAME，SNAME，NUM(σNUM>20(B∞S∞P));第六頁，共三十六頁，2022年，8月28日∏PNAME，SNAME，NUM∞σNUM>20∞BSP∏PNAME，SNAME，NUMσNUM>20∞P∞BS第七頁，共三十六頁，2022年，8月28日二、關(guān)系代數(shù)的等價變換

設(shè)關(guān)系代數(shù)的兩個表達式為E1，E2，如果兩個表達式的相同關(guān)系具有相同的值時，總是得到相等的結(jié)果，那么就說這兩個表達式是等價的，并用E1E2來表示。令U和B分別代表一元和二元關(guān)系代數(shù)運算，則有：一元運算的交換律：U1U2R二元運算的交換律：RBS二元運算的結(jié)合律：RB(SBT)一元運算的冪：URU2U1RSBR(RBS)BTUUR第八頁，共三十六頁，2022年，8月28日U(RBS)U(R)BU(S)U(R)BU(S)U(RBS)一元運算相對于二元運算的分配律：

一元運算的因子分解：設(shè)Attr(F)表示在一公式F中出現(xiàn)的屬性，Attr(R)表示關(guān)系R的屬性集合則:

σF1σF2RσF2σF1RσF1∏A2R∏A2σF1R∏AσFRσF∏ARσF(R∞S)(σFR)∞(σFS)∏A(R∞S)(∏A(R))∞(∏A(S))第九頁，共三十六頁，2022年，8月28日三、在分布式數(shù)據(jù)庫中為簡化查詢而應(yīng)用于等價變換的一般準則準則1:使用選擇和投影的冪等來為每個關(guān)系產(chǎn)生相應(yīng)的選擇和投影。準則2:把樹中的選擇和投影運算盡可能地向下推移（在算符樹中）。例Q：∏PNAME,SNAME,NUM(σNUM>

20(B∞S∞P));可優(yōu)化為Q*:(σNUM>20(∏PNAME,SNAME,NUMB))∞(∏PNAME,SNAME,NUMS)∞(∏PNAME,SNAME,NUMP)

●公共子表達式的問題：在查詢中多次出現(xiàn)的子表達式,應(yīng)該一次求值,多次使用。第十頁，共三十六頁，2022年，8月28日4.3把全局查詢變換成段查詢1.限定關(guān)系的代數(shù)學(xué)限定關(guān)系(QualifiedRelation)是一種帶有限定語的關(guān)系。用[R：qR]來表示一個限定關(guān)系，這里R是一個關(guān)系，而qR是一個限定語。通常qR相應(yīng)于一個分片謂語。限定關(guān)系轉(zhuǎn)換規(guī)則：規(guī)則一：σF[R:qR]規(guī)則二：∏A[R:qR]規(guī)則三：[R:qR]∞[S:qs]規(guī)則四：[R:qR]∝[S:qs]規(guī)則五：[R1:qR1]∪[R2:qR2]σF[R:FANDqR][∏AR:qR][R∞S:qRANDqs][R∝S:qRANDqs][R1∪R2:qR1ORqR2]第十一頁，共三十六頁，2022年，8月28日

2.限定關(guān)系等價如果兩個限定關(guān)系的實體是等價的關(guān)系，并且它們的限定語代表了同一真值函數(shù)(即如果我們把兩個限定語用到同一元組上，那么就得到相同的真值)，則這兩個限定關(guān)系是等價的。對于空數(shù)據(jù)分片：σF(￠)∏A(￠)R∞￠R∝￠R∪￠￠∝R￠

￠

￠￠R￠

第十二頁，共三十六頁，2022年，8月28日準則三：把選擇向下推到樹葉處，然后對它們使用限定關(guān)系代數(shù)進行轉(zhuǎn)換；如果結(jié)果的限定語是永假式，則用空關(guān)系來代替此選擇的結(jié)果。準則四：利用限定關(guān)系代數(shù)來求連接的操作數(shù)的限定語之值；如果這個連接的結(jié)果的限定語是永假式，則用空關(guān)系來代替此子樹，包括此連接及它的操作樹在內(nèi)。第十三頁，共三十六頁，2022年，8月28日3.水平分段關(guān)系的化簡例4-1對EMP(ENUM,ENAME,SAL,TAX,DNUM)建立水平分段如下：EMP1=σ

ENUM<=10（EMP）EMP2=σ

10<ENUM<=20（EMP）EMP3=σ

ENUM>20（EMP）給出查詢Q1：σ

ENUM=1（EMP）第十四頁，共三十六頁，2022年，8月28日σENUM=1

∪EMP1EMP2EMP3∪σ

ENUM=1(EMP1)σ

ENUM=1(EMP2)σENUM=1EMP1σ

ENUM=1(EMP3)σ

ENUM=1(EMP2)=σENUM=1(EMP2:10<ENUM<20ANDENUM=1)=￠第十五頁，共三十六頁，2022年，8月28日4.分段連接問題設(shè)有已分段關(guān)系R，S，實現(xiàn)R，S連接有兩種策略，第一是先合并，后連接，第2是先連接后合并（稱之為分布連接）如果有關(guān)段的條件是高度選擇的話，則采用第一種方法好；如果段與段之間的連接能達到消除大量無關(guān)段的目的，則采用第二種方法好。第十六頁，共三十六頁，2022年，8月28日準則五：為了分布實施出現(xiàn)在全局查詢中的連接運算，必須把段的合并向上推，超出分布的連接范圍。例4.2對關(guān)系EMP(ENUM,ENAME,SAL,TAX,DNUM)DEPT(DNUM,DNAME,AREA,MGRNUM)建立如下水平分段：EMP1=σDNUM

<=10(EMP)EMP2=σ10<DNUM<=20(EMP)EMP3=σDNUM>20(EMP)DEPT1=σDNUM

<=10(DEPT)DEPT2=σDNUM

>10(DEPT)給定查詢Q：(假定銷售部門編號小于10)第十七頁，共三十六頁，2022年，8月28日Q：σDNAM

=“sales”(EMP∝DEPT)σDNAM=“sales”∝∪∪EMP1EMP2EMP3DEPT1DEPT2σDNAM=“sales”σDNAM=“sales”σDNAM=“sales”∪EMP1DEPT1EMP2DEPT1EMP3DEPT1∝∝∝第十八頁，共三十六頁，2022年，8月28日EMP1雇員（DNUM<=10）EMP2雇員（10<DNUM<=20）EMP3雇員（DNUM>20）DEPT1DNUM<=10DEPT2DNUM>10EMP1DEPT1∝σDNAM=“sales”第十九頁，共三十六頁，2022年，8月28日4.4垂直分段的化簡化簡的原理是在全部段中決定出足以回答給定查詢的一個適當子集，然后從查詢表達式中刪除所有其他的片。以及刪除在分段模式的逆反中用來重構(gòu)全局關(guān)系的若干連接操作。例4-3對關(guān)系：

EMP(ENUM,ENAME,SAL,TAX,DNUM)DEPT(DNUM,DNAME,AREA,MGRNUM)

建立如下分片：EMP1=∏ENUM，ENAME，SAL(EMP)EMP2=∏ENUM，ENAME，TAX(EMP)

定義查詢Q：∏ENAME，SAL(EMP)第二十頁，共三十六頁，2022年，8月28日∏ENAME，SAL

∞EMP1EMP2∏ENAME，SALEMP1第二十一頁，共三十六頁，2022年，8月28日4.5分布式分組和聚集函數(shù)求值的查詢一、關(guān)系代數(shù)的擴充利用GBG,AFR操作來擴充關(guān)系代數(shù)，其中各符號的含義為:G

是一些屬性，它們決定了R的分組方法；AF是要對每個求值分組的聚集函數(shù)；G和AF可以不指定。

GBG,AFR是一個關(guān)系，它是由G的屬性和AF的聚集函數(shù)組成的一個關(guān)系模式。元組數(shù)與R中的組數(shù)一樣多，G的屬性取分組的值，而AF的屬性取對此組求出的聚集函數(shù)的值。第二十二頁，共三十六頁，2022年，8月28日例4-4關(guān)系SUPPLY（SNO,PNO,QUAN）Q1：GBAVG(QUAN),σPNO

=“P01”(SUPPLY)Q2：GBSNO,PNO,SUM(QUAN)(SUPPLY)Q3：σSUM

(QUAN)>300GBSNO,PNO,SUM(QUAN)(SUPPLY)

如果每一分組都完整地包含在一個段里的話，GB相對于合并運算的分配律是成立的，即

GBG,AF(R1∪R2)(GBG,AFR1)∪(GBG,AFR2)第二十三頁，共三十六頁，2022年，8月28日例如供應(yīng)商供應(yīng)某種產(chǎn)品的情況表（SUPPLY)SNOPNOQUTNS01P01160S01P01200S01P02300S01P02100SNOPNOQUTNS02P0180S02P01100S02P02300S02P02100第二十四頁，共三十六頁，2022年，8月28日準則六為了在一全局查詢中進行分布分組和聚集函數(shù)求值，可以把合并運算（表示段的收集）向上推至相應(yīng)的group-by操作范圍之外。Q3對應(yīng)的算符樹為：假設(shè)supply的元組按屬性Sno和Pno的值進行分組，而且把Sno相同的值分在了supply1和supply2的分片中，則：∪σSUM(QUAN)>300σSUM(QUAN)>300GBSNUM,PNUM,SUM(QUAN)GBSNUM,PNUM,SUM(QUAN)Supply1Supply2第二十五頁，共三十六頁，2022年，8月28日二、參數(shù)性查詢1.參數(shù)性查詢的化簡

Q4：σSNo=$XORSNo=$Y(SUPPLY)

對于含有參數(shù)性的化簡則在編譯時只能進行一部分，而另一部分要等到運行時才能完成，由于效率方面的考慮，在運行時不采用過于復(fù)雜的優(yōu)化技術(shù)。運行時的優(yōu)化常采用簡單的測試來完成。即在編譯的時候通過對一些限定語和選擇條件進行的代數(shù)操作來獲得測試的表達式，然后在執(zhí)行時通過對可能的數(shù)據(jù)段進行永假式測試，如成立則簡化查詢的執(zhí)行。第二十六頁，共三十六頁，2022年，8月28日2、在參數(shù)性查詢多次激活中使用的臨時關(guān)系為了降低在每次激活時重復(fù)執(zhí)行查詢時所需的代價，一個有用的方法是在該查詢的元發(fā)站點上建立若干臨時關(guān)系，其中存儲每次迭代所需的數(shù)據(jù)的超集（supperset）第二十七頁，共三十六頁，2022年，8月28日4.6、基于等價變換的查詢優(yōu)化基于等價變換的查詢優(yōu)化就是利用查詢對應(yīng)的關(guān)系代數(shù)并轉(zhuǎn)換成算符樹形式，再利用前面介紹的優(yōu)化準則，達到數(shù)據(jù)查詢的優(yōu)化目的?；诘葍r變換的查詢優(yōu)化的一般步驟如下：把查詢語言對應(yīng)的命令轉(zhuǎn)換成關(guān)系代數(shù)對應(yīng)的算符樹。如果是分布式透明系統(tǒng)，則需要把全局查詢轉(zhuǎn)換成段查詢對應(yīng)的算符樹。第二十八頁，共三十六頁，2022年，8月28日利用優(yōu)化準則化簡所有的算符樹。利用化簡的算符樹檢索數(shù)據(jù)庫并生成查詢結(jié)果。例4-5有全局關(guān)系

EMP(ENO,ENAME,EAGE,ESEX)SALE(ENO,PNO,QUANTITY)EMP的水平分片EMP_M和EMP_F為男職員和女職員，SALE的水平分片SALE_G和SALE_L分別為銷售數(shù)量大于20和不大于20的分片?，F(xiàn)在考慮全局查詢：SELECTENAMEFROMEMP,SALEWHEREEMP.ENO=SALE.ENOANDESEX=’F’ANDQUANTITY>20

第二十九頁，共三十六頁，2022年，8月28日EMP.ENO=SALE.ENO1把SQL語句轉(zhuǎn)換成關(guān)系代數(shù)對應(yīng)的算符樹∏ENAME（σ

ESEX=’F’ANDQUANTITY>20(EMP∞SALE)）對應(yīng)的算符樹如下：∏ENAMEσESEX=F∧QUANTITY>20∞EMP.ENO=SALE.ENOEMP-M∪∪EMP-FSALE-GSALE-LEMP∏ENAMEσESEX=F∧QUANTITY>20∞EMP.ENO=SALE.ENOSALE第三十頁，共三十六頁，2022年，8月28日把全局查詢轉(zhuǎn)換成段查詢對應(yīng)的算符樹用優(yōu)化準則化簡所有的算符樹?！荅NAME∞EMP.ENO=SALE.ENOEMP-MEMP-F∪σESEX=FσESEX=F∪σQUANTITY〉20σQUANTITY〉20SALE-LSALE-G第三十一頁，共三十六頁，2022年，8月28日∏ENAME∞EMP.ENO=SALE.ENOEMP-FSALE-G第三十二頁，共三十六頁，2022年，8月28日3.7基于半連接程序的查詢優(yōu)化

所謂半連接程序是指通過半連接運算來生成等價的處理序列。設(shè)A，B分別是R和S的屬性組，它的半連接程序可以有如下兩種刻畫形式。S∞A=B(R∝A=B（∏BS）)R∞A=B(S∝A=B（∏AR）)對于R∝

A=BS，其處理過程為在本地把S投影到B;

把此投影的結(jié)果發(fā)送到R所在的站點并執(zhí)行半連接運算;

把這個半連接結(jié)果送到S所在的站點執(zhí)行連接運算。第三十三頁，共三十六頁，2022年，8月28日優(yōu)化步驟和費用估計基于半連接的查詢優(yōu)化的一般步驟為：查詢語言對應(yīng)的命令轉(zhuǎn)換成關(guān)系代數(shù)表達式；計算所有可能的等價半連接程序的代價；從中選擇一個最小的方案，執(zhí)行并獲得查詢結(jié)果。費用估計:假設(shè)網(wǎng)絡(luò)中站點之間傳遞相同信息的數(shù)據(jù)所花費的代價是相同的，并且忽略站點之間的差異以及路游選擇費用，則一個站點發(fā)送X個字節(jié)的信息到另一個站點所花費的費用為：

C[X]=C0+C1*X

其中C0,C1是與網(wǎng)絡(luò)性能有關(guān)的參數(shù)。第三十四頁，共三十