列式数据库的数据压缩技术研究

丁锐恒 梁波

摘  要：随着大数据产业的兴起，列式数据库的应用价值得以体现。凭借其灵活高效的查询性能以及对复杂异构数据的兼容支持，列式数据库在海量数据的分布式存储和数据查询分析领域具有广阔的应用前景。首先从实际应用的角度阐述列式数据库的基本特性和存储架构；其次分析列式数据库中所应用的数据压缩技术并通过实验验证数据压缩对列式数据库存取性能的影响程度。

关键词：列式数据库；数据压缩；压缩算法；预处理

中图分类号：TP391     文献标识码：A   文章编号：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  引  言

如今，数据分析已广泛应用于科学实验、医疗卫生、商业决策、社交网络、生产制造等诸多领域。数据存储作为数据分析工作的首要步骤，其重要性不言而喻。在过去的几十年里，行式数据库（Row-Oriented DBMS）因良好的结构特性和通用的查询语言，在数据的存储管理中占据主导地位。数据库应用场景的扩展和交互式设备的普及，使得数据体量攀升、数据结构多样化。传统行式数据库的性能已不能满足数亿级别数据的秒级检索、实时处理、大規模存储等需求。近些年来，在Stonebraker、Daniel、Abadi、Boncz等数据库专家的大力提倡下，列式数据库（Column-Oriented DBMS）技术及相关应用快速发展[1，2]。基于对联机分析处理（On-Line Analysis Processing）支持友好、查询性能强悍、易于搭建分布式集群等优势，列式数据库已逐渐替代行式数据库而成为众多企业搭建数据仓库（Data Warehouse）的首选方案[3，4]。然而，无论是行式数据库还是列式数据库，数据存储量增长所导致的存储成本提高都是数据管理不可避免的问题[5，6]。与此同时，随着分布式、云计算技术在数据库领域的发展与应用，大规模数据实时传输成本控制也是亟待解决的问题。纵观整个数据库领域，几乎所有的数据库（无论是行式数据库还是列式数据库）都会应用数据压缩技术，数据库的压缩效率也成为评价数据库性能优劣的标准之一。数据压缩是指在不损失信息量的前提下按照一定的编码规则对数据进行重新组织从而达到减少数据长度的目的，而列式数据库的存储原理决定了其在数据压缩上的优势。美国媒体流量分析公司Nielsen Media Research以列式数据库产品Sybase IQ搭建数据仓库，初始大小为17.969 TB，运行两年后数据仓库的数据量为17.585 TB，相比之下，Yahoo公司基于行式数据库Oracle搭建的数据仓库从最开始的17.014 TB扩大到100 TB[7]。对比行式数据库，在列式数据库中应用数据压缩具有显著的效果。本文主要围绕列式数据库中的数据压缩技术进行综述，首先介绍列式数据库的特性和存储原理，其次阐述了预处理编码技术和LZ系列压缩算法在列式数据库中的应用。

1  列式数据库

1.1  列式数据库特性

列式数据库的诞生最早可以追溯到20世纪90年代。ExpressWay Technologies公司在当时推出一款有助于传统数据库提升报表制作速度的工具，其原理就是将数据表进行垂直划分以列的方式进行存储从而提高查询的速度。1994年，Sybase公司认准这项技术并收购了ExpressWay Technologies公司，在1996年推出了基于列存储的数据库产品——Sybase IQ。此后随着工业界数据体量的增长和数据分析的发展，人们开始注意到列式数据库在存储管理大规模数据上的优势。在2005年第31届超大型数据库会议（Very Large Data Bases）上，由Mike Stonebraker等人发表的论文“C-Store： A Column-Oriented DBMS”中正式提出了列式数据库的概念。所谓列式数据库，就是以数据表中的列（属性）为单位进行数据写入，将数据表不同元组中的相同属性值存储在一起，将同一元组中不同的属性值分别存放在不同的存储单元中[8]。相较于行式数据库，列式数据库的存储结构具有以下优势：

1）连续存储数据的结构类型相同且具有一定的相关性，非常适合进行高效的压缩操作。

2）以列为单位进行存储，在查询时可以将查询命令分解成以列为对象的操作，只需读取所涉及的列即可。

例如，对一张气候表Climate Record（Date，

Temperature， Wind， Rain）执行查询操作SELECT date

FROM Climate Record WHERE Temperature>35 AND Temperature<40 ORDER BY Date DESC。首先读取Temperature属性列，筛选出Temperature值介于35和40之间的记录并读取这些记录的Data属性列，最后根据Data值进行排序。整个过程只读取了Temperature列和Data列，極大地节省了I/O带宽也减少了内存和Cache等资源的使用，同时也省去了行式数据库中映射（Projection）运算的开销[9]。

1.2  列式数据库存储架构

列式数据库强调列簇（Column Family）的概念，首先采用键空间（Keyspace）作为基础的数据表存储架构，键空间中包含若干个列簇，如图1所示。

