丁銳恒 梁波

摘 ?要：隨著大數(shù)據(jù)產(chǎn)業(yè)的興起，列式數(shù)據(jù)庫(kù)的應(yīng)用價(jià)值得以體現(xiàn)。憑借其靈活高效的查詢性能以及對(duì)復(fù)雜異構(gòu)數(shù)據(jù)的兼容支持，列式數(shù)據(jù)庫(kù)在海量數(shù)據(jù)的分布式存儲(chǔ)和數(shù)據(jù)查詢分析領(lǐng)域具有廣闊的應(yīng)用前景。首先從實(shí)際應(yīng)用的角度闡述列式數(shù)據(jù)庫(kù)的基本特性和存儲(chǔ)架構(gòu)；其次分析列式數(shù)據(jù)庫(kù)中所應(yīng)用的數(shù)據(jù)壓縮技術(shù)并通過實(shí)驗(yàn)驗(yàn)證數(shù)據(jù)壓縮對(duì)列式數(shù)據(jù)庫(kù)存取性能的影響程度。

關(guān)鍵詞：列式數(shù)據(jù)庫(kù)；數(shù)據(jù)壓縮；壓縮算法；預(yù)處理

中圖分類號(hào)：TP391 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? 文章編號(hào)：2096-4706（2023）14-0042-06

Research on Data Compression Technology of Column-oriented Database

DING Ruiheng1， LIANG Bo2

（1.Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming ?650504， China; 2.Computer Technology Application Key Laboratory of Yunnan Province， Kunming University of Science and Technology， Kunming ?650500， China）

Abstract： With the rise of big data industry， the application value of column-oriented database is reflected. With its flexible and efficient query performance and compatible support for complex heterogeneous data， column-oriented database has broad application prospects in the field of distributed storage of massive data and data query analysis. Firstly， the basic characteristics and storage architecture of column-oriented database are expounded from the perspective of practical application; secondly， it analyzes the data compression technology applied in column-oriented database and verifies the impact of data compression on the access performance of column-oriented database through experiments.

Keywords： column-oriented database; data compression; compression algorithm; pretreatment

0 ?引 ?言

