PolarDB-X 存储引擎核心技术 | 索引回表优化

作者：攒叶

引言

数据库系统为了高效地存储、检索和维护数据，采用了多种不同的数据组织结构。不同的组织结构有其特定的用途和优化点，比如提高查询速度、优化写入性能、减少存储空间等。常见的数据库记录组织结构有：

1. B-Tree。B-Tree 是一种平衡的多路搜索树，特别适合存储在外部存储器（如硬盘）中。它通过减少访问磁盘的次数来优化读写操作。B-Tree 广泛应用于数据库管理系统和文件系统中，用于存储索引和数据。典型的代表有 MySQL。
2. LSM Tree。LSM Tree 是一种适合写入密集型场景的数据结构，通常用于 NoSQL 数据库中。它将数据更新操作写入内存中的结构，然后定期合并到磁盘上。这种设计充分利用了顺序写能力，大幅度优化了写入性能。使用 LSM Tree 的佼佼者有 LevelDB、HBase 等。
3. Heap Table。Heap Table 是一种简单的数据记录组织方式。Heap Table 的记录以任意顺序插入到表中，数据的写入性能几乎能达到磁盘写入的上限。但是由于其无序性，数据查询效率不如索引表。为了改进查询性能，Heap Table 通常还会搭配如 B-Tree 这样的索引结构使用。典型的数据库有 PostgreSQL。
4. Skip List 跳表。跳表是一种概率性结构，它通过在多层链表上添加“快速通道”的方式来实现快速搜索，实现了平均复杂度为 O(log n) 的插入、删除和查找操作。同样用于某些版本的 NoSQL 数据库中，被用作内存索引的一种有效结构。

每种数据组织结构都有其优势和应用场景。关系型数据库 OLTP 业务对并发读写、MVCC、空间利用率、高效查找和范围查询、优化磁盘 I/O、平衡性等等都要有均衡的诉求，目前 PolarDB-X 采用了 B-Tree 的索引组织结构。

B-Tree 索引中最常用到的是聚簇索引（即主键索引）。通过聚簇索引，查询能够直接找到对应数据行的所有数据。值得注意的是，PolarDB-X 存储引擎在聚簇索引上还放入数据行的版本信息。当查询进行时，PolarDB-X 需要通过比对查询的视图信息以及聚簇索引上行记录的版本信息，来确定查询需要查找的版本记录。当聚簇索引上的当前版本并不满足要求时，需要通过 Undo 日志把对应记录的历史版本构建出来。

聚簇索引对于主键查询非常有效，然而如果查询的条件并不由主键来决定时，查询需要回退到全量扫描。为了解决这个问题，非聚簇索引被引入。非聚簇索引与聚簇索引很相似，但非聚簇索引有一个重要的区别：

非聚簇索引没有版本信息，即通过非聚簇索引只能查找最新版本。当查找非聚簇索引时，需要首先确认该版本是否为本查询所需要的版本。但由于非聚簇索引上没有版本信息，所以进一步需要通过主键信息查找聚簇索引，以获得版本信息。

通过非聚簇索引查找对应的聚簇索引记录，这个过程通常被称为回表。

下面展示了一个典型的非聚簇索引的使用案例

年级成绩表（聚簇索引）：

班级-学生号索引（非聚簇索引）

当查询二班的所有学生号时，虽然只需要查找非聚簇索引即可，但是由于不能确定是否可见，还需要回查聚簇索引上对应的主键记录，确定其真实的版本号信息。

非聚簇索引回表代价

一条 SQL 语句回表代价取决于回表的频次以及回表本身的开销。

回表本身开销在于 B-Tree 查找，即一次非聚簇索引记录的查询，需要一次聚簇索引的查询。

回表的频次则取决于 SQL 语句的类型。特别是对于 Range 查询：

SELECT sec FROM t1 WHERE sec BETWEEN ? AND ?

当 PolarDB-X DN 存储引擎执行一条 SQL 时，需要经历开表、B-Tree 查找等等阶段，Range 查询会显著地增大回表开销的占比，如果每一行记录都需要回表，则会造成严重的性能问题。

