列式數(shù)據(jù)庫(kù)壓縮方法探討

列式數(shù)據(jù)庫(kù)——壓縮算法探討OUTLINE簡(jiǎn)介背景優(yōu)勢(shì)現(xiàn)狀數(shù)據(jù)壓縮簡(jiǎn)介列數(shù)據(jù)庫(kù)壓縮算法列數(shù)據(jù)庫(kù)簡(jiǎn)介列存儲(chǔ)數(shù)據(jù)庫(kù)是相對(duì)于傳統(tǒng)的以記錄或數(shù)據(jù)行（Record，Row）為單位進(jìn)行數(shù)據(jù)處理的數(shù)據(jù)庫(kù)（例如SQLServer）來(lái)說的，它以數(shù)據(jù)表中的列（Column）為單位對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和查詢等處理。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù),即數(shù)據(jù)按記錄存儲(chǔ),每一條記錄的所有屬性都存儲(chǔ)在一起,如果要查詢一條記錄的一個(gè)屬性值,需要先讀取整條記錄的數(shù)據(jù)。而列數(shù)據(jù)庫(kù)是按數(shù)據(jù)庫(kù)記錄的列來(lái)組織和存儲(chǔ)數(shù)據(jù)的,數(shù)據(jù)庫(kù)中每個(gè)表由一組據(jù)庫(kù)記錄的列來(lái)組織和存儲(chǔ)數(shù)據(jù)的,數(shù)據(jù)庫(kù)中每個(gè)表由一組頁(yè)鏈的集合組成,每條頁(yè)鏈對(duì)應(yīng)表中的一個(gè)存儲(chǔ)列,而該頁(yè)鏈中每一頁(yè)存儲(chǔ)的是該列的一個(gè)或多個(gè)值。列數(shù)據(jù)庫(kù)產(chǎn)生背景現(xiàn)今的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)大多衍生于70年代的SystemR項(xiàng)目原型和Ingres項(xiàng)目原型，但是隨著應(yīng)用和硬件技術(shù)的發(fā)展，DBMS的需求不僅僅滿足于SystemR和higres設(shè)計(jì)面向OLTP數(shù)據(jù)處理的初衷，而更多的是地球科學(xué)、醫(yī)學(xué)等數(shù)據(jù)倉(cāng)庫(kù)以及決策支持系統(tǒng)等的OLAP的數(shù)據(jù)處理需求，而在這些應(yīng)用中，大多數(shù)信息都是散亂的、稀疏的，并且需要對(duì)數(shù)據(jù)進(jìn)行大量的查詢處理，以便對(duì)其進(jìn)行數(shù)據(jù)有效的分析處理;同時(shí)由于硬件技術(shù)的發(fā)展，傳統(tǒng)的高性能硬件逐漸大眾化，使得數(shù)據(jù)倉(cāng)庫(kù)等應(yīng)用得更加普遍。因此為了滿足該類應(yīng)用場(chǎng)景的需求，數(shù)據(jù)庫(kù)系統(tǒng)發(fā)展的方向由滿足OLTP數(shù)據(jù)處理的需求轉(zhuǎn)向滿足OLAP數(shù)據(jù)處理的需求，OLAP是對(duì)列進(jìn)行操作的，于是便衍生出面向分析處理(OLAP)的列存儲(chǔ)數(shù)據(jù)庫(kù)系統(tǒng)。列數(shù)據(jù)庫(kù)優(yōu)勢(shì)能夠迅速的執(zhí)行復(fù)雜查詢壓縮技術(shù)為數(shù)據(jù)倉(cāng)庫(kù)、商務(wù)智能應(yīng)用中巨大的數(shù)據(jù)量節(jié)約存儲(chǔ)成本節(jié)省大量I/O帶寬列數(shù)據(jù)庫(kù)發(fā)展現(xiàn)狀比較著名的列數(shù)據(jù)庫(kù)系統(tǒng)有開源項(xiàng)目C-Store，是由麻省理工、耶魯大學(xué)、布朗大學(xué)等合作研發(fā)的，并于2005年發(fā)布第一版本，2006年升級(jí)為第二版本。在C-Store的研究基礎(chǔ)上，又衍生出來(lái)商業(yè)化的Vertica以及內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)MonetDB。Google的BigTable也是一種面向列存儲(chǔ)的數(shù)據(jù)庫(kù)系統(tǒng)，該系統(tǒng)是Google內(nèi)部開發(fā)用來(lái)處理大數(shù)據(jù)量的系統(tǒng)，Googfe的很多項(xiàng)目包括網(wǎng)索引、GoogleEarth和谷歌財(cái)務(wù)都是建立在該系統(tǒng)基礎(chǔ)上的。SQLSERVER2011也支持列存儲(chǔ)索引FACEBOOK的數(shù)據(jù)倉(cāng)庫(kù)RCFile：一個(gè)結(jié)合了行存儲(chǔ)和列存儲(chǔ)的數(shù)據(jù)管理系統(tǒng)數(shù)據(jù)壓縮簡(jiǎn)介定義：在不丟失信息的前提下，縮減數(shù)據(jù)量以減少存儲(chǔ)空間，提高其傳輸、存儲(chǔ)和處理效率的一種技術(shù)方法。流行算法：列數(shù)據(jù)庫(kù)壓縮隨著數(shù)據(jù)庫(kù)的規(guī)模越來(lái)越大，如何在數(shù)據(jù)庫(kù)中使用數(shù)據(jù)壓縮是很多研究者關(guān)注的熱點(diǎn)。然而，傳統(tǒng)的行存儲(chǔ)數(shù)據(jù)庫(kù)由于存儲(chǔ)的數(shù)據(jù)的差異性較大，對(duì)其采用壓縮也往往每次查詢時(shí)不得不進(jìn)行解壓。不過壓縮后數(shù)據(jù)量小的優(yōu)點(diǎn)在某種程度上還是勝過解壓的額外開銷的。列存儲(chǔ)的概念提出以后，由于列存儲(chǔ)的特點(diǎn)，它非常適合輕量級(jí)壓縮，從而可以不解壓而直接訪問壓縮態(tài)的數(shù)據(jù)。公司組織數(shù)據(jù)倉(cāng)庫(kù)大小（TB）原始數(shù)據(jù)大?。═B）數(shù)據(jù)行數(shù)數(shù)據(jù)庫(kù)操作系統(tǒng)數(shù)據(jù)庫(kù)廠商存儲(chǔ)廠商YAHOO100.38617.0143853ORACLEUNIXORALCEEMCNielsenMediaResearch17.68517.9695024SYSBASEIQUNIXSYSBASEEMC列數(shù)據(jù)庫(kù)主要壓縮算法在SIGMOD06會(huì)議上,DanielJ.Abadi通過在開源的列數(shù)據(jù)庫(kù)C-Store上進(jìn)行實(shí)驗(yàn)比較和理論分析指出,主要的壓縮方法有以下三類:游程編碼算法(Run-lengthEncoding)詞典編碼算法(DictionaryEncoding)位向量算法(Bit-VectorEncoding)。游程編碼算法(RunlengthEncoding)游程編碼算法是比較適合列數(shù)據(jù)庫(kù)的壓縮算法之一,即用一個(gè)三元組記錄數(shù)據(jù)值、數(shù)據(jù)出現(xiàn)的起始位置和持續(xù)長(zhǎng)度(即行程),以代替具有相同值的若干連續(xù)原始數(shù)據(jù),使三元組的存儲(chǔ)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度。三元組描述為(X,Y,Z)其中X:數(shù)據(jù)的值,Y:起始位置,Z:長(zhǎng)度。訂單類型產(chǎn)品ID產(chǎn)品類型Q112Q115Q118Q114Q125Q232Q234訂單類型產(chǎn)品ID產(chǎn)品類型Q1,1,51,1,42Q2,6,22,5,253,7,184524壓縮后詞典編碼算法(DictionaryEncoding)詞典編碼就是生成一個(gè)原始值替代值的對(duì)照詞典。為了起到壓縮的作用,替代值的長(zhǎng)度小于原始值的長(zhǎng)度。存儲(chǔ)的時(shí)候,只存儲(chǔ)替代值而不是原始值,從而壓縮了存儲(chǔ)空間。字典表Q100Q201訂單類型Q1Q1Q1Q1Q1Q2Q2訂單類型00000000000101壓縮后位向量編碼算法(Bit-VectorEncoding)位向量編碼是為每一個(gè)不同的取值生成一個(gè)位向量,根據(jù)位向量(串)中不同的位置取值0或1來(lái)對(duì)應(yīng)并確定不同的原始值。訂單類型Q1Q1Q1Q1Q1Q2Q2Q1位向量Q2位向量10101010100101壓縮后優(yōu)劣對(duì)比名稱游程編碼詞典編碼位向量算法共同特征適用于重復(fù)數(shù)據(jù)較多，不適用于重復(fù)數(shù)據(jù)較少適用數(shù)據(jù)列的不同特征重復(fù)數(shù)據(jù)的排序比較規(guī)則取值空間較小取值空間較小不適用的數(shù)據(jù)列不同特征排序不規(guī)則a)取間空間較大b)數(shù)據(jù)類型長(zhǎng)度比詞典符號(hào)長(zhǎng)度更小取值空間較大優(yōu)點(diǎn)對(duì)于適用的數(shù)據(jù)特征,有比較好的壓縮效果a)對(duì)于數(shù)據(jù)類型要求較低b)對(duì)于數(shù)據(jù)排序要求較低a)對(duì)于數(shù)據(jù)類型要求較低b)對(duì)于數(shù)據(jù)排序要求較低c)在有些情況,查詢效率要比詞典編碼高缺點(diǎn)對(duì)列值的重復(fù)性以及排序要求較高需要?jiǎng)?chuàng)建一張?jiān)~典表,增加維護(hù)代價(jià),如果數(shù)據(jù)重復(fù)性不高,詞典表會(huì)過于巨大用位置代表數(shù)據(jù),如取值空間較大,或重復(fù)性較低,占用空間會(huì)比較大LZ77壓縮算法原理（1）LZ77算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，其基本原理是將已輸入數(shù)據(jù)流的一部分作為字典，編碼器為輸入數(shù)據(jù)流開一個(gè)窗口，并且隨著對(duì)字符串的編碼不斷地將窗中的數(shù)據(jù)從右一道左。滑動(dòng)窗一般分為兩部分，左邊的部分稱為搜索緩沖存儲(chǔ)器，這一部分是當(dāng)前的字典，始終存有剛剛輸入的字符和已編碼過的字符；右邊的部分稱為向前的緩沖存儲(chǔ)器。其中存有即將被編碼的輸入字符集。在實(shí)際應(yīng)用中，搜索緩沖存儲(chǔ)器的窗口一般較長(zhǎng)，可長(zhǎng)達(dá)幾千字節(jié)，而向前的緩沖存儲(chǔ)器只有幾十字節(jié)。LZ77編碼舉例sirsideastmaneasilyeasesseasickseals步驟位置匹配串輸出11－－從右向左搜索22eas(7,3,e)34eas(15,3,e)第一個(gè)參數(shù)代表在在這個(gè)窗口的位置上中后退N個(gè)字符第二個(gè)參數(shù)代表匹配到的最長(zhǎng)字符串的長(zhǎng)度第三個(gè)參數(shù)代表未匹配到的第一個(gè)字符

