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

数据运维 2024-05-07 大猫 手机阅读

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

传送门：

OB小优系列（一）：OceanBase查询优化器的设计之道和工程实践

OB小优系列（二）：OceanBase并行执行引擎实现

OB小优系列（三）：OceanBase查询改写的最佳实践


引言 


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


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


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


场景介绍 


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


OB小优系列文章 | 聚合类相关子查询提升（上）-1


为此，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改写第二式，它能够很好的处理以上这两个问题。