TiDB 源码阅读系列文章（二十一）基于规则的优化 II

select max(a) from t group by t.pk;

select a from t;

select count(a) from t group by t.pk;

select if(isnull(a), 0, 1) from t;

select t1.a from t1 left join t2 on t1.b = t2.pk;

select t1.a from t1;

select distinct(t1.a) from t1 left join t2 on t1.b = t2.b;

select distinct(t1.a) from t1;

-- 非相关子查询
select * from t1 where t1.a > (select t2.a from t2 limit 1);
-- 相关子查询
select * from t1 where t1.a > (select t2.a from t2 where t2.b > t1.b limit 1);

即直接执行子查询获得结果，再利用这个结果改写原本包含子查询的表达式；比如上述的非相关子查询，如果其返回的结果为一行记录 “1” ，那么整个查询会被改写为：

```sql

select * from t1 where t1.a > 1;

```

详细的代码逻辑可以参考 [expression_rewriter.go](https://github.com/eurekaka/tidb/blob/logical_rules_reading/planner/core/expression_rewriter.go) 中的 [handleScalarSubquery](https://github.com/eurekaka/tidb/blob/logical_rules_reading/planner/core/expression_rewriter.go#L685) 和 [handleExistSubquery](https://github.com/eurekaka/tidb/blob/logical_rules_reading/planner/core/expression_rewriter.go#L535) 函数。

对于包含 IN (subquery) 的查询，比如：

```sql

select * from t1 where t1.a in (select t2.a from t2);

```

会被改写成：

```sql

select t1.* from t1 inner join (select distinct(t2.a) as a from t2) as sub on t1.a = sub.a;

```

如果 `t2.a` 满足唯一性属性，根据上面介绍的聚合消除规则，查询会被进一步改写成：

```sql

select t1.* from t1 inner join t2 on t1.a = t2.a;

```

这里选择将子查询转化为 inner join 的 inner plan 而不是执行子查询的原因是：以上述查询为例，子查询的结果集可能会很大，展开子查询需要一次性将 `t2` 的全部数据从 TiKV 返回到 TiDB 中缓存，并作为 `t1` 扫描的过滤条件；如果将子查询转化为 inner join 的 inner plan ，我们可以更灵活地对 `t2` 选择访问方式，比如我们可以对 join 选择 `IndexLookUpJoin` 实现方式，那么对于拿到的每一条 `t1` 表数据，我们只需拿 `t1.a` 作为 range 对 `t2` 做一次索引扫描，如果 `t1` 表很小，相比于展开子查询返回 `t2` 全部数据，我们可能总共只需要从 `t2` 返回很少的几条数据。

注意这个转换的结果不一定会比展开子查询更好，其具体情况会受 `t1` 表和 `t2` 表数据的影响，如果在上述查询中， `t1` 表很大而 `t2` 表很小，那么展开子查询再对 `t1` 选择索引扫描可能才是最好的方案，所以现在有参数控制这个转化是否打开，详细的代码可以参考 [expression_rewriter.go](https://github.com/eurekaka/tidb/blob/logical_rules_reading/planner/core/expression_rewriter.go) 中的 [handleInSubquery](https://github.com/eurekaka/tidb/blob/logical_rules_reading/planner/core/expression_rewriter.go#L596) 函数。

则将其过滤条件添加到 `LogicalApply` 的 join condition 中，然后将该 `LogicalSelection` 从 inner plan 中删除，再递归地对 inner plan 提升算子。

以如下查询为例：

```sql

select * from t1 where t1.a in (select t2.a from t2 where t2.b = t1.b);

```

其生成的最初执行计划片段会是：

![1.png](https://upload-images.jianshu.io/upload_images/542677-d01f93be2416556f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

`LogicalSelection` 提升后会变成如下片段：

![2.png](https://upload-images.jianshu.io/upload_images/542677-7d11730db1688b53.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

到此 inner plan 中不再包含相关列，于是 `LogicalApply` 会被转换为如下 LogicalJoin ：

![3.png](https://upload-images.jianshu.io/upload_images/542677-9b7df1ed09ba348d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

即要求子查询最多输出一行记录，比如这个例子：

```sql

select *, (select t2.a from t2 where t2.pk = t1.a) from t1;

```

因为子查询出现在整个查询的投影项里，所以 `expressionRewriter` 在处理子查询时会对其生成的执行计划在根节点上加一个 `LogicalMaxOneRow` 限制最多产生一行记录，如果在执行时发现下层输出多于一行记录，则会报错。在这个例子中，子查询的过滤条件是 `t2` 表的主键上的等值条件，所以子查询肯定最多只会输出一行记录，而这个信息在“构建节点属性”这一步时会被发掘出来并记录在算子节点的 `MaxOneRow` 属性中，所以这里的 `LogicalMaxOneRow` 节点实际上是冗余的，于是我们可以将其从 inner plan 中移除，然后再递归地对 inner plan 做算子提升。

则首先将这个投影算子从 inner plan 中移除，再根据 `LogicalApply` 的连接类型判断是否需要在 `LogicalApply` 之上再加上一个 `LogicalProjection` ，具体来说是：对于非 semi-join 这一类的连接（包括 inner join 和 left join ），inner plan 的输出列会保留在 `LogicalApply` 的结果中，所以这个投影操作需要保留，反之则不需要。最后，再递归地对删除投影后的 inner plan 提升下层算子。

```sql

select *, (select sum(t2.b) from t2 where t2.a = t1.pk) from t1;

```

其最初生成的执行计划片段会是：

![4.png](https://upload-images.jianshu.io/upload_images/542677-c812770e277e0a4a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

将聚合提升到 `LogicalApply` 后的执行计划片段会是：

![5.png](https://upload-images.jianshu.io/upload_images/542677-400e0ce5a3d138ed.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

即先对 `t1` 和 `t2` 做连接，再在连接结果上按照 `t1.pk` 分组后做聚合。这里有两个关键变化：第一是不管提升前 `LogicalApply` 的连接类型是 inner join 还是 left join ，提升后必须被改为 left join ；第二是提升后的聚合新增了 `Group By` 的列，即要按照 outer plan 传进 inner plan 中的相关列做分组。这两个变化背后的原因都会在后面进行阐述。因为提升后 inner plan 不再包含相关列，去相关后最终生成的执行计划片段会是：

![6.png](https://upload-images.jianshu.io/upload_images/542677-9d4e39e7aed7422e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

聚合提升有很多限定条件：

* `LogicalApply` 的连接类型必须是 inner join 或者 left join 。 `LogicalApply` 是根据相关子查询生成的，只可能有 3 类连接类型，除了 inner join 和 left join 外，第三类是 semi join （包括 `SemiJoin`，`LeftOuterSemiJoin`，`AntiSemiJoin`，`AntiLeftOuterSemiJoin`），具体可以参考 `expression_rewriter.go` 中的代码，限于篇幅在这里就不对此做展开了。对于 semi join 类型的 `LogicalApply` ，因为 inner plan 的输出列不会出现在连接的结果中，所以很容易理解我们无法将聚合算子提升到 `LogicalApply` 之上。

* `LogicalApply` 本身不能包含 join condition 。以上面给出的查询为例，可以看到聚合提升后会将子查询中包含相关列的过滤条件 (`t2.a = t1.pk`) 添加到 `LogicalApply` 的 join condition 中，如果 `LogicalApply` 本身存在 join condition ，那么聚合提升后聚合算子的输入（连接算子的输出）就会和在子查询中时聚合算子的输入不同，导致聚合算子结果不正确。

* 子查询中用到的相关列在 outer plan 输出里具有唯一性属性。以上面查询为例，如果 `t1.pk` 不满足唯一性，假设 `t1` 有两条记录满足 `t1.pk = 1`，`t2` 只有一条记录 `{ (t2.a: 1, t2.b: 2) } `，那么该查询会输出两行结果 `{ (sum(t2.b): 2), (sum(t2.b): 2) } `；但对于聚合提升后的执行计划，则会生成错误的一行结果` { (sum(t2.b): 4) } `。当 `t1.pk` 满足唯一性后，每一行 outer plan 的记录都对应连接结果中的一个分组，所以其聚合结果会和在子查询中的聚合结果一致，这也解释了为什么聚合提升后需要按照 `t1.pk` 做分组。

* 聚合函数必须满足当输入为 `null` 时输出结果也一定是 `null` 。这是为了在子查询中没有匹配的特殊情况下保证结果的正确性，以上面查询为例，当 `t2` 表没有任何记录满足 `t2.a = t1.pk` 时，子查询中不管是什么聚合函数都会返回 `null` 结果，为了保留这种特殊情况，在聚合提升的同时， `LogicalApply` 的连接类型会被强制改为 left join（改之前可能是 inner join ），所以在这种没有匹配的情况下，`LogicalApply` 输出结果中 inner plan 部分会是 `null` ，而这个 `null` 会作为新添加的聚合算子的输入，为了和提升前结果一致，其结果也必须是 `null` 。

```sql

select *, (select count(*) from t2 where t2.a = t1.a) from t1;

```

其生成的最初的执行计划片段会是：

![7.png](https://upload-images.jianshu.io/upload_images/542677-16b0cdcf345577a8.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

因为聚合函数是 `count(*)` ，不满足当输入为 `null` 时输出也为 `null` 的条件，所以它不能被提升到 `LogicalApply` 之上，但它可以被改写成：

![8.png](https://upload-images.jianshu.io/upload_images/542677-74c87be3a4c518a0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

注意 `LogicalAggregation` 的 `Group By` 新加了 `t2.a` ，这一步将原本的先做过滤再做聚合转换为了先按照 `t2.a` 分组做聚合，再将聚合结果与 `t1` 做连接。 `LogicalSelection` 提升后 inner plan 已经不再依赖 outer plan 的结果了，整个查询去相关后将会变为：