PolarDB-X 的 XPlan 索引选择

前言

对于数据库来说，正确的选择索引是基本的要求，选错索引轻则导致查询缓慢，重则导致数据库整体不可用。PolarDB-X 存在多种不同的索引，局部索引、全局索引、列存索引、归档表索引。

局部索引就是单机数据库上常用的索引，目的是避免全表扫描。

全局索引是分布式数据库为了避免全分片扫描，冗余一份数据，采用与主表不同分区键的索引表。

列存索引是主表的列存副本，提供 HTAP 能力。

归档表索引是归档表上的列布隆过滤器，为归档表提供一定的 TP 查询能力。

本文主要介绍一种 CN 上的局部索引算法：XPlan 索引选择。

什么是 XPlan

PolarDB-X 包含计算节点(CN)和数据节点(DN)，CN 负责 SQL 解析、优化和执行，DN 节负责数据的持久化，CN 与 DN 之间通过 RPC 通信。DN 100%兼容 Mysql，也是作为 PolarDB-X 标准版进行售卖的。

CN 与 DN 之间 RPC 通信的内容其实就是标准的 SQL，CN 会将解析优化好的语法树转成 SQL 传给 DN 重新解析、优化。对比起来，将 CN 的语法树直接传给 DN 执行听起来就更优[1]。

但这样其实不一定好，主要原因是作为存算分离的架构，数据都在 DN 上，DN 可以直接在数据上进行 index dive，而 CN 的统计信息是采样出来的静态数据，更新不及时，所以基数估计比不上 DN 精确，导致索引选择准确度不如 DN，在很多场景下节省的 DN 解析优化的消耗远不如选错索引的后果。

但对于用户核心的点查场景，这样的 CN 优化一遍 DN 再优化一遍的流程就会成为瓶颈，所以 PolarDB-X 提供 XPlan 机制：对于点查场景，直接传输执行计划交给 DN 执行。

这样的定位说明 XPlan 不是必须的能力，而是锦上添花的能力。目前 XPlan 的适用范围被限定为单张表的 DQL，只支持 Scan、Filter 和 Project 算子。

XPlan 在 Sysbench 点查上有 10%以上的提升，但线上在用户的真实场景下 XPlan 索引错选导致的慢查询问题频发。对于 PolarDB-X 来说，选错索引有两种可能：基数估计错误和执行计划缓存下的倾斜索引。

基数估计错误的三个常见原因统计信息缺失、倾斜数据和关联列，学术界、工业界研究了几十年都无法解决[2]。这些问题虽然无法解决，但是很容易检测到，PolarDB-X 基本策略是检测到这些问题就禁用 XPlan，交给 DN 做局部索引选择。同样发现索引错选也是容易的。通过预先和事后的检测，希望尽量减少 XPlan 错选概率。

PolarDB-X 的优化器与索引选择

下图是一条 sql 过 PolarDB-X 优化器的大致过程：经过 RBO 和CBO后生成最好的单机执行计划，并基于 CBO 产生的最优执行计划的代价判断当前查询是否为 AP 查询，如果不是 AP 查询则直接构造单机执行计划，否则进一步考虑是否可以走列存索引。

无法走列存索引则基于最优单机执行计划插入 shuffle 算子构造分布式执行计划，否则将基于列存索引构造最优分布式执行计划。

局部索引、全局索引、归档表索引选择都在 CBO 里，局部索引选择影响的是 Logicalview 算子的 IO 代价，全局索引选择会将扫描主表的执行计划替换为全局索引回表，归档表索引选择可以将过滤条件复杂无法走索引的归档表扫描替换为多个简单走索引的归档表扫描。列存索引选择是利用列存对 AP 查询重新生成最优的分布式执行计划。

XPlan 索引选择则是在单机优化器的最后对 logicalview 中进行索引选择。这与 CBO 里的局部索引选择不同，CBO 里的局部索引选择只影响 Logicalview 算子的 IO 代价进而影响整个执行计划的代价，是 CN 基于自己的统计信息模拟 DN 做索引选择的过程，并不是 DN 真正使用的索引，只有 XPlan 会指定 DN 的索引。

PolarDB-X 的执行计划缓存与倾斜值问题

PolarDB-X 的执行计划获取大致逻辑如下

getPlan(String sql)     if PlanCache doesn't contain sql :        PlanCache.put(sql, getPlanByOptimizer(sql))    Plan =  PlanCache.get(sql)    if PlanManager contiain sql :        Plan = PlanManager.choose(sql)    return Plan