sirsideastmaneasilyeasesseasicksealsLZ78算法介紹(1)LZ78是一個(gè)基于字典的壓縮算法，需要維護(hù)一個(gè)字典，該算法輸出的碼字由兩個(gè)元素組成:一個(gè)參照最長(zhǎng)匹配字典輸入索引以及一個(gè)非匹配的字符。其基本思想就是不斷地從字符流中提取新的字符串，然后用碼字表示這個(gè)詞條，因此，對(duì)字符流的編碼就變成了用碼字去替換字符流，生成碼字流，從而達(dá)到壓縮數(shù)據(jù)的目的。LZ78算法介紹(2)例如，字符串ABBCBCABABCAABCAAB，其過程如圖1234567ABBCBCABABCAABCAABoutputIndexString(0,A)1A(0,B)2B(2,C)3BC(3,A)4BCA(2,A)5BA(4,A)6BCAA(6,B)7BCAABLZW算法LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來(lái)完成的。LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。

LZW算法取得了專利，專利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法LZW編碼舉例位置123456789字符ABBABABAC步驟位置碼字詞典輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC76－－－3輸入數(shù)據(jù)流：適應(yīng)列數(shù)據(jù)庫(kù)的LZ算法1LZ77和LZ78算法的結(jié)合背景：數(shù)據(jù)列中的數(shù)據(jù)項(xiàng)一般在上下文中更容易找到匹配串；數(shù)據(jù)列的存儲(chǔ)類型固定，因此每項(xiàng)的存儲(chǔ)空間固定，更易使用滑動(dòng)窗口算法：采用兩個(gè)滑動(dòng)窗口，同時(shí)向后移動(dòng)。一為比對(duì)窗口，2為待編碼窗口初始字典置為空，先在最初的比對(duì)窗口中采用LZ78算法壓縮，并將壓縮的長(zhǎng)度大于1的字符串存入字典。帶編碼窗口先和比對(duì)窗口進(jìn)行匹配，并將匹配出來(lái)的字符串存入字典，再在字典表中查看是否有匹配的字符串。優(yōu)點(diǎn)適合與數(shù)據(jù)庫(kù)的數(shù)據(jù)特性壓縮出來(lái)的數(shù)據(jù)可以方便進(jìn)行數(shù)據(jù)庫(kù)的增刪改查，order，join等操作（即不解壓數(shù)據(jù)，直接對(duì)壓縮態(tài)數(shù)據(jù)進(jìn)行操作）適應(yīng)列數(shù)據(jù)庫(kù)的LZ算法2RowId域名123……567/index滑動(dòng)窗口編碼窗口壓縮后RowId域名123……50010116001cctv0107100/index字典表001100大致思路如下圖：適應(yīng)列數(shù)據(jù)庫(kù)的LZ算法3原數(shù)據(jù)：Source.txt文件大小：21762字節(jié)LZ77算法壓縮后大?。?869字節(jié)LZW算法壓縮后大?。?172字節(jié)自定義算法壓縮后字節(jié)：2791字節(jié)idNo.idNo.idNo.idNo.idNo.12000070482001070615200207082220020709292003071322000070492001070616200207082320020709302003071332000070410200207041720030713242