SQL 子查询优化详解( 二 ) _子查询

文章插图

实际执行时，查询计划执行器（Executor）在执行到 Filter 时，调用表达式执行器（Evaluator）；由于这个条件表达式中包含一个标量子查询，所以 Evaluator 又会调用 Executor 计算标量子查询的结果。
这种 Executor - Evaluator - Executor 的交替调用十分低效！考虑到 Filter 上可能会有上百万行数据经过，如果为每行数据都执行一次子查询，那查询执行的总时长显然是不可接受的。
Apply 算子上文说到的 Relation - Expression - Relation 这种交替引用不仅执行性能堪忧，而且，对于优化器也是个麻烦的存在——我们的优化规则都是在匹配并且对 Relation 进行变换，而这里的子查询却藏在 Expression 里，令人无从下手。
为此，在开始去关联化之前，我们引入 Apply 算子：
Apply 算子（也称作 Correlated Join）接收两个关系树的输入，与一般 Join 不同的是，Apply 的 Inner 输入（图中是右子树）是一个带有参数的关系树。
Apply 的含义用下图右半部分的集合表达式定义：对于 Outer Relation RR 中的每一条数据 rr，计算 Inner Relation E(r)E(r)，输出它们连接（Join）起来的结果 r⊗E(r)r⊗E(r) 。Apply 的结果是所有这些结果的并集（本文中说的并集指的是 Bag 语义下的并集，也就是 UNION ALL）。

文章插图

Apply 是 SQL Server 的命名，它在 HyPer 的文章中叫做 Correlated Join 。它们是完全等价的。考虑到 SQL Server 的文章发表更早、影响更广，本文中都沿用它的命名。

根据连接方式（⊗⊗）的不同，Apply 又有 4 种形式：

Cross Apply A×A×：这是最基本的形式，行为刚刚我们已经描述过了；
Left Outer Apply ALOJALOJ：即使 E(r)E(r) 为空，也生成一个 r°{NULLs}r°{NULLs} 。
Semi Apply A∃A∃：如果 E(r)E(r) 不为空则返回 rr，否则丢弃；
Anti-Semi Apply A?A?：如果 E(r)E(r) 为空则返回 rr，否则丢弃；

我们用刚刚定义的 Apply 算子来改写之前的例子：把子查询从 Expression 内部提取出来。结果如下：

文章插图

上面的例子中，我们可以肯定 Scalar Agg 子查询有且只有一行结果，所以可以直接转成 Apply 。但某些情况下，可能无法肯定子查询一定能返回 0 或 1 行结果（例如，想象一下 Query 2 如果 c_custkey 不是唯一的），为了确保 SQL 语义，还要在 Apply 右边加一个 Max1RowMax1Row 算子：
Max1Row(E)=?????Null,E,error,if |E|=0if |E|=1otherwiseMax1Row(E)={Null,if |E|=0E,if |E|=1error,otherwise
理论上，我们可以将所有的子查询转换成 Apply 算子，一个通用的方法如下：

如果某个算子的表达式中出现了子查询，我们就把这个子查询提取到该算子下面（留下一个子查询的结果变量），构成一个 ALOJALOJ 算子。如果不止一个子查询，则会产生多个 ALOJALOJ 。必要的时候加上 Max1RowMax1Row 算子。
然后应用其他一些规则，将 ALOJALOJ 转换成 A×A×、A∃A∃、A?A? 。例如上面例子中的子查询结果 XX 被用作 Filter 的过滤条件，NULL 值会被过滤掉，因此可以安全地转换成 A×A× 。

下面这个例子中，Filter 条件表达式中包含 Q1Q1、Q2Q2 两个子查询。转换之后分别生成了对应的 Apply 算子。其中 Q2Q2 无法确定只会生成恰好一条记录，所以还加上了 Max1RowMax1Row 算子。