如今，數(shù)據(jù)分析已廣泛應(yīng)用于科學(xué)實(shí)驗(yàn)、醫(yī)療衛(wèi)生、商業(yè)決策、社交網(wǎng)絡(luò)、生產(chǎn)制造等諸多領(lǐng)域。數(shù)據(jù)存儲(chǔ)作為數(shù)據(jù)分析工作的首要步驟，其重要性不言而喻。在過去的幾十年里，行式數(shù)據(jù)庫(kù)（Row-Oriented DBMS）因良好的結(jié)構(gòu)特性和通用的查詢語言，在數(shù)據(jù)的存儲(chǔ)管理中占據(jù)主導(dǎo)地位。數(shù)據(jù)庫(kù)應(yīng)用場(chǎng)景的擴(kuò)展和交互式設(shè)備的普及，使得數(shù)據(jù)體量攀升、數(shù)據(jù)結(jié)構(gòu)多樣化。傳統(tǒng)行式數(shù)據(jù)庫(kù)的性能已不能滿足數(shù)億級(jí)別數(shù)據(jù)的秒級(jí)檢索、實(shí)時(shí)處理、大規(guī)模存儲(chǔ)等需求。近些年來，在Stonebraker、Daniel、Abadi、Boncz等數(shù)據(jù)庫(kù)專家的大力提倡下，列式數(shù)據(jù)庫(kù)（Column-Oriented DBMS）技術(shù)及相關(guān)應(yīng)用快速發(fā)展[1，2]?；趯?duì)聯(lián)機(jī)分析處理（On-Line Analysis Processing）支持友好、查詢性能強(qiáng)悍、易于搭建分布式集群等優(yōu)勢(shì)，列式數(shù)據(jù)庫(kù)已逐漸替代行式數(shù)據(jù)庫(kù)而成為眾多企業(yè)搭建數(shù)據(jù)倉(cāng)庫(kù)（Data Warehouse）的首選方案[3，4]。然而，無論是行式數(shù)據(jù)庫(kù)還是列式數(shù)據(jù)庫(kù)，數(shù)據(jù)存儲(chǔ)量增長(zhǎng)所導(dǎo)致的存儲(chǔ)成本提高都是數(shù)據(jù)管理不可避免的問題[5，6]。與此同時(shí)，隨著分布式、云計(jì)算技術(shù)在數(shù)據(jù)庫(kù)領(lǐng)域的發(fā)展與應(yīng)用，大規(guī)模數(shù)據(jù)實(shí)時(shí)傳輸成本控制也是亟待解決的問題?？v觀整個(gè)數(shù)據(jù)庫(kù)領(lǐng)域，幾乎所有的數(shù)據(jù)庫(kù)（無論是行式數(shù)據(jù)庫(kù)還是列式數(shù)據(jù)庫(kù)）都會(huì)應(yīng)用數(shù)據(jù)壓縮技術(shù)，數(shù)據(jù)庫(kù)的壓縮效率也成為評(píng)價(jià)數(shù)據(jù)庫(kù)性能優(yōu)劣的標(biāo)準(zhǔn)之一。數(shù)據(jù)壓縮是指在不損失信息量的前提下按照一定的編碼規(guī)則對(duì)數(shù)據(jù)進(jìn)行重新組織從而達(dá)到減少數(shù)據(jù)長(zhǎng)度的目的，而列式數(shù)據(jù)庫(kù)的存儲(chǔ)原理決定了其在數(shù)據(jù)壓縮上的優(yōu)勢(shì)。美國(guó)媒體流量分析公司Nielsen Media Research以列式數(shù)據(jù)庫(kù)產(chǎn)品Sybase IQ搭建數(shù)據(jù)倉(cāng)庫(kù)，初始大小為17.969 TB，運(yùn)行兩年后數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)量為17.585 TB，相比之下，Yahoo公司基于行式數(shù)據(jù)庫(kù)Oracle搭建的數(shù)據(jù)倉(cāng)庫(kù)從最開始的17.014 TB擴(kuò)大到100 TB[7]。對(duì)比行式數(shù)據(jù)庫(kù)，在列式數(shù)據(jù)庫(kù)中應(yīng)用數(shù)據(jù)壓縮具有顯著的效果。本文主要圍繞列式數(shù)據(jù)庫(kù)中的數(shù)據(jù)壓縮技術(shù)進(jìn)行綜述，首先介紹列式數(shù)據(jù)庫(kù)的特性和存儲(chǔ)原理，其次闡述了預(yù)處理編碼技術(shù)和LZ系列壓縮算法在列式數(shù)據(jù)庫(kù)中的應(yīng)用。

1 ?列式數(shù)據(jù)庫(kù)

1.1 ?列式數(shù)據(jù)庫(kù)特性

列式數(shù)據(jù)庫(kù)的誕生最早可以追溯到20世紀(jì)90年代。ExpressWay Technologies公司在當(dāng)時(shí)推出一款有助于傳統(tǒng)數(shù)據(jù)庫(kù)提升報(bào)表制作速度的工具，其原理就是將數(shù)據(jù)表進(jìn)行垂直劃分以列的方式進(jìn)行存儲(chǔ)從而提高查詢的速度。1994年，Sybase公司認(rèn)準(zhǔn)這項(xiàng)技術(shù)并收購(gòu)了ExpressWay Technologies公司，在1996年推出了基于列存儲(chǔ)的數(shù)據(jù)庫(kù)產(chǎn)品——Sybase IQ。此后隨著工業(yè)界數(shù)據(jù)體量的增長(zhǎng)和數(shù)據(jù)分析的發(fā)展，人們開始注意到列式數(shù)據(jù)庫(kù)在存儲(chǔ)管理大規(guī)模數(shù)據(jù)上的優(yōu)勢(shì)。在2005年第31屆超大型數(shù)據(jù)庫(kù)會(huì)議（Very Large Data Bases）上，由Mike Stonebraker等人發(fā)表的論文“C-Store： A Column-Oriented DBMS”中正式提出了列式數(shù)據(jù)庫(kù)的概念。所謂列式數(shù)據(jù)庫(kù)，就是以數(shù)據(jù)表中的列（屬性）為單位進(jìn)行數(shù)據(jù)寫入，將數(shù)據(jù)表不同元組中的相同屬性值存儲(chǔ)在一起，將同一元組中不同的屬性值分別存放在不同的存儲(chǔ)單元中[8]。相較于行式數(shù)據(jù)庫(kù)，列式數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)具有以下優(yōu)勢(shì)：

