基于列存儲機制下多維數(shù)據(jù)倉庫模型的優(yōu)化與研究

徐曉錦 孫 蕾

(華東師范大學(xué)計算機科學(xué)技術(shù)系 上海 200241)

基于列存儲機制下多維數(shù)據(jù)倉庫模型的優(yōu)化與研究

徐曉錦 孫 蕾

(華東師范大學(xué)計算機科學(xué)技術(shù)系 上海 200241)

通過對分布式列存儲機制下多維數(shù)據(jù)倉庫模型的研究，考慮到多維數(shù)據(jù)倉庫模型上的關(guān)聯(lián)和聚集操作常常會引入大量的數(shù)據(jù)遷移，提出一種有效的列存儲機制下多維數(shù)據(jù)倉庫模型的優(yōu)化方法即結(jié)合層次編碼技術(shù)。采用維表層次全局域編碼和維表層次局部域編碼相結(jié)合的方式對傳統(tǒng)星型模型維表中的層次信息進行二進制編碼整合，將維表的層次信息壓縮進事實表形成無連接星型模型，并針對新模型下的數(shù)據(jù)特征提出一種復(fù)合壓縮策略，以期減少分布式列存儲機制下的OLAP操作引入的數(shù)據(jù)遷移并降低數(shù)據(jù)存儲空間，提升系統(tǒng)的查詢性能。實驗結(jié)果表明，該優(yōu)化方法是可行且有效的。

數(shù)據(jù)倉庫 OLAP 無連接星型模型 列存儲 數(shù)據(jù)壓縮

0 引 言

列存儲系統(tǒng)將數(shù)據(jù)表記錄中同一屬性值存儲在一起，在進行查詢時，列存儲系統(tǒng)只需將需要的列讀入內(nèi)存，減少了無關(guān)列的讀取，非常適合用于讀優(yōu)化系統(tǒng)，故近年來隨著數(shù)據(jù)量的急速增加，列存儲技術(shù)在數(shù)據(jù)倉庫中得到了廣泛的應(yīng)用[1-2]。列存儲機制下數(shù)據(jù)倉庫的模型優(yōu)化[4-6]、數(shù)據(jù)壓縮[7-9]等也被廣泛研究。

傳統(tǒng)行存儲系統(tǒng)下的多維模型多包含維表和事實表，且OLAP查詢處理多涉及事實表和維表之間的關(guān)聯(lián)以及基于維表的層次信息進行聚集等。在分布式列存儲機制下這些操作會引入大量的數(shù)據(jù)遷移，降低系統(tǒng)的查詢性能[3]。故如何消除維表和事實表之間的連接減少數(shù)據(jù)的遷移是非常重要的。如Theodoratos等人[4]采用整數(shù)編碼對維表層次信息編碼提出一種基于混合替代鍵的星型模型，但整數(shù)編碼長度較長且不利于利用維層次前綴編碼來提高分組聚集操作。Karayannidis

等人[5]提出對維表層次信息進行編碼形成層次代理鍵存放到事實表中，然后基于層次編碼對事實表進行聚簇存儲，這樣縮小查詢空間范圍，但增加了存儲空間。王會舉等人[6]提出采用局部的層次編碼技術(shù)將維表的層次信息壓入事實表，從而減少事實表與維表間的連接，但局部層次編碼增加了編碼的復(fù)雜度而且不利于應(yīng)對維表層次信息的變化。為解決上述問題，本文提出采用基于維表層次信息的全局層次編碼和局部層次編碼相結(jié)合的方式對維表中的層次信息進行編碼，并按照一定規(guī)則將維表的層次編碼整合成復(fù)合編碼來替代原星型模型事實表中的主鍵和外鍵，形成無連接星型模型。將維表的層次信息壓入到事實表中，消除事實表與維表之間的連接，并且使得事實表可以獨立執(zhí)行維表上的聚集操作，從而提升系統(tǒng)的查詢性能。

