一種基于立方體的復雜查詢的高效算法

摘 要：提出一種高效的整體多特征方查詢算法。該算法首先將數據立方體水平分塊成多個小數據集，然后將各子查詢中的聚集函數分類，并對其中的分布和代數聚集函數使用分布聚集特性優化計算，使得整體多特征方查詢可以局部使用分布多特征方查詢的優化計算方法。實驗結果證明該方法可以有效地提高整體多特征方查詢的效率。

關鍵詞：復雜查詢； 多特征方； 多粒度聚集

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)03-0030-04

0 引言

近年來，對多維空間（MultiDimensional Space，MDS） 上的數據分析成為研究的熱點。多維數據分析有著廣泛的應用前景，如可以實現趨勢預測、發現異常模式，以及回答WhatIf問題等。由于多維數據表的數據特點和數據復雜性，需要分析多個屬性間的關系以及對多個維屬性同時進行操作。多維數據模型采用數據立方體（Data Cube）形式。數據立方體表示多維數據的優勢在于它能在多個粒度層上表示數據，同時有利于計算聚集值?；跀祿⒎襟w的查詢可以方便地進行各種OLAP操作[1]，如上卷、下鉆、切片、切塊等。由于海量數據所帶來的問題，完全物化整個數據立方體是不現實的。目前很多研究工作均集中在如何有效減小立方體大小，提高聚集計算速度，從而快速響應查詢等方面。這些研究一般針對的都是簡單查詢。簡單查詢大多可以直接使用分布聚集函數（如sum()，count()等）或代數聚集函數（average()等）實現。隨著數據挖掘技術的發展和商業競爭的需求，多粒度的復雜聚集研究已經成為數據立方體技術進一步發展的方向[2]。多粒度的復雜聚集是基于立方體的復雜查詢的基本特征。相對于簡單查詢，復雜查詢能提供更多和更詳細的數據信息，對決策分析提供強有力的支持。現有的決策支持系統追求的目標就在于如何有效地回答大型數據庫的復雜查詢。立方體查詢之所以不同于一般的SQL查詢，就在于它允許在多個粒度上計算聚集值。復雜查詢實例如下：

查詢1 按{month， customer， item}的所有分組， 求出2004年的最低價格，并在最低價格的元組中，找出銷售量最大和最小的商品利潤總和。

查詢2 按{month，customer，item}的所有分組， 求出2004年所有分組的最低價格，并求出各分組中商品價格在最低價格的125%、150%、175%以內的商品總銷售量。

上述立方體查詢將會在八個不同粒度上計算聚集值[3]，分別是{month}、{customer}、{item}、{month， customer}、{month， item}、{customer， item}、{month， customer， item}和{*}。其中，“*”表示所有（ALL）。 這里的每個粒度，就對應著SQL中的一個Group By分組。