1）連續(xù)存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)類型相同且具有一定的相關(guān)性，非常適合進(jìn)行高效的壓縮操作。

2）以列為單位進(jìn)行存儲(chǔ)，在查詢時(shí)可以將查詢命令分解成以列為對(duì)象的操作，只需讀取所涉及的列即可。

例如，對(duì)一張氣候表Climate Record（Date，

Temperature， Wind， Rain）執(zhí)行查詢操作SELECT date

FROM Climate Record WHERE Temperature>35 AND Temperature<40 ORDER BY Date DESC。首先讀取Temperature屬性列，篩選出Temperature值介于35和40之間的記錄并讀取這些記錄的Data屬性列，最后根據(jù)Data值進(jìn)行排序。整個(gè)過程只讀取了Temperature列和Data列，極大地節(jié)省了I/O帶寬也減少了內(nèi)存和Cache等資源的使用，同時(shí)也省去了行式數(shù)據(jù)庫(kù)中映射（Projection）運(yùn)算的開銷[9]。

1.2 ?列式數(shù)據(jù)庫(kù)存儲(chǔ)架構(gòu)

列式數(shù)據(jù)庫(kù)強(qiáng)調(diào)列簇（Column Family）的概念，首先采用鍵空間（Keyspace）作為基礎(chǔ)的數(shù)據(jù)表存儲(chǔ)架構(gòu)，鍵空間中包含若干個(gè)列簇，如圖1所示。

列簇下包含若干個(gè)行，行鍵（Row Key）是每個(gè)行的唯一標(biāo)識(shí)，如圖2所示。行中包含不同數(shù)量、不同類型的列關(guān)鍵字以及對(duì)應(yīng)的時(shí)間戳，列關(guān)鍵字表示一種屬性值的數(shù)據(jù)類型同時(shí)也是基礎(chǔ)的存儲(chǔ)單元。數(shù)據(jù)表在被存儲(chǔ)之前必須先創(chuàng)建列簇，不同元組中的同一屬性值共同構(gòu)成一個(gè)列簇，在同一列簇下更改（增加或刪除）某一屬性值，只需對(duì)包含該屬性值的行進(jìn)行操作即可。通過列簇的劃分，使得列式數(shù)據(jù)庫(kù)在簡(jiǎn)單查詢時(shí)可以直接在相應(yīng)的列簇中進(jìn)行查找，并通過行鍵確定目標(biāo)值[10-13]，極大地縮減了查詢所涉及的范圍，對(duì)于海量數(shù)據(jù)表的簡(jiǎn)單查詢來說所節(jié)省的查詢時(shí)間是非常可觀的。

2 ?預(yù)處理技術(shù)

預(yù)處理是指在進(jìn)行數(shù)據(jù)壓縮之前通過對(duì)原始數(shù)據(jù)進(jìn)行可逆的轉(zhuǎn)義處理從而加強(qiáng)后續(xù)壓縮效率的一種方法。在列式數(shù)據(jù)庫(kù)數(shù)據(jù)寫入階段，針對(duì)特定的數(shù)據(jù)類型進(jìn)行預(yù)處理能夠明顯提升數(shù)據(jù)表整體的壓縮效果。下面將對(duì)列式數(shù)據(jù)庫(kù)中常規(guī)數(shù)據(jù)類型的預(yù)處理編碼進(jìn)行闡述。

2.1 ?文本（char、string）數(shù)據(jù)編碼

