前言
今天遇到一则十分有趣的 SQL 优化案例，涉及到相关子查询的上拉，在 17 版本的 release note 中，在 Optimizer 小节中有这样一段描述：
Allow correlated IN subqueries to be transformed into joins (Andy Fan, Tom Lane)
即允许相关的 IN 子查询转换为 JOIN，部分场景下可以大幅度提升查询性能，作者是国内大佬，给大佬点赞！👍🏻
子查询的分类
与子查询类似的是子连接，出现在 FROM 关键字后的子句是子查询语句，出现在 WHERE/ON 等约束条件中或投影中的子句是子连接语句，不过大多数时候，二者并不会分的那么细。
其中，子查询又可以细分为相关子查询和非相关子查询，顾名思义，，相关子查询会导致外层表每获得一个元组，子查询就需要重新执行一次；而非相关子查询是指在子查询语句是独立的，和外层的表没有直接的关联，子查询可以单独执行一次，外层表可以重复利用子查询的执行结果。这一段话听起来和标量子查询很类似，不过标量子查询返回的是单个值，通常出现在 SELECT 列表中，对于标量子查询的改写就那么一个套路，使用 LEFT JOIN，如果关联字段是主外键的关系，那么就使用 INNER JOIN 进行改写。关于标量子查询的案例，可以参照 DB Killer？原来是标量子查询！
说了一大堆，让我们看个具体例子：
postgres=# select version();version---------------------------------------------------------------------------------------------------------PostgreSQL 16.1 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44), 64-bit(1 row)postgres=# CREATE TABLE tb1 (id SERIAL PRIMARY KEY,c1 INT,c2 INT);CREATE TABLEpostgres=# CREATE TABLE tb2 (id INT PRIMARY KEY,c1 INT,c2 INT);CREATE TABLEpostgres=# CREATE INDEX tb2_c1_c2_idx ON tb2(c1, c2);CREATE INDEXpostgres=# INSERT INTO tb2 (id, c1, c2) VALUES(1, 1, 100),(2, 1, 200),(3, 2, 100),(4, 2, 200),(5, 3, 100),(6, 3, 200),(7, 4, 100),(8, 4, 200),(9, 5, 100),(10,5, 200);INSERT 0 10postgres=# INSERT INTO tb1 (c1, c2)SELECT (random()*4+1)::INT,(random()*1000)::INTFROM generate_series(1, 10000);INSERT 0 10000postgres=# analyze tb1,tb2;ANALYZEpostgres=# explain analyze SELECT *FROM tb1WHERE id IN (SELECT idFROM tb2WHERE tb2.c1 = tb1.c1);QUERY PLAN---------------------------------------------------------------------------------------------------------Seq Scan on tb1 (cost=0.00..5830.00 rows=5000 width=12) (actual time=0.019..19.580 rows=2 loops=1)Filter: (SubPlan 1)Rows Removed by Filter: 9998SubPlan 1-> Seq Scan on tb2 (cost=0.00..1.12 rows=2 width=4) (actual time=0.001..0.001 rows=2 loops=10000)Filter: (c1 = tb1.c1)Rows Removed by Filter: 8Planning Time: 0.297 msExecution Time: 19.598 ms(9 rows)
查询 SQL 很简单，正如前文所说，相关子查询类似于嵌套循环，复杂度为 O(N^2)，子查询里的 tb2.c1 = tb1.c1 明确引用了外层表 tb1 的列，表明它要"带着"当前行的值去执行子查询，所以执行计划中可以看到，loops = 10000，说明子查询循环了一万次！如果子查询的执行路径再差一些的话，那性能自然也会急剧恶化。有趣的是，让我们用 EXISTS 等价改写一下看看
postgres=# explain analyze SELECT *FROM tb1WHERE EXISTS (SELECT 1FROM tb2WHERE tb2.id = tb1.idAND tb2.c1 = tb1.c1);QUERY PLAN----------------------------------------------------------------------------------------------------------------------------Merge Join (cost=1.55..2.08 rows=2 width=12) (actual time=0.037..0.044 rows=2 loops=1)Merge Cond: (tb1.id = tb2.id)Join Filter: (tb1.c1 = tb2.c1)Rows Removed by Join Filter: 8-> Index Scan using tb1_pkey on tb1 (cost=0.29..328.29 rows=10000 width=12) (actual time=0.007..0.010 rows=11 loops=1)-> Sort (cost=1.27..1.29 rows=10 width=8) (actual time=0.022..0.023 rows=10 loops=1)Sort Key: tb2.idSort Method: quicksort Memory: 25kB-> Seq Scan on tb2 (cost=0.00..1.10 rows=10 width=8) (actual time=0.011..0.013 rows=10 loops=1)Planning Time: 0.228 msExecution Time: 0.084 ms(11 rows)
可以惊奇地看到，对于 EXISTS，16 版本是可以自动上拉的！查询性能各位也可以看到，相差了 200 倍之多！
那同样的查询，让我们到 17 版本中，再次验证下：
postgres=# EXPLAIN ANALYZESELECT *FROM tb1WHERE id IN (SELECT idFROM tb2WHERE tb2.c1 = tb1.c1);QUERY PLAN----------------------------------------------------------------------------------------------------------------------------Merge Join (cost=1.55..2.08 rows=2 width=12) (actual time=0.067..0.078 rows=1 loops=1)Merge Cond: (tb1.id = tb2.id)Join Filter: (tb1.c1 = tb2.c1)Rows Removed by Join Filter: 9-> Index Scan using tb1_pkey on tb1 (cost=0.29..328.29 rows=10000 width=12) (actual time=0.024..0.029 rows=11 loops=1)-> Sort (cost=1.27..1.29 rows=10 width=8) (actual time=0.029..0.031 rows=10 loops=1)Sort Key: tb2.idSort Method: quicksort Memory: 25kB-> Seq Scan on tb2 (cost=0.00..1.10 rows=10 width=8) (actual time=0.012..0.016 rows=10 loops=1)Planning Time: 0.498 msExecution Time: 0.169 ms(11 rows)postgres=# select version();version------------------------------------------------------------------------------------------------------------PostgreSQL 17devel on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44), 64-bit(1 row)
可以很清楚地看到，在 17 版本中，tb1 上有索引，不用额外的 sort，所以自动改写为了 Merge Join，查询性能大幅提升。
那让我们看下这个 patch 做了哪些功能 (以下来自 GPT 的解读)：这个 Patch 的核心目的，就是在只有一级 «外层引用»(varlevelsup = 1) 的 ANY (...) 子查询场景下，绕过原来两步扁平化的限制，一步性地把相关的 ANY_SUBLINK 直接改写成带 LATERAL 的 EXISTS_SUBLINK，然后让现有的 convert_EXISTS_sublink_to_join 逻辑把它拉平为一个半连接（semi-join）。这样就彻底消除了那种「外层每行都循环跑一次子查询」的子计划，大幅提升性能。
简而言之，对于 any 类型的子连接 (以下是作者的原话)
关联的是向上 2+ 层也可以，但这张场景太少了。
Greenplum 的行为如何？
那么 Greenplum 行为又会如何？为此，我特意去 Greenplum 6 和 7 里面都实验了一下，6 会将其改写了 Hash Semi Join
postgres=# EXPLAIN ANALYZESELECT *FROM tb1WHERE id IN (SELECT idFROM tb2WHERE tb2.c1 = tb1.c1);QUERY PLAN--------------------------------------------------------------------------------------------------------------------------Gather Motion 6:1 (slice1; segments: 6) (cost=5.25..175.91 rows=14 width=12) (actual time=1.470..1.543 rows=1 loops=1)-> Hash Semi Join (cost=5.25..175.91 rows=3 width=12) (actual time=0.454..1.080 rows=1 loops=1)Hash Cond: ((tb1.c1 = tb2.c1) AND (tb1.id = tb2.id))Extra Text: (seg0) Hash chain length 1.0 avg, 1 max, using 3 of 524288 buckets.-> Seq Scan on tb1 (cost=0.00..118.00 rows=1667 width=12) (actual time=0.011..0.098 rows=1723 loops=1)-> Hash (cost=5.10..5.10 rows=2 width=8) (actual time=0.011..0.011 rows=3 loops=1)-> Seq Scan on tb2 (cost=0.00..5.10 rows=2 width=8) (actual time=0.005..0.005 rows=3 loops=1)Planning time: 0.288 ms(slice0) Executor memory: 59K bytes.(slice1) Executor memory: 4172K bytes avg x 6 workers, 4172K bytes max (seg0). Work_mem: 1K bytes max.Memory used: 128000kBOptimizer: Postgres query optimizerExecution time: 1.965 ms(13 rows)postgres=# select version();version-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------PostgreSQL 9.4.26 (Greenplum Database 6.26.4 build commit:bcbaaead795b417d18644f36f334827f0815cf37) on x86_64-unknown-linux-gnu, compiled by gcc (GCC) 6.4.0, 64-bit compiled on Mar 8 2024 00:39:37(1 row)
7 则是将其改写了 Hash Join
postgres=# EXPLAIN ANALYZESELECT *FROM tb1WHERE id IN (SELECT idFROM tb2WHERE tb2.c1 = tb1.c1);QUERY PLAN---------------------------------------------------------------------------------------------------------------------------Gather Motion 8:1 (slice1; segments: 8) (cost=1.03..47.09 rows=2000 width=12) (actual time=2.217..2.275 rows=1 loops=1)-> Hash Join (cost=1.03..24.59 rows=250 width=12) (actual time=1.594..2.248 rows=1 loops=1)Hash Cond: ((tb1.c1 = tb2.c1) AND (tb1.id = tb2.id))Extra Text: (seg5) Hash chain length 1.0 avg, 1 max, using 1 of 524288 buckets.-> Seq Scan on tb1 (cost=0.00..14.50 rows=1250 width=12) (actual time=0.008..0.087 rows=1285 loops=1)-> Hash (cost=1.01..1.01 rows=1 width=8) (actual time=0.023..0.025 rows=2 loops=1)Buckets: 524288 Batches: 1 Memory Usage: 4097kB-> Seq Scan on tb2 (cost=0.00..1.01 rows=1 width=8) (actual time=0.017..0.018 rows=2 loops=1)Optimizer: Postgres-based plannerPlanning Time: 0.244 ms(slice0) Executor memory: 34K bytes.(slice1) Executor memory: 4152K bytes avg x 8 workers, 4157K bytes max (seg5). Work_mem: 4097K bytes max.Memory used: 128000kBExecution Time: 3.171 ms(14 rows)
但是无疑，二者都可以大幅提升此类查询的执行效率。
小节
在张树杰老师的《PostgreSQL技术内幕：查询优化深度探索》一书中，有这样一段描述
EXISTS 类型的相关子连接会被提升，非相关子连接会形成子执行计划单独求解。需要注意的是，还需要保证 EXIST 类型的相关子连接是"简单"的才能被提升
ANY 类型非相关子连接可以提升 (仍然需要是"简单"的子连接) 并且可以通过物化的方式进行优化，而 ANY 类型的相关子连接目前还不能提升。
也就是说，可以粗略的理解为：对于 ANY 类型的子连接，只提升非相关子连接，而对于 EXISTS 类型的子连接，则只提升相关子连接。在 17 版本中，对于 1+ 层的情况，也可以进行上拉。最后，再次给 andy fan 大佬点赞，使得 PG 的优化器能力更上一层楼。
借此案例，相信各位对于 EXISTS 和 ANY 的理解能够理解更加深入，除了我们所熟知的
•对于单纯判断"是否存在"，二者其实等价，结果相同
•当子查询可能返回 NULL 时，NOT IN 会产生空，可能不符合预期
•NOT EXISTS 则更健壮，推荐用于排除性判断
•子查询的提升
OK，That's all。最后，欢迎各位参加月底济南的 IvorySQL 大会，我会与各位分享最新版的《PostgreSQL DBA Daily》，是的，它又双叒叕来了~ 并会打印一些纸质版带过去，送给参会的读者朋友们。
