基于分片的高維稀疏數據存儲模式優化研究

邵慧萌，舒紅平，鄭皎凌，許源平，文立玉

成都信息工程學院 軟件工程系，成都 610225

基于分片的高維稀疏數據存儲模式優化研究

邵慧萌，舒紅平，鄭皎凌，許源平，文立玉

成都信息工程學院 軟件工程系，成都 610225

1 引言

1.1 問題的提出

本問題來源于東汽工模具分廠質量管理系統，下面通過該系統中的“零件質量表”說明本文將要解決的問題。

在該工模具分廠零件質量管理系統（數據庫采用Oracle數據庫）的開發維護過程中，發現存在例如“零件質量表”的一類關系表。其中id為唯一主鍵，代表零件批次的編號；除id外的其他各列，分別為某一批次的某一種不合格原因，其中某一批次的零件的不合格原因有多種?！傲慵|量表”中數據如表1所示。

“零件質量表”除主鍵id外還有15個屬性列（維度），共有53 579條記錄，具有維度較高、數據量較大的特點。

由于僅在主鍵id上建立了索引，在執行查詢操作時，Oracle將讀取表中所有的行，并檢查每一行是否滿足語句的WHERE限制條件。此時，Oracle順序地讀取分配給表的每個數據塊，直到讀到表的最高水線處（High Water Mark，HWM，Oracle中用于標識表的最后一個數據塊），即對整個關系表進行全表掃描（Full Table Scan）[1-2]。對該表進行的全表掃描將耗費大量的磁盤讀寫（I/O），增大了系統開銷，影響最終的查詢效率[3]。

表1 零件質量表

另外，由于同一批次的零件只有一個或多個不合格原因，所以“零件質量表”的不合格原因屬性列中的內容是稀疏的。由于大量的空白數據的存在，Oracle數據庫對其進行存儲時仍占用了固定的存儲空間，造成存儲空間的浪費。

為了后文表述的方便，這里將“零件質量表”形式化地表述為下列樣式：

其中id為關系表T_fact的唯一主鍵，cοli(1≤i≤n)為T_fact的其他屬性，并滿足如下特定：

（1）n相對較大（例如n≥10）；

（2）cοli(1≤i≤n)列中對應數據有大量空值存在。

在“零件質量表”中，cοl1，cοl2，…，cοln對應各個不合格原因屬性列。本文所用到的符號如表2所示。

表2 本文所用到的符號

1.2 問題的解決方案

針對1.1節提出的問題，采用列式存儲數據庫的思想，對表進行了分片和過濾空值的操作。對原表進行改造后，降低了磁盤讀寫（I/O），減小了系統開銷，使查詢效率得到提高；同時過濾空值后達到節省磁盤空間的目的。

2 相關工作

傳統行存儲數據庫主要應用于更新密集型的OLTP應用中。在行存儲數據庫中，讀某個列必須讀入整行，這樣就在無形之中增加了I/O開銷；每一行的數據寬度不等長，修改數據可能導致行遷移[4]，并且在行存儲數據庫中，行遷移不可避免，通過增加每個塊的大小可以減少行遷移的可能性，但也會造成更大的空間浪費；在行數據較多的情況下，當執行insert操作插入數據時，可能導致行鏈接[5-6]。

隨著企業信息化程度的提高，只讀的OLAP查詢等分析型數據庫應用的有著不同于傳統數據庫應用的新需求，對高性能查詢處理有更高的要求。列存儲數據模型如Sybase IQ、C-Store和MonetDB已經被證明在只讀的數據倉庫查詢處理中具有非常好的性能[7-9]。很多實驗也表明對于高選擇率、高投影率和大量聚集計算的OLAP查詢，列存儲的性能大大好于過行存儲[10-11]。

以國內市場占有率較高的列式存儲數據庫GBase 8a為例，它具有列式存儲數據庫查詢響應時間短，不讀取無效數據、高壓縮比等優點。它能夠降低I/O開銷，同時提高每次I/O的效率，大大提高查詢性能。查詢語句只從磁盤上讀取所需要的列，其他列的數據是不需要讀取的。例如，有兩張表，每張表100 GB且有100列，大多數查詢只關注幾個列，采用列存儲，不需要像行存數據庫一樣，將整行數據取出，只取出需要的列。磁盤I/O是行存儲的1/10或更少，查詢響應時間提高10倍以上。另外它的壓縮比可以達到5～20倍以上，數據占有空間降低到傳統數據庫的1/10，節省了存儲設備的開銷[12]。