列簇下包含若干个行，行键（Row Key）是每个行的唯一标识，如图2所示。行中包含不同数量、不同类型的列关键字以及对应的时间戳，列关键字表示一种属性值的数据类型同时也是基础的存储单元。数据表在被存储之前必须先创建列簇，不同元组中的同一属性值共同构成一个列簇，在同一列簇下更改（增加或删除）某一属性值，只需对包含该属性值的行进行操作即可。通过列簇的划分，使得列式数据库在简单查询时可以直接在相应的列簇中进行查找，并通过行键确定目标值[10-13]，极大地缩减了查询所涉及的范围，对于海量数据表的简单查询来说所节省的查询时间是非常可观的。

2  预处理技术

预处理是指在进行数据压缩之前通过对原始数据进行可逆的转义处理从而加强后续压缩效率的一种方法。在列式数据库数据写入阶段，针对特定的数据类型进行预处理能够明显提升数据表整体的压缩效果。下面将对列式数据库中常规数据类型的预处理编码进行阐述。

2.1  文本（char、string）数据编码

Char或string类型文本数据作为数据库的主要存储对象，早在20世纪80年代，数据压缩领域的相关学者就提出在采用Burrows-Wheeler（BWCA）、部分匹配预测（PPM）等压缩算法处理文本数据时，利用文本数据的现实语义进行文本替换的转化处理方案[14]。该方案是一种基于MTF（move-to-front）[15]技术的单词转化方法，它通过隐式字典来记录首次出现的单词并利用隐式索引替换掉后续出现的同一单词[16]。在MTF的基础上，相关学者根据字母组合在单词中出现的频率提出了自适应构建字典的方法。如为“ary”“ion”“ing”等高频字母组合构建字典，对文本数据中出现的这些字母组合进行替换处理从而获得压缩增益[17，18]，同样还有大写字母替换、行尾字符替换等[19-21]。实验结果表明，基于替换的文本数据预处理能够有效提升文本数据的压缩比率，其增益平均百分比为5%。

2.2  Int、Float型数据编码

除了上述基于数据本身需要替换编码以外，还有不少针对数据类型的存储格式而设计的编码算法。这类算法通常不直接压缩数据，而是改变数据格式的排列组合从而加强通用压缩算法对某种数据类型的压缩效果，比如T64算法、Delta算法、Gorilla算法等。T64算法的原理是获取连续的64个整数值并生成64×64位矩阵，将矩阵进行转置并裁剪未使用的位[22]（通过计算数据的最小值和最大值来检测未使用的位）。T64算法能够有效加强Zstd算法处理Int型数据的压缩效果，其增益约为6%。而Delta算法则是常用在列式数据库中针对序列数据（主要由Float和Int组成）的编码算法。其原理是保持序列中第一个值不变，序列中除第一个值以外的值被两个相邻值的差值替换。如原始序列为：1（base）、2、3、4、5、6、7、8、9……，经过Delta处理过后序列变为：1（base）、1、1、1、1、1、1、1、1……。Gorilla[23]算法是对Delta算法的一种扩展，它通过利用数据列当前值与先前值的异或比较（XOR）生成增量编码来压缩序列中表示时间戳（timestamp）和值（value）的数据块。整个编码流程如图3所示，Gorilla按照时间将数据列划分成若干个数据块，在存储第一个数据块（Header）后利用Delta算法处理后面的数据块（图中A部分所示），编码具体的流程如图中B部分所示，图中C部分为面向位的异或比较的流程[24，25]。目前，T64、Delta和Gorila算法在列式数据库中有着广泛的应用。

3  LZ系列压缩算法

数据压缩起源于香浓提出的信息熵理论，其本质是对信源数据文件进行再编码，在不损失信息量的情况下减少数据文件的大小[26]。作为计算机领域应用最广泛的技术之一，数据压缩发展至今已经诞生了数百种压缩算法，目前在列式数据库中所应用的还是以LZ4为代表的LZ系列算法（Lempel-Ziv Series Encoding）为主。列式数据库中连续存储的数据具有相同的数据类型且往往具有一定的关联性，非常契合LZ4这类基于上下文滑动窗口的压缩算法。下面将依次分析LZ系列算法中三种较有代表性的压缩算法并进行实验测试。

3.1  LZ4算法

LZ4[27]是基于LZ77算法思想而设计的一款通用型无损压缩算法。由Abraham Lempel和Jacob Ziv发明的LZ77算法[28]奠定了现代压缩技术的基础，LZ77算法通过结合自适应字典技术，利用字典的映射关系在编码时消除重复出现的字符来达到压缩目的。理论上LZ77算法可以达到信息熵的极限，LZ77压缩流程如图4所示。LZ4算法在LZ77算法的基础上简化了字符串的匹配机制，取消了缓冲区，其压缩流程如下：

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

2）从待压缩数据中取出4字节，并在哈希表中寻找匹配的字符串，若成功匹配则再次取出4字节进行后续匹配，直至匹配失败进入4）。

3）输出所有匹配成功字符串的匹配序列，匹配序列结构如图5所示（其中令牌前4位保存未匹配字符长度，后4位为匹配成功字符长度）。

