对于数据库来说，正确地选择索引是基本要求，选错索引轻则导致查询缓慢，重则导致数据库整体不可用。PolarDB分布式版存在多种不同的索引：局部索引、全局索引、列存索引、归档表索引。
- 局部索引就是单机数据库上常用的索引，目的是避免全表扫描。
- 全局索引是分布式数据库为了避免全分片扫描，冗余一份数据，采用与主表不同分区键的索引表。
- 列存索引是主表的列存副本，提供HTAP能力。
- 归档表索引是归档表上的列布隆过滤器，为归档表提供一定的TP查询能力。
本文主要介绍一种CN上的局部索引算法：XPlan索引选择。
什么是XPlan
云原生数据库PolarDB分布式版（PolarDB for Xscale，简称“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分布式版提供XPlan机制：对于点查场景，直接传输执行计划交给DN执行。
这样的定位说明XPlan不是必须的能力，而是锦上添花的能力。目前XPlan的适用范围被限定为单张表的DQL，只支持Scan、Filter和Project算子。
XPlan在Sysbench点查上有10%以上的提升，但线上在用户的真实场景下XPlan索引错选导致的慢查询问题频发。对于PolarDB分布式版来说，选错索引有两种可能：基数估计错误和执行计划缓存下的倾斜索引。
基数估计错误的三个常见原因统计信息缺失、倾斜数据和关联列，学术界、工业界研究了几十年都无法解决[2]。这些问题虽然无法解决，但是很容易检测到，PolarDB分布式版基本策略是检测到这些问题就禁用XPlan，交给DN做局部索引选择。同样发现索引错选也是容易的。通过预先和事后的检测，希望尽量减少XPlan错选概率。
PolarDB分布式版的优化器与索引选择
下图是一条SQL过PolarDB分布式版优化器的大致过程：经过RBO和CBO后生成最好的单机执行计划，并基于CBO产生的最优执行计划的代价判断当前查询是否为AP查询，如果不是AP查询则直接构造单机执行计划，否则进一步考虑是否可以走列存索引。
无法走列存索引则基于最优单机执行计划插入shuffle算子构造分布式执行计划，否则将基于列存索引构造最优分布式执行计划。
局部索引、全局索引、归档表索引选择都在CBO里，局部索引选择影响的是Logicalview算子的IO代价，全局索引选择会将扫描主表的执行计划替换为全局索引回表，归档表索引选择可以将过滤条件复杂无法走索引的归档表扫描替换为多个简单走索引的归档表扫描。列存索引选择是利用列存对AP查询重新生成最优的分布式执行计划。
XPlan索引选择则是在单机优化器的最后对Logicalview中进行索引选择。这与CBO里的局部索引选择不同，CBO里的局部索引选择只影响Logicalview算子的IO代价进而影响整个执行计划的代价，是CN基于自己的统计信息模拟DN做索引选择的过程，并不是DN真正使用的索引，只有XPlan会指定DN的索引。
PolarDB分布式版的执行计划缓存与倾斜值问题
PolarDB分布式版的执行计划获取大致逻辑如下：
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选择代价最低的执行计划。
在《PolarDB分布式版优化器核心技术～执行计划管理》一文中，提及了Optimize Once和Optimize Always的概念，PolarDB分布式版采用的理念就是Optimize Once，尽量少进入优化器，主要的考量是PolarDB分布式版的优化器结构相当复杂，如果采用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分布式版之前已经在线上验证过论文里面的部分方案，设计了下图所示的一套反馈和演化的机制，由于执行计划飘忽不定导致rt不稳定，最后导致反馈演化功能被关闭。TiDB也做过类似的尝试，也是强制关闭的状态。
基于大部分学术界方案生产上不可用的事实和XPlan的锦上添花定位，XPlan索引选择的设计都以不负优化为前提，PolarDB分布式版采取的方案有点类似于[4]，不同点在于XPlan不会考虑期望基数，而是最大基数。
当然同样的问题也出现在全局索引选择上，但是由于全局索引选择的必要性，XPlan的方案并不适用，PolarDB分布式版有一套不同的方案来处理全局索引的倾斜值问题，在后续文章会进一步展开。
XPlan索引选择算法
XPlan核心问题有两个：如何选择索引以及如何进行执行计划传输和执行。执行计划传输和执行的大致逻辑如下图所示：在算子树上将filter尽量下推，用filter-XplanScan的pattern进行索引选择并记录到XplanScan中，基于算子树填充protobuf，利用私有协议传输给DN解析出来后直接对Innodb数据进行读取和过滤。由于本文的主旨是XPlan索引选择而不是XPlan，这个部分不再展开，后面主要介绍如何进行XPlan的索引选择。
XPlan索引选择会尽量减少错选的概率，具体流程下图所示：
1）首先，检查当前表的统计信息是否过期，由于统计信息可能因为各种原因无法自动更新，没有统计信息的索引选择就是乱猜，所以统计系信息过期之后会禁用XPlan，有个小优化是pk、uk的查询不受此影响。统计信息过期的时限是7天，内核每天都会自动检查并收集3天未更新的统计信息，并在完成后再次检查统计信息，依然存在超过3天未更新的表则会发出内核报警。这个判断会减少统计信息缺失导致的基数估计错误。
2）第二步是过滤可能的倾斜索引，统计信息模块提供能力检查给定的列集合是否存在倾斜值，倾斜列的索引不会被XPlan使用。这个过滤会减少Plan Cache导致的倾斜值问题。关联列估算错误一般是由于列间独立性假设的选择率迭乘导致基数估计过小，由于倾斜列被过滤，也不会出现关联列导致的基数估计过小。
3）第三步利用基数估计模块挑选选择率最好的索引，只有足够好的索引才可以走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分布式版的采样对于一张表会采出10万行数据，采样出来的频率大于5且频率/采样率大于1万就会被判断成倾斜值。这个倾斜值判断的逻辑有改进的空间，且对抗sample的稳定性也不够强，但目前来说还是能够取得预期的效果。
那么算法就很简单了，穷举n个索引的所有前缀列，判断其在sample出的10万行中最大频率是否满足上述条件即可。若索引平均列数为m，则时间复杂度为O(1e5*nm)，这个时间可以忽略不计了。当然还有更细的优化，比如倾斜列的前缀一定是倾斜列，更大的列集合优先判断供后续剪枝之类的，不再赘述。
额外提一句PolarDB分布式版采样采用的是block sampling[5]，在Innodb的主键上Random Walk出一些page，对于主键是天然倾斜的(特别是复合主键)，所以主键的前缀列不会做倾斜值判断。
回退机制与可观测性
鉴于DN的index dive能力对于单张表的估算有更好的表现，PolarDB分布式版选择的兜底策略是DN返回XPlan在Innodb上扫描的行数，CN一旦发现XPlan在索引上扫描的行数超出阈值，则关闭当前SQL模版的XPlan，并发出报警。后续12小时内对应SQL模版都不会再走XPlan。这个简单的机制对于只有Plan Cache的数据库也同样有效：发现Plan Cache的查询出现异常慢的情况，可以对这个模版禁用Plan Cache。
PolarDB分布式版支持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分布式版对于点查场景的专门优化XPlan的索引选择方案。
包括PolarDB分布式版的优化器架构和其中涉及的多种索引选择、XPlan面临的索引错选问题和其中的基数估计错误、执行计划缓存机制导致的倾斜值问题，针对性设计了一个能预先检测避免错选的算法，并提供监控报警机制、错选后的兜底回退机制以及良好的可观测性，显著降低了XPlan索引错选的概率。
当然，XPlan的普适性、倾斜值判断的稳定性、关联列估算能力等都可以做进一步的优化。
引用
[1] Assembling a Query Engine From Spare Parts
[2] Efficient Query Re-optimization with Judicious Subquery Selections
[3] Robust Query Optimization Methods With Respect to Estimation Errors: A Survey
[4] Towards a Robust Query Optimizer: A Principled and Practical Approach
[5] A Survey of Data Partitioning and Sampling Methods to Support Big Data Analysis