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