封閉立方體反轉索引查詢優化技術

收稿日期：2007-11-22；修回日期：2008-03-28

基金項目：廣東省科技計劃資助項目(2006B11301001)；廣州市科技計劃資助項目(2006Z3-D3081)

作者簡介：肖偉吉（1983-），男，廣東汕頭人，碩士研究生，主要研究方向為數據倉庫（xwjxwj238@163.com）；奚建清（1962-），男，江蘇人，教授，博導，主要研究方向為數據庫和數據倉庫、P2P分布式系統、中文信息處理、知識管理、軟件開發技術；歐國華（1969-），男，廣東清遠人，工程師，主要研究方向為計算機應用*

（華南理工大學 計算機科學與工程學院，廣州 510006）

摘 要：處理用戶復雜查詢請求的速度是數據倉庫關鍵性能之一。論述了在QC算法產生的聚集表上建立反轉索引和查詢并還原出立方體上界的方法，查詢算法包括位圖查詢算法和反轉列表查詢算法。最后進行了性能測試，結果表明這兩種算法均能夠提高查詢的速度。

關鍵詞：封閉立方體；位圖查詢算法；反轉列表查詢算法

中圖分類號：TP311

文獻標志碼：A

文章編號：1001-3695(2008)10-2977-05

Inverted index search optimization technology of closed cube

XIAO Wei-ji，XI Jian-qing，Ou Guo-hua

（School of Computer Science Engineering， South China University of Technology， Guangzhou510006， China）

Abstract:The speed of dealing with the users’ complex queries is one of the key performance of the data warehouse. This paper dissertated the methods of making inverted index on aggregate table by QC algorithm and searching and reverting the upper bound of the cube. The search methods included bitmap search algorithm and inverted lists search algorithm. Finally， carried out performance test. The result shows that these two algorithms can improve the query speed.

Key words：closed cube; bitmap search algorithm; inverted lists search algorithm

為了提高聯機分析處理整體的查詢性能，本文利用QC算法[1，2]建立了封閉立方體，并在其產生的聚集表的每一個維度上建立反轉索引。同時設計和實現了在反轉索引上的兩種查詢算法，即位圖查詢算法和反轉列表查詢算法，提高了查詢的性能。

1 立方體上界的生成

11 封閉立方體的特性

李盛恩等人在文獻[3]中定義了覆蓋、基本元組集和封閉元組的概念如下：

假設關系R的模式是R(A1，A2，…，An ，M)。 其中：A作為維屬性，1≤i≤n; M作為度量屬性; A1，A2，…，An是R的關鍵字。用C 表示由R 產生的數據立方體。

定義 1 t1∈C， t2∈C， Ai， 1≤i≤n，如果滿足以下條件，則稱t2覆蓋t1或t1被t2覆蓋：

如果t2 (Ai )≠all，則t1 (Ai) = t2 (Ai )；

如果t2 (Ai)=all，則t1(Ai )可以取任意值。

例如：元組(*，0，*，40)覆蓋元組(*，0，1，30)，(*，0，0，10)， (0，0，*，40)，(0，0，1，30)，(0，0，0，10)，(*，0，*，40)。其中：40為度量值。

定義2 元組t 的基本元組集為BTS(t′)={t′|t′∈R，t∈C，t覆蓋t′}。

例如：BTS((0，1，*，80))={(0，1，1，20)，(0，1，2，60)}，BTS((0，1，1，20))={(0，1，1，20)}。由定義1 和2 可知，如果t2覆蓋t1 ，則BTS(t1)BTS(t2)。

定義3 對于元組t1∈C，如果不存在元組t2∈C， t2≠t1，t1覆蓋t2，并且BTS(t1)=BTS(t2)，則稱元組t1為封閉元組。

例如：元組(*，*，*，160)不是封閉元組，因為它覆蓋元組(0，*，*，160)，并且它們的BTS相等。

筆者還在上面定義的基礎上提出了下面兩個定理。為本文的查詢優化算法提供了理論基礎。

定理 1 在封閉數據立方體中對任意的聚集函數，均可以從某個封閉元組中得到非封閉元組的聚集函數值。

