digoal
2022-11-28
PostgreSQL , PolarDB , DuckDB , 块级别压缩 , 轻量级压缩
https://duckdb.org/2022/10/28/lightweight-compression.html
DuckDB 支持高效的轻量级压缩,自动用于减小数据大小,而不会产生高昂的压缩和解压缩成本。
压缩算法通常会将数据集大小减少75-95%,具体取决于数据的可压缩程度。压缩不仅可以减少数据集的存储占用空间,而且通常还可以提高性能,因为需要从磁盘或通过网络连接读取的数据更少。
列存储格式,例如 DuckDB 的本机文件格式或Parquet,尤其受益于压缩。这是因为单个列中的数据通常非常相似,压缩算法可以有效地利用这一点。而以行格式存储数据会导致不同列的数据交错,从而导致较低的压缩率。
压缩遵循固定模式的数据。没有任何模式的数据,例如随机噪声,不能被压缩。正式地,数据集的可压缩性被称为它的熵。
大多数人熟悉的压缩算法都是通用压缩算法,例如zip、gzip或zstd。通用压缩算法通过查找位模式来工作。因此,它们与数据类型无关,并且可以用于任何位流。它们可用于压缩文件,但也可应用于通过套接字连接发送的任意数据。
通用压缩非常灵活且易于设置。有许多提供压缩的高质量库(例如 zstd、snappy 或 lz4)可用,它们可以应用于以任何方式存储的任何数据集。
通用压缩的缺点:
- (解)压缩通常很昂贵。虽然如果我们是从硬盘读取和写入或通过慢速互联网连接这并不重要,但当数据存储在 RAM 中时,(解)压缩的速度可能成为瓶颈。
- 黑匣子运行, 阻止系统在执行期间利用压缩算法发现的模式. (也就是无法根据数据的特征(模式)动态选择压缩算法).
- 在压缩少量数据时,压缩率会受到很大影响。要获得良好的压缩比,必须使用至少256KB的块。由于 DuckDB 在每列的基础上压缩数据,块大小将是每列必须解压缩的最小数据量。对于 256KB 的块大小,获取一行可能需要解压缩数兆字节的数据。这可能会导致查询获取少量行,例如
SELECT * FROM tbl LIMIT 5
或SELECT * FROM tbl WHERE id = 42
产生大量成本,尽管表面上看起来很便宜。
DuckDB 仅使用专门的轻量级压缩算法。由于这些算法中的每一个都在数据中的不同模式上以最佳方式工作,因此 DuckDB 的压缩框架必须首先决定使用哪种算法来存储每一列的数据。
DuckDB 的存储将表拆分为行组。这些是行组,存储在称为Column Segments120K的柱状块中。这种存储布局类似于Parquet - 但有一个重要区别:列被分成固定大小的块。做出这个设计决定是因为 DuckDB 的存储格式支持对存储格式进行就地 ACID 修改,包括删除和更新行以及添加和删除列。通过将数据划分为固定大小的块,这些块在不再需要时可以很容易地重用,并且避免了碎片化。
压缩框架在各个Column Segments的上下文中运行。它分两个阶段运作。首先分析列段中的数据。在此阶段,我们扫描段中的数据并找出该特定段的最佳压缩算法。之后进行压缩,将压缩后的数据写入磁盘的块中。
虽然这种方法需要两次遍历段内的数据,但这不会产生很大的成本,因为存储在一个段中的数据量通常很小,足以容纳在 CPU 缓存中。也可以考虑分析步骤的采样方法,但通常我们重视选择最佳压缩算法和减小文件大小,而不是略微提高压缩速度。
DuckDB 实现了几种轻量级压缩算法,我们正在向系统添加更多算法。我们将在以下部分介绍其中一些压缩算法以及它们的工作原理。
- Constant Encoding
- Run-Length Encoding (RLE)
- Bit Packing
- Frame of Reference
- Dictionary Encoding
- FSST (Fast Static Symbol Table)
- Chimp & Patas
查看表的各个column segment使用的压缩算法:
SELECT * EXCLUDE (column_path, segment_id, start, stats, persistent, block_id, block_offset, has_updates)
FROM pragma_storage_info('taxi')
USING SAMPLE 10 ROWS
ORDER BY row_group_id;
row_group_id | column_name | column_id | segment_type | count | compression |
---|---|---|---|---|---|
4 | extra | 13 | FLOAT | 65536 | Chimp |
20 | tip_amount | 15 | FLOAT | 65536 | Chimp |
26 | pickup_latitude | 6 | VALIDITY | 65536 | Constant |
46 | tolls_amount | 16 | FLOAT | 65536 | RLE |
73 | store_and_fwd_flag | 8 | VALIDITY | 65536 | Uncompressed |
96 | total_amount | 17 | VALIDITY | 65536 | Constant |
111 | total_amount | 17 | VALIDITY | 65536 | Constant |
141 | pickup_at | 1 | TIMESTAMP | 52224 | BitPacking |
201 | pickup_longitude | 5 | VALIDITY | 65536 | Constant |
209 | passenger_count | 3 | TINYINT | 65536 | BitPacking |