Char或string類型文本數(shù)據(jù)作為數(shù)據(jù)庫(kù)的主要存儲(chǔ)對(duì)象，早在20世紀(jì)80年代，數(shù)據(jù)壓縮領(lǐng)域的相關(guān)學(xué)者就提出在采用Burrows-Wheeler（BWCA）、部分匹配預(yù)測(cè)（PPM）等壓縮算法處理文本數(shù)據(jù)時(shí)，利用文本數(shù)據(jù)的現(xiàn)實(shí)語義進(jìn)行文本替換的轉(zhuǎn)化處理方案[14]。該方案是一種基于MTF（move-to-front）[15]技術(shù)的單詞轉(zhuǎn)化方法，它通過隱式字典來記錄首次出現(xiàn)的單詞并利用隱式索引替換掉后續(xù)出現(xiàn)的同一單詞[16]。在MTF的基礎(chǔ)上，相關(guān)學(xué)者根據(jù)字母組合在單詞中出現(xiàn)的頻率提出了自適應(yīng)構(gòu)建字典的方法。如為“ary”“ion”“ing”等高頻字母組合構(gòu)建字典，對(duì)文本數(shù)據(jù)中出現(xiàn)的這些字母組合進(jìn)行替換處理從而獲得壓縮增益[17，18]，同樣還有大寫字母替換、行尾字符替換等[19-21]。實(shí)驗(yàn)結(jié)果表明，基于替換的文本數(shù)據(jù)預(yù)處理能夠有效提升文本數(shù)據(jù)的壓縮比率，其增益平均百分比為5%。

2.2 ?Int、Float型數(shù)據(jù)編碼

除了上述基于數(shù)據(jù)本身需要替換編碼以外，還有不少針對(duì)數(shù)據(jù)類型的存儲(chǔ)格式而設(shè)計(jì)的編碼算法。這類算法通常不直接壓縮數(shù)據(jù)，而是改變數(shù)據(jù)格式的排列組合從而加強(qiáng)通用壓縮算法對(duì)某種數(shù)據(jù)類型的壓縮效果，比如T64算法、Delta算法、Gorilla算法等。T64算法的原理是獲取連續(xù)的64個(gè)整數(shù)值并生成64×64位矩陣，將矩陣進(jìn)行轉(zhuǎn)置并裁剪未使用的位[22]（通過計(jì)算數(shù)據(jù)的最小值和最大值來檢測(cè)未使用的位）。T64算法能夠有效加強(qiáng)Zstd算法處理Int型數(shù)據(jù)的壓縮效果，其增益約為6%。而Delta算法則是常用在列式數(shù)據(jù)庫(kù)中針對(duì)序列數(shù)據(jù)（主要由Float和Int組成）的編碼算法。其原理是保持序列中第一個(gè)值不變，序列中除第一個(gè)值以外的值被兩個(gè)相鄰值的差值替換。如原始序列為：1（base）、2、3、4、5、6、7、8、9……，經(jīng)過Delta處理過后序列變?yōu)椋?（base）、1、1、1、1、1、1、1、1……。Gorilla[23]算法是對(duì)Delta算法的一種擴(kuò)展，它通過利用數(shù)據(jù)列當(dāng)前值與先前值的異或比較（XOR）生成增量編碼來壓縮序列中表示時(shí)間戳（timestamp）和值（value）的數(shù)據(jù)塊。整個(gè)編碼流程如圖3所示，Gorilla按照時(shí)間將數(shù)據(jù)列劃分成若干個(gè)數(shù)據(jù)塊，在存儲(chǔ)第一個(gè)數(shù)據(jù)塊（Header）后利用Delta算法處理后面的數(shù)據(jù)塊（圖中A部分所示），編碼具體的流程如圖中B部分所示，圖中C部分為面向位的異或比較的流程[24，25]。目前，T64、Delta和Gorila算法在列式數(shù)據(jù)庫(kù)中有著廣泛的應(yīng)用。

3 ?LZ系列壓縮算法

