数据库内核那些事｜PolarDB IMCI 让你和复杂低效的子查询说拜拜

1. 行列混查的优化器架构

In-Memory Column Index（简称 IMCI）是云原生数据库 PolarDB MySQL 用于复杂 SQL 查询加速度的技术，它通过为 PolarDB 存储引擎增加列格式的索引，再结合并行向量化执行的 SQL 算子，将实时数据上的复杂分析性能提升 1 到 2 个数量级。让客户可以在单一 PolarDB 上同时运行事务处理和复杂分析负载，简化业务架构并降低使用成本。

IMCI 虽然利用了新的索引存储格式和 SQL 执行引擎算子，却同时保留了 100%的 MySQL 语法兼容，用户无需做任何语法修改即可实现透明复杂查询加速，这是通过 PolarDB 的 SQL 解析器和优化器独特架构来实现的：

​

一条 SQL 经 Parser 处理后生成一个 LogicalPlan，再经行存优化器生成 PhysicalPlan 并计算出执行代价，对于代价超出配置阈值的 SQL 会再经过一次面向 IMCI 执行器的规则优化和代价优化过程。由于 IMCI 执行算子不支持直接执行子查询。这第二步的关键过程即包含子查询去关联，此外还包含 JoinReorder 过程。本文内容主要阐述 IMCI 中的子查询去关联这一步骤的关键技术。

2. 关联子查询的作用

关联子查询作为查询中被广泛使用的一个特性，被广泛的使用在用户的业务场景之中，在没有索引等方式进行优化的情况下，其基本的执行方式类似于 nested loop。在数据量较大的查询下，这样的执行方式复杂度过高，很难让用户接受，因此有必要在优化器中进行子查询去关联，将其改写为不带有关联项的子查询，随后通过其他更高效的 join 算法来提高查询的效率。因为目前 IMCI 的查询执行基本不利用索引执行查询，在这个场景下，nested loop join 风格的关联子查询处理效率慢到难以让客户接受，因此在 PolarDB-IMCI 中，我们实现了一套子查询去关联的规则，实现了对于绝大多数子查询的去关联化，为 IMCI 上执行的关联子查询起到了良好的加速作用。

3. 关联子查询的介绍：一个例子

如以下 SQL，就是一个经典的关联子查询的例子:

SELECT COUNT(*) FROM t1WHERE   t1.c1 > (SELECT MAX(t2.c2)              FROM t2              WHERE t1.c1 = t2.c1); -- subquery

在上面这个 SQL 中，这个子查询中的条件是 t1.c1 = t2.c1，其中 t1.c1 引用了外层查询的值，这个查询本来的查询计划是这样。

​

可以看到，因为左下角这个带有关联项的 filter 的存在，对于 t1 中的每一行，我们都要将其代入右侧的查询，以类似 nested loop join 的执行方式执行：对于 t1 的每一行，我么都需要重新执行一次右侧的查询，如果 t1，t2 的数据量都很大，这里的 join 使用的是算法是 nested loop join，会导致查询耗时过久。

在一些关于 SQL 优化的文章中可能会提到，对于上文的 SQL，我们可以改写成这样来进行加速:

SELECT COUNT(*) FROM t1,    (SELECT t2.c1 as c1, MAX(t2.c2) as max_c2      FROM t2       GROUP BY t2.c1) AS tmpWHERE   t1.c1 = tmp.c1 AND t1.c1 > tmp.max_c2;

这样改写之后，原先子查询里面的关联项被提取了出来，关联子查询消失了！此时查询计划变成了这样：

​

可以看到，原先的 nested loop join 消失了，我们不必像之前一样低效的反复执行子查询了。

通过对比这个通过 SQL 改写完成的子查询去关联的查询计划，其实可以发现，这个改写其实只是做了一件简单的事情：把带有关联的 filter 向上提，直到提到一个能够直接获取关联项的位置，如下图所示。

​

完成这个操作之后，带有关联项的 filter 消失，同时 nested loop join 因为等值条件的加入可以变成 hash join。那么我们进一步的扩展这个想法，是不是所有的子查询都可以这么做呢？答案是肯定的。

4. 子查询去关联的算法

在上节一开始的查询计划表示中，我们将其中的 nested loop join 称之为 dependent join(在 SQL Server 中称之为 apply，下文可能会部分使用该术语)，其与普通的 join 的区别在于：

• 是没有谓词的 inner join。

• outer plan 引用了 inner plan 输出的行（例如上文中的 t1.c1 = t2.c1）。

上文中提到，我们去关联的基本想法就是把关联项一直向上提，直到关联项越过 dependent join，这样就消去了这一个关联项，下文我们将通过多条规则的组合来达成消去任意关联子查询的目标，接下来将以 dependent join 的 outer plan 的根节点为标准对规则进行分类，如果我们能够处理任意类型的根节点，那么通过反复应用规则，一定可以将查询的关联项消去。

