子查询优化之 Semi-join 优化 | StoneDB 研发分享 #2

缘起

StoneDB 在列式存储引擎 Tianmu 的加持下，在大多数场景下相对 MySQL 都会有大幅性能提升。当然，这是需要工程师不断优化代码才能做到的，而且，性能好也需要通过基准测试才有说服力，所以我们也会针对 TPC-H 的测试语句进行测试排查，争取不断提升 StoneDB 的性能。本文主要讲解对 TPCH_Q4 的分析优化，在这个优化过程中，我们涉及到了对子查询中的 Semi-join 优化。
首先看一下 Q4 的查询语句，比较简单：

1. explain
2. select o_orderpriority,
3.        count(*) as order_count
4. from orders
5. where o_orderdate >= date'1993-07-01'
6.   and o_orderdate < date'1993-07-01' + interval'3'month
7.   andexists(
8.         select *
9.         from lineitem
10.         where l_orderkey = o_orderkey
11.           and l_commitdate < l_receiptdate
12.     )
13. groupby o_orderpriority
14. orderby o_orderpriority;

复制代码

可以看到，这个语句中只有两个查询表, 4 个谓词条件，特点是在子查询中使用了外表的字段，我们也管这种叫做相关子查询，而在驱动表里则使用了聚合。
这里科普一下，驱动表（Driving Table），也称外层表（Outer Table）,顾名思义，驱动表是用来驱动查询的。驱动表仅仅用于 Nested-Loop Join 和 Hash Join，简单来说，就是用来最先获得数据，并以此表的数据为依据，逐步获得其他表的数据，直至最终查询到所有满足条件的数据的第一个表。
介绍完简单的语句之后，说下我们在这里的优化方案。
常见的子查询优化

子查询合并：如果两个查询块语义等价，则能够将其合并成一个子查询，这样多次 TableScan、TableJoin 都可以消减为单表的 Scan、Join。
子查询展开：又称为子查询上拉，把子查询的查询谓词和表提到上层中，变为 join 操作，这样子查询就不存在了，连接方法和连接顺序也可以随意调整了，如 Nested-Loop Join 可以换成 Hash Join 等等，我们的 Q4 也就是通过这种方式进行优化的。
针对 Q4 的优化方案

上一段也有说到，针对 Q4，我们需要是子查询展开优化。就是将子查询重写为同语义的 Semi-join(半连接), 然后执行 Semi-join 即可。
mysql 的子查询展开代码流程

resolve_subquery :对subqueryitem进行解析，收集能够unnesting为semi-join的所有subqueryblock，这里有很多的严格限制条件(mysql5.7有11个限制条件)，基本来说就是只允许 SPJ 的 subquery 进行 unnesting，具体条件可详见函数中的代码及注释。可以做 unnesting，会把这个 subquery 的 item 对象，加入到外层 select_lex::sj_candidates 中后续使用，无法做 unnesting 的，则调用 select_transformer，尝试做 IN->EXIST 的转换。
convert_subquery_to_semijoin: 将真正可以展开的(内层有 table)，建立 sj-nest 这个 TABLE_LIST 对象， 基本思路就是想将 inner table 放到外层的 Join list 中， 内层的谓词条件都放在外层对应的 ON/WHERE 条件上。sj-nest 是后续优化 Semi-join 的一个重要结构，会用子查询 SELECT_LEX 中的内容对其进行填充。
我们的优化方案

首先是 MySQL-5.7 只展开 in 子查询，无法展开 exists 子查询，而我们的 Q4 就是一个 exists 子查询；再者我们的 Tianmu 查询引擎目前没有执行 Semi-join 流程，所以即使是 in 子查询也无法在 tianmu 引擎中执行。所以我们的优化方案也就不言自明了，首先在 MySQL-5.7 增加针对 exists 子查询展开的这个 case，然后让我们的 tianmu 引擎能够执行 semi-join。
优化器改写

我们的 exists 语句改写参照 in 语句进行的，但是跟 in 语句稍有不同。首先 resolve_subquery 函数中，判断是 exists 则不进行转换，这里我们把他加回来；resolve_subquery只是进行的判断，是否能够转换，真正的转换操作是在 convert_subquery_to_semijoin 函数中进行的，在 convert_subquery_to_semijoin 中，我们把子查询所有用到的表上提到 sj_nest，把所有的谓词上提到 sj_cond, in 子查询因为 in 子查询是一个谓词，所以需要针对谓词进行单独处理，exists 则不需要，直接上提。但是这里我们还需要做一个操作，就是把子查询中用到的外表的表达式放到 sj_outer_exprs 中，所有用到内表的表达式放到 sj_inner_exprs 中，这个 mysql 的执行器或者 tianmu 执行器都会用到。我们可以使用 EXPLAIN 语句在查询、调试我们优化后的语句：