數(shù)據(jù)壓縮起源于香濃提出的信息熵理論，其本質(zhì)是對(duì)信源數(shù)據(jù)文件進(jìn)行再編碼，在不損失信息量的情況下減少數(shù)據(jù)文件的大小[26]。作為計(jì)算機(jī)領(lǐng)域應(yīng)用最廣泛的技術(shù)之一，數(shù)據(jù)壓縮發(fā)展至今已經(jīng)誕生了數(shù)百種壓縮算法，目前在列式數(shù)據(jù)庫(kù)中所應(yīng)用的還是以LZ4為代表的LZ系列算法（Lempel-Ziv Series Encoding）為主。列式數(shù)據(jù)庫(kù)中連續(xù)存儲(chǔ)的數(shù)據(jù)具有相同的數(shù)據(jù)類型且往往具有一定的關(guān)聯(lián)性，非常契合LZ4這類基于上下文滑動(dòng)窗口的壓縮算法。下面將依次分析LZ系列算法中三種較有代表性的壓縮算法并進(jìn)行實(shí)驗(yàn)測(cè)試。

3.1 ?LZ4算法

LZ4[27]是基于LZ77算法思想而設(shè)計(jì)的一款通用型無損壓縮算法。由Abraham Lempel和Jacob Ziv發(fā)明的LZ77算法[28]奠定了現(xiàn)代壓縮技術(shù)的基礎(chǔ)，LZ77算法通過結(jié)合自適應(yīng)字典技術(shù)，利用字典的映射關(guān)系在編碼時(shí)消除重復(fù)出現(xiàn)的字符來達(dá)到壓縮目的。理論上LZ77算法可以達(dá)到信息熵的極限，LZ77壓縮流程如圖4所示。LZ4算法在LZ77算法的基礎(chǔ)上簡(jiǎn)化了字符串的匹配機(jī)制，取消了緩沖區(qū)，其壓縮流程如下：

1）初始化存放字典的哈希表，哈希值為字符串位置的偏移值。

2）從待壓縮數(shù)據(jù)中取出4字節(jié)，并在哈希表中尋找匹配的字符串，若成功匹配則再次取出4字節(jié)進(jìn)行后續(xù)匹配，直至匹配失敗進(jìn)入4）。

3）輸出所有匹配成功字符串的匹配序列，匹配序列結(jié)構(gòu)如圖5所示（其中令牌前4位保存未匹配字符長(zhǎng)度，后4位為匹配成功字符長(zhǎng)度）。

4）將匹配失敗的4個(gè)字節(jié)及其位置的偏移值添加到哈希表中并檢查是否有哈希沖突，若發(fā)生沖突則將原來的哈希值更新為當(dāng)前4個(gè)字節(jié)對(duì)應(yīng)的值，最后輸出匹配序列。

5）檢查當(dāng)前位置是否超出字典窗口大小，若大于字典窗口的最大值則以當(dāng)前位置為起點(diǎn)更新哈希表中的值并重復(fù)2），直至待壓縮數(shù)據(jù)剩最后12個(gè)字符并將這12個(gè)字符直接放至輸出文件的最后。

3.2 ?Snappy算法

Snappy[29]同樣也是由LZ77算法衍生而來的。它在LZ77匹配機(jī)制上做出了調(diào)整，優(yōu)化了匹配方式。基于類似于希爾排序控制增量的思想，通過動(dòng)態(tài)增加匹配偏移字節(jié)數(shù)來提高掃描字符串的效率，其壓縮流程如下：

1）首先在匹配開始階段初始化用于匹配的字典，字典內(nèi)保存滑動(dòng)窗口中每一個(gè)字節(jié)開始4個(gè)字節(jié)轉(zhuǎn)換成Uint32的偏移值，字典的下標(biāo)為偏移值的Hash值。

2）重復(fù)遍歷（默認(rèn)16次，每次偏移一個(gè)字節(jié)）滑動(dòng)窗口，通過匹配字符串的偏移值來尋找相同的字符串，查找成功則進(jìn)入5）。

3）繼續(xù)查找剩余字符串。此時(shí)偏移字節(jié)逐步累加，匹配方式與上一步相同。

4）處理未匹配的字符串。生成1個(gè)標(biāo)簽字節(jié)記錄當(dāng)前偏移位置和未匹配字符串的長(zhǎng)度。

5）處理匹配成功的字符串，更新滑動(dòng)窗口并重復(fù)2）直至找到待壓縮數(shù)據(jù)塊的最后15個(gè)字符并將這15個(gè)字符直接放至輸出文件的最后。

3.3 ?Zstd算法

