高级数据库十二：数据库压缩

Dear 丶 2022-06-02 00:49 159阅读 0赞

# Database Compression #

## 背景 ##

如果数据库需要从硬盘中获得数据，那么数据的I/O操作才是数据库的瓶颈。所以需要对数据进行压缩。

内存中的数据库管理系统比较复杂。压缩数据库降低了DRAM的性能要求和处理时间。DRAM不仅价格贵，而且在运行且维护的代价也非常大。

关键在于如何平衡速度和压缩率之间的关系。在内存数据库中，按照老师的说法，总是选择速度而不是压缩率。也就是说，如果有一个压缩率非常棒的算法，但是它的速度较慢，也不会选择这个。因为如果内存数据库的运行速度变慢，就失去了它最大的优势。

### 现实世界中的数据特性 ###

我们可以根据现实世界中一些数据的特点设计特定的压缩算法。

数据集倾向于对属性值分布严重偏斜。比如，zipfian分布（在给定的语料中，对于任意一个term，其频度(freq)的排名（rank）和freq的乘积大致是一个常数。例如，url，少量的页面被大量的页面引用；大量的页面被少量的页面引用）。

数据集往往有相同的元组属性之间的高度相关性。比如，邮政编码与城市、火车的出发时间和到达时间。

### 压缩目标 ###

目标1：必须产生固定长度的值。这种数据存储的优势在上篇文章说了。

目标2：允许DBMS在查询执行期间尽可能延缓解压缩。在查询的时候，假设DBMS是一条一条查，那么它就应该是一条一条数据解压。这个目标在朴素压缩上是难以完成的，但是后两种压缩方式都有围绕这个目标进行设计。

### 无损压缩 vs 有损压缩 ###

对于DBMS而言，所有的压缩都应该是无损的。你从什么数据压缩过来，就应该能够完全地解压回这种方式。

如果需要有损压缩，那么一定是在应用层面上的设计，应用设计者人为地造出有损压缩。但是对于DBMS，它并不清楚什么数据可以进行有损压缩，什么数据需要进行无损压缩，所以一律都是无损的。

有一些新式的DBMS支持模糊查询：[BlinkDB][], [SnappyData][]。

### 压缩粒度（COMPRESSION GRANULARITY） ###

1.  Block-level  
    
    
     *  压缩同一个表的一组元组。
2.  Tuple-level  
    
    
     *  压缩整个元组的内容（仅NSM）。
3.  Attribute-level  
    
    
     *  压缩一个元组中的单个属性值。
     *  可以为同一个元组定位多个属性。
4.  Column-level  
    
    
     *  压缩为多个元组存储的一个或多个属性的多个值（仅限DSM）。

## ZONE MAPS ##

类似于一种预处理的手段，对于每一个BLOCK，可以先将它的聚合函数给求出来。

![15143930107850.jpg][]

## 朴素压缩 ##

使用通用算法压缩数据。  
压缩范围仅限于输入的数据。

算法有LZO (1996)，LZ4 (2011)，Snappy (2011)，Zstd (2015)。

需要考虑的是Computational overhead和压缩、解压速率，通常而言，这些算法都比较慢。

### Entropy Encoding ###

类似霍夫曼编码，常用的用更少的比特位，不常用的用更多的比特位。

### Dictionary Encoding ###

构建将数据段映射到标识符的数据结构。

将原始数据中的这些段替换为对字典数据结构中的段位置的引用。

### MySQL压缩方式 ###

![15143938133139.jpg][]

压缩页的大小通常是这些，这样就更好管理。

如果我们需要读取压缩页中的值，进行解压。

![15143939405624.jpg][]

### 缺点 ###

因此，这限制了压缩方案的“大小范围”，如果压缩页太大，那么无论DBMS需要读取的是一条数据还是一万条数据，它都要全部解压。

这些方案也不考虑数据的高级含义或语义。

## OLAP 列压缩 ##

这是众多数据库中最常用的方式。

常见的有：

*  Null Suppression
 *  Run-length Encoding
 *  Bitmap Encoding
 *  Delta Encoding
 *  Incremental Encoding
 *  Mostly Encoding
 *  Dictionary Encoding

MSSQL的列索引是数据的第二个副本（又名破碎的镜像），原始数据仍然以NSM格式存储。

但是我们现在说的是原始数据的压缩。

### NULL 压缩 ###

数据中连续的零或空白被替换为有多少和哪里存在的描述。

