您的位置:  首页 > 技术杂谈 > 正文

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

2022-12-02 18:00 https://my.oschina.net/StoneDB/blog/5602922 StoneDB 次阅读 条评论

缘起

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

首先看一下 Q4 的查询语句,比较简单:

explain
select o_orderpriority,
count(*) as order_count
from orders
where o_orderdate >= date '1993-07-01'
and o_orderdate < date '1993-07-01' + interval '3' month
and exists(
select *
from lineitem
where l_orderkey = o_orderkey
and l_commitdate < l_receiptdate
)
group by o_orderpriority
order by 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`))
group by `tpch_db`.`orders`.`o_orderpriority`
order by `tpch_db`.`orders`.`o_orderpriority` limit 100;

子查询被成功上提到外层查询中,接下来只要能够正确执行 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/orders
add query table: ./test_db/lineitem
T:-1 = TABLE_ALIAS(T:1,"lineitem")
T:-2 = TMP_TABLE(T:-1,T:4294967293) // -> for distinct tmp table
T:-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 table
VC:-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 的相关知识。

作者:段福相

编辑:宇亭

参考链接:

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/

扫码添加小助手

加入StoneDB开源社区用户群

讨论交流,共同进步

HTAP 的下一步?SoTP 初探(下):解读 Serving over TP 和其典型案例场景

2023 年十大战略技术趋势中哪一项最需要 HTAP ?

HTAP 的下一步?SoTP 初探

存算一体 VS 存算分离 ,IT发展下的技术迭代

没有HTAP,机器学习和人工智能都是不切实际的 

面向场景,HTAP到底是刚需还是炒作?

StoneDB 团队成员与 MySQL 之父 Monty 会面,共话未来数据库形态

HTAP的关键技术有哪些?| StoneDB学术分享会

解读《Benchmarking Hybrid OLTP&OLAP Database Systems》| StoneDB学术分享会

深度干货!一篇Paper带您读懂HTAP | StoneDB学术分享会

本文分享自微信公众号 - StoneDB(StoneDB2021)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
  • 0
    感动
  • 0
    路过
  • 0
    高兴
  • 0
    难过
  • 0
    搞笑
  • 0
    无聊
  • 0
    愤怒
  • 0
    同情
热度排行
友情链接