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

2022-12-02
浙江
本文字数：4590 字
阅读完需：约 15 分钟

缘起

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

首先看一下 Q4 的查询语句，比较简单：

explainselect o_orderpriority,       count(*) as order_countfrom orderswhere o_orderdate >= date'1993-07-01'  and o_orderdate < date'1993-07-01' + interval'3'month  andexists(        select *        from lineitem        where l_orderkey = o_orderkey          and l_commitdate < l_receiptdate    )groupby o_orderpriorityorderby 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 语句在查询、调试我们优化后的语句：

select`tpch_db`.`orders`.`o_orderpriority`AS`o_orderpriority`, count(0) AS`order_count`from`tpch_db`.`orders`semi         join (`tpch_db`.`lineitem`)where ((`tpch_db`.`lineitem`.`l_orderkey` = `tpch_db`.`orders`.`o_orderkey`) and       (`tpch_db`.`orders`.`o_orderdate` >= DATE'1993-07-01') and       (`tpch_db`.`orders`.`o_orderdate` < < cache > ((DATE'1993-07-01' + interval'3'month))) and       (`tpch_db`.`lineitem`.`l_commitdate` < `tpch_db`.`lineitem`.`l_receiptdate`))groupby`tpch_db`.`orders`.`o_orderpriority`orderby`tpch_db`.`orders`.`o_orderpriority`limit100;

复制代码

子查询被成功上提到外层查询中，接下来只要能够正确执行 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, 然后等去重之后，再添加聚合属性。细节处理很多，大家可以直接看代码。

我们来看一个具体例子：

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,<null>)VC:-2.4 = CREATE_VC(T:-2,EXPR("date_add_interval"))C:0.AND(VC:-2.2,<,VC:-2.4,<null>)VC:-2.5 = CREATE_VC(T:-2,EXPR("1"))VC:-2.6 = CREATE_VC(T:-2,EXPR("0"))C:0.AND(VC:-2.5,<>,VC:-2.6,<null>)VC:-2.7 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:11))VC:-2.8 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:12))C:0.AND(VC:-2.7,<,VC:-2.8,<null>)VC:-2.9 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:0))C:1 = CREATE_CONDS(T:-2,VC:-2.1,=,VC:-2.9,<null>)C:0.AND(C:1)T:-2.ADD_CONDS(C:0,WHERE)T:-2.APPLY_CONDS()T:-2.MODE(DISTINCT,0,0)T:-4 = TMP_TABLE(T:4294967294)                                   // -> for group by tmp tableVC:-4.0 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))A:-1 = T:-4.ADD_COLUMN(VC:-4.0,LIST,"o_orderpriority","ALL")A:-2 = T:-4.ADD_COLUMN(<null>,COUNT,"order_count","ALL")VC:-4.1 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))A:-3 = T:-4.ADD_COLUMN(VC:-4.1,GROUP_BY,"null","ALL")VC:-4.2 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))A:-4 = T:-4.ADD_COLUMN(VC:-4.2,LIST,"null","ALL")VC:-4.3 = CREATE_VC(T:-4,PHYS_COL(T:-4,A:-4))T:-4.ADD_ORDER(VC:-4.3,ASC)RESULT(T:-4)

复制代码

从例子中我们可以看到，T:-2 这个临时表是用来去重的，T:-4 这个临时表是用来聚合的，最后物化的结果集也是 T:-4 这个临时表。

Materialize

Materialize 方式是直接将内表进行物化，当然如果内表包含相关条件，则无法直接进行物化，这里需要把需要相关条件提出来，变成外表的 join 条件，注意这里执行器需要 join 的表换成我们为内表创建的临时表，而不是原来的物理表。这种执行方式不是有必须包含主键的限制，但是他有两个问题，首先是他走了两遍查询流程，比 DuplicateWeedout 要慢，然后就是相关条件的提取非常困难，目前还是无法在所有场景下都支持，所以最后的代码中没有包含使用 Materialize 方式的代码，后续如果必须有主键这个限制很大，我们会考虑把 Materialize 的方式加回来，但是肯定是能使用 DuplicateWeedout，优先使用 DuplicateWeedout。