1. select`tpch_db`.`orders`.`o_orderpriority`AS`o_orderpriority`, count(0) AS`order_count`
2. from`tpch_db`.`orders`semi
3.          join (`tpch_db`.`lineitem`)
4. where ((`tpch_db`.`lineitem`.`l_orderkey` = `tpch_db`.`orders`.`o_orderkey`) and
5.        (`tpch_db`.`orders`.`o_orderdate` >= DATE'1993-07-01') and
6.        (`tpch_db`.`orders`.`o_orderdate` < < cache > ((DATE'1993-07-01' + interval'3'month))) and
7.        (`tpch_db`.`lineitem`.`l_commitdate` < `tpch_db`.`lineitem`.`l_receiptdate`))
8. groupby`tpch_db`.`orders`.`o_orderpriority`
9. orderby`tpch_db`.`orders`.`o_orderpriority`limit100;
10. 子查询被成功上提到外层查询中，接下来只要能够正确执行 Semi-join 就大功告成了。

复制代码

Semi-join 的执行策略

MySQL 的 Semi-join 执行策略

Semi-join 的执行概括来看就是想办法把内层的查询进行去重。在写我们自己的 Semi-join 执行前，我们先学习一下 MySQL 中执行的方式，主要有 4 种，分别是：
DuplicateWeedout，使用临时表针对 join 序列中，join 内表产生的重复部分，做消除处理；内层子查询的表通过在外层表的 rowid 上建立唯一索引来对重复生成的 country 行数据做去重。
FirstMatch，比较好理解，在选中内部表的第 1 条与外表匹配的记录后，就跳过后续的匹配过程，从外层表的下一条记录重新开始，从而也达到了去重的目的。
LooseScan，把 inner-tables 中的第一个表，其数据基于索引进行分组，取每组第一条数据向后做匹配。
Materialize，这个是想法上最直观的，通过将 inner-table 去重，并固化成临时表，遍历 outer-table，然后在固化表上去寻找匹配。
Tianmu 的 Semi-join 执行策略选择

根据我们的执行引擎特点，最后决定使用实现 DuplicateWeedout 和 Materialize 两种执行策略。
因为 Tianmu 是列存，内部没有 row by row 的执行流程，所以放弃了 FirstMatch；而且只有主键，没有索引， LooseScan 其实主要使用索引，所以也放弃这一方案了。
DuplicateWeedout

DuplicateWeedout 方式其实相对比较容易实现，可以复用现有的 inner-join 执行流程，其实 semi-join 跟 inner-join 的主要区别就内表的去重，这个确实是我们的难点，因为 mysql 这里使用了，默认主键(rowid)来进行内表的去重，而我们的此概念，所以在这里我们又增加一个限制，就是给必须外表必须包含主键，才能子查询展开。另外一个难点是我们的 group by 处理，因为我们 group by 和 distinct 是同一个算子，而且做不到先去重后聚合这种操作，所以这里我们增加了一个临时表，专门用来去重，然后再分组聚合，这里又会遇到新的问题，因为 SPJ 和 非 SPJ 语句用到的 Field 是不同的， 例如我们需要将 count(*), min(xxx),avg(xxx) 等 Field 中聚合去掉，保留原始 Field, 然后等去重之后，再添加聚合属性。细节处理很多，大家可以直接看代码。
我们来看一个具体例子：
[code]add query table: ./test_db/ordersadd query table: ./test_db/lineitemT:-1 = TABLE_ALIAS(T:1,"lineitem")T:-2 = TMP_TABLE(T:-1,T:4294967293)                              // -> for distinct tmp tableT:-3 = TABLE_ALIAS(T:0,"orders")VC:-2.0 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:5))A:-1 = T:-2.ADD_COLUMN(VC:-2.0,LIST,"o_orderpriority","ALL")VC:-2.1 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:0))A:-2 = T:-2.ADD_COLUMN(VC:-2.1,LIST,"o_orderkey","ALL")VC:-2.2 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:4))VC:-2.3 = CREATE_VC(T:-2,EXPR("date_literal"))C:0 = CREATE_CONDS(T:-2,VC:-2.2,>=,VC:-2.3,)VC:-2.4 = CREATE_VC(T:-2,EXPR("date_add_interval"))C:0.AND(VC:-2.2,