并行數(shù)據(jù)庫(數(shù)據(jù)庫)

時間：2022-12-12 14:30:02 | 來源：信息時代

時間：2022-12-12 14:30:02 來源：信息時代

    并行數(shù)據(jù)庫 : 以并行計算機為硬件環(huán)境并能充分體現(xiàn)多處理和I/O并行性的數(shù)據(jù)庫。并行數(shù)據(jù)庫是并行計算技術(shù)與數(shù)據(jù)庫技術(shù)相結(jié)合而產(chǎn)生的新一代數(shù)據(jù)庫,并行數(shù)據(jù)庫著眼于采用各種并行算法提高數(shù)據(jù)庫系統(tǒng)的計算速度和解決復雜性計算問題的能力。
從20世紀70年代開始,并行計算機系統(tǒng)發(fā)展十分迅速,很多大規(guī)模并行計算機系統(tǒng)(簡記作MPP)已經(jīng)投入市場,如nCUBE、iPSC、Paragon、KSR-1、CM2、CM5等。最近,隨著高速通信網(wǎng)絡技術(shù)的出現(xiàn)(如ATM和光纖通信技術(shù))和操作系統(tǒng)的進展,基于網(wǎng)絡的多計算機機群并行計算環(huán)境(簡稱機群并行計算環(huán)境)也開始出現(xiàn),如NECTAR、PVM等系統(tǒng)。MPP和機群并行計算環(huán)境為高性能數(shù)據(jù)庫系統(tǒng)的實現(xiàn)帶來了希望。在MPP和機群并行計算系統(tǒng)的基礎上建立的數(shù)據(jù)庫系統(tǒng)稱為并行數(shù)據(jù)庫系統(tǒng)。并行數(shù)據(jù)庫系統(tǒng)引起了學術(shù)界和工業(yè)界密切關(guān)注,已經(jīng)成為一個重要的數(shù)據(jù)庫研究領域。
并行數(shù)據(jù)庫系統(tǒng)的歷史可以追溯到數(shù)據(jù)庫機(database machine,DBM)的研究。數(shù)據(jù)庫機或稱數(shù)據(jù)庫機器旨在設計支持各種數(shù)據(jù)庫管理系統(tǒng)功能的專用硬件,用專用計算機系統(tǒng)結(jié)構(gòu)代替通用的Von Neumann計算機系統(tǒng)結(jié)構(gòu),為高性能數(shù)據(jù)庫系統(tǒng)提供一個高效支撐環(huán)境。數(shù)據(jù)庫機試圖通過減少軟件的復雜性來提高系統(tǒng)的效率和可靠性; 通過增加專用硬件、并行處理能力來改善數(shù)據(jù)庫系統(tǒng)的性能。人們設計了很多數(shù)據(jù)庫機。數(shù)據(jù)庫機一般都作為通用計算機(稱為宿主機)的后端機使用。在這種宿主機-后端機結(jié)構(gòu)中,宿主機是用戶與數(shù)據(jù)庫機的界面,后端機(即數(shù)據(jù)庫機)實現(xiàn)數(shù)據(jù)庫的存取與控制。鑒于處理機與輔助存儲器速度的極不匹配,加上數(shù)據(jù)庫機硬件設計與實現(xiàn)的開銷太大,數(shù)據(jù)庫機沒有取得成功。但是,數(shù)據(jù)庫機的研究對并行數(shù)據(jù)庫系統(tǒng)的建立起到了很大的作用,很多研究成果已經(jīng)直接用于并行數(shù)據(jù)庫系統(tǒng)。
20世紀80年代末期,人們開始研究如何在通用并行計算機系統(tǒng)上實現(xiàn)并行數(shù)據(jù)庫系統(tǒng)。關(guān)系數(shù)據(jù)模型的面向集合和非過程性為關(guān)系數(shù)據(jù)庫系統(tǒng)的并行化提供了有利的條件。并行數(shù)據(jù)庫系統(tǒng)的研究主要圍繞著關(guān)系數(shù)據(jù)庫進行,包括三個研究領域:并行數(shù)據(jù)庫的物理組織、并行數(shù)據(jù)操作算法的設計及并行數(shù)據(jù)庫查詢的優(yōu)化處理。
并行數(shù)據(jù)庫物理存儲方法的目的是在多處理機之間分布各種數(shù)據(jù)庫對象(關(guān)系、索引等),使得在查詢處理過程中系統(tǒng)的并行性能夠得到充分的發(fā)揮,最小化查詢處理的響應時間。數(shù)據(jù)分布對并行數(shù)據(jù)庫系統(tǒng)的性能具有極大的影響。到目前為止,人們已經(jīng)提出了一維數(shù)據(jù)分布、多維數(shù)據(jù)分布等多種并行數(shù)據(jù)庫物理存儲方法。一維數(shù)據(jù)分布方法是最簡單的數(shù)據(jù)分布方法,已被Bubba、Gamma、Teradata等并行數(shù)據(jù)庫原型系統(tǒng)采用。一維數(shù)據(jù)分布技術(shù)的特點是: 通過劃分關(guān)系的一個屬性的域值來劃分整個關(guān)系,得到一組子關(guān)系,然后在多處理機之間分布這些子關(guān)系。目前已經(jīng)出現(xiàn)的一維數(shù)據(jù)分布方法主要包括 round-robin、hash、rangepartition、hybrid-range-partition等方法。一維數(shù)據(jù)分布方法具有一個共同的問題: 不能夠有效地支持在非劃分屬性上具有選擇謂詞的查詢。為了解決這個問題,后來又提出一些多維分布方法,其中包括CMD數(shù)據(jù)分布方法、基于錯誤校正碼的數(shù)據(jù)分布方法、隨機數(shù)據(jù)分布方法、基于hilbert曲線的數(shù)據(jù)分布方法、BERD數(shù)據(jù)分布方法等。除了數(shù)據(jù)分布方法以外,人們還對傳統(tǒng)的數(shù)據(jù)庫物理存儲方法進行了拓展,進行并行化,使其適合于并行數(shù)據(jù)庫系統(tǒng),如并行B-樹和并行GRID文件等。
并行數(shù)據(jù)操作算法研究的目的是設計實現(xiàn)各種關(guān)系操作的并行算法,如并行排序算法、并行連接操作算法、并行集合操作算法、并行選擇操作算法、并行投影操作算法等,重點是并行連接操作算法的研究。目前已經(jīng)出現(xiàn)了很多并行連接算法。這些算法可以歸結(jié)為四類: 并行嵌套循環(huán)連接算法、并行排序合并連接算法、并行Hash連接算法及基于特定存儲結(jié)構(gòu)的并行連接算法。前三類并行連接算法不考慮被連接關(guān)系的物理存儲結(jié)構(gòu)。第四類并行連接算法是充分利用被連接關(guān)系的物理存儲結(jié)構(gòu)特點的并行連接算法。
并行數(shù)據(jù)庫查詢的優(yōu)化處理是并行數(shù)據(jù)庫系統(tǒng)的關(guān)鍵組成部分。在并行數(shù)據(jù)庫系統(tǒng)中,查詢優(yōu)化的目標是尋找查詢的具有最小響應時間的執(zhí)行計劃、需要新的查詢處理算法和新的查詢優(yōu)化技術(shù)。目前已經(jīng)出現(xiàn)了兩類并行數(shù)據(jù)庫查詢處理和優(yōu)化方法。一類是并行數(shù)據(jù)流方法; 另一類是并行查詢計劃空間搜索方法。并行數(shù)據(jù)流方法的基本思想是使用數(shù)據(jù)操作的順序算法開發(fā)關(guān)系數(shù)據(jù)庫系統(tǒng)的固有并行性,實現(xiàn)關(guān)系查詢的并行執(zhí)行。這種方法既不需要設計新的并行數(shù)據(jù)操作算法,也不需要修改現(xiàn)有的順序數(shù)據(jù)操作算法,是一種在現(xiàn)有數(shù)據(jù)庫技術(shù)的基礎上實現(xiàn)并行數(shù)據(jù)庫系統(tǒng)的簡單方法。Gamma、Volcano、Tandem等并行數(shù)據(jù)庫系統(tǒng)原型使用了這種方法。但是,并行數(shù)據(jù)流既沒有考慮數(shù)據(jù)操作本身的并行處理也沒有考慮在并行計算環(huán)境下的查詢優(yōu)化問題,不能充分地發(fā)揮多處理機的并行性,系統(tǒng)的查詢處理的效率和能力受到很大的限制。于是,人們研究了基于查詢計劃空間搜索的并行數(shù)據(jù)庫查詢優(yōu)化方法,提出了很多新的并行查詢優(yōu)化方法。這些方法可以分為兩類: 兩階段方法和一階段方法。兩階段方法分兩階段產(chǎn)生高效率的并行查詢執(zhí)行計劃。第一階段使用傳統(tǒng)的查詢優(yōu)化方法產(chǎn)生高效率的順序查詢執(zhí)行計劃。第二階段并行化第一階段產(chǎn)生的順序查詢執(zhí)行計劃,產(chǎn)生一個高效率的并行查詢執(zhí)行計劃。兩階段算法具有一個很大的問題: 第一階段產(chǎn)生的順序查詢執(zhí)行計劃可能具有很高的固有順序性,從而第二階段產(chǎn)生的并行查詢執(zhí)行計劃的并行性可能很低。一階段方法直接產(chǎn)生高效率的并行查詢執(zhí)行計劃,不需要首先得到優(yōu)化的順序查詢執(zhí)行計劃,避免了兩階段方法的問題。但是,一階段方法的復雜性遠高于兩階段方法。目前提出的一階段方法都是近似或啟發(fā)式方法,主要有基于左線性樹的方法、基于右線性樹的方法、基于濃密樹的方法、基于右片段樹的方法、基于操作森林的方法和基于多重加權(quán)樹的方法等。
目前,人們已經(jīng)開始把并行數(shù)據(jù)庫的基礎研究成果轉(zhuǎn)化為數(shù)據(jù)庫產(chǎn)品,出現(xiàn)了很多商品化的并行數(shù)據(jù)庫系統(tǒng),并得到了廣泛的應用。