在我们的测试数据中发现，全回表相比于不回表，性能有10倍以上的差距。

索引回表操作还会对 Buffer Pool 造成冲击，特别是当 Buffer Pool 资源紧张时，大量的回表操作会占用了 Buffer Pool 的空闲页，导致数据库雪崩。

考虑极端情况，如果一张表上几乎没有修改，则因为要判断可见性而带来的回表操作几乎是没有意义的。

通过上面分析可以发现，因为判断可见性而带来的回表，代价是昂贵，且大多数情况下是无必要的。目前单机数据库如 MySQL 通过引入最小活跃事务号，辅助非聚簇索引的可见性判断，大幅度降低了因为可见性判断而带来的回表问题。

但是，对于 PolarDB-X 这样的分布式数据库，情况会变得更复杂，这个方案将不再适用。为了解决这个问题，PolarDB-X DN 存储引擎提出了 CSM (Commit Snapshot Manager) 方案。

下面会介绍单机数据库 MySQL 的解决方案，并引申到 PolarDB-X 针对分布式场景设计的 CSM 方案。

单机 MySQL 非聚簇索引回表优化

为了解决这个问题，MySQL 通过引入最小活跃事务号，辅助非聚簇索引的可见性判断，大幅度避免了回表查询的次数，大大降低了查找代价。

事务 ID 号唯一标识了一个事务。MySQL 会维护一个事务 ID 号生成器。该事务 ID 号生成器会生成全局唯一单调递增的事务 ID 号。当事务启动时，都需要从该事务 ID 号生成器里获取一个事务 ID 号作为自己的事务标识。

同时，MySQL 还维护了一个全局的状态变量：min_active_trx_id。min_active_trx_id 表示所有活跃事务里最小的事务 ID 号。这意味着，所有事务 ID 号比 min_active_trx_id 小的事务都已提交。

除此之外，还会在非聚簇索引的每一个数据页上维护一个特殊的持久化信息：max_trx_id。max_trx_id 表示本数据页内所有修改过该数据页的事务里最大的事务ID号。

当查询发起时，会构建一个视图，该视图需要获取当前系统的 min_active_trx_id 作为视图的 up_limit_id。当查找非聚簇索引时，可以通过 up_limit_id 与数据页的 max_trx_id 做比较来确定可见性。相关流程图如下所示：

分布式数据库的索引回表困境

对于分布式数据库，回表问题会被进一步放大。PolarDB-X，分布式查询采用基于全局时间戳TSO 的 MVCC 多版本查询。即分布式查询视图的版本号 GCN 是由外部的全局授时服务生成的 TSO 来指定，而并非从数据库管理系统里的本地 trx 最新状态获取。

由于网络、系统调度等原因，当分布式查询真正发起时，节点内的事务系统状态可能已经发生过多次变化，事务系统状态最新的 min_active_trx_id 信息已经不再适用于本次分布式查询 GCN 视图的构建。

以下面例子为例：

对于上述发起的分布式查询，实际上由于 (snapsho_GCN = 99) < (rec_GCN = 100)，所以该记录对于该视图应该是不可见的。

之所以出现上述问题，其核心原因在于，所有的分布式事务的提交顺序并非由本地生成，而是由外部全局协调器统一生成。即多个分布式事务的分支事务在各个节点上的实际提交顺序可能是不同的。

这导致分布式查询的可见性要远比本地单机查询复杂，目前业界内基于单机查询设计的非聚簇索引优化理论，在分布式查询上不再有效。

如何在分布式数据库管理系统里，降低非聚簇索引因为查找版本信息而带来的额外回表代价，是分布式数据库管理系统设计里最关键的问题之一。

Commit Snapshot Manager 方案

单机数据库管理系统上非聚簇索引的优化方案，在分布式场景下不再适用的原因是：分布式查询需要的是“彼时彼刻”的 min_active_trx_id，但数据库现有的设计只能提供“此时此刻”的 min_active_trx_id。

