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.