基于關系的并行數據倉庫的數據劃分和操作

（華東理工大學 計算機系， 上海 200237）

摘 要：目前并行數據庫的研究已經進入了實際應用階段，而數據倉庫的大數據量處理更需要并行處理能力的支持。針對數據倉庫的特點，提出了一種可操作的并行化數據劃分方法和物理存儲方案，同時對基于該種數據存儲的數據操作做了詳細的討論，并對各種Join操作的具體處理方法進行了歸類論述。

關鍵詞： 并行數據操作； 數據倉庫； 數據劃分； Join操作

中圖法分類號： TP311.13文獻標識碼： A

文章編號： 1001 3695(2006)08 0212 04



Data Placement and Operation of Relation based Parallel Data Warehouse 

LV Cheng， JIN Deng nan

（Dept. of Computer， East China University of Science Technology， Shanghai 200237， China）

Abstract: Parallelize has already been used in DBMS， and is more useful in data warehouse which must handle the massive data processing. The paper gives operable parallel ways for data placement and store in data warehouse environment， and also discuss the data operation based this physical structure， especially the parallel implementing methods of Join operation. 

Key words: Parallel Data Processing; Data Warehouse; Data Placement; Join Processing



1 引言

20世紀70～80年代，國外不少工作者潛心研究數據庫機器[1]，其中很重要的一點就是致力于實現數據操作并行化的專用硬件的設計。由于種種原因，數據庫機器最終沒有進入實用階段，但卻為數據庫系統的發展指明了方向。隨著通用并行計算機系統的發展和成熟，并行數據庫的研究取得了極大的進展，并已成為并行計算機研究的主要應用之一。目前各大主流的商用數據庫產品都成功地增加了并行處理能力，如Oracle公司的OPS（Oracle Parallel Server）、Informix公司的On line Dynamic Server和Sybase公司的VSA（Virtual Server Architecture）等。雖然這些產品大都還是在原有系統的基礎上進行的并行化改進，但這足以說明并行技術的運用是目前高性能數據處理的必由之路。

數據倉庫的自身特點決定了對大規模數據進行有效的管理和操作是技術層面的核心所在。目前世界上大型的數據倉庫系統（如WalMart，SBC）的數據量已接近200TB，所以數據倉庫的應用對并行化技術提出了更高的要求。同時，由于其數據倉庫一般專注于OLAP和DSS等類型的操作，因此可以在體系結構上作具有針對性的優化或簡化。

盡管現在主流的數據倉庫解決工具提供了新的數據模型解決方案，如星型、立方體模型等，它們對特定的OLAP應用確實起到了很好的效果，但是如果以數據倉庫作為企業信息系統的基礎，絕對是一個適合于使用規范化方法的領域[2]。而其他模型則可以用于以數據倉庫為基礎建立主題明確的數據集市。本文以基于關系的數據倉庫為對象，在體系結構、數據存儲和操作性能方面，在已有方法的基礎上提出了可操作的解決方案。

2 一種基于容錯的體系架構



并行數據庫系統的研究從一開始就與體系結構密切相關，文獻[3]中歸納了四種典型的并行計算機結構：SE（Share Everything），SM（Share Memory），SD（Share Disk），SN（Share Nothing）。1986年，美國學者M.Stonebraker提出SN結構是支持并行數據庫系統的最好并行結構[5]，它具有共享資源少、系統開銷小、加速比高等優點和近乎線形的可擴充性。早期的Ga mma ，Bubba和Tandem均是SN結構的例子，而國內的PARO等并行數據庫原型系統也采用該結構。

圖1、圖2就是使用最廣泛的SE結構和SN結構的模型。一般來講，在處理機數目較少的并行系統中，SE結構的性能超過SN和SD結構，但是在高端的并行數據庫系統中，首選的還是SN結構。通過在每個Note上進行數據劃分，結合關系查詢固有的并行性，實現以數據劃分為基礎的并行數據流方法[3]。