4.1 下推规则

首先有一个最显然的规则，其中 F(T)∩A(D)=∅ 表示 T 中没有引用 D 的任何结果。这个规则的意思是，如果 T 中没有引用 D 的任何结果（也就是没有关联），那么这就是一个普通的 join。

​

另一个规则是通用的规则，没有什么使用限制，主要是用来提高执行效率。

​

这里的 D 是对 T1 上所有被 T2 引用的列取 distinct 的结果，在 SQL Server 中叫做 MagicSet[1]，这样做的好处是：对于等式左边的查询，我们需要对 T1 的每一行执行右边的 T2 子查询，但是等式右边的查询，仅需要对 D 上的每一行执行 T2 ，因为 D 的结果集一定比 T2 小，所以这样能加快关联子查询执行的效率，后面子查询去关联部分也会用到 MagicSet。

▶︎ Filter 和 Project

如果 outer plan 的根节点是一个 Filter，我们可以通过应用以下规则来把这个 filter 提到 join 上。

​

就是普通的谓词下推的逆操作。

Project 也是类似的，A(D) 代表 D 输出的所有列，将其与 project 要输出的列 A 取并集即可。

​

▶︎ Group By

在 PostgreSQL 的 SQL 语法情形下，outer plan 的根节点是 Groupby 的情况下可以采用这个方式，保留 aggregate 不变，grouping column 与 D 的所有列取并集（其实就是 groupby 列里面加一个 D 的 unique key）。

​

对于 A={∅} 的情况，也就是 scalar aggregation，情况有一些不一样：首先，下推后的 inner join 要改为 outer join；其次，部分聚合函数需要做改写，比如这条 SQL:

SELECT c_custkey, (    SELECT COUNT(*)    FROM ORDERS    WHERE o_custkey = c_custkey) AS count_ordersFROM CUSTOMER;

如果变换之后不对 SQL 做任何更改，SQL 会变成：

SELECT c_custkey, COUNT(*)FROM CUSTOMER LEFT JOIN ORDERS ON o_custkey = c_custkeyGROUP BY c_custkey;

如果某个用户没有任何订单，SQL1 应当返回[c_custkey_1, 0]，但是在 SQL2 中，LEFT JOIN 会首先返回一行[c_custkey_1, NULL]，随后聚合函数返回[c_custkey_1, 1]，与变换前的结果不一致了。

之所以出现这个结果，是因为变换后的 aggregation 无法区分 NULL 是来自于 ORDERS 表还是 LEFT JOIN 产生的结果，因此我们需要通过改写聚合函数来让其区分这两种 NULL，改动也很简单，把 COUNT(*)变为 COUNT(not_null_column)即可，例如这条 SQL，正确的改写是：

SELECT c_custkey, COUNT(o_orderkey) -- 用orders表的主键(not null)代替FROM CUSTOMER LEFT JOIN ORDERS ON o_custkey = c_custkeyGROUP BY c_custkey;

▶︎ Join

outer plan 的根节点是 join 时，根据 join 的类型，有不同的去关联方式，首先是最简单的 inner join:

这里 F( T2 )∩A(D)=∅ 表示 T2 中没有引用 D 中的列，这个规则实际上是做了类似 join reorder 的工作，通过重排 join 顺序让 D 先与有关联项的子查询进行 join，以便进行下一步的去关联。

对于 outer 和 semi join，也有类似的方式。

​

​

还有一些其他的下推规则，在这里因为篇幅原因不做赘述，感兴趣的话可以参考原论文。[2]

4.2 规则运行过程

我们以 TPC-H Q17 的一个简化版本作为例子:

select  COUNT(*)from  lineitem l1where  l_quantity < (    select      avg(l_quantity) as l_avg    from      lineitem l2    where      l1.l_partkey = l2.l_partkey  );

这个查询未经去关联的 plan 如下：

​

我们对这个查询计划应用上文提到的规则：

​

这个例子中，我们通过应用两条规则将 groupby 和 filter 拉到 join 上方之后，关联项被消除，也就完成了子查询的去关联。

4.3 一些例外情况

遍观上文的相关规则，所有的规则都是针对 dependent join 是 inner join 的情形，但是用户 SQL 中其实并不总是这样的 SQL，举一个用户 SQL 简化而来的例子:

SELECT  c1,  (SELECT t2.c2 FROM t2 LEFT JOIN t3 ON t2.c1 = t3.c1 AND t3.c3 = t1.c3 GROUP BY t2.c2)FROM t1;

根据标量子查询的语义，我们可能会转换出如下形状的执行计划：

​

