[DB] Database Compression

Database Compression

数据库压缩是一种优化技术，用于减少存储空间和提高查询性能。数据库压缩的目的是在不丢失任何数据的情况下，以更高效的方式存储数据，并尽可能延迟数据解压的过程以提高查询效率。以下是数据库压缩的三个主要目标和相关知识点：

1. 目标 #1：生成定长值

固定长度的值：压缩算法应尽量将数据压缩成固定长度的值。这有助于系统更高效地存储和管理压缩数据，因为固定长度的数据可以在存储空间中被更简单地排列和索引。
- 例外情况：对于可变长度数据（如 VARCHAR），系统可以将这些值存储在单独的池中，而不是直接存储在主数据块中。这种设计能够处理可变长度数据的复杂性，同时避免占用主数据存储的空间。
- 优点：定长值简化了存储管理和数据访问，因为存储结构不需要动态调整长度，可以在固定的位置快速找到需要的数据。

2. 目标 #2：尽可能延迟解压缩

延迟解压缩（Late Materialization）：理想情况下，在查询执行过程中应尽可能推迟数据的解压缩，直到绝对需要的时候。延迟解压缩可以减少处理开销，因为系统只在必要时解压缩数据，从而避免不必要的计算。
- 作用：通过尽可能晚地解压数据，查询处理器可以在压缩状态下处理更多数据，这有助于减少内存和计算的使用，同时提高查询性能。
- 实际场景：例如，在一个分析性查询中，如果只需要查询某些列，系统可以在解压缩之前使用索引或其他优化方法快速筛选掉无关的行，避免不必要的解压缩操作。

3. 目标 #3：必须是无损压缩

无损压缩：数据库压缩必须是无损的，也就是说，压缩后的数据在解压缩时应完全恢复为原始数据，不能有任何信息丢失。这对于数据库系统至关重要，因为它们通常需要处理金融、医疗或法律等领域的敏感和关键数据。
- 无损压缩的例子：常见的无损压缩算法包括 RLE（Run-Length Encoding）、字典压缩（Dictionary Compression）和 位图压缩（Bitmap Compression）。这些算法在压缩时不会丢失任何信息，解压后可以得到与压缩前完全相同的数据。

常用的压缩技术：

RLE (Run-Length Encoding)：这种方法通过将重复的连续数据（如相同的数字或字符）压缩成表示重复次数的标记来减少数据的大小。例如，将 AAAABBB 压缩为 4A3B。
字典压缩：通过将频繁出现的值存储在字典中，并用字典中的索引来代替原始值，从而减少存储的大小。字典压缩特别适用于具有大量重复值的数据列（如分类字段）。
位图压缩：位图压缩常用于压缩布尔值或低基数的分类数据。它通过使用位图来表示数据的存在或缺失，减少了存储空间。

Lossless v.s. Lossy Compression（无损压缩与有损压缩）中文解释及相关知识点

数据库压缩技术可以分为无损压缩和有损压缩两大类，但在数据库管理系统 (DBMS) 中，压缩必须是无损的，以确保数据的完整性和准确性。

1. 无损压缩（Lossless Compression）

定义：无损压缩是一种压缩方法，在压缩和解压缩过程中不会丢失任何信息。解压缩后的数据与原始数据完全相同，所有的信息都能被精确恢复。
在数据库中的应用：由于数据库需要确保数据的准确性和完整性，因此 DBMS 使用的压缩技术必须是无损的。在数据库系统中，丢失数据可能会导致严重的错误或数据不一致，特别是在财务、医疗等对数据精度要求极高的领域。
- 原因：用户依赖数据库中的数据来进行关键决策、分析或操作，因此丢失任何数据都会对业务或系统的正确性产生负面影响。
常见无损压缩技术：
- 字典压缩（Dictionary Compression）
- RLE 压缩（Run-Length Encoding）
- 霍夫曼编码（Huffman Encoding）
- 位图压缩（Bitmap Compression）

2. 有损压缩（Lossy Compression）

