文章起源：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分布式版新人入门