- 数据库压缩
- 真实世界的数据特征
- 观察
- 本节话题
- 数据库压缩的目的
- 有损压缩和无损压缩的对比
- 压缩颗粒度
- 选择 #1: 块级
- 选择 #2: 元组级
- 选择 #3: 属性级
- 选择 #4: 列级
- NAÏVE 压缩
- 考虑因素
- 举例：MYSQL INNODB 压缩
- 列压缩
- 1. 游程编码
- 2. 字典编码
- 3. 位图编码
- 4. 增量编码 Delta Encoding
- 5. 比特打包 Bit-Packing
- 游程编码
- 定义
- 举例
- 字典压缩
- 定义
- 选择 #1: 一次性的 All-At-Once
- 选择 #2：递增式 Incremental
- 字典的范围
- 选择 #1: 块级字典
- 选择 #2: 表级字典
- 选择 #3: 多表字典
- 编码 / 解码
- 保留顺序的编码
- 字典数据结构
- 选择 #1：数组
数据库压缩
数据库压缩
真实世界的数据特征
数据集往往具有 高度偏斜 的属性值分布。
•
例子： 布朗语料库的 Zipfian 分布。
数据集倾向于在同一元组的属性之间具有 高相关性。
•
例子： Zip Code 与城市，订单日期与发货日期
观察
I/O 是传统上查询执行过程中的主要瓶颈。如果 DBMS 仍然需要读取数据，我们需要确保它能最大限度地从数据中提取有用的信息。
关键的权衡是速度与压缩率。
•
压缩数据可以减少 DRAM 的需求和处理量。
本节话题
•
背景介绍
•
Naïve 的页面压缩
•
Native 列式压缩
•
中间数据
数据库压缩的目的
减少数据库物理表示的大小，以增加每单位计算或 I/O 的访问和处理的数值数量。
•
目标1：必须产生 固定长度 的值。
•
目标2：必须是一个 无损 的方案。
•
目标3：理想情况下，在查询执行过程中尽可能地 推迟解压时间。
有损压缩和无损压缩的对比
当DBMS使用压缩时，它总是无损的，因为人们不喜欢丢失数据。
任何种类的 有损压缩都必须在应用层面进行。
在查询执行过程中，读取少于整个数据集的数据，有些类似压缩。
•
近似查询处理
如果我们想在我们的 DBMS 中添加压缩功能，我们必须问自己的第一个问题是，什么是我们想要压缩的东西？
这就决定了我们可以使用哪些压缩方案。
压缩颗粒度