例如：元組(*，0，*，40)覆蓋封閉元組(0，0，*，40)，(0，0，1，30)和(0，0，0，10)，因為元組(0，0，*，40)中出現all的次數最多，所以BTS(*，0，*，40)=BTS(0，0，*，40)，兩者的聚集函數值相等。

定理2 如果按照第i，i+1，…，n+1層的次序查找被t覆蓋的封閉元組，并且如果在第j (j≥i)層找到則不必到第j +1層繼續查找。

根據文獻[3]中的定義和定理，在檢查n個滿足條件的封閉元組時，不必把整個立方體數據全部讀入內存，可以按照一定的次序一部分一部分地加載，當找到一個滿足條件的封閉元組時就停止查找。

通過上面的定義及定理，封閉立方體中查找一個元組的過程可以分解為兩步:a)利用某種存取方法(如索引)從外存上找到滿足上界條件的類，并將這些類一一讀到內存;b)在內存中利用下界作最后的判斷。由于只保存上界，本文的查詢優化算法針對上界而設計。

12 封閉立方體上界的求解

封閉立方體的上界集是通過商立方體和QC-Tree算法產生的，從文獻[2]中派生出一個產生上界的具體例子，如事實表和維表分別如下：

事實表（gid、pid、tid分別是地理維、產品維、時間維的編號）

gid

pid

tid

sales

1116

12112

2129

維表

Geo（地理維）

gidcountryprovincecity

1CNGDGZ

2CNYNKM

Product（產品維）

pidCategory

1P1

2P2

Time（時間維）

tidhalfyear

1S

2F

筆者用*號表示最高的層次，即該維的任意值。

Geo

allcountryprovincecity

*CNGDGZ

*CNYNKM

Product：

allcategory

*P1

*P2

Time：

allhalfyear

*S

*F

下面利用層次聚集算法生成聚集圖，如圖1所示。

Countryprovince city cat halfyear sales

CNGDGZP1S6

CNGDGZP2S12

CNYNKMP1F9

QC算法求上界集分為三步：

a）求上界；

b）投影；

c）求覆蓋集。

求解過程如下：

輸入：

(* * *)，View

(* * *) -> (CN * *)

(GD * *) ->(GZ * S)

(GZ P1 S)->(GZ P1 S)

(GZ P2 S)->(GZ P2 S)

(YN * *)->(KM P1 F)

(CN P1 *)->(CN P1 *)

(CN P1 S)-> (GZ P1 S)

(CN P1 F)-> (KM P1 F)

(CN P2 *)->(GZ P2 S)

(CN * S)->(GZ * S)

(CN * F)->(KM P1 F)

求出上界集如下：

(CN * *)0

(CN P1 *)1

(GZ * S)2

(GZ P1 S)3

(GZ P2 S)3

(KM P1 F)3

從求解過程可以看出上界集具有如下特點：

a）“*”號表示該維上任意的值，具體值的個數表示所在的層次。

b）在上界集中，記錄是按層次從小到大排列的。

c）查詢的記錄存在覆蓋的關系，當在入口層找不到時，將向下面一層找，一直到最后一層，如果找不到則返回。下面是覆蓋查詢的例子：

(GD * *) -> (GZ * S)

(* * S)-> (GZ * S)

2 反轉索引的建立和壓縮算法

文獻[5，6]提出了許多針對OLAP的索引，如位圖索引、多維索引、連接索引等。文獻[4]中給出了如何在Oracle中創建位圖索引的簡單方法。文獻[7]中作者認為建立和維護位圖索引時間和空間代價小，且位圖索引可以彼此一起工作以達到減少搜索空間的目的，所以作者認為在數據倉庫環境中，位圖索引比B樹索引更有優勢。

本文在QC算法產生的上界集上建立反轉索引。下面講述建立的方法。