優(yōu)化后的模型用維復(fù)合編碼代替了事實表中的主鍵外鍵，且列存儲將同一屬性下的數(shù)據(jù)組織存儲，增加了數(shù)據(jù)之間的相似性使得該類數(shù)據(jù)更易壓縮，節(jié)省數(shù)據(jù)存儲空間；進一步也可以減少I/O的訪問次數(shù)，提升系統(tǒng)性能。鑒于Abadi等人[7]提出的基于決策樹方法的列存儲壓縮策略，王振璽等人[8]提的區(qū)級壓縮策略等都忽略了不同壓縮方算法適用范圍的重疊性，文中針對優(yōu)化后模型組織下的數(shù)據(jù)特征，細(xì)化考慮列存儲不同壓縮方法適用范圍的重疊性，提出采用多級壓縮的復(fù)合壓縮策略以達(dá)到更好的壓縮效果，進一步提升系統(tǒng)性能。

1 基于列存儲機制下的多維數(shù)據(jù)倉庫模型的優(yōu)化過程

1.1 基本概念

多維數(shù)據(jù)倉庫模型通常包括維表和事實表兩大類，而其組織的數(shù)據(jù)又主要分為度量和維度兩大類。細(xì)分概念如下：維(Dimension)：是人們觀察數(shù)據(jù)的特定角度，是考慮問題時的一類屬性，屬性集合構(gòu)成一個維(時間維、地理維等)；維的層次(Level)：人們觀察數(shù)據(jù)的某個特定角度(即某個維)還可以存在細(xì)節(jié)程度不同的各個描述方面(時間維：日期、月份、年)；維的成員(Member)：維的一個取值，是數(shù)據(jù)項在某維中的描述；度量(Measure)：某特定時間點跟某事物相關(guān)的值。在OLAP中，通常每個維度信息被存儲在一張關(guān)系表中即維表，度量則被存儲在事實表中。星型模型和雪花模型是最典型的傳統(tǒng)數(shù)據(jù)倉庫多維模型，文中的研究以星型模型為例。

1.2 基于列存儲機制下的星型數(shù)據(jù)模型的優(yōu)化

數(shù)據(jù)倉庫的查詢往往涉及維表中的層次屬性和事實表中的度量屬性。傳統(tǒng)的行存儲數(shù)據(jù)倉庫上的查詢會涉及大量的維表和事實表之間的關(guān)聯(lián)，消耗大量的時間。如今大數(shù)據(jù)時代，數(shù)據(jù)量急劇增加，由于基于列存儲上的查詢可以減少無關(guān)列的讀取，故為了加快數(shù)據(jù)的查詢操作，數(shù)據(jù)的存儲慢慢由傳統(tǒng)的行存儲向列存儲轉(zhuǎn)換。目前常用的列存儲分解存儲模型DSM(decomposed storage model)[9]，采用對數(shù)據(jù)庫中的關(guān)系表進行垂直劃分成一些小的二元關(guān)系表的形式存儲每列數(shù)據(jù)。由行存儲轉(zhuǎn)換為列存儲的方式在減少查詢無關(guān)列的讀取的同時也破壞了維表上的層次信息的完整性。為了消除維表和事實表之間頻繁的連接以及保持維表上的層次信息的完整性，文中借鑒泛關(guān)系模式的思想[10]對模型進行優(yōu)化，采用層次屬性全局編碼和層次屬性局部編碼相結(jié)合的方式將維表中的層次信息壓縮到事實表，既保持了維表上層次信息的完整性又使得事實表可以獨立處理數(shù)據(jù)從而更加適用于分布式列存儲系統(tǒng)。模型優(yōu)化涉及的定義如下：

圖1 日期維度上Month層全局統(tǒng)一編碼

圖2 地域維度上的City層的局部統(tǒng)一編碼

定義5 (維復(fù)合編碼) 以維度為粒度，對模型中各個維度的維層次編碼進行組合。本文所采用的編碼規(guī)則：時間維度為第一有限維度，其他維度的優(yōu)先級根據(jù)其成員數(shù)確定，成員數(shù)越少優(yōu)先級越高。

歸納起來，采用基于維表層次信息的全局層次編碼和局部層次編碼相結(jié)合的方式對列存儲機制下數(shù)據(jù)倉庫多維模型的主要優(yōu)化步驟如圖3所示。

圖3 基于層次編碼的模型優(yōu)化過程

? 首先取出多維模型中維表Di上的層次Li。

? 其次取得某維表上的Li層次上的層次屬性全局域gobaldom(Li)和層次屬性局部域localdom(Li)。

? 接著對該維表Li層上的各層次屬性局部域的交集與層次屬性全局域做判斷，若其相似度較高(localdom(Li1∩Li2∩…∩Lij)/gobaldom(Li) >=β)或者Li層的次屬性全局域取值較少(gobaldom(Li)<α)則對該層采用層次屬性全局域編碼，否則采取層次屬性局部域編碼。