實際上，現在的技術趨勢是將這兩種并行性結合起來，實現分層的結構模型，即將基于SE結構的工作站運用到SN結構的每個節點中去，增強單個節點的處理能力，形成超級節點（Supernodes），而高速光纖互連技術在節點的連接方面提供了保障。例如，NCR公司的Teradata系統，在V2版本后，就在單節點上采用了對稱多處理機技術（SMP），并引入了虛擬處理器的概念[6]，每個虛擬處理器就是一系列協同工作的UNIX進程的集合。所有這些SMP節點協同工作組成了海量并行處理（MPP）系統。

容錯是在設計整個體系結構時必須考慮的重要因素，一個能夠商用的系統，必須確保在單個Note故障時具有不影響關鍵處理的能力。文獻[10]總結了幾種原型系統的節點故障處理機制，并認為Gamma系統采用的鏈式分布結構對系統負載平衡和容錯的效果最佳。但是，它卻需要對存儲數據進行邊界控制，從而增加了系統實現的難度；且過于簡化，沒有考慮數據的實際分布情況[7]，并且不易支持目前主流的Hash數據分布。考慮到這些情況，我們在節點的控制上引入簇（Cluster）的概念，由固定數目的節點組成一個簇（圖3以四個節點的簇為例），整個系統由若干個簇組成，簇內的各節點在數據的存儲上互作備份。分簇的SN結構如圖4所示。

如圖3所示，Note1故障時，查詢操作完全可以由訪問簇內的其他節點來調度，更新等操作也可以直接對備份數據進行，同時寫的恢復日志在故障節點恢復后，再通過日志前滾到當前狀態并拋棄恢復日志。在這種結構下，簇實際上是由存儲關系決定的節點組合，只要設計好節點數據劃分的方法（同時考慮主存儲節點和備份存儲節點），就可以很容易地實現以簇為單位的系統擴展。具體的劃分和存儲方法將在下一節敘述。如圖5所示，同簇的節點可以訪問同一組磁盤陣列，節點管理的磁盤為虛擬盤，可以獲得類似SD結構的容錯能力，當單個節點故障時，其進程可以直接遷移到同一個簇中的其他節點上來處理。

3 數據劃分和存儲



數據劃分和存儲是整個并行數據庫研究的基礎，各種數據操作必須基于相應的數據劃分和存儲方法來進行。目前常用的數據劃分方法有Round Robin，Hash，Range和Hybird Range，而Hash劃分有其獨具的優點：

(1)易于實現，通過維護Hash表就可以完成數據分布和遷移；

(2)它對Join操作有天然的優化作用；

(3)通過選用高級Hash算法，數據的均勻分布容易達到平衡負載和減小互連復雜度的目標。

下面針對數據倉庫的特點，可以對具體方案做優化和擴展。

3.1 基于主索引的存儲結構

在關系 R 中，選取一個或多個屬性作為主索引（PI），將其作為整個記錄的劃分屬性。例如定義一個以 V 為定義域的函數H1： V→{0，1，…，N 1}，這里N為并行系統的節點數。設r是R 的任意元組，根據哈希方法，它被存儲到H1( r PI])節點上，其中 r [PI]表示元組上主索引的值。一般認為Hash方法的難點在于選取一個良好的Hash散列函數，能夠解決數據偏斜問題。而實際上并沒有這樣一勞永逸的方法，每一種Hash函數只能針對某些特定情況進行改良，要想得到好的效果就必須在數據庫物理設計時對劃分屬性的選擇或設計進行充分的研究。數據倉庫不同于OLTP系統，數據在加載時已經能夠反映出其分布規律，并且它采用的是一種迭代式的開發，所以在ETL階段就可以對每個關系的PI的選擇作細致的考量。

假設節點數的擴展是有規律的，我們設計一個值域為10個比特位的Hash函數 H(x) ，有1024個Hash Buckets，那么節點數 N 最好為1 024的約數，這樣如果PI值分布均勻，則每個節點的記錄數也一定是均勻的。最簡單的處理是節點號 H1= H（r (PI)）mod N 即可，這里定義第一個Hash函數H1（ x）= x mod N ?？紤]到前面所說的基于簇的容錯結構，每個元組均有其主存儲節點和在同一個簇中的備份存儲節點，我們可以設計其第二個哈希分布函數如下（設單個簇包括 M個節點，N= M×i， i 是正整數）：