然而由于傳統行存儲數據庫與列存儲數據庫的底層物理存儲模式不同，使得用戶很難在同一數據庫系統中根據需要自由轉換兩種存儲模式來存儲數據及執行查詢。同時企業同時部署行存儲和列存儲兩種數據庫系統也無疑增大了部署和維護開銷，對于絕大部分企業都是無法承受的[13]。本文基于行存儲數據庫，采用列式存儲數據庫的思想，對原始表進行了分片和過濾空值的操作，達到降低磁盤讀寫（I/O），減小系統開銷，提高查詢效率和節省磁盤空間的目的。

3 數據表的分片設計及實現

表T_fact具有多個屬性列(n≥10)，直接對其執行查詢操作（例如下面的sql語句）時，需要對整個數據表進行掃描，增大了系統開銷，影響最終的查詢效率[14]。

圖1 對“零件質量表”進行分片后表結構的變化

由此可知，每次查詢所占用的I/O空間數據塊為((n+1)×d)/D×t，其中d為平均每個屬性列所占字節數。

在列式存儲[15]數據庫中，數據庫首先在各屬性列上執行選擇操作，然后將各組的結果進行連接，最后根據需要進行分組、排序等操作后得到最終查詢結果，這樣就避免了對全表進行掃描?；诹惺酱鎯祿斓乃枷?，對表進行了分片操作。

下面，舉一個例子進行說明：

例1如圖1所示，將“零件質量表”垂直分片。將“零件質量表”分為“零件質量表_刻線問題表”，…，“零件質量表_物件丟失表”，“零件質量表_其他原因表”，“零件質量表_報廢表”，共n張表。其中為了程序設計的方便，每個列表的表名是由原始表表名和當前列的列名組成的。每個表中包含有“零件質量表”的id及cοli(1≤i≤n)共兩個屬性列，其中id為“零件質量表”的外鍵，cοli(1≤i≤n)為該元組在“零件質量表”中cοli(1≤i≤n)列上的取值。

接下來，將原表中的數據導入到分片之后的表中。由于原始除主鍵id列外，其他各列都存在著大量的空值數據，所以有必要對原表中的數據進行處理，避免導入大量空值數據。在這里，采取直接將空值過濾的方法，通過執行如下sql語句，將原始表中的非空數據導入到對應的列表中。

例2通過分析，通過如下sql語句，將原始表“零件質量表”中的非空數據導入到各個列表中。

對空值進行過濾后，使得每個列表中沒有空值數據的存在。效果如圖2所示。

4 存儲空間率分析

通過以上處理，大大減少了數據所占用的存儲空間。下面給出處理過之后與原始表所占用存儲空間的比率：

假設bc_cοl為原始表T_fact平均每列空值的個數，d_cοl為平均列寬，則存儲空間比可以簡化為：

圖2 對“零件質量表”進行分片、空值過濾后，表中數據的變化情況

例3在關系表“零件質量表”中，該表的記錄數rc= 3 579，主鍵id列寬d_id=32 Byte，其余列寬d_cοl=512 Byte，該表每列空白記錄數bc_cοli(1≤i≤15)分別為1 954，2 148，1 113，1 647，751，944，1 031，641，1 019，2 526，666，115，1 787，574，2 871。

在本例中，原始表所占存儲空間為3 579×(32+15× 512)=27 601 248 Byte≈28 MB，分片之后所占用存儲空間為(15×3 579-(1 954+2 148+1 113+1 647+751+944+1 031+ 641+1 019+2 526+666+115+1 787+574+2 871))×(32+ 512)=18 440 512 Byte≈18 MB。通過計算，得出該表的存儲空間比為18 440 512/27 601 248≈67%。

5 基于分片存儲模式的查詢實現

將表進行分片之后，sql語句可以等價轉化為：

其中原有查詢的關系代數形式：

轉化為如下形式：

該sql語句執行過程中，所需要的I/O數據塊為：

其中，p=3為本次查詢所涉及到的表的個數，D為一個數據塊的大小（Byte），t為關系表T_fact的元組數，d_id為屬性列id所占的空間（Byte），d_cοlk為每個屬性列所占用的字節數。

假設各個列寬都為d，分片后每個列表又存儲了T_fact的主鍵id，因此所涉及的列數最大為2×p，分片后查詢語句所需I/O數據塊個數可簡化為(2×p×d)/D×t；而針對原表的查詢語句所占空間為((n+1)×d)/D×t。當2×p小于n+1時，以下算式成立：(2×p×d)/D×t＜((n+1)×d)/D×t。

例4根據一定的條件，從數據庫中選出三列。其中sql語句1直接從原有“零件質量表”中獲取數據；通過對關系表進行分片，sql語句2從三個列表“零件質量表_刻線問題表”、“零件質量表_零件丟失表”和“零件質量表_其他原因表”中獲得數據。