4）将匹配失败的4个字节及其位置的偏移值添加到哈希表中并检查是否有哈希冲突，若发生冲突则将原来的哈希值更新为当前4个字节对应的值，最后输出匹配序列。

5）检查当前位置是否超出字典窗口大小，若大于字典窗口的最大值则以当前位置为起点更新哈希表中的值并重复2），直至待壓缩数据剩最后12个字符并将这12个字符直接放至输出文件的最后。

3.2  Snappy算法

Snappy[29]同样也是由LZ77算法衍生而来的。它在LZ77匹配机制上做出了调整，优化了匹配方式。基于类似于希尔排序控制增量的思想，通过动态增加匹配偏移字节数来提高扫描字符串的效率，其压缩流程如下：

1）首先在匹配开始阶段初始化用于匹配的字典，字典内保存滑动窗口中每一个字节开始4个字节转换成Uint32的偏移值，字典的下标为偏移值的Hash值。

2）重复遍历（默认16次，每次偏移一个字节）滑动窗口，通过匹配字符串的偏移值来寻找相同的字符串，查找成功则进入5）。

3）继续查找剩余字符串。此时偏移字节逐步累加，匹配方式与上一步相同。

4）处理未匹配的字符串。生成1个标签字节记录当前偏移位置和未匹配字符串的长度。

5）处理匹配成功的字符串，更新滑动窗口并重复2）直至找到待压缩数据块的最后15个字符并将这15个字符直接放至输出文件的最后。

3.3  Zstd算法

Zstd[30]的设计原理大体上与Deflate算法[31]相同。Deflate算法在LZ77算法的基础上结合了Huffman编码，利用Huffman编码将LZ77算法的输出结果再编码以获得极高的压缩比。Zstd在Deflate算法的基础上做了以下改变：

1）使用有限状态熵编码（Finite State Entropy）[32]代替Huffman编码。

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

3）允许偏移量重复出现。Zstd算法提供几十种压缩级别，以适应不同的硬件环境。同时，Zstd还提供一种训练压缩字典的模式，通过样本训练字典并在适当的场景加载字典。训练字典模式在压缩冗余较大数据文件时的效果非常明显，能够在保证高压缩比的前提下获得极高的压缩速度。

4  算法性能测试

本文针对上述三种压缩算法在列式数据库的存储、查询性能方面进行了对比实验。实验环境如下：CPU Intel Xeon E7- 4807 （24） @ 1.862 GHz；内存16 GB（DDR3 800）；缓存L1 32 Kbytes、L2 256 Kbytes、L3 18 432 Kbytes；硬盘SSD 4 TB、HHD 250 GB×2；软件操作环境Ubuntu 20.04.3 LTS；软件及算法ClickHouse v21.9.2.17-stable、LZ4 v1.9.3、Snappy v1.1.9、Zstd v1.5.2。测试数据集统一采用美国1987年至2017年民用航班数据，共1.75亿条数据，大小为54.20 GB，算法性能对比如表1和图6所示，其中压缩比（CR）的计算公式为：

CR = COMa /COMb                 （1）

其中，COMa表示压缩后数据文件的大小，COMb表示压缩前数据文件的大小，CR值越低压缩效果越好。

由表1和图6可知三种算法性能各有优劣，适用于不同的场景。在读取经过压缩后的数据时需要先将处于压缩态的数据块从硬盘读入内存；接着从内存传输至CACHE，并在CACHE中解压；再把解压后的数据传回内存中；最后才能对数据进行查询操作。Zstd算法在压缩（解压）过程中需要再次对输出结果进行有限状态熵编码（解码），因此同等条件下Zstd算法的压缩比最好，适合于对时效性要求较低的海量数据存储场景。三种算法中LZ4算法的综合性能最好，尤其是I/O速度高出其他两种算法一个数量级，是列式数据库中应用面最广的一款压缩算法。虽然Snappy算法的压缩和查询性能都不如另外两种算法，但其对硬件的兼容性高且压缩速度快，非常适合分布式的存储场景。

5  结  论

大数据时代下列式数据库在数据分析领域具有广阔的应用前景，面向列的存储机制为列式数据库提供了强大的查询能力和灵活可扩展的数据类型支持。本文从数据存储的角度阐述了列式数据库中常用的预处理编码方式和主流的LZ系列压缩算法，并将三种LZ系列算法集成到ClickHouse列式数据库中加以实验测试并总结各自的适用场景。数据压缩不仅有助于列式数据库节省存储成本同时还能提高数据的传输效率，已是列式数据库不可或缺的组成部分。希望通过本文的综述分析能为数据压缩技术在列式数据库中的研究与应用提供有益参考。

参考文献：

[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] 陳晓宁.海量数据下列式数据库研究 [D].广州：华南理工大学，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原理解析与应用实践 [M].北京：机械工业出版社，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，FUKETA 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，FRANKLIN 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.數据压缩导论：第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.

作者简介：丁锐恒（1997—），男，汉族，四川德阳人，硕士研究生在读，主要研究方向：数据库技术、数据压缩。