在QC層次聚集算法中，上界集中的記錄是按從低層到高層遞歸生成的，低層的記錄存在高層記錄的覆蓋，層次越高，實例化的維就越多，最后一層每個維度都被實例化。雖然層次聚集算法產生上界的過程中產生的層次是不定的，即可能先產生第三層的記錄，又產生第一層記錄、第二層記錄，又產生第三層記錄，但這并不影響最終生成的上界次序。假如生成的原始上界數據如表1所示，它有五個維度，分別為{A，B，C，D，E}和一個度量{F}。

表1 上界集原始數據tidABCDEF1a1b1***32a1b2c1**53*b1c1*e194a1*c2d1e265a3b2c3d2e346a2b1c1d1e247a3b1c2d2e3721 反轉索引的建立

2. 1. 1 反轉索引的建立方法

在Oracle中也應用了反轉索引技術[8]，本文的建立方法是對于每一個維度的每一個屬性值注冊一個元組ID的列表L與它聯系起來。這里ID列表其實就是該維度屬性值出現在上界集中行的行數。例如，對于第一個維度A，其屬性值a1出現在上界集1，2，4行，那么屬性a1聯系的ID列表就是{1，2，4}。對于五個獨立維度的反轉索引ID列表如表2~6所示。

表2 第一維度A 的反轉索引屬性值ID列表L列表的大小a11243a261a3572表3 第二維度B 的反轉索引屬性值ID列表L列表的大小b113674b2252

表4 第三維度C的反轉索引屬性值ID列表L列表的大小c12363c2472c351表5 第四維度D的反轉索引屬性值ID列表L列表的大小d1462d2572表6 第五維度E的反轉索引屬性值ID列表L列表的大小e131e2462e35722. 1. 2 反轉索引性質

定理3 反轉索引列表的存儲空間小于等于原始上界集的數據使用的存儲空間。

證明 設產生的上界集有T個元組和D個屬性維，則需要存儲的空間為D×T個整數。現在考慮反轉索引，每個元組和D′（D′≤D ，因為“*”號屬性不包括在內）個維度屬性相聯系，因此在反轉表中將出現D′次。那么整個反轉索引僅需要D′×T（D′≤D）個整數。故結論成立。

通過以上對上界集進行反轉索引的建立過程可以看出，建立的反轉索引有如下的特點：

a）基于獨立維度進行索引，并不需要按維度順序進行索引。

b）索引后文件體積不大于原來的上界集產生的文件大小。

c）在數據立方體中不再需要存儲非度量維。

d）每一維的每一個屬性值v（v≠“*”）的元組ID列表代表了該屬性值在上界集中出現的一系列位置，這些位置是按升序排列的。

e）可在生成上界集的同時生成索引文件，降低了磁盤訪問開銷。

22 反轉索引存儲壓縮算法

上面介紹了如何對上界集作反轉索引，通過具體的數據集實驗測試，發現了封閉立方體產生的上界集，每一維有很多屬性值出現在上界集中的行位置具有連續性，因為QC算法依次對第一維到最后一維的屬性值進行了排序。

比如屬性值a1可能連續出現在第1～500行，屬性b2可能連續出現在第200～600行。利用這個特點可以對反轉索引的存儲進行壓縮。比如屬性a1，存儲為{-1，1，500}，屬性b2存儲為{-1，200，600}。這里{-1}是一個標記，表示后面連續的兩個數字是這個屬性的一個范圍。通過這種存儲方案，存儲的空間減少了。

通過測試發現，對于一個九維50萬的數據集，原始大小為83.1 MB，反轉索引大小為57 MB，壓縮的反轉索引為25.8 MB。可見，壓縮反轉索引節省了約69%的空間。

3 查詢算法的設計與實現

在第2章反轉索引建立后，由數據倉庫MDX模塊的解析產生了一個點查詢集合。這些點查詢需要有快速查詢的算法提供支持，滿足用戶快速獲得查詢度量結果的需要。下面設計并實現兩種有效的查詢優化算法，這兩種算法都是基于上面建立的壓縮的反轉索引。在介紹查詢算法之前，通過一個具體的例子看看在上界集中怎么查找到用戶需要的上界。