sql語句1：

select t.刻線問題，t.零件丟失，t.其他原因

from零件質量表 t

where t.id＞4 600 and t.id＜10 001；

sql語句2：

select t1.刻線問題，t2.零件丟失，t3.其他原因

from零件質量表_刻線問題表t1，

零件質量表_零件丟失表t2，

零件質量表_其他原因表t3

where t1.id=t2.id（+）and t1.id=t3.id（+）and

t1.id＞4 600 and t1.id＜10 001；

其中，查詢所涉及到的表的個數p=3，id列寬d_id= 32 Byte，其余各列列寬d_cοl=512 Byte，表中記錄條數為t= 53 579，數據塊大小D=8 192 Byte。代入以上公式得，原始表對應的查詢所需I/O塊個數為：53 579×(15×512+32)/ 8 192=50 440，分片后對應的查詢語句所需I/O塊個數為53 579×(3×(512+32))/8 192=10 674。

由于在該方法中只對有限的幾個屬性列表進行掃描，避免了對具有n個屬性列的關系表T_fact進行全表掃描，降低了整個查詢I/O，從而提高了性能。并且由上式可知，當關系表的列數越多、查詢所涉及的表的個數越少，就越能夠提高查詢性能。

6 實驗結果與分析

6.1 存儲空間分析

6.1.1 理論值分析

在對該集團公司工模具分廠的相關關系表進行改造后，占用的磁盤存儲空間變小，查詢所需要的I/O數據塊減少，達到了實驗的預期效果。

首先分析關系表占用存儲空間，通過0分析和參照例3的計算步驟，隨機抽取4張關系表，計算得出了在改造前后所占用的理論存儲空間大?。↘B），如圖3所示。

圖3 對表進行改造后，理論存儲空間大小對比

從圖3中可以看出，對原始表進行改造后，其所占理論存儲空間有了明顯的減少，改造前后的存儲空間比取決于存儲空間的比率R。

6.1.2 實際值分析

下面通過執行如下sql語句來查看Oracle為原始表實際分配存儲空間大小（KB），其中本機Oracle版本為10 g Release 2（10.2.0.2）64位。其中user_segments視圖存儲了DBMS為每個表分配的存儲空間，where語句限定要查詢的表。

通過執行如下sql得到分片后，所有列表占用的存儲空間大?。↘B）總和。其中下劃線在Oracle中為特殊字符，需要用ESCAPE關鍵字轉義。

得到原始表“零件質量表”占用存儲空間大小為15 360 KB，分片后所有列表占用的存儲空間大小總和為4 288 KB。通過對上面隨機抽取的4張關系表進行執行sql語句，得到查詢結果如圖4所示。

圖4 對表進行改造后，實際存儲空間大小對比

如圖4所示，由于Oracle默認為4張原始表分配了同樣的存儲空間15 360 KB，實際值與理論值出現偏差；如理論分析相同，在對表進行分片后所需要的實際存儲空間大大減小。

6.2 查詢所需I/O數據塊數量分析

根據分析，在對分片后的關系表進行查詢操作時，I/O所需數據塊的個數隨著查詢所涉及關系表個數的增加而增加；而在對原關系表進行的查詢操作中，所涉及關系表的個數與所需I/O數據塊個數無關。從圖5可以看出，查詢所涉及的關系表的個數與所需I/O數據塊個數的關系（橫坐標為查詢所涉及表的個數）。與例4的執行步驟一樣，4次查詢操作都是對同一個關系表“零件質量表”進行原始表查詢和分片查詢。

圖5 查詢所涉及關系表的個數，對數據塊個數的影響

另外，圖5也反應了查詢所需數據塊個數與所涉及關系表的個數的關系。可以看出，在對原始表進行查詢時，無論查詢所涉及表的個數是多少，I/O數據塊的數量始終都是50 440。而對表進行分片后，查詢所需I/O數據塊的個數隨著涉及表的個數的增加而增加，呈現出遞增的趨勢，并且在涉及關系表個數很少的情況下可以達到理想的I/O開銷。

7 結束語

在實驗中，采用列式存儲數據庫的思想，對表進行了分片和過濾空值的操作。從實驗結果中可以發現，在對原表進行改造后，達到了減少查詢所需要的I/O數據塊的個數，降低磁盤讀寫（I/O），減小系統開銷的目的，使查詢效率得到提高。同時在對空值進行過濾后，顯著降低了磁盤占用空間。

另外，在改造后的列表中有相當多的重復數據的存在，在下一步實驗中將采用壓縮編碼技術使存儲空間壓縮比更加理想。

