写点什么

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

作者:StoneDB
  • 2022-12-02
    浙江
  • 本文字数:4590 字

    阅读完需:约 15 分钟

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


缘起

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 种,分别是:

  1. DuplicateWeedout,使用临时表针对 join 序列中,join 内表产生的重复部分,做消除处理;内层子查询的表通过在外层表的 rowid 上建立唯一索引来对重复生成的 country 行数据做去重。

  2. FirstMatch,比较好理解,在选中内部表的第 1 条与外表匹配的记录后,就跳过后续的匹配过程,从外层表的下一条记录重新开始,从而也达到了去重的目的。

  3. LooseScan,把 inner-tables 中的第一个表,其数据基于索引进行分组,取每组第一条数据向后做匹配。

  4. 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。


总结

通过子查询优化这个,发现 Tianmu 引擎中部分语句性能慢的原因是优化器还不够完美,相比其他组件,我们目前的优化器可能没做那么精致,虽然我们的大部分语句性能都不错,但是遇到个别复杂语句时性能却不够给力。我们后续会 Tianmu 的 Join order 做优化,敬请期待。

以上就是本次分享,欢迎大家批评指正,我们会持续发布 StoneDB 的研发分享文章,希望能帮助到大家学习数据库和 StoneDB 的相关知识。

作者:段福相

编辑:宇亭

StoneDB 的 2.0 架构完全对标 Oracle MySQL MDS(HeatWave),HeatWave 有多强大?我们后面也会出一篇文章给大家分享一下。目前,我们的架构设计方案的 RFC 文档也完全公布在了 Github 上:

https://github.com/stoneatom/stonedb/issues/436 


如果您想了解更多,也可以关注我们的 Github 仓库:

https://github.com/stoneatom/stonedb


参考链接:

1. 《Semi-join 优化执行代码分析》  

    https://zhuanlan.zhihu.com/p/382416772

2. 《MySQL 是怎样运行的》    第 14 章 基于规则的优化

    https://book.douban.com/subject/35231266/

3. 《数据库查询优化器的艺术》    第 11 章 MySQL 查询优化器概述

    第 12 章 MySQL 查询优化器相关数据结构    https://book.douban.com/subject/25815707/

发布于: 刚刚阅读数: 5
用户头像

StoneDB

关注

https://github.com/stoneatom/stonedb 2022-05-07 加入

企业级一体化实时HTAP开源数据库。 100%兼容MySQL,高性能高可用。 针对热数据、小数据和宽数据的分析加速器。

评论

发布
暂无评论
子查询优化之 Semi-join 优化 | StoneDB 研发分享 #2_MySQL_StoneDB_InfoQ写作社区