分类
devops

run-end-encoded

Run-End Encoding(REE,游程结束编码)是一种数据压缩和存储格式,主要用于列式存储(如 Apache Arrow、Parquet 等)。它是传统游程编码(RLE,Run-Length Encoding)的一种变体。
它的核心思想是通过记录“数据值”以及该值连续出现时的结束位置(索引),而不是记录重复的次数,从而节省存储空间并提升查询性能。

核心工作原理

假设有一组包含大量连续重复元素的数组(共 8 个元素,索引从 0 开始):
原始数组:[“A”, “A”, “A”, “B”, “B”, “C”, “C”, “C”]
– 1. 传统 RLE(游程编码):记录“值”和“连续重复的长度”。
• Values(值):[“A”, “B”, “C”]
• Lengths(长度):[3, 2, 3]
– 2. REE(游程结束编码):记录“值”和该段重复数据结束时的累积索引位置(Run-End)。
• Values(值):[“A”, “B”, “C”]
• Run-Ends(结束位置):[3, 5, 8](表示索引 0~2 是 A,3~4 是 B,5~7 是 C)

为什么使用 Run-End Encoding?

相比于传统的 RLE,REE 在现代大数据处理和向量化计算中具有显著优势:
– 支持快速随机访问:在传统 RLE 中,要查找第 i 个元素,必须从头累加前面的所有长度。而在 REE 中,由于 Run-Ends 数组是严格单调递增的,系统可以直接使用二分查找在 (O(\log N)) 的时间内定位到任意索引对应的值。
– 无需解压即可计算:在执行过滤(Filter)或聚合(Aggregate)操作时,计算引擎可以直接在压缩后的 Values 和 Run-Ends 数组上运行,大幅减少内存带宽消耗。
– 极高的压缩率:对于存在大量连续重复值的数据(例如按某列排序后的表、状态标志位、时间序列中的恒定指标等),REE 可以将存储空间压缩几个数量级。

常见应用场景

  • Apache Arrow:Arrow 内存格式原生支持 Run-End Encoded 数组类型,用于加速内存中的数据分析与零拷贝传输。
  • 列式数据库与文件格式:在 ClickHouse、DuckDB 或 Parquet 的底层编码优化中,常利用类似机制处理低基数且连续分布的数据列。
    如果你想进一步了解,我可以为你提供:
  • 代码实现示例(如使用 Python/PyArrow 创建和操作 REE 数组)