数据库内核那些事｜细说PolarDB优化器查询变换：IN-List变换

导读

数据库的查询优化器是整个系统的"大脑"，一条SQL语句执行是否高效在不同的优化决策下可能会产生几个数量级的性能差异，因此优化器也是数据库系统中最为核心的组件和竞争力之一。阿里云瑶池旗下的云原生数据库PolarDB MySQL版作为领先的云原生数据库，希望能够应对广泛用户场景、承接各类用户负载，助力企业数据业务持续在线、数据价值不断放大，因此对优化器能力的打磨是必须要做的工作之一。

本系列将从PolarDB for MySQL的查询变换能力开始，介绍我们在这个优化器方向上逐步积累的一些工作。

*本篇为「PolarDB优化器查询变换」系列第四篇，前三篇内容分别解读了：

1. Join消除

2. 窗口函数

3. Join条件下推

引言

PolarDB MySQL作为一款HTAP数据库，在复杂SQL查询优化能力上做了很多深入工作。早期用户SQL都非常简单，MySQL单机能力也有限。随着业务数据越来越多，业务场景越来越复杂，迫切需要越来越强大的数据库来满足统计、报表需求。

PolarDB在并行能力、查询变换能力、优化器等方面都做了非常深入的工作，这些工作有一个总目标：让用户的复杂查询执行得越来越快。本篇文章将对PolarDB的IN-List变换进行深入阐述，从而让我们对PolarDB的查询改写能力有更感性的认知。下面是一个常见的慢SQL：in函数运算，里面的常量比较多。

select        sum(l_extendedprice) / 7.0 as avg_yearly
from
        lineitem
        where
            l_partkey in (
9628136,19958441,10528766,.......); #in list里面有上千个常量值。

SQL语句是常见的单表过滤查询，然后进行agg汇总，实际执行耗时比较长，执行比较慢的原因是IN-List里面有上千个常量值。

原生MySQL

原生的MySQL执行计划如下：

+---------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                           |
+---------------------------------------------------------------------------------------------------+
| -> Aggregate: sum(lineitem.L_EXTENDEDPRICE)
    -> Filter: (lineitem.L_PARTKEY in (9628136,19958441,10528766,....) (cost=60858714.81 rows=297355930)
        -> Table scan on lineitem  (cost=60858714.81 rows=594711859)
|
+---------------------------------------------------------------------------------------------------+

执行过程是线性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改写为

select ... from lineitem where l_partkey in (...)
====>
select ... from lineitem where l_partkey in 
 (select dt._col_1 from (values (9628136),(19958441),...) dt)

Step 2：SubQuery Unnest-消除子查询

子查询已经是非相关的，通过SU技术，可以消除子查询，转化为semi-join。物化表经过去重，并且Join列非空，进而可以转化为inner-join。

SQL将继续改写为：

====>
select ... from lineitem, (values (9628136),(19958441),...) dt) where l_partkey = dt._col_1

通过这种变换能到得如下好处：

不用逐条去做filter，因为MySQL执行器是火山模型，增加了一个filter算子就增加了一层虚函数调用；

Join有join buffer，可以一个batch一个batch参与Join，这是转成join list的一个好处；

转成join list，join的优化非常多，如join order&access path，总能选到更优plan。

最后执行的plan如下：

+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Aggregate: sum(lineitem.L_EXTENDEDPRICE)
    -> Nested loop inner join
        -> Table scan on dt
            -> Materialize with deduplication
                -> scan on in-list: 100000 rows
        -> Index lookup on lineitem using LINEITEM_FK2 (L_PARTKEY=dt._col_1), with index condition: (lineitem.L_PARTKEY = dt._col_1)  (cost=7.34 rows=29)

物化表数据量少，作为外表，inner-join成功使用lineitem索引，只要扫10万条物化表记录，然后再使用LINEITEM_FK2索引进行连接，整条SQL执行下来只需要32s。

测试效果

PolarDB IN-List优化后在 TPCH 100G 数据集上比原生方式提升11.5倍，又因为PolarDB支持并行查询，32并行度模式下提升上百倍。