示例：Oracle的字节对齐位图代码（BBC）

在稀疏数据的宽表中很有用。

### RUN-LENGTH ENCODING ###

将单个列中相同值的运行压缩为三元组：

*  属性的值。
 *  列段中的起始位置。
 *  运行中的元素个数

需要将列进行智能排序来最大化压缩率。

### BITMAP ENCODING ###

为特定属性的每个唯一值存储单独的位图，其中矢量中的偏移量与元组相对应。

可以使用我们所说的关于位图索引的压缩方案。

只有属性值基数低才有实际意义。

### DELTA ENCODING ###

记录在同一列中相互跟随的值之间的差异。

*  基本值可以在线存储或在单独的查找表中存储。
 *  可以结合RLE来获得更好的压缩比。

![15144308916985.jpg][]

### INCREMENTAL ENCODING ###

增量编码的类型，通常的前缀或后缀及其长度被记录，以便它们不需要被复制。  
这对于排序的数据效果最好。

![15144309509998.jpg][]

记录和上一个的公共前缀，并进行压缩。

但是也因为存的仅仅与上一条数据的关系，所以解码的时候也需要一行一行地解。

### MOSTLY ENCODING ###

如果属性的值“大部分”小于最大大小，则可以将它们存储为较小的数据类型。

将不能压缩的剩余值将以其原始格式存储。

![15144310734915.jpg][]

### DICTIONARY COMPRESSION ###

用较小的代码替换频繁的模式。  
DBMS中最普遍的压缩方案。  
需要支持快速编码和解码。  
还需要支持范围查询。

#### All At Once ####

将整个表一起计算，来产生字典。  
新元组必须使用单独的字典，否则必须重新计算所有元组。

#### DICTIONARY SCOPE ####

1.  Block Level  
    
    
     *  在一个表中只包含元组的一个子集。
     *  可能降低压缩比，但可以更容易地添加新的元组。
2.  Table Level  
    
    
     *  为整个表构建一个字典。
     *  更好的压缩比，但更新代价大。
3.  Multi-Table  
    
    
     *  可以是子集或整个表。
     *  有时对联接和设置操作有帮助。

#### Incremental ####

将新的元组添加到现有的字典中。

可能需要重新编码现有的元组。

#### MULTI-ATTRIBUTE ENCODING ####

不是为每个字典条目存储单个值，而是存储跨越属性的条目。

老师不确定任何DBMS实际上实现了这个。

![15144325163016.jpg][]

### ENCODING / DECODING ###

需要有一种数据结构支持编码和解码，而不是单方向的hash操作。

#### ORDER-PRESERVING COMPRESSION ####

编码值需要支持与原始值相同的顺序进行排序。

![15144326891887.jpg][]

![15144327218937.jpg][]

我们查了字典之后，再查压缩表。

![15144328734417.jpg][]

我们只需要查阅字典即可。

### DICTIONARY IMPLEMENTATIONS ###

哈希表：

*  快速，紧凑。
 *  无法支持范围和前缀查询。

B+树：

*  比散列表慢，需要更多的内存。
 *  可以支持范围和前缀查询。

SHARED-LEAVES树

用一个树进行编码，一个树进行解码。

![15144332773302.jpg][]

## OLTP 索引压缩 ##

对于OLTP，DBMS不能使用OLAP压缩技术，因为我们需要支持快速随机元组访问。

在进行事务时，即时压缩和解压缩“热”元组将太慢。

索引将消耗OLTP数据库的大部分内存，所以压缩原有数据是得不偿失的，所以我们应该要对索引进行压缩。

### HYBRID INDEXES ###

将单个逻辑索引拆分为两个物理索引。随着时间的推移，数据从一个阶段迁移到另一个阶段。

*  动态阶段：新数据，快速更新。
 *  静态阶段：旧数据，压缩+只读。

所有更新进入动态阶段。  
查询可能需要检查两个阶段。

![15144347177274.jpg][]

### 压缩B+树 ###

![15144347547728.jpg][]

我们有很多的空余空间。但是因为这是一个只读树，所以我们知道这些空余空间永远不会被用到，所以我们可以将整棵树进行压缩。

![15144348019427.jpg][]

我们可以进一步地将这些指针给压缩了。

![15144348150943.jpg][]

## 参考资料 ##

[课件][Link 1]  
[zipfian分布][zipfian]

