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 t1
WHERE
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 tmp
WHERE
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_orders
FROM CUSTOMER;如果变换之后不对 SQL 做任何更改，SQL 会变成：
SELECT c_custkey, COUNT(*)
FROM CUSTOMER LEFT JOIN ORDERS ON o_custkey = c_custkey
GROUP 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_custkey
GROUP 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 l1
where
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_custkey
FROM customer
WHERE 1000000 <
(SELECT SUM(o_totalprice)
FROM orders
WHERE o_custkey = c_custkey)
其能够有两种去关联的形式，第一种是先 group by，再做 join。
SELECT c_custkey
FROM customer,
(SELECT o_custkey, SUM(o_totalprice)
FROM orders
GROUP BY o_custkey
HAVING 1000000 < SUM(o_totalprice)) AS agg_result
WHERE c_custkey = agg_result.o_custkey
另一种则是先做 join，再做 group by。
SELECT c_custkey
FROM customer LEFT JOIN orders ON c_custkey = o_custkey
GROUP BY c_custkey
HAVING 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.