定义：有损压缩是一种在压缩过程中丢失部分数据的方法。这种压缩技术通常用于图像、音频或视频等场景，因为人类感官系统对这些类型的数据较为宽容，允许某些细节的丢失。
- 特点：压缩后的数据在解压缩时不能完全恢复为原始数据。有损压缩可以在较大幅度减少数据量的同时保持较高的感知质量（如图片的视觉质量、声音的听觉质量等）。
在数据库中的应用：
- 禁止直接使用有损压缩：在数据库管理系统中，不允许直接使用有损压缩，因为它会导致数据的丢失，这在精确数据处理的场景下是不可接受的。
- 应用层上的有损压缩：如果某些数据允许损失细节（例如图像、视频或音频数据），则有损压缩可以在应用层进行处理，而不在数据库核心层进行。这意味着数据库本身仍然会存储原始或无损压缩的数据，而有损压缩操作由应用程序负责完成。
应用层的有损压缩示例：
- 图像或视频文件的压缩，例如 JPEG（图像）或 MP3（音频），这些格式允许一定程度的细节丢失，以换取较小的文件尺寸和更快的传输速度。这类压缩在数据库之外进行处理，数据库只负责存储文件，而不执行有损压缩。

Compression Granularity（压缩粒度）中文解释及相关知识点

在数据库压缩中，压缩粒度决定了系统在数据存储时进行压缩的单位。根据不同的粒度，压缩可以发生在多个层次，从单个列到整个块。以下是四种常见的压缩粒度选择：

1. Choice #1: Block-level Compression（块级压缩）

定义：在块级压缩中，系统会对属于同一个表的一组元组（tuples）或行进行压缩。块级别通常指存储数据的物理页面或数据块。
特点：将一整个物理块的数据进行压缩，块可能包含一个或多个完整的元组。
- 优势：压缩整个块可以减少 I/O 操作，因为系统在查询时通常会读取整个块，而压缩可以减少传输的数据量。
- 适用场景：块级压缩适合于对完整块的访问较多的工作负载，如扫描大范围的数据集。

2. Choice #2: Tuple-level Compression（元组级压缩）

定义：在元组级压缩中，整个元组（即一行数据）的内容会被压缩。这通常适用于行存储模型（如 NSM）。
特点：每个元组作为一个单元进行压缩，在解压时可以恢复该元组的所有属性。
- 优势：适用于访问整行数据的场景，特别是在事务处理（OLTP）工作负载中，频繁的插入和更新操作使得元组级别的压缩能保持较好的数据局部性。
- 劣势：如果查询只需要访问某些列，压缩和解压整行的数据会带来不必要的开销。
- 适用场景：行存储模型中的 OLTP 系统，因为这些系统通常处理单个元组的插入、更新和查询。

3. Choice #3: Attribute-level Compression（属性级压缩）

定义：属性级压缩指的是对单个元组中的某个属性（列）进行压缩。它可以处理一个元组的多个属性，但每个属性会被单独压缩。
- 示例：当某个元组的某个属性（例如，一个较长的字符串）占用了较大的空间时，系统可以对该属性进行压缩，从而减少存储溢出（overflow）情况。
特点：属性级压缩通常用于处理某些需要额外存储的可变长度字段（如字符串、二进制数据等），也可以用于压缩多个属性以减少存储空间。
- 优势：可以选择性地压缩占用空间大的属性，而无需压缩整个元组，提供了更灵活的压缩控制。
- 适用场景：适合于含有可变长度字段的场景，尤其是需要处理溢出存储的情况下。

4. Choice #4: Column-level Compression（列级压缩）

定义：列级压缩专门用于列存储模型（DSM），它对同一列的多个值进行压缩，即多个元组的同一属性会被批量压缩。
特点：在 DSM 模型中，数据是按列存储的，因此列级压缩针对列中的值进行压缩。这种方式特别适合于分析型工作负载，因为查询往往只涉及部分列。
- 优势：
  - 高效压缩：列中的数据类型和分布通常是相似的，这使得列级压缩非常高效，压缩率高。
  - 查询效率高：系统只需读取和解压需要的列，不必处理整行数据，从而减少了 I/O 开销。
- 劣势：在需要频繁插入或更新数据时，列级压缩可能会导致性能下降，因为每次操作需要在多个列中进行修改。
- 适用场景：适合列存储模型的 OLAP 系统，尤其是需要对大量数据进行扫描和分析时。

各压缩粒度的对比：

块级压缩：压缩整个物理块，适用于大数据扫描和整体查询场景。
元组级压缩：压缩整行，适用于行存储模型中的事务处理场景。
属性级压缩：对单个属性进行压缩，适用于有可变长度数据的情况，特别是需要处理数据溢出的场景。
列级压缩：在列存储模型中压缩同一列的多个值，适用于分析型工作负载和列存储系统。

