系列文章导读
OceanBase 是100% 自主研发,连续7年稳定支撑双11,创新推出“三地五中心”城市级容灾新标准,是全球唯一在 TPC-C 和 TPC-H 测试上都刷新了世界纪录的国产原生分布式数据库,于 2021 年 6 月份正式开放源代码。查询优化器是关系数据库系统的核心模块,是数据库内核开发的重点和难点,也是衡量整个数据库系统成熟度的“试金石”。为了帮助大家更好地理解 OceanBase 查询优化器,我们将撰写查询改写系列文章,带大家更好地掌握查询改写的精髓,熟悉复杂 SQL 的等价性,写出高效的 SQL。本文是 OceanBase 改写系列第三篇,将重点介绍聚合类相关子查询的改写机制,欢迎探讨~进入【SQL 改写专题】 查看系列内容
专栏作者介绍
OceanBase 优化器团队,由 OceanBase 高级技术专家溪峰、技术专家山文等领衔,致力于打造全球领先的分布式查询优化器。
系列内容构成
本次查询改写系列不仅包括子查询优化、聚合函数优化、 窗口函数优化、 复杂表达式优化四大模块,还有更多模块内容,敬请期待,欢迎关注 OceanBase 开源用户群 (钉钉号:3325 4054),进群与 OceanBase 查询优化器团队一同交流。
一、 引言
上一期文章《子查询提升首篇》中我们提到了子查询通常有两类,第一类子查询返回的结果是一个集合,第二类子查询返回的结果是一个具体的值。针对第一类子查询,上一期文章介绍了第一类的改写提升。本期文章我们将介绍一种针对第二类子查询的改写方式。
第二类改写——子查询结果只返回一个值,往往很容易联想到聚合函数, Q1就是一个典型的例子。这种子查询的使用方式在业务 SQL 中也非常常见。这里,给定一张 PLAY 表,表中记录了所有电影的排片信息,一张 TICKETS 记录了所有的实际售票信息,Q1 查出了所有票价低于该影片平均售价的场次。
-- 影片表 MOVIE(movie_id, movie_name, release_date) -- 排片表 PLAY(play_id, movie_id, time, price, seats) -- 售票表 TICKETS(play_id, movie_id, real_price, sale_date); Q1: SELECT * FROM PLAY P WHERE P.price < (SELECT AVG(T.real_price) FROM TICKETS T WHERE T.movie_id = P.movie_id);
这条 SQL 执行时,执行引擎会迭代 PLAY
中的每一行,待其获得 PLAY.movie_id
后,填到子查询中,计算聚合函数 AVG(TICKETS.real_price)
,最后判断过滤条件是否满足。本质上,这个过程类似于一次 NEST-LOOP Join。子查询的计算次数取决于 PLAY
的行数。
我们不难发现,Q1有两个主要特点:
1. 它是一个相关子查询,引用了外层的列;
2. 它不是一个简单的 SPJ 查询,它的投影项中包含一个聚合函数用来计算一个统计值。
这一类子查询 OceanBase 称之为聚合类相关子查询,并引入了聚合类子查询提升来改写这一类 SQL。
二、聚合优先的聚合类子查询提升
以电影排片为例,我们知道通常一部影片会排很多的场次,也就是说在排片表PLAY
中movie_id
会包含很多重复的值。仔细观察 Q1,我们不难发现,对于PLAY.movie_id
相同的记录,子查询会被反复计算,并且这些子查询的计算结果都相同。针对这种情况,一个自然的想法是对于PLAY.movie_id
相同记录,子查询能不能只计算一次?基于这种思路,OceanBase 会将上述 Q1 的查询改写成 Q2 的形式。
Q2: SELECT P.* FROM PLAY P, (SELECT movie_id, AVG(real_price) AS avg_price FROM TICKETS T GROUP BY movie_id) V WHERE P.movie_id = V.movie_id AND P.price < V.avg_price;
在 Q2 中,我们使用了一个分组查询提前算出了每一部影片的平均票价,之后主查询需要使用不同的统计值时,可以直接从提前聚合出的结果中获得。Q2 中的视图 V 实现了这个效果,它只需要扫描一遍 TICKETS
表就可以获得所有电影的平均售价。之后 Q2 只需要将 PLAY
和 V
按照 movie_id 连接,就可以快速找出哪些排片的平均售价偏低了。
Q2 中的视图 V: SELECT movie_id, AVG(real_price) AS avg_price FROM TICKETS T GROUP BY movie_id;
从 Q1 到 Q2 的改写是将一个聚合类相关子查询改写成了一次分组(GROUP BY) + 一次连接(JOIN)。因为改写后的 SQL 是先做分组聚合,再做连接,因此我们称之为聚合优先的聚合类子查询提升。改写后的查询预期需要扫描 PLAY
表和 TICKETS
表各一次。这种改写有以下好处:
1.如果 PLAY
和 TICKETS
在 movie_id
上有索引,我们可以使用 merge aggregation 来优化视图 V 的计算,使用 merge join 来处理 PLAY
与 V 的连接。
2.如果 PLAY
上有 (movie_id, price)
的索引,可以使用V
作为驱动表,然后使用 NEST-LOOP JOIN将 P.movie_id = V.movie_id AND P.price < V.avg_price
转换为 PLAY
上的过滤条件,利用 index scan 大大减少 PLAY
的扫描量。
3.即便没有合适的索引,我们依然可以使用 HASH JOIN 来计算 PLAY
与 V
的连接。
可以看到,改写后的 SQL 在计划选择上有了更大空间。原始的 Q1 查询中,我们只能利用主查询中的 PLAY
来驱动子查询的计算,本质上是一个 NEST LOOP JOIN 的过程。在改写后,我们可以采用更多的 JOIN 的算法,甚至可以利用子查询提升产生的视图来驱动主查询中的表进行连接。
2.1 一个改写小陷阱
接下来我们再来看一个特殊的例子,Q3 这条 SQL 查出了所有落座率低于50%的场次。如果我们参考 Q2 对这条 SQL 进行改写,会得到形如 Q4 的 SQL。实际上 Q4 与Q3 并不是完全等价的,这是聚合类子查询提升的一个陷阱。
Q3: SELECT * FROM PLAY P WHERE p.seats * 0.5 > (SELECT count(*) FROM TICKETS T WHERE T.play_id = P.play_id); Q4: SELECT P.* FROM PLAY P, (SELECT play_id, count(*) AS cnt FROM TICKETS T GROUP BY play_id) V WHERE P.play_id = V.play_id AND P.seats * 0.5 > V.cnt;
我们考虑一种极端的情况,某场电影一张票都没有卖出去,那么这场电影的落座率就是0%,显然应该把这个场次输出到结果中。
- 在Q3中,这个场次在子查询中找不到匹配的行,但因为
count(*)
的性质子查询会返回结果 0。进一步p.seats * 0.5 > 0
的结果是一个 true,那么这个场次的记录会输出到结果中。 - 在Q4中,
TICKETS
中没有这个场次的记录,提前聚合的视图 V 中就不会包含该场次的聚合结果,Play
与V
的内连接也无法成功。显然这个场次的记录也就不会输出到Q4的结果中。
可以看到, Q3 和 Q4 在语义上是不等价的。
基于上述分析,我们发现对于count(*)
来说,子查询的相关条件结果是空集的情况下使用内连接会得到错误的结果,与此同时子查询的相关条件结果集为空集的时候count(*)
的结果为 0。那么将 Q4 稍加改造,就能得到一个与 Q3 等价的 Q5。
Q5: SELECT P.* FROM PLAY P LEFT JOIN (SELECT play_id, count(*) AS cnt FROM TICKETS T GROUP BY play_id) V ON P.play_id = V.play_id WHERE P.seats * 0.5 > (CASE WHEN V.play_id IS NULL THEN 0 ELSE V.cnt end);
在 Q5 中,我们使用了 left join 和 case when 来区分在子查询中能匹配到数据的行和不能匹配的数据行。对这两类,我们都能生成正确的过滤条件来替换原来包含子查询的过滤条件。
1.考虑在子查询中能匹配到数据的记录: 它能和 V
的一行连接。外连接的结果中 V.play_id
也不会是 NULL,最终的过滤条件会是P.seats * 0.5 > V.cnt
。
2.考虑在子查询中不能匹配到数据的记录: 它不能和 V
的一行连接。外连接的结果中 V.play_id
必然是 NULL,最终的过滤条件会是P.seats * 0.5 > 0
。
三、 连接优先的聚合类子查询提升
当子查询中的相关条件都是等值条件时,我们可以采用 Q1->Q2 或者 Q3 ->Q4 的方式进行改写。接下来,我们考虑一个更加复杂的子查询 Q6:查找所有上映一周内票房收入超过5万的电影。这个查询中,存在一个非等值的相关条件 T.sale_date < M.release_date + 7
。在 Q6 中,子查询每次需要聚合的范围变成了T.Movie_id = ? and T.sale_date < ? + 7
。这个范围显然无法提前聚合出来,它无法使用上一节给出的方式进行变换。
Q6: SELECT * FROM MOVIE M WHERE (SELECT sum(real_price) FROM TICKETS T WHERE T.movie_id = M.movie_id AND T.sale_date < M.release_date + 7) > 50000;
在 OceanBase 中,Q6 会被改写成 Q7 的形式。Q7 对 M
表中的每一行都会在 T
表中找出匹配的记录集合,然后进行分组求和统计(movie_id
假定是 MOIVIE
的主键),得到总票房,最后在 Having 判断总票房是否超过 50000。语义上,Q6 和 Q7 是等价的。
Q7: SELECT M.* FROM MOVIE M, TICKETS T WHERE T.movie_id = M.movie_id AND T.sale_date < M.release_date + 7 GROUP BY M.movie_id HAVING sum(T.real_price) > 50000;
从 Q6 到 Q7 的改写是将一个聚合类相关子查询改写成了一次连接(JOIN)+ 一次分组(GROUP BY)。因为改写后的 SQL 是先做连接,再做分组聚合,所以我们称之为连接优先的聚合类子查询提升。从直观上看,改写后的查询相比改写前的查询并不能提升执行性能。对于 MOVIE
表的每一行 Q7 依然要查出 TICKETS 中满足条件T.movie_id = M.movie_id AND T.sale_date < M.release_date + 7
的记录再做聚合。实际上这种改写方式存在以下好处:
- 更灵活的连接次序。如果子查询的相关条件中只有非等值条件,那么改写后的查询只能做 NEST-LOOP JOIN,但是可以选择子查询中的表作为驱动表。
- 更丰富的连接算法。如果子查询的相关条件中存在等值连接条件,那么改写后的查询还可以选择 HASH JOIN 或 MERGE JOIN 的连接方式,此时查询只需要扫描外层查询和子查询中的表各一次。
3.1 给读者的一个思考
与聚合优先的聚合类子查询提升相同,当子查询中的聚合函数是count(*)
时,连接优先的聚合类子查询提升也存在一个相似的小陷阱。两者要考虑的问题相同,但处理方式略有区别,我们把这个问题作为课后作业留给各位读者。请各位读者思考一下Q8应该怎样做连接优先的聚合类子查询提升。
Q8: SELECT * FROM MOVIE M WHERE (SELECT count(*) FROM TICKETS T WHERE T.movie_id = M.movie_id AND T.sale_date > M.release_date + 30) > 0;
四、总结
本文主要介绍了一种聚合类相关子查询的改写策略——聚合类子查询提升,以及这个改写策略中存在的陷阱。根据子查询中相关连接条件的不同,这一改写策略又可以细分成聚合优先的聚合类子查询提升和连接优先的聚合类子查询提升。聚合类子查询提升可以把聚合类子查询改写成连接的形式,让优化器能够选择更丰富的连接算法和连接次序。整体上,这是一个基于规则的改写策略。至此,我们介绍了 OceanBase 对两类子查询的改写方式。在下一篇中,我们将会聚焦在分组操作(GroupBy)上,介绍 OceanBase 在分组上的一些改写优化实践。
五、附录
1、首发!OceanBase 改写系列一:OceanBase 查询改写实践概述
2、OceanBase 改写系列二: 子查询提升首篇
最后的最后,如果你有任何问题都可以和我们联系。
联系我们
欢迎广大 OceanBase 爱好者、用户和客户随时与我们联系、反馈,方式如下:
社区版官网论坛
社区版项目网站提 Issue