并行數(shù)據(jù)庫系統(tǒng)

PAGE3并行數(shù)據(jù)庫系統(tǒng)1并行數(shù)據(jù)庫概述并行數(shù)據(jù)庫系統(tǒng)是在并行機(jī)上運(yùn)行的具有并行處理能力的數(shù)據(jù)庫系統(tǒng)，是數(shù)據(jù)庫技術(shù)與并行計(jì)算技術(shù)結(jié)合的產(chǎn)物。1.1并行數(shù)據(jù)庫系統(tǒng)的目標(biāo)：1．高性能。通過將數(shù)據(jù)庫在多個磁盤上分布存儲，利用多個處理機(jī)對磁盤數(shù)據(jù)進(jìn)行并行處理，解決I/O瓶頸問題。通過開發(fā)查詢間并行性、查詢內(nèi)并行性以及操作內(nèi)并行性，提高查詢效率。2．高可用性?？赏ㄟ^數(shù)據(jù)復(fù)制來增強(qiáng)數(shù)據(jù)庫的可用性，當(dāng)一個磁盤損壞時，該盤上的數(shù)據(jù)在其他磁盤上的副本仍可供使用。3．可擴(kuò)充性。系統(tǒng)通過增加處理和存儲能力而平滑地擴(kuò)展性能的能力。線形伸縮比：是指任務(wù)擴(kuò)大N倍、系統(tǒng)處理和存儲能力也擴(kuò)大N倍時系統(tǒng)性能不變，即：小任務(wù)在小系統(tǒng)上的運(yùn)行時間與大（N倍）任務(wù)在大系統(tǒng)上的運(yùn)行時間之比為1。線形加速度比：是指任務(wù)不變、系統(tǒng)處理和存儲能力擴(kuò)大N倍時系統(tǒng)性能也提高N倍，即：小系統(tǒng)上執(zhí)行一個任務(wù)的時間與大（N倍）系統(tǒng)上執(zhí)行同一個任務(wù)的時間之比為N。1.2支持并行數(shù)據(jù)庫的并行結(jié)構(gòu)1.2.1共享內(nèi)存（SM）并行結(jié)構(gòu)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)…互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)…共享存儲器共享存儲器磁盤磁盤磁盤磁盤磁盤磁盤…圖1.1SM結(jié)構(gòu)并行計(jì)算機(jī)（負(fù)荷比較均衡、成本高、可用性不是很好）1.2.2共享磁盤（SD）并行結(jié)構(gòu)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)…存儲器存儲器存儲器存儲器存儲器存儲器…互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)磁盤磁盤磁盤磁盤磁盤磁盤圖1.2SD結(jié)構(gòu)并行計(jì)算機(jī)（成本低、可擴(kuò)充性好、可用性強(qiáng)。實(shí)現(xiàn)起來比復(fù)雜）1.2.3無共享資源（SN）并行結(jié)構(gòu)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)處理機(jī)處理機(jī)處理機(jī)…處理機(jī)處理機(jī)處理機(jī)存儲器存儲器存儲器存儲器存儲器存儲器…磁盤磁盤磁盤磁盤磁盤磁盤…圖1.3SN結(jié)構(gòu)并行計(jì)算機(jī)（成本低、可伸縮性與可用性高。實(shí)現(xiàn)復(fù)雜、節(jié)點(diǎn)負(fù)荷難均衡）GROUPBYDEPTNUMORDERBYDEPTNUM；可以分解為掃描DEPT表和EMP表，對兩表進(jìn)行結(jié)合，對結(jié)合結(jié)果排序以及分組和輸出五個子任務(wù)。前一操作的輸出即是下一操作的輸入。如果后一操作等待前一操作產(chǎn)生一定量的輸出后（而不必等待前一操作執(zhí)行完畢）即可在另一處理機(jī)上開始執(zhí)行，這種并行方式稱為垂直并行或流水線并行。操作內(nèi)（intra-Operation）并行性操作內(nèi)并行性的粒度最細(xì)，它將同一操作（如掃描操作、合并操作、排序操作等）分解成多個獨(dú)立的子操作，由不同的處理機(jī)同時執(zhí)行。事務(wù)（Transation）事務(wù)內(nèi)事務(wù)間查詢（Query）查詢內(nèi)查詢間操作（Operation）操作內(nèi)操作間并行粒度細(xì)粗圖2.1四種并行粒度2.1.1并行化形式水平并行化（獨(dú)立并行化，IndependentParallelism）和垂直并行化（流水線并行化，PipeliningParallelism）OP1OP1OP2OP2(a)水平并行化（b）垂直并行化圖2.2.并行化的兩種形式如果兩個操作OP1、OP2無相互依賴關(guān)系，則稱這兩個操作相互獨(dú)立。水平并行化指的是互相獨(dú)立的多個操作或者一個操作內(nèi)互相獨(dú)立的多個子操作分別由不同的處理機(jī)并行執(zhí)行的形式。如果操作OP2直接依賴于OP1，并且OP2必須等待OP1處理完所有元組后方可開始執(zhí)行，則稱OP2以阻塞方式直接依賴于OP1；如果OP2無需等待OP1執(zhí)行完畢即可在另一處理機(jī)上開始執(zhí)行，則稱OP2以流水線方式直接依賴于OP1。垂直并行化則是指存在流水線方式依賴關(guān)系的操作分別由不同處理機(jī)并行執(zhí)行的形式。例如，排序操作、掃描操作由不同的處理機(jī)并行執(zhí)行就是水平并行化的實(shí)例。排序排序排序……↓↓↓掃描掃描掃描……↓↓↓例如：掃描操作、排序操作、連接操作、分組操作由不同的處理機(jī)并行執(zhí)行就是垂直并行優(yōu)化的實(shí)例。掃描↓排序↓連接↓分組由于關(guān)系代數(shù)的封閉性和數(shù)據(jù)操作的相對獨(dú)立性，關(guān)系查詢具有三種固有并行性，即操作間的流水線并行性、操作間的獨(dú)立并行性以及操作內(nèi)的獨(dú)立并行性，這為關(guān)系代數(shù)的并行化提供了現(xiàn)實(shí)基礎(chǔ)。2.1.2并行操作算法并行數(shù)據(jù)庫操作算法的研究已經(jīng)成為并行數(shù)據(jù)庫系統(tǒng)近幾年一個非?；钴S的研究領(lǐng)域。并行操作算法有并行結(jié)合算法、并行掃描算法、并行排序算法等。由于結(jié)合操作是關(guān)系數(shù)據(jù)庫系統(tǒng)中最耗時且最常用的操作，對并行結(jié)合操作的研究最多。提出了基于嵌套循環(huán)的并行結(jié)合算法、基于合并掃描的并行結(jié)合算法、基于HASH的并行結(jié)合算法、基于索引的并行結(jié)合算法等?；谇短籽h(huán)的并行結(jié)合算法（S>>R）輸入：R，S：待結(jié)合的兩個關(guān)系；A：連接屬性；P：處理機(jī)數(shù)輸出：關(guān)系R和S的結(jié)合結(jié)果（結(jié)合屬性為A）方法：（1）把S均勻地分布到P個處理機(jī)，設(shè)Si是S在結(jié)點(diǎn)i上的子集合；（2）FORI=1TOpDO（并行地）處理機(jī)i按照結(jié)合屬性值排序SiENDDO；（3）在R所在的處理機(jī)上，對R按結(jié)合的屬性排序，再以流水線方式向P個處理機(jī)廣播R的元組；（4）FORi=1TOpDO（流水線方式并行的）處理機(jī)i以流水線方式接收R的元組；對磁盤上的S中元組和內(nèi)存中R的元組結(jié)合、輸出；ENDFOR；該算法適合于S的元組數(shù)遠(yuǎn)遠(yuǎn)大于R的元組數(shù)（R元組數(shù)較少）R1S1S1S2RR1S1S1S2RS3R2R2S21R3S3R3S3┇┇RP1SP1SRP1SP1SP圖2.3R與S基于嵌套循環(huán)的并行結(jié)合示意圖圖2.4一次哈希與排序并行結(jié)合圖二、基于排序的并行結(jié)合算法基于排序的并行結(jié)合算法由兩個階段組成：排序階段和結(jié)合階段。在排序階段，它按照結(jié)合屬性的值排序每個結(jié)合關(guān)系；在結(jié)合階段，完成兩個排序關(guān)系的結(jié)合。輸入：R，S：待結(jié)合的兩個關(guān)系。A：連接屬性P：處理機(jī)數(shù)H：HASH函數(shù)輸出：關(guān)系R和S的結(jié)合結(jié)果（結(jié)合屬性為A）方法：（1）使用HASH函數(shù)在P個處理結(jié)點(diǎn)間分布R和S的元組，設(shè)Si和Ri是S和R在結(jié)點(diǎn)i上的子集：（2）FORi=1TOpDO（水平并行地），處理機(jī)i排序Ri和SiENDFOR；（3）i=1TOpDO（水平并行地），結(jié)點(diǎn)i完成Ri和Si的結(jié)合輸出R和S的結(jié)合結(jié)果ENDFOR；理論和實(shí)驗(yàn)結(jié)果表明，當(dāng)兩個結(jié)合關(guān)系的元組數(shù)相差較小時，該算法的效率高于前一個算法。基于二次HASH的并行連接算法通過一個定義在結(jié)合連接屬性上的HASH函數(shù)把兩個結(jié)合關(guān)系分解為P個子集合，然后使用P個處理機(jī)并行地完成結(jié)合操作。輸入：關(guān)系R和S：HASH函數(shù)H1和H2，結(jié)點(diǎn)數(shù)P，子集合數(shù)M。輸出：關(guān)系R和S的連接結(jié)果。使用H1把R劃分為M個子集合，HASH值為i的元組送入子集合Ri，并存儲到所有可用的磁盤；使用H1把S劃分為M個子集合，HASH值為i的元組送入子結(jié)合Si，并存儲到所有可用的磁盤；FORI=1TOMDO（并行地）使用H2把Ri分布到p個處理結(jié)點(diǎn)，在每個結(jié)點(diǎn)的內(nèi)存中建立Ri元組的HASH表；使用H2以流水線方式向p個處理結(jié)點(diǎn)發(fā)送Si的元組；FORJ=1TOpDO（并行地）結(jié)點(diǎn)j用收到的Si的元組匹配Ri的HASH表，進(jìn)行Si和Ri的結(jié)合；輸出R和S的結(jié)合結(jié)果。算法中的M應(yīng)該充分大，以減少R的子集合對應(yīng)的HASH表超過可用內(nèi)存容量的概率。實(shí)驗(yàn)表明，使用并行數(shù)據(jù)操作算法實(shí)現(xiàn)查詢的并行處理可以充分地發(fā)揮多處理機(jī)的并行性，從而改善關(guān)系運(yùn)算的效率，提高查詢處理的速度。RSHASH1HASH1R1R2R3…RmS1S2S3…SmHASH2HASH2P1P2P3…PpP1P2P3…PpR1R11R12…R1pS1S11S12…S1pR2R21R22…R2pS2S21S22…S2p┇┇RiRi1Ri2…RipSiSi1Si2…Sip┇┇RmRm1Rm2…RmpSmSm1Sm2…Smp在站點(diǎn)P1，對R的每一個M足夠大，以保證每條鏈不太長。子集R均有一個鍵值表值。2.1.并行數(shù)據(jù)庫查詢優(yōu)化問題與順序數(shù)據(jù)庫查詢問題有所不同。在順序數(shù)據(jù)庫系統(tǒng)中，給定一個查詢Q，查詢優(yōu)化算法只需找到Q的一個具有最小工作量的執(zhí)行計(jì)劃。Q的最小工作量的執(zhí)行計(jì)劃可能具有很強(qiáng)的固有順序性，難以并行化，因而不具有最小響應(yīng)時間，在并行數(shù)據(jù)庫系統(tǒng)中，查詢優(yōu)化的目標(biāo)是尋找Q的具有最小響應(yīng)時間的執(zhí)行計(jì)劃，執(zhí)行計(jì)劃的工作量不是第一重要的。于是，在并行數(shù)據(jù)庫系統(tǒng)中，需要新的查詢處理算法和新的查詢優(yōu)化技術(shù)。并行查詢優(yōu)化面臨的兩大困難：執(zhí)行計(jì)劃搜索空間的龐大。設(shè)SPLAN（Q）是查詢Q的順序執(zhí)行計(jì)劃空間，P是一個順序執(zhí)行計(jì)劃，PARALLEL（P）是該計(jì)劃的所有并行化方案，那么查詢Q的并行執(zhí)行計(jì)劃空間PARALLEL（P）則可以由下述公式來表示：PPLAN（Q）=∪PARALLEL（P）P∈SPLAN（Q）由此可見，依靠傳