H2（H，H1）{

If（（a=floor(H1/M) * M+(H mod (M 1))）==H1）

Then return H1+1 

Else return a;

} 

這樣每個節點中的數據就可以近乎均勻地被備份到同一個簇中的其他節點上去。實際的操作中，可以根據Hash函數精心設計用于分布的Hash Map，在系統擴充時的數據遷移也需要一個完整的Hash Map映射遷移的方案。

滿足Hash數據劃分的數據記錄的物理結構有如下必要項：

Row Hash就是散列函數 H（x） 得出的哈希值，是定位記錄位置的基礎。Unique Value確保了每個記錄的全局唯一性。

3.2 基于子表的索引結構

一維數據的劃分曾被認為具有難以克服的缺點，那就是不能很好地支持在非劃分屬性上具有選擇謂詞的查詢。其實與通常的數據庫物理結構一樣，這個問題可以通過索引的方法得到解決。同時數據倉庫的特點決定了其并不需要對單個記錄的操作做出很快的反應，其應用主要集中在諸如全表掃描、多表連接、大量數據的排序、聚集等操作，所以沒有必要將普通數據庫里的樹索引結構移植過來。這里我們用一種簡化的方法來實現索引，即將索引字段單獨拿出，為其建一個新表作為索引。這樣做有下面幾個優點：

(1)簡化了索引的生成、維護和使用，避免了并行條件下管理樹索引的復雜性；

(2)如果將索引表按索引屬性作Hash排序則可以優化對索引屬性的等值查詢；

(3)如果將索引表按索引屬性作按值的排序則可以優化對索引屬性的范圍查詢。

考慮到索引屬性表不可避免的數據偏斜問題，我們用兩種方法來存儲索引表：

（1）如果索引屬性的值是全局唯一的，那么它通過Hash散列一定具有良好的分布性，就將索引屬性作為PI，與主表一樣用Hash方法將每個索引表的元組分布到各個節點中去，稱之為第一類索引。其單個記錄的結構如下：

這樣對于單條記錄的查詢變成了最多兩個節點間的操作，首先查找索引表，得到記錄的Row ID后再訪問存放實際數據的節點，避免了在全部節點上做全表掃描。對于范圍的查詢可以通過掃描各節點上的索引表的Index Value來實現。

（2）如果索引屬性是不唯一的，將其按Hash分布則極可能會引起數據偏斜，所以應該改變其存儲策略，變為本地存儲，這樣在分布上可以達到相對均勻的效果，稱之為第二類索引。其單個記錄的結構如下：

在本地的存儲同樣可以采用Hash排序或者是按值排序來根據不同形式的查詢做優化。

3.3 分區表和Hash劃分的結合：PPI（Partitioned Primary Index）

為了提高各種數據查詢和操作的性能，現在大多數的DBMS均提供了對大表的分區管理策略，這一點在數據倉庫中尤其重要。舉例來說，數據倉庫中存放有大量的歷史記錄，相對而言近期的數據會比較頻繁地被用到，通常被稱為熱點數據。對這部分數據的查詢應盡量避免全表掃描，通常將表按時間屬性分區存儲可以達到這樣的效果，如按月劃分。在基于主索引的存儲結構中，記錄會根據劃分屬性的Hash值排序，為了達到分區訪問的目的，可以擴充記錄格式如下：

這樣在記錄磁盤上的存儲是按照先Part Number再Row Hash的順序排序的，對于與分區屬性相的選擇查詢和分組操作會起到極大的優化效果，如圖6所示。當然，選擇分區屬性時應注意分區數不應該太多，否則會大大影響基于PI的操作效率。

這三點數據劃分和存儲策略的優點將會在具體數據操作時體現出來，下面就在本節物理結構的基礎上集中討論最常見的Join算法的具體實現。

4 Join操作的分類、索引選擇和優化