Naïve Compression（简单压缩）中文解释及相关知识点

Naïve Compression 指的是使用通用的压缩算法对数据进行压缩，这种压缩方式的范围仅基于输入的数据本身。与数据库中特定场景优化的压缩技术不同，简单压缩不考虑数据的上下文，而是应用在任何数据类型上。以下是简单压缩的特点及相关考虑因素：

1. Naïve Compression 概述

定义：简单压缩使用通用压缩算法对数据进行压缩。与数据库中按列或按属性等细粒度优化的压缩方法不同，简单压缩的目标是对提供的输入数据进行直接压缩，不考虑数据的结构或上下文。
- 这些算法通常适用于多种类型的数据，可以对数据进行快速压缩和解压缩。

2. 常见的通用压缩算法

LZO (1996)：一种快速压缩算法，设计用于高效的实时压缩，具有快速的解压缩速度，广泛应用于嵌入式系统和传输需要。
LZ4 (2011)：以极高的压缩和解压缩速度著称的压缩算法，常用于性能敏感的应用场景。尽管压缩率不是最优，但它的速度使其非常受欢迎。
Snappy (2011)：由 Google 开发的压缩算法，平衡了较快的压缩/解压缩速度和合理的压缩率。被广泛用于大数据处理系统中，如 Hadoop、Cassandra 等。
Oracle OZIP (2014)：Oracle 专有的压缩算法，用于优化其数据库产品的压缩性能，专注于高效的压缩和解压缩操作。
Zstd (2015)：一种较新的压缩算法，结合了高压缩率和高速解压缩。Zstd 被认为是 Zlib 和 LZ4 之间的权衡，能够提供较高的压缩率，同时保持快速的解压缩速度。

3. 简单压缩的考虑因素

在使用通用的简单压缩算法时，主要需要考虑以下两个方面：

计算开销（Computational Overhead）
- 计算复杂度：压缩和解压缩操作会增加 CPU 的负担。在某些情况下，压缩操作的计算开销可能会抵消压缩带来的存储或传输节省。例如，当系统需要高吞吐量时，复杂的压缩操作可能会成为性能瓶颈。
- 资源消耗：简单压缩算法通常依赖 CPU 的计算资源来执行压缩和解压操作，因此在选择算法时，需要权衡其对系统资源的需求。
压缩速度与解压缩速度（Compress vs. Decompress Speed）
- 压缩速度：一些压缩算法，如 LZ4 和 Snappy，虽然压缩率可能不如其他算法高，但它们的压缩速度极快，适合实时性要求较高的场景。
- 解压缩速度：某些场景中，解压缩速度比压缩速度更重要。例如，在查询过程中，快速解压数据可以提高查询响应时间。因此，选择压缩算法时，除了压缩速度，还应考虑解压缩的效率。
- 压缩率：虽然提高压缩率可以节省更多存储空间，但这通常会以牺牲压缩或解压缩速度为代价。Zstd 提供了一种高效的压缩率与速度平衡，是一种不错的选择。

4. 适用场景

实时数据传输：如视频流、网络传输中，通常需要较快的压缩和解压缩速度，LZ4 和 Snappy 这样的算法表现优异。
大数据存储：如 Hadoop、Cassandra 这类大数据处理系统，通常会使用 Snappy 进行数据压缩，以提高数据的存储和传输效率。
嵌入式系统：由于资源受限，嵌入式系统中常使用 LZO 这样的压缩算法，提供实时性和高效的性能。

Naïve Compression 的局限性与理想状态

1. Naïve Compression 的局限性

解压缩操作的必要性：在 Naïve Compression（简单压缩）中，DBMS 必须在读取或修改数据之前先解压缩数据。这意味着每次查询或更新数据时，都需要执行额外的解压缩步骤，增加了 CPU 和 I/O 的负担。
- 限制压缩方案的作用范围：由于解压缩是查询或修改数据的前置条件，这就限制了压缩的作用范围。在高频查询或数据处理场景下，解压缩的开销会影响系统性能，尤其是当大量数据需要被频繁读取和更新时。
数据语义的忽略：Naïve Compression 通常使用通用的压缩算法（如 LZ4、Snappy 等），这些算法不考虑数据的高层次语义或含义。也就是说，压缩算法仅关注字节层面的压缩，而不理解数据的结构或意义。
- 没有针对性优化：例如，某些列中可能存在重复数据或数据的分布特性很容易被优化，但 Naïve Compression 并不会根据这些特性来优化压缩方式。这种缺乏上下文感知的压缩策略在复杂数据库系统中显得不够高效。