上述说的“时刻”并不是物理时间上的时刻，而是 GCN 这样的逻辑“时刻”。即：

对于 snapshot_GCN = 99 的分布式查询，它需要的是 DN 节点处于 GCN = 99 时事务系统对应的 min_active_trx_id。

一个直观的设想是，如果事务系统维护了过去所有时间点的事务系统状态信息，并且提供能力回查当时时刻的 min_active_trx_id 状态，则可以解决分布式场景下非聚簇索引因为无法判断可见性而需要回表的问题。

当然这个代价是巨大的，以 10 万 TPS 为例，每分钟需要产生至少 90 MB 的数据。

PolarDB-X 存储引擎采用了 CSM 方案来均衡了资源开销与可用性，以极低的代价维护过去时间点的近似 min_active_trx_id 状态，彻底解决了分布式场景下非聚簇索引频繁回表的问题。 CSM 是一个环形队列，每间隔一定时间（如 1 秒）则会产生一个 Commit Snapshot。更具体地说：

1. CSM 收集开始
2. 获取系统当下的 min_active_trx_id 作为 up_limit_id
3. 获取系统当下的 sys_GCN, sys_SCN 为 csm_GCN 以及 csm_SCN
4. 将 (up_limit_id， csm_GCN， csm_SCN) 作为一个 Commit Snapshot，插入到 CSM

其中，sys_GCN 是 PolarDB-X 存储引擎维护的本节点上的最大 GCN 号。其更新时机为：

1. 分布式查询由外部协调者指定了 snapshot_GCN 作为分布式查询视图的 GCN，sys_GCN = max { sys_GCN, snapshot_GCN }
2. 分布式事务提交由外部协调者指定了 commit_GCN 作为分布式事务的提交号 GCN，sys_GCN = max { sys_GCN, commit_GCN }

显然，sys_GCN，min_active_trx_id 均满足单调递增永不回退。这意味着：

在 CSM 环形队列上，csm_GCN、up_limit_id 总是有序的。

当分布式查询发起时，根据视图的 snapshot_GCN，从 CSM 尾部开始查找，直到找到 csm_GCN 刚好不大于 snapshot_GCN 的 CSM 元素，取该元素的 up_limit_id 作为视图的 up_limit_id——我们就得到了我们想要的“彼时彼刻”的 up_limit_id。值得注意的是，由于有序性的保证，上述查找可通过二分查找完成。

显然，这个 up_limit_id 只是“彼时彼刻”真正的 up_limit_id 的近似值。但通过上述步骤，我们总是能够拿到一个比真实值要小的近似值。幸运的是，当我们拿一个更小的 up_limit_id 去做可见性判断时，并不会导致误判。

可以看见，上述 CSM 中的 Commit Snapshot 还包括了 csm_SCN。这是因为 PolarDB-X 标准版还支持了闪回查询 AS OF 语法。通过闪回查询，可以轻松完成游戏回档、业务回滚、数据误删恢复等特性。有关 PolarDB-X DN 存储引擎的事务系统的设计，可参考过往文章《PolarDB-X 存储引擎核心技术 | Lizard分布式事务系统》。

SELECT sec FROM t1 AS OF SCN $SCN WHERE sec BETWEEN ? AND ?
SELECT sec FROM t1 AS OF TIMESTAMP $time WHERE sec BETWEEN ? AND ?

测试结果显示，对于分布式事务的一致性查询，开启 CSM ( 32 KB 内存资源 + 少量计算开销 ) 具有显著的性能提升：

# 压测SQL，模拟命中sec列的索引
SELECT sec FROM t1 WHERE sec BETWEEN ? AND ?

云原生数据库PolarDB分布式（PolarDB-X）大降价，价格下调40%，最低至0.75元/小时。

阿里巴巴双十一同款数据库，原生MySQL生态，基于Paxos三副本确保RPO=0，支持集中式和分布式一体化。

点击下方链接，立即购买

https://common-buy.aliyun.com/?commodityCode=drds_polarxpre_public_cn