數據倉庫應用的特點之一就是要支持高效的表連接操作。在非并行的環境中，超大表的連接是災難性的，時常會出現資源被耗盡的情況。并行環境下，通過并行數據流技術的應用，這方面的操作可能得到較好的支持。各種不同結構的并行系統，數據庫操作方面的處理是有共性的，那就是數據流的歸并和分裂。一個并行查詢處理計劃是關系操作以及并歸和分裂操作共同組成的數據流網絡。下面就在上一節數據存儲方案的基礎上來討論并行的Join操作，其中與非并行環境下相似的優化被直接略去。

在邏輯層的應用中，Join可以分為Inner Join，Left Join，Right Join，Full Join和Cross Join幾種。而在DBMS實際執行計劃中，通過對數據存儲情況的分析卻可以分為循環嵌套連接、排序合并連接等。這里在文獻[4]的基礎上，考慮到數據的物理分布，以下將分類進行討論。

4.1 合并連接（Merge Join）

兩個表有如下結構：

(1)連接屬性就是兩張表的主索引，例如：

SELECT*FROM table1，table2

WHERE table1.A=table2.A; 

這里A屬性在兩張表里均是PI，它們都是按A屬性分布存儲到各個節點上的，因此這樣的合并操作只需要在單個節點內進行，最后將各節點的結果集并歸（一般會要求排序，這里忽略）即可。

(2)連接屬性是其中一個表的主索引，例如：

SELECT*FROM table1，table2

WHERE table1.A=table2.B 

因為必須要將合并操作分布到每個節點上去，所以通常可以將Table2讀出，按照Table2.B屬性重新分布到各個節點的緩沖區上去，然后采用與第一種情況一樣的方法即可。但這樣的數據劃分可能是極度偏斜的，容易造成節點間的負載不均。實際上對于這種非劃分屬性的偏斜是任何劃分方法都難以避免的，目前研究較為有效的方式是采用虛擬機技術來實現動態負載平衡[8]，這已經超出本文的范疇了。在本文討論的Hash分布的基礎上一種較為有效的改進是，如果兩個表的大小有懸殊，可將小表復制到每個節點中去，在本地用Sort Merge方法完成Join。

(3)連接屬性在兩個表中均不是主索引，例如：

SELECT*FROM table1，table2

WHERE table1.B=table2.C 

這種處理是最差的情況，物理設計階段的任務之一就是要盡量避免這種操作的發生。它常常需要將兩張表都進行重分布。當然在第二種情況中的改進方法如果適用也可以取得較好的效果。實際上，多數并行數據庫連接算法的研究反而是在這里進行的[4]，在此就不做敘述了。

(4)排除合并連接（Exclusion Merge Join）。這種操作常出現在Not In語句中，例如：

SELECT*FROM table1

WHERE table1.A NOT IN 

(SELECT table2.B from table2); 

這種連接其實可以轉換成前面幾種情況來處理。具體到這個例子可以將Table2.B讀出Hash重分布到各節點緩沖區，變換成單節點的同等操作。

合并連接的特點是：需要Join的記錄必須分布到單節點上去才能進行；對每張表只讀取一次；比乘積連接（Product Join）的效率要高；在沒有更好的優化方式時，它是一種比較通用的方法。

4.2 哈希連接（Hash Join）

為了充分利用Hash分布的特點，在特定情況下可以采用Hash連接的方法。如合并連接中的第二種情況，如果Table1是一個大表而Table2又足夠小，可以將Table2復制到每個節點上，然后按連接屬性作Hash排序。這樣的排序結果可以放在主存中，再讀出Table1進行匹配查找。該方法的優點是避免了對大表的排序操作。

4.3 嵌套連接（Nested Join）

如果兩張表的連接屬性上均有索引，在連接數據量較小的情況下，可以考慮利用索引來完成連接操作。設Table1和Table2的B字段上均有子表索引，看下面的查詢語句：

SELECT*FROM table1，table2

WHERE table1.A=table2.B 

