查询优化概念
查询变换的概念非常简单，就是基于关系代数的等价变换规则，将查询的一种形式转换为另外一种等价但更为高效的形式，通过这种转换，既可以保证查询结果的正确性，又可以提升查询的执行效率。
优化器可以完成的变换非常多，如果将每一种变换视为一种改写规则的话，几百个规则也是比较常见的。其中有些变换（规则），总是可以让查询变得更为高效，我们称其为启发式变换，但有些则不一定，需要基于代价来决定。
本篇文章将介绍PolarDB实现的一个启发式查询变换——join消除。
该功能在PolarDB for MySQL 8.0.2.2.9版本上线。
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消除能力的，客户的查询从原来的3表left join变为了单表，执行时间大大缩短。
为此我们调研了MariaDB的实现，觉得其原理是有参考性的，但实现中所能覆盖的场景还不全面，在一些简单情况以及复杂嵌套的场景下(semi-join），支持的还很不够，因此基于MySQL 8.0的codebase做了自己的实现。
基本原理
基本的思路并不复杂，考虑如下这个join
outer_table LEFT JOIN (inner_table) ON condition(outer_table,inner_table)
由于是LEFT JOIN，外表的数据是不会丢失的，如果同时可以保证：
1. 对外表的任一行，内表能匹配join条件的行数有且仅有一行；
2. 在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 t1.* from t1 left join (t2 left join t3 on t3.a=t2.b) on t2.a=t1.a; => select t1.* 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;
当然各种其他场景还有很多，但只要遵循前面提到的几个判定原则，就都可以逐一的完成消除。
与PostgreSQL的对比
PG在计算层的能力一直是其比较引以为傲的点，其统计信息和代价模型是非常优秀的，加上更完备的join ordering算法，确实可以生成较高质量的执行计划。
不过在查询变换方面，Postgres的能力也只能说相当一般（有机会后续会写文章介绍PG的优化器），它也实现了left join消除的功能，基本思路与PolarDB的一致，基于内表的唯一性判定，但其支持的场景就更为简单了：
● 只能支持left join的内侧是一个base relation，或者是一个subquery；
这严重限制了join消除应用的范围，不过好的一点是，当内侧是个subquery(derived table)时，它不仅支持基于group by列的唯一性检查，对于distinct / set operation，都有相应的判断机制，具体实现可参见：
query_is_distinct_for(Query *query, List *colnos, List *opids)
这个函数，不过其思路和实现都非常简单，PolarDB后续也会类似去扩展下。
与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个最基础的问题：
1. MySQL的各个原有变换，加的都比较"随意"，其自身和原有处理流程的耦合导致增加新变换很困难；
2. 变换执行时机不合理，不同变换之间是存在一定前后依赖关系的，这种关系并没有很好的被利用；
3. 某些变换并不一定带来收益，需要基于统计信息 + 代价来做决定，这种决定MySQL是完全不支持的，变了就是变了，无论效果好坏。
为了解决这3个基本问题，团队在做的一个非常重要和复杂的事情，就是重构MySQL的查询变换流程：
1. 解耦原有的resolve + transform交错的流程，把变换作为单独的步骤，以"规则"为单位，各自独立完成，这样变换就可以通过添加新规则而不断独立扩展；
2. 在基于规则的抽象后，引用枚举框架来枚举不同变换（规则）间的先后顺序，通过反复迭代也可使得相互依赖的规则都可以按照更优的顺序被执行；
3. 实现CBO模块的可重入+可重用能力，这样可以基于代价来决定是否执行变换。