? 然后對同一維表上不同層次得到的維層次屬性編碼按照維層次由高至低進行組合形成維表層次編碼且這些維表層次編碼即包含了原多維模型中維表上的層次信息。

? 最后，將多維模型中所有維表層次編碼進行組合形成維復(fù)合編碼，以此來代替原模型中事實表上的主鍵外鍵。維復(fù)合編碼包含了各個維表中的完整層次信息，消除了維表和事實表之間的鏈接操作，減少了分布式列存儲機制下OLAP操作引入的數(shù)據(jù)遷移量，從而提升系統(tǒng)的查詢性能。

1.3 面向列存儲機制下優(yōu)化后模型可采用的復(fù)合壓縮策略

對傳統(tǒng)數(shù)據(jù)倉庫多維模型的優(yōu)化將維表的層次信息壓縮成了維表層次編碼，并且用維復(fù)合編碼代替了原事實表中主鍵外鍵，在一定程度上減少了數(shù)據(jù)的存儲空間。又由于在列存儲機制下同一屬性的屬性值存儲在一起，增加了相鄰數(shù)據(jù)之間的相似性，因此若能對優(yōu)化后模型組織的數(shù)據(jù)進行進一步的壓縮則可得到更好壓縮效率，從而進一步可以減少I/O的訪問次數(shù)，提升系統(tǒng)的查詢性能。

在此，示例性地采用分布式并行處理數(shù)據(jù)庫Teradata[11]對優(yōu)化后模型組織的數(shù)據(jù)進行列式存儲。鑒于在Teradata的列存儲模式下，每個AMP下所對應(yīng)的磁盤矩陣中屬于同一列的數(shù)據(jù)會被存放到同一個container中去，在本案例中的復(fù)合壓縮策略是基于container粒度的。依據(jù)經(jīng)過維層次二進制編碼后的數(shù)據(jù)特征，本文采用前綴壓縮、簡單字典、位圖編碼、游程編碼、空值壓縮、LZ編碼這6種壓縮方法對新模型組織的數(shù)據(jù)進行有效壓縮。具體的復(fù)合壓縮策略實現(xiàn)算法如下所示：

輸入：待壓縮的container

輸出：壓縮是否成功

1. if(C是否是維復(fù)合編碼) then begin

2. Return 對C采用前綴壓縮

3. if(C中的空值比例大于閾值a) then begin

4. Return 對C采用控制壓縮

5. if(C中的相同值所占比例大于b) then begin

6. if(C中的不同值的個數(shù)大于c) then begin

7. Return 對C采用字典壓縮

8. if(C′中的平均連續(xù)長度大于d) then begin

9. Return對C′采用游程壓縮

10. else Return C′

11. else then begin

12. Return 對C采用位圖壓縮

13. else if(C中的屬性值平均長度大于e) then begin

14. Return 對C采用LZ壓縮

15. Return C

其中，算法的步1-步2是對復(fù)合編碼進行判斷壓縮處理，因為維復(fù)合編碼是由多個維度的二進制維層次編碼組合而成比較特殊，且編碼后的事實表按照維復(fù)合編碼進行排序后存儲，使得相鄰維復(fù)合編碼往往含有較多的相同二進制位，故我們對于維復(fù)合編碼采用前綴壓縮；步3-步4是用來處理輸入的數(shù)據(jù)序列中空值較多的情況，若空值比例較大則采用空值壓縮；步5-步14是用來處理數(shù)據(jù)序列中相同值較多的情況，且將簡單字典、LZ編碼和位圖編碼置為同一層次的壓縮，其中步5-步10對經(jīng)過字典編碼后的序列又進一步判斷，對由簡單字典編碼后的連續(xù)序列進行判斷，若平均連續(xù)長度大于d，則采用游程編碼進行了第二層級的壓縮，從而取得更好的壓縮效果。

2 實驗與分析

2.1 實驗環(huán)境

實驗使用的開發(fā)環(huán)境為Eclipse，使用的并行數(shù)據(jù)庫為Teradata 14.10版本。選用Java語言實現(xiàn)了無連接星型模型的編碼以及復(fù)合壓縮策略。

2.2 數(shù)據(jù)集描述

