基于分片的高維稀疏數(shù)據(jù)存儲模式優(yōu)化研究

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

成都信息工程學(xué)院 軟件工程系，成都 610225

基于分片的高維稀疏數(shù)據(jù)存儲模式優(yōu)化研究

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

成都信息工程學(xué)院 軟件工程系，成都 610225

1 引言

1.1 問題的提出

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

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

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

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

表1 零件質(zhì)量表

另外，由于同一批次的零件只有一個或多個不合格原因，所以“零件質(zhì)量表”的不合格原因?qū)傩粤兄械膬?nèi)容是稀疏的。由于大量的空白數(shù)據(jù)的存在，Oracle數(shù)據(jù)庫對其進(jìn)行存儲時仍占用了固定的存儲空間，造成存儲空間的浪費(fèi)。

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

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

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

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

在“零件質(zhì)量表”中，cοl1，cοl2，…，cοln對應(yīng)各個不合格原因?qū)傩粤?。本文所用到的符號如?所示。

表2 本文所用到的符號

1.2 問題的解決方案

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

2 相關(guān)工作

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

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

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

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

3 數(shù)據(jù)表的分片設(shè)計及實現(xiàn)

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

圖1 對“零件質(zhì)量表”進(jìn)行分片后表結(jié)構(gòu)的變化

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

在列式存儲[15]數(shù)據(jù)庫中，數(shù)據(jù)庫首先在各屬性列上執(zhí)行選擇操作，然后將各組的結(jié)果進(jìn)行連接，最后根據(jù)需要進(jìn)行分組、排序等操作后得到最終查詢結(jié)果，這樣就避免了對全表進(jìn)行掃描?；诹惺酱鎯?shù)據(jù)庫的思想，對表進(jìn)行了分片操作。

下面，舉一個例子進(jìn)行說明：

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

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

例2通過分析，通過如下sql語句，將原始表“零件質(zhì)量表”中的非空數(shù)據(jù)導(dǎo)入到各個列表中。

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

4 存儲空間率分析

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

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

圖2 對“零件質(zhì)量表”進(jìn)行分片、空值過濾后，表中數(shù)據(jù)的變化情況

例3在關(guān)系表“零件質(zhì)量表”中，該表的記錄數(shù)rc= 3 579，主鍵id列寬d_id=32 Byte，其余列寬d_cοl=512 Byte，該表每列空白記錄數(shù)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 基于分片存儲模式的查詢實現(xiàn)

將表進(jìn)行分片之后，sql語句可以等價轉(zhuǎn)化為：

其中原有查詢的關(guān)系代數(shù)形式：

轉(zhuǎn)化為如下形式：

該sql語句執(zhí)行過程中，所需要的I/O數(shù)據(jù)塊為：

其中，p=3為本次查詢所涉及到的表的個數(shù)，D為一個數(shù)據(jù)塊的大?。˙yte），t為關(guān)系表T_fact的元組數(shù)，d_id為屬性列id所占的空間（Byte），d_cοlk為每個屬性列所占用的字節(jié)數(shù)。

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

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

sql語句1：

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

from零件質(zhì)量表 t

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

sql語句2：

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

from零件質(zhì)量表_刻線問題表t1，

零件質(zhì)量表_零件丟失表t2，

零件質(zhì)量表_其他原因表t3

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

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

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

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

6 實驗結(jié)果與分析

6.1 存儲空間分析

6.1.1 理論值分析

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

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

圖3 對表進(jìn)行改造后，理論存儲空間大小對比

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

6.1.2 實際值分析

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

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

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

圖4 對表進(jìn)行改造后，實際存儲空間大小對比

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

6.2 查詢所需I/O數(shù)據(jù)塊數(shù)量分析

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

圖5 查詢所涉及關(guān)系表的個數(shù)，對數(shù)據(jù)塊個數(shù)的影響

另外，圖5也反應(yīng)了查詢所需數(shù)據(jù)塊個數(shù)與所涉及關(guān)系表的個數(shù)的關(guān)系?？梢钥闯?，在對原始表進(jìn)行查詢時，無論查詢所涉及表的個數(shù)是多少，I/O數(shù)據(jù)塊的數(shù)量始終都是50 440。而對表進(jìn)行分片后，查詢所需I/O數(shù)據(jù)塊的個數(shù)隨著涉及表的個數(shù)的增加而增加，呈現(xiàn)出遞增的趨勢，并且在涉及關(guān)系表個數(shù)很少的情況下可以達(dá)到理想的I/O開銷。

7 結(jié)束語

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

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

[1]周志德.Oralce數(shù)據(jù)庫的SQL查詢優(yōu)化研究[J].計算機(jī)與數(shù)字工程，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數(shù)據(jù)庫性能調(diào)整與優(yōu)化[D].大連：大連理工大學(xué)，2007.

[4]張仁惠.消除行遷移與Oracle數(shù)據(jù)庫性能調(diào)優(yōu)[J].科技信息：科學(xué)教研，2007（33）.

[5]蘇大威，張樂.基于Oracle數(shù)據(jù)庫開發(fā)系統(tǒng)的物理設(shè)計優(yōu)化策略[J].計算機(jī)工程，2002（2）.

[6]巢子杰.Oracle數(shù)據(jù)庫優(yōu)化探究[J].軟件導(dǎo)刊，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]李超，張明博，邢春曉，等.列存儲數(shù)據(jù)庫關(guān)鍵技術(shù)綜述[J].計算機(jī)科學(xué)，2010（12）.

[11]王珊，肖艷芹，劉大為，等.內(nèi)存數(shù)據(jù)庫關(guān)鍵技術(shù)研究[J].計算機(jī)應(yīng)用，2007（10）：2353-2357.

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

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

[14]宋彩霞，路新春.Oracle數(shù)據(jù)庫基于索引SQL優(yōu)化方法的研究與實現(xiàn)[J].計算機(jī)工程與設(shè)計，2004（12）：2327-2330.

[15]周軍鋒，田姍姍，藍(lán)國翔，等.TDCOL：列式存儲的XML關(guān)鍵字查詢處理策略[J].計算機(jī)科學(xué)與探索，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

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

高維；稀疏數(shù)據(jù)；列式存儲數(shù)據(jù)庫

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.

國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃（973）（No.2012CB518500）；國家自然科學(xué)基金青年基金（No.61202250，No.61203172）；四川省教育廳青年基金項目（No.11ZB088）；四川省應(yīng)用基礎(chǔ)計劃（No.2012JY0112）；成都市科技計劃項目（No.12DXYB100JH-002）；成都信息工程學(xué)院中青年學(xué)術(shù)帶頭人科研基金（No.J201208，No.J201101）；成都信息工程學(xué)院引進(jìn)人才項目（No.KYTZ201110，No.KYTZ201111）；四川省科技支撐計劃項目（No.2011SZZ027）。

邵慧萌（1986—），男，碩士，研究領(lǐng)域為數(shù)據(jù)庫與知識工程、計算機(jī)在制造業(yè)中的應(yīng)用；舒紅平（1974—），男，教授，研究領(lǐng)域為軟件工程、數(shù)據(jù)庫與知識工程、數(shù)據(jù)挖掘；鄭皎凌（1981—），女，博士，副教授，CCF會員，研究領(lǐng)域為數(shù)據(jù)庫與知識工程、機(jī)器學(xué)習(xí)。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