CMU15-445 Lecture #04: Storage Models and Compression[译]
数据库工作负载(Database Workloads)
OLTP: 在线事务处理
OLTP 工作负载的特点是快速、短暂的操作，重复的操作和简单的查询，每次仅对单个实体进行操作。OLTP 工作负载通常处理的写操作多于读操作。一个例子是亚马逊网店。用户可以将物品添加到购物车并购买，但这些操作仅影响其账户。
OLAP: 在线分析处理
OLAP 工作负载的特点是长时间运行的复杂查询和对数据库大部分内容的读取。在 OLAP 工作负载中，数据库系统通常从 OLTP 侧收集的现有数据进行分析和派生新数据。 一个例子是亚马逊计算在匹兹堡下雨天最畅销的商品。
HTAP: 混合事务+分析处理
一种新型的工作负载（最近变得流行）是 HTAP，其中 OLTP 和 OLAP 工作负载同时出现在同一个数据库中。
存储模型(Storage Models)
有不同的方法来将元组存储在页中。到目前为止，我们假定采用了 n 元存储模型。
N 元存储模型（NSM）
在 n 元存储模型中，DBMS 将单个元组的所有属性连续地存储在一个页面中。这种方法非常适用于 OLTP 工作负载，其中请求以插入为主，事务往往只操作单个实体。这种方法非常理想，因为只需要一次获取操作就能获取单个元组的所有属性。
优点：
- 快速的插入、更新和删除。
- 适用于需要整个元组的查询。
缺点：
- 扫描表的大部分或子集时效率低下。
分解存储模型（DSM）
在分解存储模型中，DBMS 将所有元组的单个属性（列）连续地存储在一个数据块中。因此，它也被称为“列存储”。这种模型非常适用于 OLAP 工作负载，其中有许多只读查询，这些查询在表的子集上执行大规模扫描。
优点：
- 减少了 I/O 浪费的数量，因为 DBMS 仅读取查询所需的数据。
- 更好的查询处理和数据压缩。
缺点：
- 对于点查询、插入、更新和删除速度较慢，因为需要元组拆分/拼接。
在使用列存储时，将元组重新组合有两种常见方法：最常用的方法是固定长度偏移量。在这种方法中，给定列中的值将属于与同一偏移量处的另一个列中的值相同的元组。因此，列中的每个值都必须具有相同的长度。
较少使用的方法是使用嵌入式元组 ID。在这种方法中，对于列中的每个属性，DBMS 都会将一个元组 ID（例如，主键）与其一起存储。然后，系统还会存储一个映射，告诉它如何跳转到具有该 ID 的每个属性。注意，该方法具有大量存储开销，因为它需要为每个属性条目存储一个元组 ID。
数据压缩(Data Compression)
压缩在基于磁盘的数据库管理系统中广泛使用，因为磁盘 I/O（几乎）总是主要的瓶颈。在具有只读分析工作负载的系统中，压缩尤其受欢迎。如果事先压缩了元组，DBMS 可以获取更多有用的元组，但代价是更大的计算开销用于压缩和解压缩。
内存中的 DBMS 更为复杂，因为它们不必从磁盘获取数据以执行查询。内存比磁盘快得多，但压缩数据库会降低 DRAM 要求和处理速度。它们必须在速度与压缩比之间取得平衡。压缩数据库降低 DRAM 需求，可能会在查询执行期间降低 CPU 成本。
如果数据集完全是随机比特，则无法执行压缩。然而，真实数据集具有可压缩的关键属性:
- 属性值高度倾斜的分布（例如，布朗语料库的 Zipfian 分布）。
- 同一元组的属性之间高度相关（例如，邮政编码到城市，订单日期到发货日期）。
考虑到这些，我们希望数据库压缩方案具有以下特点:
- 必须产生固定长度的值。唯一的例外是存储在单独池中的可变长度数据。这是因为 DBMS 应遵循字对齐，并能够使用偏移量访问数据。
- 允许 DBMS 尽可能地推迟解压缩，在查询执行期间进行后期实现。
- 必须是无损方案，因为人们不喜欢丢失数据。任何形式的有损压缩必须在应用程序层面执行。
压缩粒度(Compression Granularity)
我们希望压缩的数据类型极大地影响可以使用哪些压缩方案。有四个压缩粒度级别:
- 块级：压缩同一表的一个块的元组。
- 元组级：压缩整个元组的内容（仅适用于 NSM）。
- 属性级：压缩一个元组内的单个属性值。可以针对同一元组的多个属性进行操作。
- 列级：压缩存储在多个元组中的一个或多个属性的多个值（仅适用于 DSM）。这允许使用更复杂的压缩方案。
朴素压缩(Naive Compression)
DBMS 使用通用算法（如 gzip、LZO、LZ4、Snappy、Brotli、Oracle OZIP、Zstd）压缩数据。尽管 DBMS 可以使用多种压缩算法，但工程师通常选择提供更快的压缩/解压缩速度，而以较低的压缩比作为代价的算法。
使用朴素压缩的一个例子是MySQL InnoDB。DBMS 压缩磁盘页，将它们填充到 2KB 的幂次方，并将它们存储到缓冲池中。然而，每次 DBMS 尝试读取/修改数据时，缓冲池中的压缩数据必须首先解压缩。
由于访问数据需要解压缩压缩数据，这限制了压缩方案的范围。如果目标是将整个表压缩成一个巨大的块，则使用朴素压缩方案是不可能的，因为每次访问都需要对整个表进行压缩/解压缩。因此，MySQL 将表分成较小的块，因为压缩范围受限。
另一个问题是这些朴素方案也不考虑数据的高级含义或语义。算法不考虑数据的结构和查询计划访问数据的方式。因此，这消除了利用后期物化的机会，因为 DBMS 无法确定何时可以延迟解压缩数据。
列压缩(Column Compression)
游程长度编码（Run-Length Encoding，简称 RLE）
RLE 将单个列中连续相同值的“游程”压缩成三元组：
- 属性值
- 列段中游程的起始位置
- 游程中元素的数量
DBMS 应事先智能地对列进行排序以最大化压缩机会。这会聚类重复属性，从而增加压缩比。请注意，RLE 的有效性很大程度上取决于底层数据特征（例如每个数据中属性的数量和频率）。
位包编码（Bit-Packing Encoding）
当属性的所有值都小于声明的最大大小时，可以使用更少的位数来存储它们。
大多数编码（Mostly Encoding）
位包变体，使用特殊标记指示一个值是否超过最大大小，然后维护查找表来存储这些值。
位图编码（Bitmap Encoding）
DBMS 为特定属性的每个唯一值存储一个单独的位图，其中向量中的偏移量对应于元组。位图中的第 i 个位置对应于表中的第 i 个元组，表示该值是否存在。通常将位图分成块，以避免分配大块连续内存。
如果值的基数很低，这种方法只有在实际上是可行的，因为位图的大小与属性值的基数成线性比例。如果值的基数很高，则位图可能比原始数据集更大。
增量编码（Delta Encoding）
不是存储精确值，而是记录在同一列中相互跟随的值之间的差异。基础值可以存储在行内或单独的查找表中。我们还可以对存储的增量使用 RLE 以获得更好的压缩比。 增量编码是一种类型的增量编码，其中记录常见的前缀或后缀及其长度，以避免重复。这对于已排序的数据效果最佳。
字典压缩（Dictionary Compression）
最常见的数据库压缩方案是字典编码。DBMS 会用较小的代码替换值中的频繁模式。然后它只存储这些代码和一个数据结构（即字典），该字典将这些代码映射到它们的原始值。字典压缩方案需要支持快速编码/解码，以及范围查询。
编码和解码：字典需要决定如何编码（将未压缩的值转换为其压缩形式）和解码（将压缩的值转换回其原始形式）数据。因此，不可能使用哈希函数。 编码的值还需要支持与原始值相同的排序顺序（即保序编码）。这确保在压缩数据上运行的压缩查询返回与在原始数据上运行的未压缩查询一致的结果。这种保序属性允许直接对代码执行操作。
注意：上述压缩方案最适用于读取密集型工作负载，并且可能需要对写入提供额外的支持。