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

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