数据库内核那些事｜细说 PolarDB 优化器查询变换：IN-List 变换
导读
数据库的查询优化器是整个系统的"大脑"，一条 SQL 语句执行是否高效在不同的优化决策下可能会产生几个数量级的性能差异，因此优化器也是数据库系统中最为核心的组件和竞争力之一。阿里云瑶池旗下的云原生数据库 PolarDB MySQL 版作为领先的云原生数据库，希望能够应对广泛用户场景、承接各类用户负载，助力企业数据业务持续在线、数据价值不断放大，因此对优化器能力的打磨是必须要做的工作之一。
本系列将从 PolarDB for MySQL 的查询变换能力开始，介绍我吗，们在这个优化器方向上逐步积累的一些工作。
*本篇为「PolarDB 优化器查询变换」系列第四篇，前三篇内容分别解读了：
引言
PolarDB MySQL 作为一款 HTAP 数据库，在复杂 SQL 查询优化能力上做了很多深入工作。早期用户 SQL 都非常简单，MySQL 单机能力也有限。随着业务数据越来越多，业务场景越来越复杂，迫切需要越来越强大的数据库来满足统计、报表需求。
PolarDB 在并行能力、查询变换能力、优化器等方面都做了非常深入的工作，这些工作有一个总目标：让用户的复杂查询执行得越来越快。本篇文章将对 PolarDB 的 IN-List 变换进行深入阐述，从而让我们对 PolarDB 的查询改写能力有更感性的认知。下面是一个常见的慢 SQL：in 函数运算，里面的常量比较多。
SQL 语句是常见的单表过滤查询，然后进行 agg 汇总，实际执行耗时比较长，执行比较慢的原因是 IN-List 里面有上千个常量值。
原生 MySQL
原生的 MySQL 执行计划如下：
执行过程是线性 scan lineitem 5.9 亿条数据，逐条去判断是不是在 IN-List 里面，这个算子是 Item_func_in，in 集合元素个数比较多，我们使用 10W 常量值进行测试，这个算子做求值运算耗时较长，整体完成需要 375s。
具体看下 Item_func_in 代码执行逻辑：
判断是否可以二分查找，如可以二分查找，将 IN-List 转成有序数组；
如果产生了有序数组，则执行时优先尝试二分查找；
否则，线性 scan，逐一判断左表达式是否等于 IN-List 里面的 item。
可以看到求值逻辑已经是教优的了，这个算子基本没有优化空间了。主要是外层循环次数太多，如果能减少外层的大 loop，那么就能降低延时。
PolarDB
PolarDB 解决问题的思路是对该 SQL 做查询变换， 把 IN-List 转变成一张物化表，加入 join list，具体变换过程如下：
Step 1：转成 in 子查询，上述 SQL 改写为
Step 2：SubQuery Unnest-消除子查询
子查询已经是非相关的，通过 SU 技术，可以消除子查询，转化为 semi-join。物化表经过去重，并且 Join 列非空，进而可以转化为 inner-join。
SQL 将继续改写为：
通过这种变换能到得如下好处：
不用逐条去做 filter，因为 MySQL 执行器是火山模型，增加了一个 filter 算子就增加了一层虚函数调用；
Join 有 join buffer，可以一个 batch 一个 batch 参与 Join，这是转成 join list 的一个好处；
转成 join list，join 的优化非常多，如 join order&access path，总能选到更优 plan。
最后执行的 plan 如下：
物化表数据量少，作为外表，inner-join 成功使用 lineitem 索引，只要扫 10 万条物化表记录，然后再使用 LINEITEM_FK2 索引进行连接，整条 SQL 执行下来只需要 32s。
测试效果
PolarDB IN-List 优化后在 TPCH 100G 数据集上比原生方式提升 11.5 倍，又因为 PolarDB 支持并行查询，32 并行度模式下提升上百倍。
总结
原理上，PolarDB 做完 IN-List 转换为 Join-List 后，能得到如下两方面的提升：
IN-List 里面的常量都经过物化去重，基数可能会有不小的下降，这取决于重复值；
IN-List 消去，变成了一张物化表，参与 Join-List 后，有更多 access path 选择，比如选择更好的 index，更多的 Join 方式：hash join 还是 nest loop join。
细微之处见真功夫，做 IN-List 转换还要完成其他工作，如需要适配 prepare statement 协议、适配并行查询协议等，PolarDB 在云数据库市场能做到特性遥遥领先，离不开背后工程师们坚持客户价值第一的初心，后续我们将介绍更多查询改写相关内容，敬请期待。
微信公众号「阿里云瑶池数据库」 2023-06-19 加入
瑶池，喻指汇聚宝藏之地。阿里云瑶池数据库，汇集数据无价之宝，让数据业务持续在线，数据价值不断放大。
评论