Zstd[30]的設(shè)計(jì)原理大體上與Deflate算法[31]相同。Deflate算法在LZ77算法的基礎(chǔ)上結(jié)合了Huffman編碼，利用Huffman編碼將LZ77算法的輸出結(jié)果再編碼以獲得極高的壓縮比。Zstd在Deflate算法的基礎(chǔ)上做了以下改變：

1）使用有限狀態(tài)熵編碼（Finite State Entropy）[32]代替Huffman編碼。

2）在匹配字符串的階段不再限定匹配字符串的大小。

3）允許偏移量重復(fù)出現(xiàn)。Zstd算法提供幾十種壓縮級(jí)別，以適應(yīng)不同的硬件環(huán)境。同時(shí)，Zstd還提供一種訓(xùn)練壓縮字典的模式，通過樣本訓(xùn)練字典并在適當(dāng)?shù)膱?chǎng)景加載字典。訓(xùn)練字典模式在壓縮冗余較大數(shù)據(jù)文件時(shí)的效果非常明顯，能夠在保證高壓縮比的前提下獲得極高的壓縮速度。

4 ?算法性能測(cè)試

本文針對(duì)上述三種壓縮算法在列式數(shù)據(jù)庫(kù)的存儲(chǔ)、查詢性能方面進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境如下：CPU Intel Xeon E7- 4807 （24） @ 1.862 GHz；內(nèi)存16 GB（DDR3 800）；緩存L1 32 Kbytes、L2 256 Kbytes、L3 18 432 Kbytes；硬盤SSD 4 TB、HHD 250 GB×2；軟件操作環(huán)境Ubuntu 20.04.3 LTS；軟件及算法ClickHouse v21.9.2.17-stable、LZ4 v1.9.3、Snappy v1.1.9、Zstd v1.5.2。測(cè)試數(shù)據(jù)集統(tǒng)一采用美國(guó)1987年至2017年民用航班數(shù)據(jù)，共1.75億條數(shù)據(jù)，大小為54.20 GB，算法性能對(duì)比如表1和圖6所示，其中壓縮比（CR）的計(jì)算公式為：

CR = COMa /COMb ? ? ? ? ? ? ? ? （1）

其中，COMa表示壓縮后數(shù)據(jù)文件的大小，COMb表示壓縮前數(shù)據(jù)文件的大小，CR值越低壓縮效果越好。

由表1和圖6可知三種算法性能各有優(yōu)劣，適用于不同的場(chǎng)景。在讀取經(jīng)過壓縮后的數(shù)據(jù)時(shí)需要先將處于壓縮態(tài)的數(shù)據(jù)塊從硬盤讀入內(nèi)存；接著從內(nèi)存?zhèn)鬏斨罜ACHE，并在CACHE中解壓；再把解壓后的數(shù)據(jù)傳回內(nèi)存中；最后才能對(duì)數(shù)據(jù)進(jìn)行查詢操作。Zstd算法在壓縮（解壓）過程中需要再次對(duì)輸出結(jié)果進(jìn)行有限狀態(tài)熵編碼（解碼），因此同等條件下Zstd算法的壓縮比最好，適合于對(duì)時(shí)效性要求較低的海量數(shù)據(jù)存儲(chǔ)場(chǎng)景。三種算法中LZ4算法的綜合性能最好，尤其是I/O速度高出其他兩種算法一個(gè)數(shù)量級(jí)，是列式數(shù)據(jù)庫(kù)中應(yīng)用面最廣的一款壓縮算法。雖然Snappy算法的壓縮和查詢性能都不如另外兩種算法，但其對(duì)硬件的兼容性高且壓縮速度快，非常適合分布式的存儲(chǔ)場(chǎng)景。

5 ?結(jié) ?論

