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