[BlinkDB]: http://blinkdb.org/
[SnappyData]: http://www.snappydata.io/
[15143930107850.jpg]: https://lh3.googleusercontent.com/-AguXlwfVB30/WkRzl1X4rJI/AAAAAAAAAZg/qR2b6z5_aE0rzgCfnnhw9FbJnTASJUY-QCHMYCw/I/15143930107850.jpg
[15143938133139.jpg]: https://lh3.googleusercontent.com/-6jTlU8wIGkI/WkRzmcG1eyI/AAAAAAAAAZk/FhadMzKjF6wVBnKegxr5N0NCyI74bhj8gCHMYCw/I/15143938133139.jpg
[15143939405624.jpg]: https://lh3.googleusercontent.com/-QMnCroBGxmA/WkRznIRtIYI/AAAAAAAAAZo/kfaho5q0sfIbDrMAo43XpD4hCOSQ1K_mgCHMYCw/I/15143939405624.jpg
[15144308916985.jpg]: https://lh3.googleusercontent.com/-O21xWiLtv4c/WkRznQCjfgI/AAAAAAAAAZs/pTqzKfm8F_ccPBkfFGjw_s6Z7dv56JaHACHMYCw/I/15144308916985.jpg
[15144309509998.jpg]: https://lh3.googleusercontent.com/-B4_rC27jflw/WkRzntj566I/AAAAAAAAAZw/K49lIocENqY-vAZsRITlEW2-jYsIsu38wCHMYCw/I/15144309509998.jpg
[15144310734915.jpg]: https://lh3.googleusercontent.com/-PCxWK_oh4j8/WkRzn6HUgWI/AAAAAAAAAZ0/YzvOlTJ7RpMse5j3Mx98WA1dwBh4qx8SACHMYCw/I/15144310734915.jpg
[15144325163016.jpg]: https://lh3.googleusercontent.com/-AaxPV0eM-yc/WkRzoMVC0EI/AAAAAAAAAZ4/SrrpZzVNbh4Ol53vONa4TT32sadt0JhPACHMYCw/I/15144325163016.jpg
[15144326891887.jpg]: https://lh3.googleusercontent.com/-xPIDhbzbzmg/WkRzoU3eaeI/AAAAAAAAAZ8/ke42urjFrxkIIWTcJmGCjSBylJ7u6j3TgCHMYCw/I/15144326891887.jpg
[15144327218937.jpg]: https://lh3.googleusercontent.com/-C4KvftLMuUg/WkRzoqeh1JI/AAAAAAAAAaA/27hU3m0X5CEps_pLkzpMv1fJunanGLIOACHMYCw/I/15144327218937.jpg
[15144328734417.jpg]: https://lh3.googleusercontent.com/-cjfIOtsKm5E/WkRzo2oZ0hI/AAAAAAAAAaE/qgVJGFTDdiwHEuUVS0Ks5pTmI8icYMyiACHMYCw/I/15144328734417.jpg
[15144332773302.jpg]: https://lh3.googleusercontent.com/-xSjjPezCVQc/WkRzpdB7J8I/AAAAAAAAAaI/d79oWAaVA5AEeO-FO71j9KiYBsdGglKdwCHMYCw/I/15144332773302.jpg
[15144347177274.jpg]: https://lh3.googleusercontent.com/-IKQrnjsUf1A/WkRzpVDIVaI/AAAAAAAAAaM/vp0vKa1ogyYsMpa6A5ETXlCI0R_AYwdZACHMYCw/I/15144347177274.jpg
[15144347547728.jpg]: https://lh3.googleusercontent.com/-xzWmANtMFyE/WkRzpwjjD8I/AAAAAAAAAaQ/WhLXfo6A4W0SprAfT_Jd-2yT2U7Eusy5QCHMYCw/I/15144347547728.jpg
[15144348019427.jpg]: https://lh3.googleusercontent.com/-VFYiNXsqdF0/WkRzqCe31xI/AAAAAAAAAaU/0vqQz29htewEySNyFpxnLcebGOP1V0qegCHMYCw/I/15144348019427.jpg
[15144348150943.jpg]: https://lh3.googleusercontent.com/-AGP5gETpoHA/WkRzqWcMamI/AAAAAAAAAaY/yir2VyT5gJExEc0kHaRgWiOwwWGD6TXyQCHMYCw/I/15144348150943.jpg
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/11-compression.pdf
[zipfian]: http://blog.csdn.net/rockics/article/details/6544110