大數(shù)據(jù)時(shí)代下列式數(shù)據(jù)庫(kù)在數(shù)據(jù)分析領(lǐng)域具有廣闊的應(yīng)用前景，面向列的存儲(chǔ)機(jī)制為列式數(shù)據(jù)庫(kù)提供了強(qiáng)大的查詢能力和靈活可擴(kuò)展的數(shù)據(jù)類型支持。本文從數(shù)據(jù)存儲(chǔ)的角度闡述了列式數(shù)據(jù)庫(kù)中常用的預(yù)處理編碼方式和主流的LZ系列壓縮算法，并將三種LZ系列算法集成到ClickHouse列式數(shù)據(jù)庫(kù)中加以實(shí)驗(yàn)測(cè)試并總結(jié)各自的適用場(chǎng)景。數(shù)據(jù)壓縮不僅有助于列式數(shù)據(jù)庫(kù)節(jié)省存儲(chǔ)成本同時(shí)還能提高數(shù)據(jù)的傳輸效率，已是列式數(shù)據(jù)庫(kù)不可或缺的組成部分。希望通過本文的綜述分析能為數(shù)據(jù)壓縮技術(shù)在列式數(shù)據(jù)庫(kù)中的研究與應(yīng)用提供有益參考。

參考文獻(xiàn)：

[1] STONEBRAKER M，ABADI D J，BATKIN A，et al. C-Store： A Column-Oriented DBMS [C]//Proceedings of the 31st international conference on Very large data bases. Trondheim：[s.n.]，2005：553-564.

[2] HEINZL L，HURDELHEY B，BOISSIER M，et al. Evaluating Lightweight Integer Compression Algorithms in Column-Oriented In-Memory DBMS [EB/OL].[2023-01-08].https：//www.researchgate.net/publication/358862115_Evaluating_Lightweight_Integer_Compression_Algorithms_in_Column-Oriented_In-Memory_DBMS.

[3] AGEED Z S，ZEEBAREE S R M，SADEEQ M A M，et al. A Comprehensive Survey of Big Data Mining Approaches in Cloud Systems [EB/OL].[2023-01-05].https：//www.researchgate.net/publication/351005929_A_Comprehensive_Survey_of_Big_Data_Mining_Approaches_in_Cloud_Systems.

[4] KHALAF O I，ABDULSAHIB G M. Optimized Dynamic Storage of Data （ODSD） in IoT Based on Blockchain for Wireless Sensor Networks [J].Peer-to-Peer Networking and Applications，2021，14：2858–2873.

[5] CHANG L，WANG Z W，MA T，et al. HAWQ： A Massively Parallel Processing SQL Engine in Hadoop [EB/OL].[2023-01-04].https：//dl.acm.org/doi/10.1145/2588555.2595636.

[6] Neo4j. Overcoming SQL Strain and SQL Pain （White Paper）[EB/OL].[2022-08-22].http：//neo4j.com/resources/wp-overcomingsqlstrain/？utm_source=dbengines&utm_medium=textsqlpain&utm_content=download&utm_campaign=dl.

[7] CHANG F，Dean J，Ghemawat S，et al. Bigtable： A Distributed Storage System for Structured Data [J].ACM Transactions on Computer Systems，2008，26（2）：1-26.

[8] ALESSANDRO D，IDILIO D，ANDREA M，et al. A Survey on Big Data for Network Traffic Monitoring and Analysis [J].IEEE Transactions on Network and Service Management，2019，16（3）：800-813.

[9] 陳曉寧.海量數(shù)據(jù)下列式數(shù)據(jù)庫(kù)研究 [D].廣州：華南理工大學(xué)，2012.

[10] ZHANG J W，SUN D W. Improvement of data compression technology for power dispatching based on run length encoding [J].Procedia Computer Science，2021，183：526-532.

[11] OSMAN A M S. A novel big data analytics framework for smart cities [J].Future Generation Computer Systems，2019，91：620-633.

[12] CHAND M. What Is A Column Store Database [EB/OL].[2023-01-10].https：//www.c-sharpcorner.com/article/what-is-a-column-store-database.

[13] 朱凱.ClickHouse原理解析與應(yīng)用實(shí)踐 [M].北京：機(jī)械工業(yè)出版社，2020.

[14] KANAKARAJAN K R，KUNDUMANI B，SANKARASUBBU M. BioELECTRA： Pretrained Biomedical text Encoder using Discriminators [EB/OL].[2022-12-16].https：//aclanthology.org/2021.bionlp-1.16/.

