OB小优系列文章 | 聚合类相关子查询提升(上)

OB君:查询优化器是关系数据库系统的核心模块,也是衡量整个数据库系统成熟度的“试金石”。OceanBase的查询优化器历经了九年多时间的磨练,逐步提炼出一套独有的工程实践哲学。本系列文章将重点介绍聚合类相关子查询的改写机制,欢迎探讨~

传送门:

OB小优系列(一):OceanBase查询优化器的设计之道和工程实践
OB小优系列(二):OceanBase并行执行引擎实现
OB小优系列(三):OceanBase查询改写的最佳实践

引言

使用子查询可以让用户简洁明了地写出含义清晰的复杂SQL语句。这个功能对用户而言是非常友好的,但是对数据库而言是很不友好的。从数据库角度而言,处理子查询是相对低效的。为了改进子查询的处理,数据库系统通常会尝试改写SQL,消除子查询。业务中常见的子查询包含以下几种:

  • 非相关的子查询。这类子查询的计算完全不依赖主查询。它可以被独立的计算。通常,这类查询直接被提升为主查询中的一个视图。
  • SPJ (SELECT-PROJECT-JOIN) 类相关子查询。这类查询通常被改写为 SEMI / ANTI JOIN。

SPJ 相关子查询的处理难度是高于非相关查询的。而比前者更加复杂的一类查询是:聚合类相关子查询。本系列文章重点介绍这类子查询的改写机制(简称为 JA 改写)。

场景介绍

S 君开了一家影院,生意红火。某一天,S 君想进一步改善影院的业绩,想要知道哪些场次票价相对偏低。

OB小优系列文章 | 聚合类相关子查询提升(上)

为此,S 君写了下面这条查询。他用一个子查询统计了一部电影的平均售价,然后找出定价偏低的排片场次有哪些。PLAY表记录所有电影的排片信息;TICKETS 表记录了所有的售票信息。

Q1:
SELECT * FROM PLAY P WHERE price <
(SELECT AVG(price) FROM TICKETS T WHERE T.film = P.film);

当 S 君执行这条查询的时候,发现等了一分钟都没有获得结果。万分焦急的 S 君向经验丰富的 OB 君求助:为什么这么简单的查询执行的这么慢?

OB 君发现这条查询是一个“聚合类相关子查询”(简称为 JA 子查询,Join Aggregation)。这类查询的主要特征是:用户使用一个相关的子查询来计算一个统计值,然后利用该统计值来对主查询的结果进行过滤。

OB 君分析了这两张表的情况,不禁感叹这家影院业绩真是不错。他向 S 君解释道:你的影院效益太好,PLAY 表里排片有 10K+ ,每个排片都要算一次电影的平均售价,影院总共也就上映了100场电影,票却售出了5M 张,平均每部电影就售出了 50 K 张票,那么这条查询逻辑上要访问 10K * 50K = 500 M 才能算出结果,一分钟怎么可能算得出结果。X 君请求 OB 君帮个忙改进一下这条查询。OB 君祭出了一招:JA改写第一式,写下了查询Q2。

Q2:
SELECT * FROM PLAY P,
(SELECT film, AVG(price) as avg_price FROM TICKETS T GROUP BY film) V
WHERE P.film = V.film AND P.price < V.avg_price;

改写理念

S 君仔细分析 Q1,发现这条查询是针对PLAY中的每一行,都需要去执行一次TICKETS上的聚合查询 Q3(其中 ?的取值由P.film决定)。

Q3:
SELECT AVG(price) FROM TICKETS T WHERE T.film = ?;

在这个场景中, film 的取值数量并不多。根据 film 的取值不同,Q3 实际生成的不同查询只有 100 个。但这个 100 个参数不同的查询却会被反复执行 10K+ 次。OB 君给的优化方式是:用一个分组查询提前算出所有影片的平均售价,之后主查询需要使用不同的统计值时,可以直接从提前计算的结果中获得。Q2 中的视图 V 实现了这个效果,它只需要扫描一遍 TICKETS 表就可以获得所有电影的平均售价。

Q2 中的视图 V: SELECT film, AVG(price) as avg_price FROM TICKETS T GROUP BY film;

之后,Q2只需要将PLAY和V按照film连接,就可以快速找出哪些排片的平均售价偏低了。从 Q1 -> Q2 的改写是将一个聚合类的相关子查询改写成了一次分组(GROUP BY) + 一次连接(JOIN)。改写后的查询预期需要扫描PLAY表和TICKETS表各一次,总计 5M + 行的记录;最后执行一次 100 : 10K 的内连接。相对于原始查询 500 M+ 的预期数据访问量,执行效率会有巨大的提升。假如这两张表上有film字段的索引,那么还能利用索引加速聚合和连接的运算效率。

  1. 如果 PLAY 和 TICKETS 在 film 上有索引,我们可以使用 merge aggregation来优化视图 V 的计算,使用 merge join 来处理 P 与 V 的连接。
  2. 如果 PLAY 上有 (film, price) 的索引,可以先计算 V 的结果,然后使用 nest loop join 将 P.film = V.film AND P.price < V.avg_price 转换为 PLAY 上的过滤条件,利用 index scan 大大减少 PLAY 的扫描量。
  3. 即便没有合适的索引,我们依然可以使用 hash join 来计算 PLAY 与 V 的连接。

可以看到,改写后的 SQL 在计划选择上有了更大空间。原始的 Q1 查询中,我们只能利用主查询中的 PLAY 来驱动子查询的计算,本质上是一个 NEST LOOP JOIN 的过程。在改写后,我们可以采用更多的 JOIN 的算法,甚至可以利用子查询提升产生的视图来驱动主查询中的表进行连接。

总结

JA 改写第一式能够很有效的提升聚合类子查询的处理效率。但它并不是总是适用的。通常我们认为它有两个主要的局限性:

  1. 假如T.film = P.film对TICKETS T表有很强的过滤性,但是改写后的查询并不能利用这个条件来减少 T 表的扫描量;
  2. 相关条件必须是等值条件,如果是T.film != P.film这样的非等值条件,JA 改写是不能处理的。

在下一篇文章中,我们会介绍JA改写第二式,它能够很好的处理以上这两个问题。

We are Hiring!

OceanBase 九年如一日,不忘初心,砥砺前行,致力于实现一个中国人完全自主设计的分布式通用数据库系统,打破西方大厂在商业数据库领域的绝对垄断地位。时至今日,OceanBase 已经成功应用于蚂蚁金服的交易、支付、账务等核心系统和网商银行、印度Paytm等业务系统。

非常欢迎有志于让中国的政府和企业用上中国人自己的通用商业数据库的同学加入我们,一起为实现这一目标而共同努力!发送简历到 OceanBase-Public@list.alibaba-inc.com,我们等的就是你!

OceanBase 技术交流群

— 想了解更多OceanBase背后的技术秘密?

— 想与蚂蚁金服OceanBase的技术专家深入交流?

— 加入OceanBase钉钉互动群:搜索群号21949783