根據上述復雜查詢的實例，可以歸結出基于立方體的復雜查詢具有這樣一些特點：①查詢在所有可能的2n （n為分組維屬性的個數）個粒度上進行計算；②復雜查詢由多個具有聚集依賴關系的簡單查詢構成，這些簡單查詢構成了復雜查詢的子查詢。文獻[4]將這種在所有可能的2n個粒度進行的具有聚集依賴關系的復雜查詢稱為多特征立方體(MultiFeature Cubes，MFCubes）查詢。多特征方查詢依據查詢中所使用的聚集函數類型進行分類。在文獻[1]中將聚集函數類型分為三類，即分布（Distributive）、代數（Algebraic）和整體（Holistic）。相應地，多特征方也分為分布多特征方、代數多特征方和整體多特征方三類。

分布多特征方查詢有一個明顯特征，那就是粗粒度的聚集結果可以由細粒度的聚集結果計算得到，如查詢1為分布多特征方查詢的典型實例。假設在細粒度{month， custo￣mer， item}上計算了等于最低價格的各個月份的銷售量總和，則粗粒度{customer， item}的銷售量總和就等于細粒度{month， custo￣mer， item}中計算的12個月的銷售量相加，不必重新計算。本文稱這個特征為分布聚集特性，用于描述兩個粗細粒度間的聚集計算依賴關系。代數多特征方通過變化聚集函數也可轉換為分布多特征方，也可以使用這種聚集計算特性來實現計算的優化，如count()函數可以由sum()/n計算得出。

整體多特征方就不能直接使用分布聚集特性來優化計算。例如，查詢2為整體多特征方查詢的實例。細粒度{month， customer，item}的查詢結果不能用于計算粗粒度{customer， item}的查詢結果。已經計算了粒度{month， customer， item}的最小價格MIN(price)及各個子查詢的銷售總和SUM(R1.sales)， SUM(R2.sales)， SUM(R3.sales)。假設計算出1月份的最低價格是120美元，在最低價格150% 以內（120～180美元）的商品的銷售總和為2 000美元，而整年的最低價格是110美元，則在最低價格150%內的價格取值區間是110～165美元。無法簡單地將12個月的銷售總和相加得到整年的銷售總和，因為無法知道1月份的2 000美元中哪些是在110～165美元。

對于分布和代數多特征方查詢，由于可以直接使用分布聚集特性來簡化計算，對此已經提出了許多有效的實現技術，如PartitionedCube 算法[5]、BUC算法[6]以及OVERLAP算法[3]等。因為整體多特征方需要對各個子方獨立計算各粒度的聚集值，計算復雜度和計算代價較前兩者高出許多，所以，需要為整體多特征方查詢尋找更有效的實現方法。文獻[4]中也簡單地提到可以用PartitionedCube[5]算法中的數據分塊方法來實現，該算法是實現分布和代數立方體查詢的經典算法。PartitionedCube算法采用水平分塊方法將數據立方體分塊為多個適合內存大小的子方，然后在每個子方遞歸地實現分布和代數立方體查詢聚集計算。對于整體多特征方，需要對分塊得到的子方獨立計算各粒度上的聚集值，分別回答各個粒度上的子查詢。這種獨立計算各個粒度上聚集值的代價無疑是巨大的，特別是當分組屬性較多的時候。有沒有更有效的解決方法呢？

考慮到復雜查詢是由具有聚集依賴關系的多個簡單查詢構成，因此，復雜查詢中的聚集函數也可由簡單查詢的聚集函數組成，一般為分布聚集函數、代數聚集函數和整體聚集函數。分布和代數多特征方中不會含有整體聚集函數，而整體多特征方則很有可能是它們的組合，如查詢2中的聚集函數就是分布聚集函數MIN（）和用戶自定義函數，如1.75MIN（）。根據這個特點，可以先將子查詢的聚集函數分類，含分布和代數函數的子查詢可以使用分布聚集特性來優化計算，以提高復雜查詢的性能。同時，若自定義函數中也含有分布函數，則也可以進行聚集優化計算。

例如，查詢2中共有子四個查詢，其中第一個子查詢為求最小價格，這是一個分布聚集函數，因此在計算每個子方時，多個粒度間可以使用分布聚集特性實現，即粒度{AB}的最小價格可以由粒度{ABC}的各組最小值直接計算得到，而不必重新計算。其后的三個查詢是分布函數和代數函數之外的自定義函數，也并非需要如文獻[5]所說的那樣完全獨立計算每個粒度的聚集值。雖然不能將粒度{month， customer， item}的計算結果直接用于計算，但是假設粒度{month， customer， item}中有6個月的最小價格MIN(price)與粒度{customer， item}的最小價格是一致的，則在求粒度{customer， item}的計算過程中，就不需要重新計算這相同的6個月的聚集值，只需要計算余下6個月的聚集值即可。本文稱這兩種優化計算過程為局部聚集優化特性。

本文正是基于局部優化特性對整體多特征方進行查詢計算優化的。這是首次提出的對整體多特征方的優化算法。優化后的算法與PartitionedCube算法在模擬數據集上進行對比實驗，優化算法ImpPartitionedCube查詢效率的提高可達到90%以上。

1 整體多特征方查詢實現算法及其描述

算法的第一步是將數據立方體進行分塊處理，即將立方體分成多個子方，在各個子方上計算粒度聚集值。分塊是由于數據集太大，內存無法一次處理完而采取的基本方法。對于立方體分塊，一般有兩種分塊方法：①垂直分塊方法，如Arraybased Cube 算法[7]，即按立方體中所有分組維屬性的值均勻分塊。這樣的分塊方法不能使同一個分組的數據在同一個塊，不適合于粒度的分開計算。②水平分塊方法，即PartitionedCube[5]的分塊方法，按某個分組維屬性的值分塊，使得同一個分組的所有數據同在一個塊中。例如，分組維屬性有月份和地區，可以先按月份分塊，最多分12個塊，每個塊為一個月份的數據，若每個月份數據量太大，則對每個月份的數據再按地區分塊。這種分塊方法確保了同一個分組的數據在同一個塊中，因此適合于粒度的獨立計算。

對于整體多特征方查詢的實現，一個直接的辦法就是采用文獻[5]的PartitionedCube算法，水平分塊后獨立計算每個粒度上的聚集值。由于PartitionedCube完整算法是為實現分布和代數這兩種立方體查詢的，先將其修改為適合整體多特征方計算的ModiPartitionedCube算法。

1.1 ModiPartitionedCube算法實現整體多特征方查詢

ModiPartitionedCube算法思想主要有以下兩點：

①將數據立方體分化為多個適合內存大小的子方（MemoryCube）；

②在每個子方上獨立執行各個復雜的查詢操作（Independent Operation）。

修改后的算法描述如下：

算法中步驟（1）選擇一個分塊維屬性B_i;（2）為一個分塊程序實現將R按B_i分塊;（3）～（9）是計算含分塊維屬性的粒度分開計算;（10）、（11）是對不含分組維屬性Bi的粒度分開計算，只需要將去除B_i屬性后的立方體重復前面的過程即可，對沒有計算的粒度的實現過程也同步驟（10）和（11）。算法略。

如前所述，ModiPartitionedCube算法的實現方法需要獨立計算各個粒度上的聚集值，當立方體很大時，計算復雜，時間開銷大，查詢效率低。特別是當分組屬性很多時，實現這類復雜查詢的代價會更大。本文采用優化策略正好可以有效彌補這種不足。

1.2 改進算法ImpPartitionedCube算法思想及描述

1.2.1 算法思想

ImpPartitionedCube算法思想主要有：

①將數據立方體分塊為多個適合內存的子方；

②對各個子方，使用局部聚集優化特性計算多個粒度（Dependent Operation）。

下面分別敘述算法處理過程：

（1）立方體分塊處理

算法的第一步與ModiPartitionedCube算法一致。首先，按分組維屬性B_i( B_i∈{B₁，…， B_m})，將立方體水平分塊為n 個子方R₁，…，R_n，這n 個子方含全部分組維屬性B₁，…，B_k；若cardinality(B_i)足夠大，則得到的子方所含元組數為T/n。其中T為立方體的元組總數，ｎ不大于B_i的基數，即ｎ≤cardina￣lity(B_i)。例如，若按分組屬性Ａ分化，假設cardinality(A)=20，則基本表第一次分化的子方個數不超過20。對每個按分組維屬性分化得到的子方R_i，檢測其大小，若仍然很大，則進行二次分化，繼續選擇下一個分組維屬性，分化的方法一樣。

對分化得到的每個子方，分別進行各粒度上的查詢聚集計算。按分組維屬性分化得到的所有粒度分成兩組：

一組含分組屬性B_i，可以在這n 個子方上計算出來。聚集計算之前，先按粒度中的維屬性進行排序。對于排序，本文采用了先計算細粒度再計算粗粒度的計算次序，這樣做可采用PIPESORT[3]算法中的共享前綴排序技術。例如，若先對細粒度{ABC}進行排序和操作，然后計算粒度{AB} ，就無須再對AB排序，直接可以共享前面排序的結果。

對于不含分組維屬性B_i的各粒度計算，可以有兩種方法：①重新遍歷每個子方，分別計算各個子方數據；②將R再次分化，重新讀取數據。此次分化的R含（K-１）個分組維屬性（不含B_i），實現方法與前面含K個分組屬性的過程一樣。我們采用的是方法②，因為它分化得到的子方要少于方法①，這樣可以減少遍歷的子方數目。

（2）按子查詢聚集函數分類處理對分布和代數聚集函數使用局部聚集優化特性優化聚集計算

在確定粒度計算順序后，為了使用分布聚集特性，將各個子查詢中的聚集函數進行分類：一類為分布或代數函數；另一類為整體聚集函數。先計算前者，這樣可以利用使用部分聚集特性來優化計算，再計算整體聚集值。例如查詢2， 計算最小價格時就可以使用分布聚集特性，計算后三個子查詢時采用的是逐個測試的方式，以確認能否使用局部的分布聚集特性。

例如，分組維屬性為{A，B，C}，其粒度個數為八個，執行這八個粒度上的聚集計算需要以下過程：①先按A分塊，則得到的子方可逐次計算含A的三個粒度ABC、AB和A。②對于含屬性B的粒度計算，則是將數據集去掉屬性列A后，對余下的數據集進行操作。若仍大于內存，則按屬性B進行分塊，對分塊后的子方逐次計算粒度BC和B。③若在②中不需要分塊，則直接對其中的立方體計算粒度C，采用類似②的操作，去掉屬性列A和B，僅含分組維屬性C。若還大于內存，則按C分塊，計算粒度C。④若在③中不需要對C分塊，則直接對其中的數據集計算粒度ALL；否則去掉所有的分組維屬性A、B、C，對余下的數據集進行類似②的操作，計算粒度ALL。

算法中步驟(2)實現將R分塊，按 B_i分化，若基本立方體無須分塊，則分塊個數n=1；（3）～（11）是對分塊后的子方計算含維屬性B_i的所有粒度；（6）先對子方排序，為使用共享前綴排序技術，先按最細粒度的維屬性排序；（7）和（8）是對含分布和代數聚集函數的子查詢使用局部聚集優化特性計算；（9）和（10）是對余下子查詢計算聚集值；（12）和（13）對不含分組維屬性B_i的粒度進行計算，只需要將去除Bi屬性后的立方體重復前面的過程即可，對余下沒有計算的粒度，也是重復（12）和（13）。算法略。

2 實驗和結果分析

算法用VC++6.0實現，采用隨機函數生成四組均勻分布的模擬數據集，元組數為100萬～500萬。數據表含五個維屬性，分組維屬性個數為3，詳細參數如表1所示。在內存為2.0 GHz、CPU主頻為2.6 GHz、操作系統為Windows 2000的Dell Workstation PWS650計算機上進行實驗，將ImpPartitionedCube算法與PartitionedCube算法進行比較。假設將大型數據集分塊一次得到的子方均適合內存。實驗的目的主要是比較ImpPartitionedCube算法與ModiPartitionedCube算法的性能，兩種算法分塊的次數與子方個數是相同的，排序過程也是相同的，故實驗結果中的時間不含立方體分塊時間和排序時間，是復雜查詢實現各個子查詢的聚集計算的時間效率。用兩種算法對復雜查詢2的查詢效率進行比較，實驗結果如圖1所示。

從圖1中可以看出，使用了局部分布聚集特性計算的算法性能提高很明顯，最低也提高了80%，高時達到90%以上。提高的主要原因在于采用了局部聚集優化特性優化計算過程后，簡化了聚集計算過程，使遍歷數據量大大減少。實驗實現復雜查詢2，有一個分布函數，遍歷數據量只有ModiPartitionedCube算法的45%左右。

3 結束語

本優化算法是針對整體多特征方的優化算法，其優越性主要有：①將立方體進行水平分塊，適合粒度的分開計算；②將各子查詢的聚集函數分類，對分布函數使用分布聚集特性進行查詢的優化，改進了原來的整體多特征方不能用分布聚集特性的不足。在模擬數據集上進行實驗驗證，結果證明使用局部分布聚集特性優化計算后的整體多特征方算法的性能顯著提高。

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