[15] ZHAO R，ZHENG K C，ZHA Z J. Stacked Convolutional Deep Encoding Network For Video-Text Retrieval [J/OL].arXiv：2004.04959 [cs.MM].[2022-12-05].https：//arxiv.org/abs/2004.04959v1.

[16] JAIN A，LAKHTARIA K I. Comparative Study of Dictionary based Compression Algorithmson Text Data [EB/OL].[2022-12-10].http：//paper.ijcsns.org/07_book/201602/20160215.pdf.

[17] KANDA S，MORITA K，F(xiàn)UKETA M. Practical String Dictionary Compression Using String Dictionary Encoding [C]//2017 International Conference on Big Data Innovations and Applications （Innovate-Data）.Prague：IEEE，2017：1-8.

[18] ZUO L Q，SUN H M，MAO Q C，et al. Natural Scene Text Recognition Based on Encoder-Decoder Framework [J].IEEE Access，2019，7：62616-62623.

[19] HABIB A，ISLAM M J，RAHMAN M S. A dictionary-based text compression technique using quaternary code [EB/OL].[2022-12-29].https：//link.springer.com/article/10.1007/s42044-019-00047-w.

[20] OSWALD C，SIVASELVAN B. An optimal text compression algorithm based on frequent pattern mining [J].Journal of Ambient Intelligence and Humanized Computing，2018，9：803-822.

[21] OSWALD C，GHOSH A I，SIVASELVAN B. Knowledge engineering perspective of text compression [C]//2015 Annual IEEE India Conference （INDICON）. New Delhi：IEEE，2015：1-6.

[22] WANG S X，CHEN H W，WU L，et al. A novel smart meter data compression method via stacked convolutional sparse auto-encoder [EB/OL].[2022-12-13].https：//www.researchgate.net/publication/337768393_A_Novel_Smart_Meter_Data_Compression_Method_via_Stacked_Convolutional_Sparse_Auto-encoder.

[23] PELKONEN T，F(xiàn)RANKLIN S，TELLER J，et al. Gorilla： A Fast， Scalable， In-Memory Time Series Database [J].Proceedings of the VLDB Endowment，2015，8（12）：1816-1827.

[24] HUANG Y W，HSU C W，CHEN C Y，et al. A VVC Proposal With Quaternary Tree Plus Binary-Ternary Tree Coding Block Structure and Advanced Coding Techniques [J].IEEE Transactions on Circuits and Systems for Video Technology，2020，30（5）：1311-1325.

[25] PATIL M V，PAWAR S，SAQUIB Z. Coding Techniques for 5G Networks： A Review [C]//2020 3rd International Conference on Communication System， Computing and IT Applications （CSCITA）.Mumbai：IEEE，2020：208-213.

[26] Sayood K.數(shù)據(jù)壓縮導(dǎo)論：第3版 [M].賈洪峰，譯.北京：人民郵電出版社，2009.

[27] YANN C. Lz4 source code [EB/OL].[2022-12-07].https：//github.com/lz4/lz4.

[28] ZIV J，LEMPEL A. A universal algorithm for sequential data compression [J].IEEE Transations on Information Theory，1977，23（3）：337-347.

[29] Google Inc. Snappy source code [EB/OL].[2022-12-25].https：//github.com/google/snappy.

[30] Yann C. Zstd source code [EB/OL].[2022-12-05].https：//github.com/facebook/zstd.

[31] OSWAL S，SINGH A，KUMARI K. Deflate Compression Algorithm [EB/OL].[2023-01-14].https：//citeseerx.ist.psu.edu/document？repid=rep1&type=pdf&doi=e8d7c01594cf4359c3d50aef7db88b0153c7fcbd.

[32] RATTANAOPAS K，KAEWKEEREE S. Improving Hadoop MapReduce performance with data compression： A study using wordcount job [C]//2017 14th International Conference on Electrical Engineering/Electronics， Computer， Telecommunications and Information Technology （ECTI-CON）. Phuket：IEEE，2017：564-567.

作者簡(jiǎn)介：丁銳恒（1997—），男，漢族，四川德陽人，碩士研究生在讀，主要研究方向：數(shù)據(jù)庫(kù)技術(shù)、數(shù)據(jù)壓縮。