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

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

传送门：

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

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

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

引言 

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

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

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

场景介绍 

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

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