所有的执行计划都会缓存在 PlanCache 中，如果 PlanManager 中有执行计划，则由 PlanManager 选择代价最低的执行计划。

这篇文章提及了 Optimize Once 和 Optimize Always 的概念，PolarDB-X 采用的理念就是 Optimize Once，尽量少进入优化器，主要的考量是 PolarDB-X 的优化器结构相当复杂，如果采用 Optimize Always，优化器的耗时在高并发 tp 的查询中代价将无法忽视。

这里回顾一下 Parameterized Queries 的常见问题，考虑以下场景

create table hot_select (    id int not null,    c_int int,    c_varchar varchar(20),    PRIMARY KEY (`id`),    KEY i_int(c_int),    KEY i_varchar(c_varchar))
select * from hot_select where c_int = 1 and c_varchar = 'a';select * from hot_select where c_int = 2 and c_varchar = 'a';

若满足 c_int = 1 的数据有 1 行，满足 c_varchar = 'a'的数据有 100 行，满足 c_int = 2 有 10000000 行，则第一条查询应该走索引 i_int，第二条查询应该走索引 i_varchar。

但两条查询共用了同一个 sql 模版，同一个 sql 模版只会 Optimize Once，这两条 sql 都只会走 i_int，导致第二条查询事实上走错了索引。

这个问题学术界已经提出了很多解决方案[3]，PolarDB-X 之前已经在线上验证过论文里面的部分方案，设计了下图所示的一套反馈和演化的机制，由于执行计划飘忽不定导致 rt 不稳定，最后导致反馈演化功能被关闭。TiDB 也做过类似的尝试，也是强制关闭的状态。

基于大部分学术界方案生产上不可用的事实和 XPlan 的锦上添花定位，Xplan 索引选择的设计都以不负优化为前提，PolarDB-X 采取的方案有点类似于[4]，不同点在于 XPlan 会考虑期望基数，而是最大基数。

当然同样的问题也出现在全局索引选择上，但是由于全局索引选择的必要性，XPlan 的方案并不适用，PolarDB-X 有一套不同的方案来处理全局索引的倾斜值问题，在后续文章会进一步展开。

XPlan 索引选择算法

XPlan 核心问题有两个：如何选择索引以及如何进行执行计划传输和执行。执行计划传输和执行的大致逻辑如下图所示：在算子树上将 filter 尽量下推，用 filter-XplanScan 的 pattern 进行索引选择并记录到 XplanScan 中，基于算子树填充 protobuf，利用私有协议传输给 DN 解析出来后直接对 Innodb 数据进行读取和过滤。

由于本文的主旨是 XPlan 索引选择而不是 XPlan，这个部分不再展开，后面主要介绍如何进行 XPlan 的索引选择。

XPlan 索引选择会尽量减少错选的概率，具体流程下图所示： 首先检查当前表的统计信息是否过期，由于统计信息可能因为各种原因无法自动更新，没有统计信息的索引选择就是乱猜，所以统计系信息过期之后会禁用 XPlan，有个小优化是 pk、uk 的查询不受此影响。

统计信息过期的时限是 7 天，内核每天都会自动检查并收集 3 天未更新的统计信息，并在完成后再次检查统计信息，依然存在超过 3 天未更新的表则会发出内核报警。这个判断会减少统计信息缺失导致的基数估计错误。 第二步是过滤可能的倾斜索引，统计信息模块提供能力检查给定的列集合是否存在倾斜值，倾斜列的索引不会被 XPlan 使用。

这个过滤会减少 Plan Cache 导致的倾斜值问题。关联列估算错误一般是由于列间独立性假设的选择率迭乘导致基数估计过小，由于倾斜列被过滤，也不会出现关联列导致的基数估计过小。 第三步利用基数估计模块挑选选择率最好的索引，只有足够好的索引才可以走 XPlan。

由于 XPlan 是 Robust Query Optimization 而不会选最好的索引，所以可能选不出好索引，这种情况下也会直接禁用 XPlan。 最后将选择出的索引记录到 XplanScan 中，到此 XPlan 的索引选择就完成了。

再考虑一下之前的例子，由于 c_int 存在倾斜，XPlan 不会再选择 i_int 而是会选择 i_varchar，从而避免了倾斜值问题。