對于表1中的原始數據，屬性對應的元組ID列表為表2～6，假如現在用戶給出了一個點查詢c=（a1，*，c2，d1，e2），屬性值a1、c2、d1、e2可能同時出現在多個共同的上界中，僅僅需要找到最小的共同上界即可。在這個例子中，本文從對應維度的元組列表中分別找出屬性值對應的元組列表：L1 (a1) = {124}; L3 (c2) = {47}; L4 (d1) = {46};L5 (e2) = {46}。很明顯，共同的上界為{4}，而且用戶的查詢本身就是一個上界，所以返回度量值6給用戶，查詢結束。

如果用戶給另一個查詢d={*，b1，c1，d1，*}，采用相同的方法：L2(b1) = {1367}; L3(c1) = {236}; L4(d1) = {46}。得到共同的上界{6}，在上界集中對應的上界是(a2，b1，c1，d1，e2)。可見，用戶的查詢是一個覆蓋的關系，即在入口層3（該查詢有三個實例化的維度）找不到該記錄，應該繼續往下面的層找，反轉索引很好解決了覆蓋的問題，最后返回給用戶查詢得到的度量值4，查詢結束。

31 位圖查詢算法的設計與實現

3. 1. 1 位圖查詢算法

輸入：一個點查詢q={…*，v1，…*，…vk….}(查詢是vk 和 * 的任意組合 )

輸出：q上界的度量值

方法：

a） 加載查詢q中某個非“*”的度量值的元組ID列表Lk（不一定要按維度順序加載）；

b）調用函數int getBitmap（Lk）；

c）如果還有非”*”的度量值的維度沒有加載，回到a）；

d）找到查找記錄所在的上界，返回找到的度量值，否則返回空。

函數int getBitmap（Lk）如下：

a）如果查詢第一次，調用該函數；否則轉到b），讀取第一個維度值的元組ID列表，申請動態位圖向量bitVector1，大小為上界集的總行數。根據元組ID列表設置位圖的相應位為1。

b）申請大小為上界集總行數的位圖向量bitVector2，根據Lk設置bitVector2的相應位為1。

c） 位圖向量bitVector1和bitVector2作與()操作，結果放到bitVector1，即bitVector1 = bitVector2。

d） If(bitVector1沒有為1的位)返回 -1（表示查詢結果找不到）。

e）If（查詢結束）返回bitVector1向量中首先出現1的位置值，否則不返回任何結果。

312 位圖查詢實例

假如對于表1的上界集有一個簡單的點查詢q={*，b1，c1，*，*}，筆者分別從表3、4中讀出維度屬性值b1、c1對應的元組ID列表，并設置相應的位圖向量，如表7所示。

表7 查詢的實例化維度值位圖向量屬性值元組ID列表位圖向量b113671100101c12360100110

通過位圖查詢算法，得到的結果位圖向量是0100100，可以看出，上界中的第三條和第六條上界是滿足本文的查詢條件的，筆者只需要返回最上面的那條上界對應的度量值9給查詢的用戶，查詢結束。可見，這條查詢記錄也是一個覆蓋查找。

32 反轉列表查詢算法

輸入：一個點查詢q={…*，v1，…*，…vk…}(查詢是vk 和 * 的任意組合 )

輸出：q上界的度量值

方法：

a）首先加載查詢q中所有非“*”的度量值的元組ID列表集合L1…Lk；

b）在每個Lk中的末尾增加“-2”作為結束標志；

c）調用函數CCInvertedListsQuery（L1…Lk）;

d）找到查找記錄所在的上界，返回找到的度量值。

函數CCInvertedListsQuery（L1…Lk）如下：

（a）初始化beginval=元組ID列表的第一個值；

初始化rdim=開始的維度；

初始化temp=入口層的行數;

初始化unchange=true;

