PAX（Partition Attributes Across）

今天分享一篇文章：《Weaving Relations for Cache Performance》，来自 2001 年 VLDB。看这篇之前需要先了解一下 NSM 和 DSM：列式存储的起源：DSM

正文 1015 字，预计阅读时间 3 分钟。

解决的问题

在决策支持系统（Decision Support Systems）的场景中，数据库的主要耗时在处理器和内存之间的数据传输，而不是内存和磁盘之间的I/O。

主要在说 cache 失效的问题，当一个数据请求在 cache 中失效了，需要重新从内存中加载数据，但是往往查询的只是某几个属性，因此只有一部分被加载到 cache 中的数据会被用到，没有高效的利用 cache。

这是 NSM 在一个 page 中的数据组织方式，每一行记录包括三个属性，序号-姓名-年龄。每个 page 中开头是个 page header，然后是一个一个记录，每个记录包括一个头部 RH（record header）和三个数据。数据放在前边，page的末尾存放每个记录的起始位置。

cache 的机制是，在用到一个数据时，把这个数据之后的几个相邻数据也加载到 cache 中。

在查询年龄小于40的姓名这个场景下。先读第一个年龄 30，满足条件，再去读姓名 Jane，发现 cache 不包括 Jane，于是加载 Jane 和之后的几个字段。可以发现 cache 失效比较多，而且加载到 cache 中的数据有很多没用。

本质是 NSM 模型在 OLAP 场景下的 CPU cache 表现不好。

要解决这个问题，用 DSM 不就好了吗？但是作者说 DSM 需要大量的时间去做 join，这也是确实存在的问题。下图是 DSM 的存储结构，每列在一个 page 中，需要跨 page 做 join。

PAX

于是作者提出了一个折中方法。只将一个 page 内的多个 record 按列式存储。

在一个 page 中，再为每个属性划分一个 迷你page，每个 迷你page 里存这个 page 里所有 record 的某个属性。

更细粒度的，PAX 的 迷你page 又分为定长 F- 的和变长的 V-，分别用来存储定长属性和变长属性。

PAX 和 NSM 的空间占用基本一样，而 DSM 需要为每一列加一个索引列。

PAX 集合了 NSM 和 DSM 的优点：（1）跨记录的空间局部性，也就是记录的相同属性存储在一起。便于高效地利用 cache。（2）最小化记录重组的代价，只在一个 page 内部重组就可以了。

总结

可以把 PAX 当做 NSM 模型的一个针对 cache 优化的实现，因为其整体还是 NSM 模型，只是调整了 page 的结构。