create table hot_select (    id int not null,    c_int int,    c_varchar varchar(20),    PRIMARY KEY (`id`),    KEY i_int(c_int),    KEY i_varchar(c_varchar))
select * from hot_select where c_int = 1 and c_varchar = 'a';select * from hot_select where c_int = 2 and c_varchar = 'a';

倾斜值判断

倾斜值也就是所谓的 skew data，在 XPlan 的场景下，只需要考虑所有索引的前缀列的组合是否有倾斜。 PolarDB-X 的采样对于一张表会采出 10 万行数据，采样出来的频率大于 5 且频率/采样率大于 1 万就会被判断成倾斜值。

这个倾斜值判断的逻辑有改进的空间，且对抗 sample 的稳定性也不够强，但目前来说还是能够取得预期的效果。 那么算法就很简单了，穷举 n 个索引的所有前缀列，判断其在 sample 出的 10 万行中最大频率是否满足上述条件即可。若索引平均列数为 m，则时间复杂度为 O(1e5*nm)，这个时间可以忽略不计了。

当然还有更细的优化，比如倾斜列的前缀一定是倾斜列，更大的列集合优先判断供后续剪枝之类的，不再赘述。 额外提一句 PolarDB-X 采样采用的是 block sampling[5]，在 Innodb 的主键上 Random Walk 出一些 page，对于主键是天然倾斜的(特别是复合主键)，所以主键的前缀列不会做倾斜值判断。

回退机制与可观测性

鉴于 DN 的 index dive 能力对于单张表的估算有更好的表现，PolarDB-X 选择的兜底策略是 DN 返回 XPlan 在 Innodb 上扫描的行数，CN 一旦发现 XPlan 在索引上扫描的行数超出阈值，则关闭当前 sql 模版的 XPlan，并发出报警。

后续 12 小时内对应 sql 模版都不会再走 XPlan。这个简单的机制对于只有 Plan Cache 的数据库也同样有效：发现 Plan Cache 的查询出现异常慢的情况，可以对这个模版禁用 Plan Cache。

PolarDB-X 支持 explain execute 语法查看 DN 物理索引。对于 XPlan，explain execute 会将 XPlan 的上下文一直传递到执行器下发物理 sql 之前将其拦截，否则会在 XPlan 的上下文中设置无法 XPlan 并走回正常物理 sql 路径。

由于回退机制的存在，explain execute 可能与线上发生问题的状态不一样，排查就会变得比较困难，所以在日志中会记录每个 XPlan 走的索引及在 Innodb 上扫描行数。

线上效果

下图是最近半个月不同版本实例 XPlan 报警的日平均发生率。

在优化版本 XPlan 索引选择逻辑改变之后，每天实例出现 XPlan 选错索引的概率从 5%降到了 0.1%，下降为原本的 1/50。注意老版本的 XPlan 选错索引后用户可以关闭 XPlan，所以真实的错选概率只会更高。

报警率概率下降的主因并不是优化器能选择对的索引了，而是优化器能不选择不对的索引了。

总结

本文详细介绍了 PolarDB-X 对于点查场景的专门优化 XPlan 的索引选择方案。

包括 PolarDB-X 的优化器架构和其中涉及的多种索引选择、XPlan 面临的索引错选问题和其中的基数估计错误、执行计划缓存机制导致的倾斜值问题，针对性设计了一个能预先检测避免错选的算法，并提供监控报警机制、错选后的兜底回退机制以及良好的可观测性，显著降低了 XPlan 索引错选的概率。

当然 XPlan 的普适性、倾斜值判断的稳定性、关联列估算能力等都可以做进一步的优化。

引用

[1] Assembling a Query Engine From Spare Parts https://www.firebolt.io/content/firebolt-vldb-cdms-2022

[2] Efficient Query Re-optimization with Judicious Subquery Selections https://arxiv.org/pdf/2202.12535.pdf

[3] Robust Query Optimization Methods With Respect to Estimation Errors: A Survey https://dl.acm.org/doi/10.1145/2854006.2854012

[4] Towards a Robust Query Optimizer: A Principled and Practical Approach https://dl.acm.org/doi/10.1145/1066157.1066172

[5] A Survey of Data Partitioning and Sampling Methods to Support Big Data Analysis https://ieeexplore.ieee.org/document/9007871

数据库 PolarDB-X 新人入门一站式页面，快速体验集中分布式一体化新特性！

云原生数据库PolarDB分布式版新人入门