基于列存儲機制下多維數據倉庫模型的優化與研究

徐曉錦 孫 蕾

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

基于列存儲機制下多維數據倉庫模型的優化與研究

徐曉錦 孫 蕾

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

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

數據倉庫 OLAP 無連接星型模型 列存儲 數據壓縮

0 引 言

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

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

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

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

1 基于列存儲機制下的多維數據倉庫模型的優化過程

1.1 基本概念

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

1.2 基于列存儲機制下的星型數據模型的優化

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

圖1 日期維度上Month層全局統一編碼

圖2 地域維度上的City層的局部統一編碼

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

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

圖3 基于層次編碼的模型優化過程

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

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

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

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

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

1.3 面向列存儲機制下優化后模型可采用的復合壓縮策略

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

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

輸入：待壓縮的container

輸出：壓縮是否成功

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

2. Return 對C采用前綴壓縮

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

4. Return 對C采用控制壓縮

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

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

7. Return 對C采用字典壓縮

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

2 實驗與分析

2.1 實驗環境

實驗使用的開發環境為Eclipse，使用的并行數據庫為Teradata 14.10版本。選用Java語言實現了無連接星型模型的編碼以及復合壓縮策略。

2.2 數據集描述

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

2.3 實驗結果及分析

(1) 實驗一

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

圖4 查詢效果圖

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

(2) 實驗二

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

圖5 壓縮效果圖

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

3 結 語

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

[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] 王珊, 王會舉, 覃雄派, 等. 架構大數據：挑戰、現狀與展望[J]. 計算機學報, 2011, 34(10):1741-1752.

[3] 王意潔, 孫偉東, 周松, 等. 云計算環境下的分布存儲關鍵技術[J]. 軟件學報, 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] 王會舉, 覃雄派, 王珊, 等. 面向大規模機群的可擴展OLAP查詢技術[J]. 計算機學報, 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] 王振璽, 樂嘉錦, 王梅, 等. 列存儲數據區級壓縮模式與壓縮策略選擇方法[J]. 計算機學報, 2010, 33(8):1523-1530.

[9] 陸戌辰, 王梅, 樂嘉錦. 列存儲中的OLAP多查詢優化方法[J]. 計算機科學與探索, 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。國家自然科學基金項目(61502170)。徐曉錦，碩士生，主研領域：數據庫理論與應用。孫蕾，副教授。

TP3

A

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