DeepSeek总结的PAX：PostgreSQL存储引擎

原文地址https://mydbanotebook.org/posts/pax-the-storage-engine-strikes-back/PAX存储引擎的反击2026年4月6日 ·目录Minipage 模式定长属性 (F-minipage)变长属性 (V-minipage)插入、删除、更新插入删除更新MVCC 问题一个可能的方向元数据 Minipage实用的缓解措施Fillfactor 和 Toast我们该何去何从参考文献感谢 Boris Novikov是他最初指引我关注 PAX 方向并随后进行了许多富有洞见的技术讨论。我感激他付出的所有时间以及我们之间进行过并仍在继续的精彩对话。要深入了解 PAX 的机制我强烈推荐阅读我之前的文章《PAX你一直在寻找的缓存性能》。PAX 在纸面上看起来很优雅minipage、缓存局部性、在 8KB 页内的列式访问。但一旦你开始考虑这如何能在 Postgres 中实际工作复杂性就迅速涌现NULL 值、变长类型、MVCC、边界移动。让我们一一探讨。Minipage 模式在 PAX 中一个页面被划分为多个 minipage。下面介绍它们如何根据数据类型而有所不同。Postgres 拥有庞大的类型库但它们总是归入两种存储类别。定长属性 (F-minipage)这适用于所有行大小都恒定的类型。大多数 Postgres 类型都属于这一类任何数值类型、布尔型、日期/时间系列、几何类型、网络地址……关于 F-minipage 的关键点在于我们根本不存储 NULL 值。完全没有占位符。没有空洞。只有实际的数据紧密排列。那么位数组呢它就是你的映射1表示“值存在”0表示“它是 NULL”。但是等一下如果不存储 NULL 值我们怎么知道位向量从哪里开始呢让我们退后一步。PAX 页面头部包含页面上的总记录数N以及指向每个 minipage 起始位置的指针因此指针的数量与列的数量相同。给定指向一个 minipage 起始位置的指针和指向下一个 minipage 起始位置的指针你就可以确切地知道该 minipage 占用了多少字节。现在一切都清晰了。位向量位于 minipage 的末尾其大小正好是N位每行一位无论是否为 NULL。从 minipage 的末尾向前回退N位那里就是你的位向量的起始位置。它之前的所有内容都是密集的值数组。提取特定行纯粹是算术运算。要获取行R检查位向量中的第R位。如果为0返回 NULL。如果为1统计第R位置之前1的个数称其为M。该值位于距值数组起始位置偏移量为M x S处其中S是该类型的固定大小。就是这样。没有猜测。没有分隔符。只有 CPU 非常擅长的算术运算。F-minipage 结构图示让我们以上面模式中的第 3 行为例检查bit_array[2] 1→ 不是 NULL统计位置 2 之前1的个数 →popcount(1, 0) 1所以M 1该值位于距值数组起始位置偏移量为M x S 1 x 4 4字节处读取该偏移量处的INT4值 →17最大密度。零缓存浪费。CPU 加载的是纯净、紧凑的整数。而popcount呢那是一条硬件指令。成本几乎为零。变长属性 (V-minipage)此类别处理像TEXT或任何变长数据类型。值从 minipage 的前端追加而一个偏移量数组从尾部增长每个偏移量指向对应值的末尾。要找到一个值的起始位置可以查看上一个值的结束位置。理论上很简单。让我们看看在实践中会发生什么。NULL 的处理方式与 F-minipage 不同。这里没有位数组。NULL 值通过偏移量数组中的一个空指针来表示。无论如何偏移量数组为每一行都有一个固定大小的条目所以你总是确切地知道期望有多少个偏移量N即页面头部的记录数。最后这一点很重要。因为偏移量是定长的一个指针就是一个整数minipage 尾部的偏移量数组的行为与 F-minipage 中的密集数组完全相同。固定大小可预测关于其起始位置没有歧义从 minipage 的末尾向前回退N x sizeof(offset)字节。那么当一个值太大时会发生什么Postgres 有一个阈值TOAST_TUPLE_THRESHOLD默认为 2KB超过这个阈值的值会被 TOAST 处理存储到单独的表中的行外。在这种情况下V-minipage 存储的是一个定长的 TOAST 指针而不是原始值。这实际上对布局来说是个好消息TOAST 指针是定长的因此它在 minipage 中占用的空间远小于原始值并且偏移量仍然像其他值一样指向其末尾。minipage 不需要知道也不关心它看到的是原始数据还是一个指针。V-minipage 结构图示遍历第 3 行“DBA life”读取offset_array[2]和offset_array[1]检查offset_array[2]不是空指针所以不是 NULL检查offset_array[1]是一个空指针所以检查offset_array[0]不是空指针读取offset_array[0]和offset_array[2]之间的字节 → “DBA life”遍历第 2 行NULL读取offset_array[1]检查offset_array[1]空指针 → NULL返回空不需要读取上一个偏移量一个空指针本身就足以确定特殊情况 —— 第 1 行“Hello”读取offset_array[0]检查offset_array[0]不是空指针所以不是 NULL没有上一个偏移量数据区的起始位置从 minipage 结构本身可知因此偏移量 0 是隐式的从数据区的起始位置到offset_array[0]读取字节 → “Hello”插入、删除、更新插入当新记录到达时PAX 将每个属性值复制到其对应的 minipage 中。对于 F-minipage这意味着将新的定长值追加到密集数组并在存在位数组中设置相应的位。对于 V-minipage新值被追加到数据区的前端并向偏移量数组添加一个新的偏移量条目。棘手的部分是空间。如果一个 minipage 已满但页面仍然有全局空闲空间PAX 会执行边界移动它根据到目前为止的平均值大小重新计算 minipage 的大小并物理移动 minipage 的内容以重新分配可用空间。这并不廉价。它可能涉及在页面内移动大量数据。如果页面本身已满则会分配一个新页面。删除原始论文这样描述删除操作PAX 在页面开头维护一个位图来跟踪已删除的记录。一旦删除PAX 会立即重组 minipage 的内容以填补被删除记录留下的空隙从而最小化碎片并保持缓存密度。这在论文所基于的 Shore 存储管理器的上下文中是有意义的。在 Postgres 中正如我们将在下一节中看到的情况变得复杂。更新PAX 通过计算值在其 F-minipage 中的偏移量并原地覆盖来更新定长属性。对于变长属性如果新值大于旧值并且 V-minipage 没有空间论文建议从相邻的 minipage 借用空间。我们不同意这种方法。在同一 minipage 内混合来自不同列的数据会破坏 PAX 旨在提供的缓存局部性。如果你的TEXT值溢出到了整数 minipage 中那么在加载整数时你也会将不相关的数据加载到缓存中。PAX 的全部意义就消失了。一个更好的方法是首先尝试边界移动在所有 minipage 之间重新分配全局空闲空间。如果页面确实已满则将记录移动到新页面。绝不要从邻居那里借用。MVCC 问题以上所有内容在论文所基于的 Shore 存储管理器的上下文中都是合理的。在 Postgres 中事情要复杂得多。Postgres从不原地修改数据。这是其 MVCC 实现的基础。DELETE操作不会移除一行。它会在旧版本上设置xmax以将其标记为死亡。UPDATE操作不是原地修改。它是删除旧版本然后插入新版本。旧版本必须物理上保留在页面上以便在更改之前开始的并发事务可以读取。这与论文中的删除算法根本矛盾该算法要求立即进行 minipage 压缩以填补被删除行留下的空隙。如果立即压缩你会物理销毁活动事务可能仍需要读取的数据。在 Postgres 中你不能这样做。老实说我目前还没有针对这个问题的干净解决方案我怀疑这是 PAX 尚未在 Postgres 中实现的原因之一。如果你有想法我真的很想听听。话虽如此这里有一个值得探索的方向。一个可能的方向元数据 Minipage如果我们添加一个专用的元数据 minipage即每个 PAX 页面上的第一个 minipage包含所有每行的可见性信息xmin、xmax、ctid以及 Postgres 已经用来编码可见性信息的infomask标志会怎么样由于xmin、xmax、ctid和infomask都是定长整数这个元数据 minipage 自然就是一个 F-minipage。不需要特殊处理。PAX 存储引擎会像对待任何其他定长列一样对待它。这也为我们之前悬而未决的删除问题提供了一个清晰的答案。在 Postgres 中删除操作不会压缩任何东西。它只是在元数据 minipage 中为旧行版本设置xmax就像今天的 Postgres 所做的一样。所有其他 minipage 的数据区保持不变。旧版本物理上保留在原位可以被删除开始之前启动的并发事务读取。带有专用于元数据结构的 minipage 的 Postgres 页面图示通过这种设计三个操作变得清晰明了。DELETE操作只需在元数据 minipage 中设置xmax。所有其他 minipage 的数据区保持不变旧版本仍然可以被并发事务读取。INSERT操作将新的行版本追加到每个 minipage并在元数据 minipage 中设置xmin。UPDATE操作是DELETE后跟INSERT完全像今天的 Postgres 一样旧版本保留在原位新版本被追加。Autovacuum 读取元数据 minipage 来识别死亡版本即xmax早于集群中最旧活动事务的版本并在没有活动事务需要这些版本时安全地压缩数据区。要读取任何值你总是精确地加载两个 minipage用于检查可见性的元数据 minipage 和用于获取数据的目标列 minipage。干净、可预测、缓存友好。这是一个理论设计。具体的工程细节——元数据 minipage 究竟如何与 Postgres 的 WAL、缓冲区管理器和索引机制交互——仍然是未解决的问题。但感觉这个方向是正确的。实用的缓解措施Fillfactor 和 Toast即使暂时不考虑 MVCC 问题边界移动的成本也很高。Postgres 的两个存储参数可以显著帮助缓解这个问题。第一个是fillfactor。Postgres 已经允许你配置一个页面在分配新页面之前可以填充到什么程度。PAX 实现将受益于比 NSM 更保守的默认值大约80%留下足够的空间来吸收边界移动而无需在每次插入时都触发完整的页面重组。它还为 MVCC 行版本保留了空间使UPDATE操作能够保留在同一页面上并允许 HOT 更新工作。第二个是toast_tuple_target。Postgres 已经公开了这个参数用于控制变长值何时被压缩或移动到 TOAST 表。为 PAX 表降低此值意味着更多的值会被 TOAST 处理为行外存储并在 V-minipage 中被定长的 TOAST 指针替换。一个充满定长指针的 V-minipage 的行为更像一个 F-minipage大小可预测边界移动更少缓存密度更高。代价是对于大值会有更多的 TOAST 表访问。但在分析型工作负载中当你扫描少量列上的许多行时你通常根本不会读取那些大的变长列。这两个参数结合起来让 PAX 实现能够有意义地控制边界移动问题而无需更改核心算法CREATETABLEmy_table(...)USINGpaxWITH(fillfactor80,toast_tuple_target512);我们该何去何从PAX 不是一个简单的即插即用优化。原始论文描述了一个干净而优雅的概念但将其映射到 Postgres 上会揭示出一层又一层的复杂性NULL 处理、MVCC 兼容性、边界移动成本、Autovacuum 集成、WAL 影响。然而其核心思想仍然引人注目。缓存污染问题是真实存在的是可测量的并且随着每一代 CPU 的发展而变得更糟。PAX 在完全正确的层面解决了它在页面内部不触及存储栈的其余部分。元数据 minipage 的方向看起来很有希望。fillfactor和toast_tuple_target缓解措施是实用的并且今天就可以使用。艰苦的工程工作仍有待完成但道路是可见的。这就是我持续写这个主题的原因。不是因为我有所有的答案而是因为我认为这些问题值得大声提出来。Postgres 迈向缓存感知存储的旅程才刚刚开始。如果你是 C 语言开发者或存储爱好者我很乐意听到你的想法或就这些概念进行合作。如果你有兴趣讨论如何将 PAX 变为现实请直接联系我参考文献Ailamaki, A., DeWitt, D. J., Hill, M. D., Skounakis, M. (2001). Weaving Relations for Cache Performance.Proceedings of the 27th International Conference on Very Large Data Bases (VLDB).https://www.vldb.org/conf/2001/P169.pdf