这个计划与文中其他查询有一个都不同的地方：t1 与关联子查询是通过 outer join 连接的，而不是 inner join! 而上文中所有的规则针对的都是 inner join 的情形。这里 IMCI 用了一个很“数学”的方式处理了这个情况：将 semi join 和 left join 转换为上文中的 inner join 即可！IMCI 通过如下方式将这两种 join 转换为 inner join。

下图展示 OuterJoin 的情形，semi 与 anti semi 的 join 的规则与 outer join 几乎没有区别。

​

这里使用了上文引入的 MagicSet，意在加速查询的执行，直接用 Subq X 也可以完成对应的转换。在转换完成之后，之前的 outer join 不再是 dependent join，取而代之，dependent join 变为了下方的 inner join，之后我们就可以通过上文提到的各种转换规则处理这个新生成的子查询，来去掉查询中的所有关联。

结合这些规则，IMCI 几乎能够解决用户场景常见的所有子查询，以下举一个关联子查询的例子:

select   * from   t1 left join t2 on     (t1.a + t2.a =        select          a        from          t3        where          t1.a = t3.a and t2.b = t3.b)

对于这条 SQL，我们先列出初始的执行计划，并且上拉 t3 表上的 filter。

​

这里我们将 Filter 和 Max1Row 检查一起上拉放进了 left join 里面，生成了 left single join，实际上就是在 join 同时做检查：对于 t2 的每一行，最多只有 t3 中的一行能与其匹配。随后把 left outer apply 转换为 inner apply。

​

这里需要注意，LEFT JOIN 的谓词从 t1.a + t2.a = t3.a 变为了 t1.c = X1.c，相当于 t1 natural join MagicSet(X1)。随后我们使用上文中针对 apply 下面含有 left join 的规则，来下推 magic set：

​

5. 未来工作

5.1 基于代价的子查询去关联

对于某些 pattern，可能有不止一种子查询去关联方式，例如以下 SQL。

SELECT c_custkeyFROM customerWHERE 1000000 <      (SELECT SUM(o_totalprice)       FROM orders       WHERE o_custkey = c_custkey)

其可以有两种去关联的方式，第一种是先 group by，再做 join。

SELECT c_custkeyFROM customer,     (SELECT o_custkey, SUM(o_totalprice)      FROM orders      GROUP BY o_custkey      HAVING 1000000 < SUM(o_totalprice)) AS agg_resultWHERE c_custkey = agg_result.o_custkey

另一种则是先做 join，再做 group by。

SELECT c_custkeyFROM customer LEFT JOIN orders ON c_custkey = o_custkeyGROUP BY c_custkeyHAVING 1000000 < SUM(o_totalprice);

这两种不同的算法在不同的数据量下性能差异很大，目前 IMCI 总是选择后者，也就是先 join 再 groupby 的方式进行去关联，因为 LEFT JOIN 可能产生大量数据，因此在部分情况下的效率不够好。后续 IMCI 会通过将这类优化引入到基于代价的查询优化中，通过查询代价从这两种算法中选择更好的那一种。

5.2 按需选择是否子查询去关联

在开头我们讲过，IMCI 直接引入子查询去关联的动机是：

因为目前 IMCI 的查询执行基本不利用索引执行查询，在这个场景下，nested loop join 风格的关联子查询处理效率慢到难以让客户接受。

但是，如果 nested loop join 也变得很快的话，我们就还需要对所有子查询去关联么，举个例子：

SELECT * FROM customer WHERE (SELECT COUNT(*) FROM orders WHERE o_custkey = c_custkey) > 1

如果这个子查询能使用 o_custkey 上建立的二级索引的话，这个 nested loop join 实际上可以很快完成，我们也就不必历经万难消除它了！实际上，index join 正是一种很特殊的关联子查询（子查询的代价很小），后期 IMCI 能够利用索引加速查询之后，我们可以让部分查询以关联子查询的方式直接执行，甚至可以通过构造关联子查询的方式加快查询的执行效率。

5.3 关系代数框架之外的子查询去关联

上文提到的所有涉及到的查询，基本都可以用关系代数表达，但是 SQL 中往往包含一些关系代数无法表达的操作，例如 order by, limit 等等，后续 IMCI 将继续拓展子查询去关联的功能，尽量让所有的关联子查询都能高效的在 IMCI 上执行。

参考文献

[1] Mostafa Elhemali, César A. Galindo-Legaria, Torsten Grabs, and Milind M. Joshi. 2007. Execution strategies for SQL subqueries.

[2] Neumann, Thomas; Kemper, Alfons (2015): Unnesting Arbitrary Queries.

了解更多阿里云瑶池数据库动态，请点击关注阿里云瑶池数据库交流社区，感谢大家的支持！

​