Subquery? No, it’s join!

在 SQL 查询中，子查询是一种常用的技能，它允许咱们在一个查询内部嵌套另一个查询，以完成更复杂的数据检索和分析。怎么在数据库内核中高效的处理子查询是非常有应战的，本文将介绍怎么在 Databend 中构建 state-of-art 的子查询 optimizer。

从广泛的角度，子查询分为相关和非相关子查询, 细分的品种包括：SCALAR/ANY/ALL/SOME/(NOT)IN/(NOT)EXISTS. 对于每一种子查询的意义，读者能够参考:www.postgresql.org/docs/curren…。尽管子查询有这么多种，但是在 Databend 中，咱们只需求处理 SCALAR/EXISTS/ANY 三种子查询，由于在 binder 阶段，能够做如下 SQL 语义等价转换:

• in=>= any(...)
• i > all()=>not(i <= any(...))
• some=>any

子查询几乎能够出现在 SQL 的任何位置，如from/where/select/group by/having/order by, 外加相关子查询的存在，所以处理子查询变得具有应战性，在深化子查询之前，先介绍一下 Databend 为了高效处理子查询 而引进的非标准 join 类型：single join和mark join。

• single join: single join 的存在是为了处理 scalar 子查询，left single join 与 left outer join 相似，但是假如超越一个 join partner 被发现就会报错，这点对应 scalar 子查询只发生一列且最多一行结果。
• mark join: mark join 引进了一个新的特点：mark, 用来符号 tuple 是否有 join partner. 其值能够是TRUE, FALSE, NULL, 能够用来处理 ANY/EXISTS 子查询

有了这两种非标准 join， 咱们能够确保所有的子查询在经过子查询 optimizer 后已经悉数转化为 join, 这为 join reorder 供给了更多的或许，能够大幅降低履行代价。

非相关子查询

非相关子查询的处理相对简略，只需求做简略的变换即可。下面经过几个简略的比如来看一下怎么展开非相关子查询:

非相关 scalar 子查询select number, (select number from numbers(10) as t2 where number > 3 limit 1) from numbers(10) as t1， 直接用 single join 即可

非相关 exists 子查询select number, exists(select * from numbers(10) as t2 where number > 3) from numbers(10) as t1;, 给子查询加上limit 1,count(*)和count(*) = 1operator, 其间limit 1能够使查询更加高效，由于只需求判断是否存在即可

非相关 any 子查询select number from numbers(10) as t1 where number > any(select number from numbers(20) as t2) or number > 1;， 在这条 SQL 中，由于包括 disjunction predicate，所以不能用 semi join 来对转化子查询，mark join 的 mark 列将替换子查询 =>marker or number > 1 非相关 any 子查询select number from numbers(10) as t1 where number > any(select number from numbers(20) as t2) or number > 1;， 在这条 SQL 中，由于包括 disjunction predicate，所以不能用 semi join 来对转化子查询，mark join 的 mark 列将替换子查询 =>marker or number > 1

相关子查询

在介绍相关子查询前，需求引进dependent join, dependent join 会为 LHS 中的每一行履行一次 RHS

中心思维在于怎么消除 dependent join 中的 correlated columns?

下面经过一条 ANY 相关子查询来看一下是怎么去相关的

select a from t1 where a > any(select b from t2 where t1.a < 1) or a > 1;

mysql> desc t1;
+-------+-----------------+------+---------+-------+
| Field | Type            | Null | Default | Extra |
+-------+-----------------+------+---------+-------+
| a     | BIGINT UNSIGNED | NO   | 0       |       |
+-------+-----------------+------+---------+-------+
1 row in set (0.03 sec)
Read 0 rows, 0.00 B in 0.015 sec., 0 rows/sec., 0.00 B/sec.
mysql> desc t2;
+-------+-----------------+------+---------+-------+
| Field | Type            | Null | Default | Extra |
+-------+-----------------+------+---------+-------+
| b     | BIGINT UNSIGNED | NO   | 0       |       |
+-------+-----------------+------+---------+-------+
1 row in set (0.03 sec)
Read 0 rows, 0.00 B in 0.017 sec., 0 rows/sec., 0.00 B/sec.

子查询中包括 correlated columnt1.a, 中心的一步便是对子查询中的表进行扩展(cross join)，t2 x t1(a) , 扩展后的子查询自然就完成了去相关。

扩展后的表假定叫 t3 包括两列(b, a’), t3 会与 t1 进行 mark join, 返回 (t1.a, mark) 两列，mark 列用于 filter:mark or a > 1中，对 mark join 后的结果进行进一步过滤

这儿需求留意的是 mark join 的 equi condition 和 non-equi condition.

至此，子查询处理的中心思维已经介绍完了。还有许多工程上的优化和特殊情况就不展开讲述了，比如

1. 怎么正确的处理 NULL, 特别是在 mark join 的完成中，NULL 的正确处理对子查询结果的正确性非常重要
2. 在对子查询中的表进行拓宽时，直接 cross join 有一定的开销，能否防止 cross join?
3. mark join 在什么情况下能够转化为 semi join?
4. ……

纵观全文，所有的子查询最终的形状都是 join, 所以 join 的功能很大程度上决议了子查询的功能，下一篇咱们讲一讲 Databend join 从 0 到 1 的一个迭代进程。