（b）while(true) {

for(1≤i≤k){

if(i==rdim )；//什么都不做

else {

temp=調用函數SequenceSearch（Li，beginval）

if（temp=-2）return; //找不到，返回

if(temp!=beginval){

beginval=temp; //改變比較初值為當前元組ID列表較大的值

rdim=i;//標記當前重新開始查找計數的那個維度序號

unchange=1; //還未找到

break；//跳出開始重新計數}

}

}

if（unchange）返回找到的結果

}

函數SequenceSearch（Li，beginval）如下：

while（Li未到結束標志-2）{

if(Li的值是-1){

讓firstval=Li下個值；

secondval=Li接下來的值；

if(firstval<=beginval beginval <=secondval)返回beginval;

//找到了

else if（firstval > beginval）返回firstval；

else 重新開始循環；}

else if(Li當前值 > beginval)返回這個當前值；

//如果遍歷到Li末尾，找不到返回-2

return -2;

雖然這種算法中SequenceSearch采用的是順序查找，因為筆者采用了壓縮算法，以至于無法用二分查找算法，但在實際的項目中，它比文獻[10]中提出的沒有采用壓縮的反轉索引聯合二分查找的算法——列表求交算法快很多。后面會給出一個測試結果分析。

33 上界的還原算法

上文設計和實現了兩種查詢算法，索引建立后并沒有保存原來的上界。但查找的過程可能會用到其他技術來提高查詢速度，如緩存策略，則可能需要用到原來的上界。下面給出不保存原始上界集，從反轉索引（此處的反轉索引需要對“*”也記錄其元組ID列表）直接獲得上界的算法。

輸入：一個點查詢q={…*，v1，…*，…vk…}(查詢是vk 和 * 的任意組合 )和找到該點查詢在上界中的位置即元組ID位置N

輸出：該點查詢的上界cell

方法：

a）加載查詢q中第i個出現“*”的維度的元組ID列表Li；

b）調用二分查找函數BinarySearch（Li，N），如果找到，則“*”就是查詢q在維度i上的上界值；如果找不到，轉到下一步；

c）根據維度i上的映射表map（該表大小為維i的勢C，記錄了該維上所有不同的屬性值），加載該維上所有元組ID列表LCj(j=1，2，…，C)；

d）for（j=0;j < C; j ++）

{

調用二分查找函數BinarySearch（LCj，N）；

If(在該LCj 上找到N)

{

cell[i]=map[j].first;

// LCj對應的維度屬性值作為該維度上的上界

break;

}

}

e）如果查詢q中還有“*”未處理，回到a）；

f）返回最終找到的上界cell。

算法的時間復雜度為O(C+1)log N。其中：C表示這個維的勢，取N為該維度所有值元組ID列表中含最多位置的元組ID列表大小。總的時間復雜度，假設現在的點查詢有D個維度為“*”號，則為O((C+1)D log N)。

4 算法性能測試

41 索引建立存儲空間比較

下面就一個九維度的基本表進行預計算得到其上界集，并通過圖表比較不進行索引的原始上界集大小，進行反轉索引后的上界集大小和壓縮反轉索引后的上界集大小。

圖2是用來作預計算的五個基本表的記錄條數以及對應的文件大小。

預計算后的結果如圖3所示。

從實驗的結果可以看出，建立反轉索引的過程中沒有對“*”號進行存儲，所以比原來上界節省了空間。通過壓縮的反轉索引，本文進一步壓縮存儲的空間。同時也為后面的查詢算法準備了數據源(這里沒有考慮存在緩存的情況，緩存可能需要保存“*”位置)。

42 查詢算法性能測試

為了比較查詢算法性能，筆者同時實現了文獻[9]中提到的列表求交算法，本文的位圖查詢算法與反轉列表查詢算法作一個性能上的比較。

421 測試環境

運行程序的測試環境如下：

機型：IBM ThinkPad R52

CPU: Inter Pentium M1.73 GHz

內存：DDRII 533 256 MB＋ 1 GB

硬盤：40 GB 5400RPM

操作系統：WindowsXP Prof.SP2

422 對Sales數據集的測試

Sales數據集是FoodMart2000數據庫的一個基本表，FoodMart2000是一個食品超市的實際數據記錄。下面對Sales數據集進行預計算（表8），并比較不同查詢算法性能的差異。

表8 Sales數據集預計算結果MBSales基本表大小原始上界集大小反轉索引大小壓縮反轉索引大小12.219.719.15.39

Sales數據集的上界集總共有190 821條記錄。不同查詢算法的性能比較：

a）查詢總時間比較（圖4）；

b）查詢平均時間比較（圖5）；

c）查詢最大時間比較（圖6）。

4. 2. 3 對九維基本表的測試

本測試是基于一個九維度500 000條記錄的基本表進行的，它產生的上界集記錄有2 439 157條。這個數據集是實際天氣數據集（weather）的一部分。預計算后結果如表9所示。

不同查詢算法的性能比較：

a）查詢總時間比較（圖7）；

b）查詢平均時間比較（圖8）；

c）查詢最大時間比較（圖9）。

表9 九維50萬數據集預計算結果MB基本表大小原始上界集大小反轉索引大小壓縮反轉索引大小16.783.853.325.7 43 實驗結果分析

從實驗結果可以看到，壓縮的反轉索引所用的存儲空間比原始產生的上界集的存儲空間少很多，就上面兩個數據集來說分別節省了72%和69%。位圖查詢算法和反轉列表查詢算法就上面兩個數據集而言每條查詢記錄的最大查找時間都不會超過1 s。在查詢的總時間上反轉列表算法比位圖查詢算法用的時間要少一些，平均時間相差不是很多，最大時間兩種算法各有不同，還要看數據集的具體分布而定。列表求交查詢算法在總時間和平均時間上相對于上面兩種基于壓縮的反轉索引的查詢算法，性能降低了至少一倍以上。所以，位圖查詢算法和反轉列表查詢算法提高了多維查詢的速度。

5 結束語

本文主要研究的對象是封閉立方體的查詢技術，首先介紹了數據倉庫的一些基本概念，接著研究了封閉立方體的特性以及如何利用QC算法產生上界集的過程并總結了上界集的特點。接下來，設計并實現了兩種查詢算法，即位圖查詢算法和反轉列表查詢算法。最后，測試了非壓縮和壓縮的反轉索引的空間代價和兩種查詢算法對不同的測試數據集的性能表現，并給出了測試結果分析。從實驗結果看出這兩種查詢算法確實能夠提高查詢的速度。

在未來的工作中，可以通過采取近來流行的一些新技術對本文的查詢作進一步的優化。比如緩存的策略，可以減少查詢的次數；比如分布式計算和并行算法，可以將查詢分布在多臺電腦上協作完成，而且近來PC機上的多核技術也為查詢提供了在單機上優化的可能。

參考文獻：

[1]LAKSHMANAN L V S， PEI J， HAN J W. Quotient cube: how to summarize the semantics of a data cube[C]//Proc of the 28th International Conference on Very Large Databases. Hong Kong: Morgan Kaufmann， 2002:778-789.

[2]LAKSHMANAN L V S， PEI J， ZHAO Y. QC-Trees:an efficient smmary structure for semantic OLAP[C]//Proc of ACM-SIGMOD International Conference on Management of Data. San Diego: California， 2003: 64-75.

[3]李盛恩，王珊.封閉數據立方體技術研究[J]. 軟件學報，2004，15(8):1165-1171.

[4]萬懷宇，黃厚寬.位圖索引及其在數據倉庫中的應用研究[J]. 鐵路計算機應用，2006，15(12):31-33.

[5]CHAN Cheng-yong， LOANNIDIS Y E. Bitmap index design and eva-luation[C]//Proc of ACM SIGMOD Conference. Seattle， Washington:[s.n.]， 1998:355-366.

[6]LI X L， HAN J W， GONZALEZ H. High-dimensional OLAP: a mini-mal cubing approach[C]// Proc of the 30th International Conference on Very Large Databases. Toronto:[s.n.]，2004:528-539.

[7]陳慧萍，陳嵐峰，王建東.大型數據倉庫實現技術的研究[J]. 計算機工程與設計，2006，27(21):3956-3958.

[8]劉斌.Oracle空間數據索引[J].電腦知識與技術，2004(11):16.

[9]YAN Z. Quotient cube and QC-Tree: efficient summarizations for semantic OLAP[D]. Vancouver: University of British Columbia，2003.