實驗的初始數(shù)據(jù)集是采用星型模型測試基準(zhǔn)稱SSB(star schema benchmark)[12]來生成原始數(shù)據(jù)。SSB是在TPC-H的基礎(chǔ)上設(shè)計的用于測試數(shù)據(jù)倉庫產(chǎn)品的數(shù)據(jù)模型，其中包括1張事實表(LINEORDER)，4張維度表(CUSTOMER、PART、DWDATE、SUPPLIER)，并定義了13條查詢語句。文中使用了文獻[13]提供的dbgen產(chǎn)生原始數(shù)據(jù)，且可用擴展因子來定義測試基準(zhǔn)集的大小，當(dāng)SF=1時，事實表LINEORDER會產(chǎn)生600萬條數(shù)據(jù)。實驗一中使用的擴展因子為5，實驗二中使用的擴展因子為1、2、3、4、5。根據(jù)層次編碼和不同壓縮算法的特點，文中涉及的參數(shù)取值如下：α=256，β=80%，a=30%，b=20%，c=20，d=4，e=20。

2.3 實驗結(jié)果及分析

(1) 實驗一

由于連接操作以及聚集操作是數(shù)據(jù)倉庫上的常用且特別耗時的操作，所以本文分別在原星型模型、編碼改進后的無連接星型模型且無壓縮以及編碼改進后的無連接星型模型且采用復(fù)合壓縮(壓縮效果見實驗二)這3種情況下組織的數(shù)據(jù)上進行連接操作以及聚集操作的測試。我們按照SSB提供的標(biāo)準(zhǔn)規(guī)則編寫相應(yīng)的查詢語句，Q1為選擇操作，Q2為連接操作，Q3為聚集操作。實驗結(jié)果如圖4所示。

圖4 查詢效果圖

由實驗結(jié)果可知，無連接星型模型非壓縮數(shù)據(jù)的查詢性能遠(yuǎn)優(yōu)于原星型模型的查詢操作。這是因為基于原星型模型上的連接操將引入大量的數(shù)據(jù)遷移，繼而消耗更多的時間。由圖5還可以看出基于無連接星型模型的壓縮數(shù)據(jù)的執(zhí)行性能優(yōu)于基于無連接星型模型的非壓縮數(shù)據(jù)，這是因為采用文中設(shè)計的復(fù)合壓縮策略選用輕量級的壓縮方法，極大程度壓縮了數(shù)據(jù)量，并且不需解壓可直接在壓縮態(tài)數(shù)據(jù)上進行查詢[14]，從而使得在系統(tǒng)加載相同量數(shù)據(jù)信息時，可以訪問更少的數(shù)據(jù)塊，節(jié)省了I/O開銷加快了查詢速度。

(2) 實驗二

壓縮率實驗選擇由無連接星型模型編碼的事實表LINEORDER的ORDERPRIORITY列來進行測試。同時也采用C-store提出的壓縮方法[7]和區(qū)級壓縮策略[8]對該列來進行壓縮，并選取SF因子為1、2、3、4、5做了5組對比實驗，實驗結(jié)果如圖5所示。

圖5 壓縮效果圖

由實驗結(jié)果可知，文中提出的自適應(yīng)選擇復(fù)合壓縮策略要比C-store的壓縮策略和區(qū)級壓縮策略的壓縮效果好。這是因為文中提出的復(fù)合壓縮策略先對ORDERPRIORITY列數(shù)據(jù)采用簡單字典編碼和位圖編碼進行了一級壓縮，然后又對由簡單字典編碼壓縮后產(chǎn)生的序列進行分析，滿足序列中相同值連續(xù)平均長度大于4時，再采用游程壓縮方法進行二級壓縮，從而盡可能利用數(shù)據(jù)序列特征，達(dá)到最優(yōu)的壓縮效果。

3 結(jié) 語