如果Table2.B是第一類索引，那么Join工作實際可以用Table1和Table2.B的索引子表在單個節點上完成，然后拿到索引子表中Table2的Rid再去讀Table2的其他屬性并完成連接。顯然，如果是兩張全表的連接，則效率不如合并連接的方法，但是如果在單個表上有低選擇性謂詞，其效率就相對較高了。我們可以大致估算一下其代價。在普通數據庫中利用非聚簇索引，如果查詢的范圍在5%（只考慮I/O代價，與磁盤參數有關），則大致等同于全表掃描的代價。并行結構的代價不應只考慮I/O次數，而要用查詢時間來衡量，因為其優勢就在于將I/O分派到各個節點上去了。這樣如果假設在索引中得到的記錄Rid均勻分布在各節點上，并且忽略節點間數據傳輸時間，那么這個度量應該是5%× N 。雖然在實際的系統中這會是一個經驗值，但已經可以看出，在并行環境下嵌套查詢的可用性被大大地提高了。

4.4 乘積連接（Product Join）

乘積連接也就是邏輯上的Cross Join，是最通用的一種連接，也是代價最高的一種連接。任何連接均可以轉換成乘積連接σπ（A×B）的形式。對乘積連接的操作可以采用以下幾種不同的方式：

(1)如果有一張表較小，可以被完整地放入節點內存，那么將這張表復制到每個節點后，再在單節點內完成連接操作。

(2)如果有一張表可以被分成 N片后放入每個節點的內存，那么可以將第二張表的數據也分成M塊按流水線方式向N 個節點發送，分多次做連接。

(3)兩張表均不能被一次性地放入內存，這樣只能將其中一張表分次發布到各個節點做連接操作，其致命之處在于要對一張表讀取多次，一般應盡量避免這樣的操作。

乘積操作的特點是無須排序，可以充分利用流水線方式的并行性。雖然一般情況下，它是一種代價最高的連接處理方式，但并行優化器在代價模型中會充分考慮到其并行效果來決定是否使用。有關優化器代價模型的設計和改進是下一步的主要研究工作。

通過對連接操作的處理方法進行分析可以看出，基于Hash的數據劃分方法經過針對性的優化和擴展，可以用多種備選方案處理Join操作，具有良好的可操作性。其他如分組聚集等操作同樣是在現有的單個節點上進行，然后按分組屬性重新分布，在單個節點上再做一次聚集，得到全局的結果集。

5 需要進一步研究的問題



本文在基于Hash分布的SN結構并行數據倉庫基礎上討論了一般數據操作的實現，但仍然有很多問題需要進一步的研究：

(1)查詢代價模型的建立以及在此基礎上進行的優化器設計的研究；

(2)針對數據均勻分布和平衡負載的高級Hash算法的研究；

(3)基于本文所述物理結構下的動態負載平衡的實現的研究；

(4)數據倉庫ETL工作的并行化研究。

參考文獻：

[1] Hurson A R， Miller L L.Parallel Architectures for Database Systems[M]. New York:IEEE Computer Society Press，1989.473-480.

[2] W H Inmon. Building the Data Warehouse[M]. 北京: 機械工業出版社，2003.55-99.

[3] 李建中.并行數據庫的查詢處理并行化技術和物理設計方法[J]. 軟件學報，1994，5(10):1-11.

[4] 李建中.并行數據操作算法和查詢優化技術[J]. 軟件學報，1994，5(10):12-23.

[5] Stonebraker M. The Case for Shared Nothing[J]. Database Eng.，1986，9(1):17-24.

[6] Carrie Ballinger. Born to Be Parallel[EB/OL]. http://www.teradata.com/t/，2004-09.

[7] 蔣 躍龍，等.并行數據庫節點故障的處理機制[J]. 計算機科學，2000，10:232-235.

[8] Tandem Database Group. NonStop SQL: A Distributed， High performance， High availability Implementation of SQL[C]. Proc.of the 2nd International Workshop on HPTS，1987.60-104.

[9] 楊 利，等.并行數據庫技術[M]. 長沙: 國防科技大學出版社，2000.11-108. 

[10] 昌 月樓，等.無共享并行數據庫中節點故障對策[J]. 計算機科學，1995，22(5):42-45.

作者簡介：呂成(1982 )，男，安徽當涂人，碩士研究生，主要研究方向為數據倉庫、并行數據庫； 金登男，男，上海人，副教授，碩士生導師，主要研究方向為人工智能、模式識別、數據挖掘。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。