背景
众所周知，数据库的查询优化器可以说是整个系统的"大脑"，一条查询语句执行的是否高效，在不同的优化器决策下，可能会产生几个数量级的性能差异，因此优化器也是数据库系统中最为核心的组件和核心竞争力之一。对于各个商业数据库，其优化器通过常年积累下来的能力，是其最为核心的商业机密，而另一方面从现有的开源数据库来看，很可惜大多数产品的优化器还都十分初级，也包括老牌的MySQL/PostgreSQL。
PolarDB for MySQL作为国内甚至国际上领先的云原生数据库，基于云底座的基础能力，在架构演进上提出了很多新的方向，也引领了云原生关系数据库的发展。PolarDB的目标是希望能够应对广泛的用户场景、承接各类的用户负载，成为新一代的云原生企业级数据库。因此对优化器能力的打磨是必须要做的工作之一。
坦白来说我们的起点并不高因为MySQL的优化器是非常薄弱的，但这也给了我们更大的发展空间，想要构建一个具有成熟能力的优化器，还有很多工作要做。
优化器本身是一个既广又深的领域，涵盖很多的话题，每个方向都可以深入下去做长年的积累，但总的来说，最为核心的几个基础组件可以概括如下：
-
查询变换
-
join ordering
-
枚举框架
-
统计信息
-
计划稳定性
-
自适应能力
PolarDB在这几个方面都做了布局并已完成了一系列工作，当然更多的还在后面，不过现在可以先系统性的向大家介绍下我们在多个方向上做的一些工作。
这个系列先从查询变换开始。
查询变换概念
查询变换的概念非常简单，就是基于关系代数的等价变换规则，将查询的一种形式转换为另外一种等价但更为高效的形式，通过这种转换，既可以保证查询结果的正确性，又可以提速查询的执行效率。
优化器可以完成的变换是非常非常多的，如果将每1种变换视为一种改写规则的话，几百个规则也是比较常见的。其中有些变换（规则），总是可以让查询变得更为高效，我们称其为启发式变换，但有些则不一定，需要基于代价来决定。
本篇文章介绍下PolarDB实现的一个启发式查询变换 - join消除。
join消除
join可以说是所有SQL语句中最为常见的算子，当然也是最为耗时的算子，一个join操作，需要将作为两边的关系(表），根据join条件中指定的连接列，拼接到一起向上层算子输出，笼统的来说，这是一个具有 M * N 运算复杂度的操作，和scan/aggregation等相比要高出一个因数，因此如何实现好的join算法、如果决定最好的join执行顺序，是每个数据库系统都不得不面对的核心问题。
那么从另外一个角度出发，是不是可以基于SQL查询中的某些特定的语义，从一开始就想办法消除掉不必要的join操作呢？例如如下这种非常简单的情况:
create table t1 (id int, PRIMARY KEY(id));
create table t2 (id int, t1_id int,
constraint `t1_id_fk` foreign key (`t1_id`) references `t1` (`id`)
);
select t2.id from t2 join t1 on t2.t1_id = t1.id;可以看到t2的t1_id列是t1 id列的外键，因此对t2的每一行，一定有且只有一行t1的数据可以和t2 join上，同时整个查询最终并不需要t1表的数据，查询可以简化为:
select t2.id from t2;这避免了对t1表的访问和大量行的连接操作，可以想见会有非常明显的性能提升。
PolarDB实现
PolarDB的优化器基于MySQL，原始是没有任何join消除能力的，在线上值班过程中，有客户遇到从MariaDB迁移过来后发现查询性能回退了非常多。排查后发现，MariaDB是具有join的消除能力的（也难怪Monty会自信满满的认为MariaDB已经全面超越了MySQL，个人觉得并不尽然，后续会专门写文章介绍MariaDB的优化器），客户的查询从原来的3表left join变为了单表，执行时间大大缩短。
为此我们调研了MariaDB的实现，觉得其原理是有参考性的，但实现中所能覆盖的场景还很不全面，在一些简单情况以及复杂嵌套的场景下(semi-join），支持的还很不够。因此基于MySQL8.0的codebase做了自己的实现。
基本原理
基本的思路并不复杂，考虑如下这个join
outer_table LEFT JOIN (inner_table) ON condition(outer_table,inner_table)由于是LEFT JOIN，外表的数据是不会丢失的，如果同时可以保证：
-
对外表的任一行，内表能匹配join条件的行数有且仅有一行
-
在LEFT JOIN以外，不再有其他地方需要引用内表的数据
则这个left join就可以安全的消除掉。
如何保证这种唯一性呢？第一个想到的自然就是唯一/主键索引，如果内表的join列是唯一索引列，自然是满足输出一行这个要求。
但实际的查询不可能总是这么简单，我们可以考虑如下几种情况：
-
唯一索引包含多列？
-
inner table包含多张表？
-
inner table中包含新的left join？
-
inner table本身是个derived table?
看似简单的join消除的问题一下子就复杂了起来，但我们可以通过逐步的分解，通过判定每一个子问题来完成是否可消除的判断：
-
一个LEFT JOIN的内部(单表/多表)，只有当所有表都保证唯一输出一行时，整个LEFT JOIN才能消除
-
对内侧的每个单表，当其join条件中涉及的所有列，是某个唯一索引的超集时，该表才能保证输出一行
-
如果内侧再次包含有LEFT JOIN，则要先深度递归进去，判断这个内侧的LEFT JOIN是否可以消除，消除后再返回来考察外层
-
如果内层包含derived table且derived table中包含group by，则从外层来看，group by列也就是derived table的主键列
遵循以上的思路依次处理每个子问题，就可以实现对各种复杂场景的可消除性的判定。具体算法和代码这里就先略过了。
看下上面几个问题的具体效果：
create table t1 (a int);
create table t2 (a int primary key, b int);
create table t3 (a int primary key, b int);
1. inner table包含多张表？
select t1.a from t1 left join (t2 join t3) on t2.a=t1.a and t3.a=t1.a;
=>
select t1.a from t1;
2. inner table中包含新的left join？
select count(*) from t1 left join (t2 left join t3 on t3.a=t2.b) on t2.a=t1.a;
=>
select count(1) from t1;
3. inner table本身是个derived table?
select t1.* from t1 left join
(
select t2.b as v2b, count(*) as v2c
from t2 left join t3 on t3.a=t2.b
group by t2.b
) v2
on v2.v2b=t1.a;
=>
select t1.* from t1;当然各种其他的场景还有很多，但只要遵循前面提到的几个判定原则，就都可以逐一的完成消除。
与mariadb的对比
我们也针对各种场景和MariaDB做了一些对比，发现在对一些场景的支持上，MariaDB的策略比较粗糙或不太合理：
-
对semi-join的处理
在MariaDB中，如果一个子查询在LEFT JOIN的ON条件中，就直接阻止了它转为semi-join，目的是为了让它仍然保留为一个谓词条件，从而在join消除的逻辑中避免对semijoin的复杂处理，但很明显这个存在误伤：如果这个LEFT JOIN本身无法被消除，semi-join岂不是也不能用了？
仍然沿用上面t0/t1/t2/t3的schema:
EXPLAIN SELECT count(*)
FROM t1
LEFT JOIN (t2
LEFT JOIN t3
ON t2.b = t3.b
AND EXISTS (
SELECT t0.a
FROM t0
WHERE t0.a = t3.b
)
) ON t1.a = t2.a;这里由于t2.b = t3.b这样的join条件，t3.b不是唯一键，这个查询是无法消除join的，而MariaDB的执行计划如下:
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| 1 | PRIMARY | t1 | ALL | NULL | NULL | NULL | NULL | 4 | |
| 1 | PRIMARY | t2 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.a | 1 | Using where |
| 1 | PRIMARY | t3 | ALL | NULL | NULL | NULL | NULL | 2 | Using where |
| 2 | DEPENDENT SUBQUERY | t0 | ALL | NULL | NULL | NULL | NULL | 4 | Using where |
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+-------------+可以看到t0的相关子查询选择了最原始的执行方式，如果t0表的数据量大，性能会非常糟糕，而PolarDB仍然支持:
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+------+----------+-------------+
| 1 | SIMPLE | t1 | NULL | ALL | NULL | NULL | NULL | NULL | 4 | 100.00 | NULL |
| 1 | SIMPLE | t2 | NULL | ALL | PRIMARY | NULL | NULL | NULL | 2 | 100.00 | Using where |
| 1 | SIMPLE | t3 | NULL | ALL | NULL | NULL | NULL | NULL | 2 | 100.00 | Using where |
| 1 | SIMPLE | <subquery2> | NULL | eq_ref | <auto_distinct_key> | <auto_distinct_key> | 5 | je_test.t3.b | 1 | 100.00 | Using where |
| 2 | MATERIALIZED | t0 | NULL | ALL | NULL | NULL | NULL | NULL | 4 | 100.00 | NULL |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+--------------+------+----------+-------------+t0还是通过semi-join MATERIALIZATION的方式来实现，效率会高很多。
-
对序列LEFT JOIN的处理
即使在一些简单场景下，MariaDB的处理也不完备:
EXPLAIN SELECT count(*)
FROM t1
LEFT JOIN t2 ON t1.a = t2.a
LEFT JOIN t3 ON t2.b = t3.a;MariaDB由于算法和实现的限制，效果如下:
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 4 | |
| 1 | SIMPLE | t2 | eq_ref | PRIMARY | PRIMARY | 4 | test.t1.a | 1 | Using where |
+------+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+在这样一个简单查询中，很明显t2/t3都是可以消除掉的，但MariaDB竟然只能处理t3表的join消除。
PolarDB实现的则更为彻底：
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| 1 | SIMPLE | t1 | NULL | ALL | NULL | NULL | NULL | NULL | 4 | 100.00 | NULL |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+性能提升
join的消除是一个必然产生收益的启发式变换，根据表的数据量、访问方式的不同，产生的性能差异可能千差万别，但一般来说，性能都是会有很大提升的，这里就用一个线上客户的实际查询做个对比：
SELECT count(*)
FROM `shop_customer` `sc`
LEFT JOIN `car` `ca` ON `sc`.`car_id` = `ca`.`id`
LEFT JOIN `company` `co` ON `sc`.`company_id` = `co`.`id`;
=>
SELECT count(*) FROM `shop_customer` `sc`;很明显最后可以变成单表的查询，在消除前，执行时间是7.5s，消除后是0.1s，提升了75倍。
比这更夸张的例子其实比比皆是，尤其是内层包含多张表的嵌套时。总的来说，join的开销通常情况下都比较大，能够消除都会有明显的提升。
总结
我们目前还在做其他一些查询变换的能力提升，毕竟MySQL原生可以支持的还太少了，但这也是个逐步补充的过程，需要针对线上的客户场景和实际需求作为素材不断积累。
在这个过程中我们遇到了3个最基础的问题：
-
MySQL的各个原有变换，加的都比较"随意"，其自身和原有处理流程的耦合导致增加新变换很困难
-
变换执行时机不合理，不同变换之间是存在一定前后依赖关系的，这种关系并没有很好的被利用
-
某些变换并不一定带来收益，需要基于统计信息 + 代价来做决定，这种决定MySQL是完全不支持的，变了就是变了，无论效果好坏。
为了解决这3个基本问题，团队在做的一个非常重要和复杂的事情，就是重构MySQL的查询变换流程：
-
解耦原有的resolve + transform交错的流程，把变换作为单独的步骤，以"规则"为单位，各自独立完成，这样变换就可以通过添加新规则而不断独立扩展
-
在基于规则的抽象后，引用枚举框架来枚举不同变换（规则）间的先后顺序，通过反复迭代也可使得相互依赖的规则都可以按照更优的顺序被执行
-
实现CBO模块的可重入+可重用能力，这样可以基于代价来决定是否执行变换
总体思路和Oracle/MemSQL的CBQT是类似的，但贴合到MySQL的codebase中，这是个难度不小的项目，应该也是业界第一个在MySQL优化器上动这种大手术的工作，还是非常有意思也有挑战的。
最后欢迎对这方面工作感兴趣的同学加入PolarDB团队，一起做世界领先的云原生数据库 ：）