2. 理想的压缩方案

压缩数据的直接操作：理想情况下，我们希望数据库管理系统（DBMS）能够直接在压缩状态下操作数据，而无需先进行解压缩。这种技术被称为压缩感知操作，即 DBMS 在处理查询、插入或更新时，能够理解并利用压缩数据的结构进行高效操作。
- 优点：通过跳过解压缩步骤，DBMS 可以减少处理时间和资源开销，提高系统的整体性能，尤其是在处理大规模数据时。

Columnar Compression（列式压缩）中文解释及相关知识点

列式存储（如 DSM 模型）非常适合采用压缩技术，因为同一列的数据类型相同，值的分布通常比较有规律，这为压缩提供了优化空间。常见的列式压缩方法包括运行长度编码、位打包编码、位图编码、增量编码和字典编码。这些方法各有优点，适合不同的数据分布和查询场景。

1. Run-length Encoding（运行长度编码，RLE）

定义：RLE 是一种非常有效的压缩方法，适用于有大量重复值的列。它通过将连续重复的值表示为一个值和其重复的次数来减少数据存储量。
- 示例：如果某列有值 A, A, A, B, B, C, C, C, C，RLE 会将其压缩为 (A, 3), (B, 2), (C, 4)。
优点：
- 对于高度重复的数据，如分类数据，RLE 压缩率极高。
- 减少了数据的冗余，可以显著节省存储空间。
缺点：
- 如果数据变化频繁或没有足够的重复值，RLE 的效果会不明显，甚至可能增加开销。
适用场景：适合于具有高重复值的列，例如布尔值、分类字段等。

2. Bit-Packing Encoding（位打包编码）

定义：位打包编码是一种基于位数的压缩技术。它通过将数据值用尽可能少的位数表示，从而减少存储空间。
- 示例：如果某列的值范围在 0 到 7 之间（可以用 3 位二进制表示），则位打包编码会用 3 位表示每个值，而不是用标准的 8 位或 32 位整数。
优点：
- 适用于值域较小的列，可以显著减少存储占用。
缺点：
- 对于值域较大的数据，压缩效果不明显，甚至增加复杂性。
适用场景：适用于值域范围较小的数据，如分类值或布尔值。

3. Bitmap Encoding（位图编码）

定义：位图编码为每个唯一值创建一个位图，每个位图中的位置表示该值在数据集中的出现位置。每一位代表对应行的值是否匹配某个唯一值。
- 示例：假设某列的值为 {A, B, A, A, C}，位图编码将会为每个唯一值创建一个位图：
  - A: 10110
  - B: 01000
  - C: 00001
优点：
- 对于分类值较少的列（例如，性别、状态等），位图编码可以显著提高查询效率，尤其是对于范围查询或布尔操作。
缺点：
- 如果唯一值较多，位图编码的空间开销会迅速增加。
适用场景：适用于分类值较少且重复度较高的列，常见于布尔字段或低基数分类字段。

4. Delta Encoding（增量编码）

定义：增量编码适用于数值连续增长的数据，记录每个值与前一个值之间的差值（delta），而不是存储实际值。
- 示例：假设某列有值 100, 105, 110, 115，增量编码将会将其表示为 100, 5, 5, 5。
优点：
- 适用于递增或递减的数值数据，压缩率较高。
缺点：
- 对于变化不规律的数据，增量编码效果较差。
适用场景：适合数值型的时间序列数据或其他按顺序排列的数据，如时间戳、编号等。

5. Dictionary Encoding（字典编码）

定义：字典编码通过为列中的每个唯一值创建一个字典，并使用字典中的索引来替代原始值，从而减少存储空间。
- 示例：如果某列有值 {A, B, A, C, B}，字典编码会将其表示为：
  - 字典：{A: 1, B: 2, C: 3}
  - 编码后的值：1, 2, 1, 3, 2
优点：
- 对于有大量重复值的列，字典编码能够显著减少存储空间，且查询时通过字典查找非常高效。
缺点：
- 对于唯一值较多的列，字典表可能变得很大，导致存储空间的节省不明显。
适用场景：适合于重复值较多的列，如分类字段或低基数数据。