并行數(shù)據(jù)庫作業(yè)論文.doc

并行數(shù)據(jù)庫的研究摘要：像其它計算領(lǐng)域一樣.并行處理也許是高性能數(shù)據(jù)庫系統(tǒng)的必由之路。近年來.隨著微處理器技術(shù)的進步.出現(xiàn)了大規(guī)模并行處理的研究熱潮。這不僅從技術(shù)上.同時也從商業(yè)上為并行數(shù)據(jù)庫系統(tǒng)的研究和發(fā)展創(chuàng)造了有利條件。按現(xiàn)階段的技術(shù)水平，大規(guī)模并行處理機能提供比傳統(tǒng)的大型機高得多的性能/價格比。并行數(shù)據(jù)庫系統(tǒng)（Parallel Database System）是新一代高性能的數(shù)據(jù)庫系統(tǒng)，是在MPP和集群并行計算環(huán)境的基礎(chǔ)上建立的數(shù)據(jù)庫系統(tǒng)。并行數(shù)據(jù)庫系統(tǒng)是在并行機上運行的具有并行處理能力的數(shù)據(jù)庫系統(tǒng)，是數(shù)據(jù)庫技術(shù)與并行計算技術(shù)相結(jié)合的產(chǎn)物。本文比較詳細的分析了并行數(shù)據(jù)庫的一些相關(guān)知識。首先介紹了什么是并行數(shù)據(jù)庫，然后分析了并行數(shù)據(jù)庫的性能以及性能的優(yōu)化方法，然后又分析了并行數(shù)據(jù)庫的體系結(jié)構(gòu)，進而分析了并行數(shù)據(jù)庫的查詢優(yōu)化方法，并在最后做了總結(jié)。1 什么是并行數(shù)據(jù)庫并行計算技術(shù)利用多處理機并行處理產(chǎn)生的規(guī)模效益來提高系統(tǒng)的整體性能，為數(shù)據(jù)系統(tǒng)提供了一個良好的硬件平臺。研究和開發(fā)適應(yīng)于并行計算機系統(tǒng)的并行數(shù)據(jù)庫系統(tǒng)成為數(shù)據(jù)學(xué)術(shù)界和工業(yè)界的研究熱點，形成了并行處理技術(shù)與數(shù)據(jù)庫技術(shù)相結(jié)合的并行數(shù)據(jù)庫新技術(shù)。 并行處理技術(shù)與數(shù)據(jù)庫技術(shù)的結(jié)合，具有潛在的可行性。因為關(guān)系數(shù)據(jù)庫模型本身就有極大的并行可能性。關(guān)系數(shù)據(jù)模型中，數(shù)據(jù)庫是元組的集合，數(shù)據(jù)庫操作實際是集合操作，許多情況下可分解為一系列對子集的操作，許多子操作不具有數(shù)據(jù)相關(guān)性，因而具有潛在的并行性。 一個并行數(shù)據(jù)庫系統(tǒng)應(yīng)該實現(xiàn)如下目標(biāo)： 1）高性能 并行數(shù)據(jù)庫系統(tǒng)通過將數(shù)據(jù)庫管理技術(shù)與并行處理技術(shù)有機結(jié)合，發(fā)揮多處理機結(jié)構(gòu)的優(yōu)勢，從而提供比相應(yīng)的大型機系統(tǒng)要高得多的性能價格比和可用性。例如，通過將數(shù)據(jù)庫在多個磁盤上分布存儲，利用多個處理機對磁盤數(shù)據(jù)進行并行處理，從而解決磁盤“I/O”瓶頸問題。通過開發(fā)查詢間并行性(不同查詢并行執(zhí)行)、查詢內(nèi)并行性(同一查詢內(nèi)的操作并行執(zhí)行)以及操作內(nèi)并行性(子操作并行執(zhí)行)大大提高查詢效率。 2）高可用性 并行數(shù)據(jù)庫系統(tǒng)可通過數(shù)據(jù)復(fù)制來增強數(shù)據(jù)庫的可用性。這樣，當(dāng)一個磁盤損壞時，該盤上的數(shù)據(jù)在其他磁盤上的副本仍可供使用，且無需額外開銷(與基于日志的恢復(fù)不同)。數(shù)據(jù)復(fù)制還應(yīng)與數(shù)據(jù)劃分技術(shù)相結(jié)合以保證當(dāng)磁盤損壞時系統(tǒng)仍能并行訪問數(shù)據(jù)。 3）可擴充性 這里，數(shù)據(jù)庫系統(tǒng)的可擴充性指系統(tǒng)通過增加處理和存儲能力而平滑地擴展性能的能力。理想情況下，并行數(shù)據(jù)庫系統(tǒng)應(yīng)具有兩個方面的可擴充性優(yōu)勢：線性伸縮和線性加速。2 并行數(shù)據(jù)庫性能研究2.1影響并行數(shù)據(jù)庫性能的幾點因素影響并行數(shù)據(jù)庫性能的因素很多, 硬件結(jié)構(gòu)、數(shù)據(jù)分布、查詢處理等都會對并行數(shù)據(jù)庫的性能帶來很大影響。并行數(shù)據(jù)庫的硬件結(jié)構(gòu)主要有三種( 見圖1) :SE ( Shared Everything ) 結(jié)構(gòu): 該結(jié)構(gòu)中所有的硬盤與內(nèi)存均可為每個處理機所共享, SE 結(jié)構(gòu)也稱為SM ( 共享內(nèi)存) 結(jié)構(gòu), 1BM3090 系列機為此結(jié)構(gòu)。SD( Shared Disk ) 結(jié)構(gòu): 每個處理機可以直接存取任何一個磁盤, 但都有其私有內(nèi)存, Wisconsin DIRECT為SD 結(jié)構(gòu)。SN( Shared Nothing ) 結(jié)構(gòu): 每個處理機都有其私有內(nèi)存和硬盤, Teradata, DBC/ 1012 屬SN 結(jié)構(gòu)。數(shù)據(jù)分布是影響并行數(shù)據(jù)庫性能的另一因素, 在并行數(shù)據(jù)庫環(huán)境中, 數(shù)據(jù)分布主要是指將一個關(guān)系水平劃分成若干片段再分配到各處理機上。需要指出, 數(shù)據(jù)分布是靜態(tài)的, 而查詢處理則是動態(tài)的, 兩者關(guān)系極為密切, 合理的數(shù)據(jù)分布可以為查詢處理打下良好的基礎(chǔ), 而查詢處理的目標(biāo)又應(yīng)與數(shù)據(jù)分布的目標(biāo)一致, 才能取得更好的效果。查詢的主要工作是執(zhí)行運算, 其中出現(xiàn)頻率高又費時間的是連接運算, 研究的重點是降低連接運算的時間。2.2提高并行數(shù)據(jù)庫性能的幾點考慮上面討論了影響并行數(shù)據(jù)庫性能的幾個主要因素, 在硬件結(jié)構(gòu)確定之后, 主要的考慮就集中在數(shù)據(jù)分布與查詢處理上, 在數(shù)據(jù)庫環(huán)境下, 數(shù)據(jù)文件之間互相聯(lián)系, 數(shù)據(jù)分布與查詢處理相互影響, 應(yīng)在一個集成的環(huán)境中, 統(tǒng)一的目標(biāo)下考慮才會有最好的效果。查詢處理主要考慮縮短連接運算時間, 數(shù)據(jù)的靜態(tài)分布要有利于兩個關(guān)系的連接運算, 能均勻地在各處理機上執(zhí)行。如果連接運算以PSMJ 算法執(zhí)行, 那么若執(zhí)行R join S, 則在N個處理機中的每個處理機的數(shù)據(jù)量應(yīng)大致為|R|/ N 與|S|/ N, 而且盡可能使每個處理機的連接屬性上的值相同, 即或 從而將連接運算變?yōu)楹唵芜B接運算, 減少連接運算的次數(shù), 縮短連接運算的時間, 這樣形成的關(guān)系R 和S 的數(shù)據(jù)分片可以通過一種改進的值域劃分法得到。在數(shù)據(jù)分片時, 數(shù)據(jù)的基本單位也要考慮, 通常都以一個完整的關(guān)系作為劃分的基本單位, 但是數(shù)據(jù)分片的基本依據(jù)是應(yīng)用, 如果應(yīng)用對某關(guān)系的訪問只包含對該關(guān)系片段中的一些元組的訪問。例如對關(guān)系R 的訪問中, 若經(jīng)常訪問的是R1 或R2 中的一些元組( R1, R2 可由查詢語句確定) , 則不妨將R 的分片按R1, R2兩部份作為基本單位, 如圖2 所示, 再將此二部份分別分到N個處理機中, 這樣可以減少查詢處理中對無關(guān)元組的訪問。3 并行數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)3.1 SQL軟件中的兩種并行性SQL是標(biāo)準(zhǔn)化的最為流行的關(guān)系查詢語言。由于SQL的非過程化特點和關(guān)系運算語義的簡潔性.使SQL軟件中存在著許多被并行化的機會。首先.把一種關(guān)系運算的輸出結(jié)果導(dǎo)向另一關(guān)系運算.使兩個以上的關(guān)系運算構(gòu)成流水線.就得到了“流水線并行性”(或稱“程序并行性”)。其次.用多臺處理機存儲器分割大的數(shù)據(jù)集.使得一個運算被分割成多個相同的關(guān)系運算而作用于不同的數(shù)據(jù)對象.就得到了所謂“劃分并行性”(或稱“數(shù)據(jù)并行性”)。流水線并行性的性能往往受到下列限制:(l)關(guān)系流水線通常比較短;(2)某些關(guān)系運算在消耗完全部輸入關(guān)系之前不產(chǎn)生輸出.比如聚集運算(aggre-gate)和排序運算(sort);(3)某些運算的代價大于其他運算。相比之下，劃分并行性提供了較好的加速和放大的機會通過劃分關(guān)系運算的輸入和輸出可以取分而治之的方法.把大作業(yè)轉(zhuǎn)化為多個獨立的作業(yè)。這是加速和放大的理想條件。3.2、并行數(shù)據(jù)庫中的錯開問題在并行數(shù)據(jù)庫系統(tǒng)中一般文獻談到的錯開形式有兩種:數(shù)據(jù)錯開和執(zhí)行錯開。特別地.錯開對并行連接算法的影響尤為嚴(yán)重.這其中的主要原因是，現(xiàn)有的并行連接算法都是對經(jīng)典連接算法的簡單并行化.因而對錯開十分敏感。由于認識到錯開是影響并行數(shù)據(jù)庫性能的主要因素之一因此.錯開問題也成為這幾年并行數(shù)據(jù)庫研究中十分活躍的領(lǐng)域。文9中更精確地歸納出了以下五種錯開:(l)內(nèi)函錯開:即關(guān)系元組中，某些屬性值遠遠超出屬性值空間的均值范圍。這種形式的錯開是數(shù)據(jù)源的特性.不隨算法而變化;(2)元組放置錯開:指關(guān)系元組的最初劃分分布。例如.使用聚集屬性方法劃分元組;(3)選擇錯開;指同樣的選擇謂詞作用于不同的數(shù)據(jù)分區(qū)所造成的選擇率的不同。明顯的例子是在分區(qū)上執(zhí)行一個區(qū)域選擇;(4)重分布錯開:指連接鍵值的分布與重分布函數(shù)期待的分布不匹配;(5)連接結(jié)果錯開:各分區(qū)的連接的選擇率呈現(xiàn)不同。好的算法應(yīng)能處理每一種錯開。3.3、并行恢復(fù)與并發(fā)控制并行恢復(fù)對于并行數(shù)據(jù)庫系統(tǒng)的堅固性致關(guān)重要。當(dāng)系統(tǒng)中某一結(jié)點或磁盤發(fā)生故障.其余存活的結(jié)點要能夠自動探測.并利用日志信息.把故障結(jié)點的工作接管過來.從而使系統(tǒng)繼續(xù)正常運轉(zhuǎn).并行系統(tǒng)中的每個結(jié)點只維持一部分日志信息.必須采取某種措施保證其一致性。另一方面.并發(fā)控制對系統(tǒng)的響應(yīng)速度影響很大.并行數(shù)據(jù)庫系統(tǒng)支持的并發(fā)事務(wù)數(shù)目要比傳統(tǒng)的大型機系統(tǒng)大得多.要獲得高的吞吐率，必需采用先進的控制技術(shù)。oraele7采用T“行級鎖”(row-level locking)思想.利用先進的“并行緩沖區(qū)管理”和“并行鎖管理”技術(shù)實現(xiàn)并發(fā)控制。這種獨特的并發(fā)控制機制不會發(fā)生并發(fā)更新和查詢的阻塞.提供了最細粒度的鎖控制.保證了數(shù)據(jù)資源上的竟?fàn)幾钚?。并行緩沖區(qū)管理程序和并行鎖管理程序負責(zé)追蹤數(shù)據(jù)塊副本的位置和最新狀態(tài)，使結(jié)點間的數(shù)據(jù)移動最小化.能有效地節(jié)約網(wǎng)絡(luò)帶寬。Oracle7的并行緩沖區(qū)管理實際上是一種改進了的多版本控制技術(shù).目前看來是一種比較先進的并發(fā)控制技術(shù)。4 并行查詢優(yōu)化數(shù)據(jù)庫查詢優(yōu)化技術(shù)一直受到十分的重視.在傳統(tǒng)的優(yōu)化方法中通常采用了代數(shù)變換和啟發(fā)式兩種優(yōu)化措施.其時間復(fù)雜性是一個主要問題。并行性的引入又給查詢優(yōu)化帶來了新的研究課題。首先.編譯時的靜態(tài)優(yōu)化缺乏關(guān)于系統(tǒng)資源可用性的知識(如可用的緩沖區(qū)大小、自由處理機的數(shù)目等).因此它產(chǎn)生的執(zhí)行規(guī)劃很難充分利用并行流水線資源以達到線性縮短求解時間之目的。解決這個問題的辦法是采用動態(tài)優(yōu)化技術(shù)。動態(tài)優(yōu)化除了執(zhí)行編譯時的優(yōu)化外，還建立了運行時支持功能.根據(jù)CPU負載、中間結(jié)果特性、主存使用情況等系統(tǒng)信息動態(tài)適應(yīng)執(zhí)行規(guī)劃。很顯然.動態(tài)優(yōu)化比靜態(tài)優(yōu)化困難得多.其次.并行執(zhí)行規(guī)劃的搜索空間變得更加龐大.使動態(tài)優(yōu)化的時間復(fù)雜性問題更加嚴(yán)重.是否存在一種折衷方案.不致于增加太多的復(fù)雜性?一種方案是所謂兩段靜態(tài)優(yōu)化.它的含義是.首先在忽略并行性的前提下對查詢進行常規(guī)優(yōu)化。然后.將選中的查詢規(guī)劃做進一步的并行化優(yōu)化.這種方法也能減小優(yōu)化的搜索空間.因此在并行化一個現(xiàn)存的DBMS時特別有吸引力。在并行查詢中，查詢樹的選擇也與傳統(tǒng)的做法不同。右深樹(right-deep tree)利于流水線并行.但其結(jié)構(gòu)靈活性差.因而對性能構(gòu)成限制。相比之下.叢生樹(bushy tree)為查詢規(guī)劃的生成提供了更多的靈活性.已經(jīng)證明，對于分類合并連接算法.叢生樹的執(zhí)行性能可以超過線性樹.特別是當(dāng)查詢中涉及的關(guān)系數(shù)目很大時更是如此。但對于散列連接算法.叢生樹結(jié)構(gòu)的執(zhí)行規(guī)劃調(diào)度要比右深樹復(fù)雜得多.要達到叢生樹充分利用流水線的目的.即使不是不可能.也是非常困難的.因此，需要提出一種更趨合理的查詢樹結(jié)構(gòu).使之更利于并行優(yōu)化的執(zhí)行規(guī)劃的產(chǎn)生。比如，有人提出了分段右深樹結(jié)構(gòu)。5 總結(jié)并行數(shù)據(jù)庫系統(tǒng)主要有兩個目的:一是利用多CPU和盤等系統(tǒng)資源極大地提高多用戶處理能力;二是利用多CPU和盤實現(xiàn)單個查詢的并行處理.顯著縮短復(fù)雜查詢的執(zhí)行時間。簡單地說就是查詢間并行和查詢內(nèi)并行.查詢內(nèi)并行性又分為算子間并行性和算子內(nèi)并行性。圍繞這兩個目的，本文從系統(tǒng)結(jié)構(gòu)的角度提出了六個方面的設(shè)計問題。除了本文提出的幾點間題之外.并行數(shù)據(jù)庫系統(tǒng)還有其它問題需要認真研