在大數(shù)據(jù)時代，為了提升數(shù)據(jù)倉庫在分布式列存儲機制下數(shù)據(jù)的處理性能，文中從兩方面入手：(1)對傳統(tǒng)數(shù)據(jù)倉庫的多維數(shù)據(jù)模型進行優(yōu)化，將原多維模型的維表的層次信息按照層次全局編碼和層次局部編碼結(jié)合的方式進行層次編碼，將維表的層次信息壓縮進事實表，消除事實表與維表之間的連接，減少分布式列存儲下OLAP操作引入的數(shù)據(jù)遷移，從數(shù)據(jù)模型層保證了數(shù)據(jù)計算的獨立性，提升系統(tǒng)的查詢性能；(2)根據(jù)列存儲模式下優(yōu)化后模型組織的數(shù)據(jù)特點，設(shè)計一種復(fù)合壓縮策略，進而節(jié)省了存儲空間并減少I/O開銷，進一步加快查詢。實驗證明，文中設(shè)計的方法能有效消除事實表和維表之間的連接，節(jié)省數(shù)據(jù)的存儲空間，提升數(shù)據(jù)倉庫在分布式列存儲機制下數(shù)據(jù)的處理性能。下一步工作將對文中提出的優(yōu)化思想與目前主流分布式數(shù)據(jù)處理平臺無縫連接做進一步的研究。

[1] Plattner H. A common database approach for OLTP and OL-P using an in-memory column database[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, 2009:1-2.

[2] 王珊, 王會舉, 覃雄派, 等. 架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J]. 計算機學(xué)報, 2011, 34(10):1741-1752.

[3] 王意潔, 孫偉東, 周松, 等. 云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)[J]. 軟件學(xué)報, 2012, 23(4):962-986.

[4] Theodoratos D, Tsois A. Heuristic optimization of OLAP queries in multidimensionally hierarchically clustered databases[C]//Proceedings of the 4th ACM International Workshop on Data Warehousing and OLAP. ACM, 2001:48-55.

[5] Karayannidis N, Tsois A, Sellis T, et al. Processing star queries on hierarchically-clustered fact tables[C]//Proceedings of the 28th International Conference on Very Large Data Bases, 2002:730-741.

[6] 王會舉, 覃雄派, 王珊, 等. 面向大規(guī)模機群的可擴展OLAP查詢技術(shù)[J]. 計算機學(xué)報, 2015, 38(1):45-58.

[7] Abadi D, Madden S, Ferreira M. Integrating compression and execution in column-oriented database systems[C]//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. ACM, 2006:671-682.

[8] 王振璽, 樂嘉錦, 王梅, 等. 列存儲數(shù)據(jù)區(qū)級壓縮模式與壓縮策略選擇方法[J]. 計算機學(xué)報, 2010, 33(8):1523-1530.

[9] 陸戌辰, 王梅, 樂嘉錦. 列存儲中的OLAP多查詢優(yōu)化方法[J]. 計算機科學(xué)與探索, 2012, 6(9):852-864.

[10] Fagin R, Mendelzon A O, Ullman J D. A simplied universal relation assumption and its properties[J]. ACM Transactions on Database Systems, 1982, 7(3):343-360.

[11] Teradata Database[OL]. http://cn.teradata.com/products-and-services/Teradata-Database.

[12] O’Neil P, O’Neil B, Chen X. Star schema benchmark[OL]. http://www.cs.umb.edu/～poneil/StarSchemaB.pdf.

[13] K?mpgen B, Harth A. No size fits all- running the star schema benchmark with SPARQL and RDF aggregate views[C/OL]. http://people.aifb.kit.edu/wa5886/ssb-benchmark/.

[13] Ferreira M C. Compression and query execution within column oriented databases[D]. Cambridge, MA, USA: Massachusetts Institute of Technology, 2005.

REASERCH AND OPTIMIZATION OF MULTI DIMENSIONAL DATA WAREHOUSE MODEL BASED ON COLUMN STORAGE

Xu Xiaojin Sun Lei

(DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China)

Based on the research of multi dimension data warehouse model on the distributed column storage, an effective distributed column storage optimization method with hierarchical coding techniques is proposed, considering that the association and aggregation operation of multi dimension data warehouse model often bring a lot of data migration. The optimization method uses local dimension hierarchical encoding and global dimension hierarchical encoding to encode the level information of the dimension table, and then compresses dimension hierarchies’ information into fact table to form a join-free star schema. Then, a composite compression strategy is put forward for the data feature of the new model to reduce the data migration introduced by OLAP operation and the data storage space under the distributed column storage mechanism, improving the query performance of the system. The experimental results show that this optimization method is feasible and effective.

Data warehouse OLAP Join-free star schema Column store Data compression

2016-01-19。國家自然科學(xué)基金項目(61502170)。徐曉錦，碩士生，主研領(lǐng)域：數(shù)據(jù)庫理論與應(yīng)用。孫蕾，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.02.008