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

本文涉及的产品
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云原生数据库 PolarDB 分布式版,标准版 2核8GB
简介: 数据库系统为了高效地存储、检索和维护数据,采用了多种不同的数据组织结构。不同的组织结构有其特定的用途和优化点,比如提高查询速度、优化写入性能、减少存储空间等,目前 PolarDB-X 采用了 B-Tree 的索引组织结构。

作者:攒叶

引言

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


  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 日志把对应记录的历史版本构建出来。


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


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


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


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

年级成绩表(聚簇索引):

学生号 (主键) 班级 成绩 版本号(隐藏列)
. . . . . . . . . . . .
225208 三班 100 7
225209 二班 99 5
. . . . . . . . . . . .


班级-学生号索引(非聚簇索引)

班级(索引列) 学生号(主键)
. . .
二班 225209
三班 225208
. . .


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

非聚簇索引回表代价

一条 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 做比较来确定可见性。相关流程图如下所示:


1.jpg


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

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

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

以下面例子为例:


时刻 分布式查询 分布式事务 A 分布式事务 B
T1 发起分布式查询从 GMS 取得 TSO,设置 GCN = 99
T2 事务 (trx_id = 90, GCN = 100)更新 page_a 上的非聚簇索引page_a 的 max_trx_id = 90
T3 事务 (trx_id = 91, GCN = 101) 提交
T4 查询在 DN 上获得视图(up_limit_id = 91, snapshot_GCN = 99)
T5 查询 page_a 上的记录,由于 up_limit_id > max_trx_id 判断为可见。


对于上述发起的分布式查询,实际上由于 (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 ?
Range_size 1 10 50 100
CSM Off (QPS) 82657 9333 1946 993
CSM On (QPS) 302332 105496 26002 13369
改进值 (%) 265% 1030% 1236% 1246%




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


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


点击下方链接,立即购买

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

相关实践学习
跟我学:如何一键安装部署 PolarDB-X
《PolarDB-X 动手实践》系列第一期,体验如何一键安装部署 PolarDB-X。
相关文章
|
5天前
|
存储 算法 数据处理
惊人!PolarDB-X 存储引擎核心技术的索引回表优化如此神奇!
【6月更文挑战第11天】PolarDB-X存储引擎以其索引回表优化技术引领数据库发展,提升数据检索速度,优化磁盘I/O,确保系统在高并发场景下的稳定与快速响应。通过示例代码展示了在查询操作中如何利用该技术高效获取结果。索引回表优化具备出色性能、高度可扩展性和适应性,为应对大数据量和复杂业务提供保障,助力企业与开发者实现更高效的数据处理。
|
9天前
|
关系型数据库 分布式数据库 数据库
PolarDB产品使用合集之表列存索引要怎么添加
PolarDB是阿里云推出的一种云原生数据库服务,专为云设计,提供兼容MySQL、PostgreSQL的高性能、低成本、弹性可扩展的数据库解决方案,可以有效地管理和优化PolarDB实例,确保数据库服务的稳定、高效运行。以下是使用PolarDB产品的一些建议和最佳实践合集。
|
9天前
|
存储 关系型数据库 分布式数据库
PolarDB产品使用合集之PolarDB支持哪些存储引擎
PolarDB是阿里云推出的一种云原生数据库服务,专为云设计,提供兼容MySQL、PostgreSQL的高性能、低成本、弹性可扩展的数据库解决方案,可以有效地管理和优化PolarDB实例,确保数据库服务的稳定、高效运行。以下是使用PolarDB产品的一些建议和最佳实践合集。
|
9天前
|
关系型数据库 分布式数据库 数据库
PolarDB产品使用合集之优化器对索引的阈值一般是多少
PolarDB是阿里云推出的一种云原生数据库服务,专为云设计,提供兼容MySQL、PostgreSQL的高性能、低成本、弹性可扩展的数据库解决方案,可以有效地管理和优化PolarDB实例,确保数据库服务的稳定、高效运行。以下是使用PolarDB产品的一些建议和最佳实践合集。
|
17天前
|
监控 关系型数据库 数据库
关系型数据库考虑索引的选择性
【5月更文挑战第20天】
31 4
|
17天前
|
关系型数据库 数据库 索引
|
18天前
|
SQL Oracle 关系型数据库
关系型数据库中对索引的数目
【5月更文挑战第19天】
34 4
|
1月前
|
SQL 运维 关系型数据库
PolarDB产品使用合集之PolarDB 2.3.0 版本的 CDC 功能支持 Polardb-X 到 Polardb-X 的数据同步吗
PolarDB产品使用合集涵盖了从创建与管理、数据管理、性能优化与诊断、安全与合规到生态与集成、运维与支持等全方位的功能和服务,旨在帮助企业轻松构建高可用、高性能且易于管理的数据库环境,满足不同业务场景的需求。用户可以通过阿里云控制台、API、SDK等方式便捷地使用这些功能,实现数据库的高效运维与持续优化。
|
9月前
|
SQL Oracle 关系型数据库
Polar DB-O (兼容 Oracle 语法版本)和Polar DB PostgreSQL 版本概述(二)
Polar DB-O (兼容 Oracle 语法版本)和Polar DB PostgreSQL 版本概述(二)
997 0
|
存储 SQL 安全
PolarDB-X内核新版本:将MySQL进行到底
在PolarDB-X最新的内核版本5.4.15中,提供诸多新功能:存储过程,读写分离优化,表级分区管理,密码、审计优化等。
683 0
PolarDB-X内核新版本:将MySQL进行到底

相关产品

  • 云原生分布式数据库 PolarDB-X
  • 云原生数据库 PolarDB