[1]周志德.Oralce數據庫的SQL查詢優化研究[J].計算機與數字工程，2010（11）：173-178.

[2]Halverson A，Bechmann J.A comparison of c.store and row. store in a common framework[C]//Proc of the 32nd Int Conf on Very Large Databases（VLDB），2006.

[3]劉博.Oracle數據庫性能調整與優化[D].大連：大連理工大學，2007.

[4]張仁惠.消除行遷移與Oracle數據庫性能調優[J].科技信息：科學教研，2007（33）.

[5]蘇大威，張樂.基于Oracle數據庫開發系統的物理設計優化策略[J].計算機工程，2002（2）.

[6]巢子杰.Oracle數據庫優化探究[J].軟件導刊，2010（2）：142-144.

[7]Sybase IQ[EB/OL].[2012-11-24].http：//www.sybase.com/products/datawarehousing/sybaseiq.

[8] C-Store[EB/OL].[2012-11-25].http：//db.csail.mit.edu/projects/cstore/.

[9]MonetDB[EB/OL].[2012-11-25].http：//www.monetdb.org/Home.

[10]李超，張明博，邢春曉，等.列存儲數據庫關鍵技術綜述[J].計算機科學，2010（12）.

[11]王珊，肖艷芹，劉大為，等.內存數據庫關鍵技術研究[J].計算機應用，2007（10）：2353-2357.

[12]南大通用.GBase 8a新型列存儲分析型數據庫產品介紹[EB/ OL].[2012-11-25].http：//www.gbase.cn/cp-8a.html.

[13]于利勝，張延松，王珊，等.基于行存儲模型的模擬列存儲策略研究[J].計算機研究與發展，2010（5）：878-885.

[14]宋彩霞，路新春.Oracle數據庫基于索引SQL優化方法的研究與實現[J].計算機工程與設計，2004（12）：2327-2330.

[15]周軍鋒，田姍姍，藍國翔，等.TDCOL：列式存儲的XML關鍵字查詢處理策略[J].計算機科學與探索，2012，6（9）：829-843.

SHAO Huimeng,SHU Hongping,ZHENG Jiaoling,XU Yuanping,WEN Liyu

Department of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China

In large databases,empty fields in high dimensional sparse table may occupy a large amount of storage space.To deal with this problem,a slicing based database structure,which simulates the principle of column-store database in traditional rowstore database,is designed.By analyzing on testing results,the storage space is decreased about 27.42%lower than the original model.The number of I/O data block is reduced to 35.27%when five fields of high-dimensional sparse data are queried,and 28.22%when four fields are selected.There will be a further reduction when the number of fields reduces.Therefore the accessing efficiency for database is improved.

high-dimensional;sparse data;column-store database

針對大型數據庫中高維稀疏關系表空字段對存儲空間的占用問題，通過利用傳統行存儲數據庫模擬列式存儲數據庫的工作原理，設計了一種基于分片的數據庫結構。通過實驗分析，數據庫存儲空間比原始模式降低了27.42%左右。在對高維稀疏數據中五個字段進行查詢時，I/O數據塊個數降低至原始模式的35.27%，對高維稀疏數據中四個字段進行查詢時，I/O數據塊個數降低至原始模式的28.22%，而隨著字段的減少I/O數據塊仍會進一步減少，從而提高了數據庫的訪問效率。

高維；稀疏數據；列式存儲數據庫

A

TP311.13

10.3778/j.issn.1002-8331.1301-0266

SHAO Huimeng,SHU Hongping,ZHENG Jiaoling,et al.Storage model optimization toward high dimensional sparse data based on slicing.Computer Engineering and Applications,2013,49（18）：99-104.

國家重點基礎研究發展規劃（973）（No.2012CB518500）；國家自然科學基金青年基金（No.61202250，No.61203172）；四川省教育廳青年基金項目（No.11ZB088）；四川省應用基礎計劃（No.2012JY0112）；成都市科技計劃項目（No.12DXYB100JH-002）；成都信息工程學院中青年學術帶頭人科研基金（No.J201208，No.J201101）；成都信息工程學院引進人才項目（No.KYTZ201110，No.KYTZ201111）；四川省科技支撐計劃項目（No.2011SZZ027）。

邵慧萌（1986—），男，碩士，研究領域為數據庫與知識工程、計算機在制造業中的應用；舒紅平（1974—），男，教授，研究領域為軟件工程、數據庫與知識工程、數據挖掘；鄭皎凌（1981—），女，博士，副教授，CCF會員，研究領域為數據庫與知識工程、機器學習。E-mail：huimengshao@163.com

2013-01-23

2013-03-11

1002-8331（2013）18-0099-06

CNKI出版日期：2013-04-08 http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.003.html