本文翻译自LanceDB官网Blog
作者：Weston Pace（Columnar File Readers in Depth: Compression Transparency）
传统观点认为压缩和随机访问难以兼容。然而，数据压缩有多种方式，其中部分方式能更好地支持随机访问。
研究何时、为何以及如何使用不同压缩算法成为了一项有趣的挑战。在开发2.1版本的过程中，我们创建了若干术语来区分不同的压缩方法。
背景
Lance的压缩作用于单个列的大数据块。当数据批次到达时，我们将其拆分为独立列，每列独立缓存数据。当某列缓存达到阈值时触发压缩流程。
我们没有row group概念，因此各列可独立累积，某列的压缩不会连带触发其他列的压缩。这意味着压缩阶段处理的是单个列的大数据块（通常默认8MB+）。
每列持续累积数据，直至达到创建数据块所需的体量（8MB+）
透明压缩 vs. 非透明压缩
影响随机访问的关键区别在于编码是否为非透明压缩。非透明压缩生成的数据块需要完全解码才能访问单个值。而透明压缩允许单独解压单个值，无需处理块内其他值（需说明这些术语是Lance内部定义，非行业标准）。
以差分编码（Delta Encoding）为例：该技术仅存储相邻值的差值。虽然差值分布范围通常更小（更易压缩），但它属于非透明压缩。
要获取第6个值，需解码前5个差值（或许可以称这为半透明，因为无需解码后续的值，但这种区分对我们并没有实用价值）。
其他非透明编码包括GZIP/LZ4/SNAPPY/ZLIB等"后向引用"类算法。这些算法通过引用先前出现的相同序列进行编码，若缺失历史数据则无法解析引用。
差分编码+位压缩（bit packing）在此场景表现出色（16字节→3字节），然而值信息会"扩散"到大部分数据中，通常需要加载整个块来解压单个值。
透明编码的典型案例是位压缩（bit packing）：通过舍弃未使用的高位来压缩整型数据。例如INT32数组[0,10,5,17,12,3]，每个值只需5位存储空间，节约下27位。
这种编码具有透明性（已知压缩位宽时），因为第6个值的位置可通过bits[bit_width*5..bit_width*6]直接定位。这种特性能显著提升随机访问效率。
虽然单独使用位压缩效果略逊（4字节 vs 3字节），但其透明压缩的优势明显：访问单个值只需读取对应字节。
变长压缩能否透明？
列表/字符串等变长结构更为复杂。即使未压缩，通常也需要多次查询来获取值：先查询值的大小，再获取值本身。
例如，字符串数组 ["compression", "is", "fun"] 在 Arrow 中实际需要两个数据缓冲区：偏移量数组和值数组。访问单个值需进行两次读取操作。
变长结构访问单个值需要两次读取
根据我们的定义，这种方式仍属随机访问。因为访问单个值不需要加载整个数据块，所以是存在透明变长编码的。
例如FSST压缩通过256字节符号表实现部分字典编码，只要持有符号表（这是元数据，后面讨论），即可独立解码任意子串。这意味着FSST是透明编码。
使用符号表透明压缩字符串数组
更完整的定义体现在我们的traits中：
透明编码必须是空布局、定宽布局或变宽布局，且元素数量与原数组一致。可包含一或多个元数据缓冲区。解码时只要持有元数据，就能独立解码出任意元素。
目前仅支持空、定宽、变宽这三种布局，是因为可以把这些布局中的一个偏移量转换为确定的范围。未来可能扩展更多布局类型。
后续议题：我们获得一个8MB的数据块，并不意味着必须将其整体压缩。可将其拆分为更小的不透明块。
1. 小分块是否仍能实现良好压缩？
2. 这是否意味着不透明编码仍可用于随机访问？
3. 如何定位需访问的特定分块？
这些都是合理的问题，我们将在后续文章中探讨。
神秘的“元数据”
我们的定义中提到“元数据”，这是此前尚未讨论的概念，但在随机访问中至关重要。为便于理解，让我们回顾下位压缩（bit packing）。
前文曾指出只要知道压缩的位宽，就能透明解码数据。如何获知位宽呢？答案是将它存入元数据。这意味着朴素的位压缩算法有1 字节的元数据。
现在考虑另一种位压缩方案。假设我们需编码至少 8MB 的整型数据，若数组中存在一个特大异常值，该离群点将彻底破坏压缩效果。解决方案有多种（例如用未使用值替换离群点、将其移至元数据等），但最简便的是分块压缩数据。
为简化说明，假设将数据分为八个 1MB 的数据块压缩（实际场景中每 1024 个值分为一个数据块更常见，但本文不作深究）。
包含异常值的块压缩效果不佳，但其余块压缩良好。由于每个压缩块可能有不同位宽，元数据会从 1 字节增至 8 字节。
这是否合理？答案取决于具体场景，我们将在后续文章中探讨。
通过分块处理，我们可以降低离群点的影响。
这是适用于大多数压缩算法的通用技术，但代价是我们的位宽元数据变得更庞大。
我们甚至可以通过非透明压缩来完全消除元数据。唯一需要做的，是将块的压缩位宽直接内置到压缩数据中。
事实上，这是当今最常用的技术，因为随机访问通常不是关注重点。
综合以上，我们可以看到单一技术（位压缩）可通过三种方式实现，并具备不同特性（透明 vs. 非透明、携带元数据）。
位压缩的三种不同的实现方式
在透明/非透明压缩特性与元数据量大小之间的权衡
剥离空值（Null Stripped）
vs. 填充空值 （Null Filled）
下一分类涉及空值处理方式：填充空值或剥离空值。
此策略基本独立于当前使用的压缩算法。剥离空值会在压缩前移除空值，填充空值则用占位符替代空值。
占位值可为任意数据，特定压缩算法可能有特殊偏好（例如位压缩中，应避免在空位插入极大异常值）。
两种处理方式对数组[0, NULL, NULL, 3, NULL, NULL, NULL, NULL]的不同表示
我们还可以看到，剥离空值会使压缩变得不透明。
在上面的示例中，我们仍然有固定宽度的布局，但值数量不再正确。我们必须遍历有效位图（validity bitmap）才能找到值缓冲区（values）的偏移量。
这意味着在解码任何单个值之前，我们都需要整个有效位图。
挑战练习：假设我们有一个大部分为空值的数组，若将有效位图声明为元数据以提升处理速度会怎样？毕竟它可能只是一个压缩位图，规模应该不会过大。这种做法是否算透明？是否符合前文的定义？这是优是劣？多大规模才算过大？
垃圾数据通常体积不大。定长类型往往很小。变长类型不需要使用占位符，仅需一个垃圾数据的偏移量（实际上它必须等于前一个偏移量）。
这一规则有两个例外：
1. 向量嵌入（vector embeddings）：因其同时具备定长和大尺寸特性（通常为3-6KB）
2. 大部分为空的数组：此情况较为明显
实践对比：Parquet vs Arrow
在 Parquet 中，它将column chunk划分为多个page（类似于上文的分块位压缩示例），并假设所有压缩都是非透明的。
因此，Parquet 能够在压缩前剥离空值。然而，当我们在 Parquet 列中执行随机访问时，必须始终读取整个page。
在Arrow的内存格式中，实际压缩程度有限（IPC格式支持部分非透明压缩）。然而Arrow的核心要求是保证尽量快地随机访问速度，其所有布局均为透明设计。
Arrow不会移除空值，且必须用占位符填充空值。不过对于大多数情况，我们都能在O(1)的读操作中访问单个值。
附加题：当前存在唯一例外情况，你知道是什么吗？
结论：如何选择？
我从事Lance文件格式的开发工作，该格式致力于实现快速全扫描与随机访问性能。您可能认为我会主张全面采用透明压缩并最小化元数据，但遗憾的是实际情况更为复杂。
有时我们发现一些可以使用非透明压缩的场景，有时更多的元数据反而有益。
在真正评估前，我们还需探讨更多概念。虽然以未明确解答问题作为博客收尾略显不妥，但🤷，See you next time，再见。
推荐阅读
