文章起源：PolarDB- X 知乎号
作者：升雨
前言
对于数据库来说，正确的抉择索引是根本的要求，选错索引轻则导致查问迟缓，重则导致数据库整体不可用。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 分布式版新人入门