再聊聊晦涩的join_collapse_limit参数

xiongcc2024年01月14日约 15 分钟

前言

关于 join_collapse_limit 参数我在之前的文章中也有所提及：深入剖析PostgreSQL优化器，但是今天细看发现有些瑕疵，理解有所偏差。今天在我复核到 Query Execution Stages 章节的时候 (到第 16 章节了，总共 29 章节，胜利曙光就在眼前🫠)，又看到了对这个参数的说明，有必要再次深入这个参数的实现原理了。

温顾

先温顾一下前置知识，假如现在有个查询是 SELECT ... FROM a, b, c, d, e WHERE ...，生成的语法分析树的结构类似如下：

这种写法是隐式连接，当然也可以使用显式连接，比如 SELECT ... FROM a, b JOIN c ON ..., d, e WHERE ...，显式指定 JOIN 关键字，那么其语法结构树类似如下：

这个时候，优化器在 deconstruct_jointree 这个函数中会去"展平" JOINEXPR 节点，用 B、C 节点替代，使其和第一个例子中类似。但是这种展平有个限制——没错，join_collapse_limit，只有当展平后的元素不超过 join_collapse_limit 才会执行，也就意味着：

表 B 必须与表 C 连接 (反之亦然，表 C 必须与表 B 连接；一对连接内的顺序不受限制)。
表 A、D、E 和 JOINEXPR 节点可以按任何顺序连接。

因此，按照假如是第一种情况，SELECT ... FROM a, b, c, d, e WHERE ...，其排列组合共有 5! = 120 这么多种组合，即

a, b, c, d, e
a, b, c, e, d
a, b, d, c, e
a, b, d, e, c
a, b, e, c, d
a, b, e, d, c
a, c, b, d, e
a, c, b, e, d
a, c, d, b, e
a, c, d, e, b
....

假如 join_collapse_limit 为 1 的话，那么 B 必须先和 C 进行连接，然后作为一个整体 (不妨用 x 替代)，那么其实就变成了 SELECT ... FROM a, x, d, e WHERE ... 四个表参与查询的结构，所以，其排列组合就变成了 4! = 24 种，足足少了 5 倍。不难想象，这种方式可以减少优化器的规划时间。

我之前也在优化器篇章里提过，PostgreSQL 采用了动态规划 (Bottom-up) 和遗传算法相结合的方式：

比如现在有个 SQL 是 select * from a where id=10，那么首先全表扫描肯定可以，然后去获取统计信息估算出相应的代价；假如 id 列有索引，那么再去估算索引扫描的代价；先为基表确定扫描路径，估计扫描路径的代价和大小，这样我们就得出了单表查询的最优解；
假如现在的 SQL 变复杂了，需要 join：select * from a join b on (a.id=b.id) where a.id>10;，那么现在就要考虑更多了，假如使用 nestloop，看看 join 能不能用上索引，被驱动表上有没有索引，估计其代价，hash join、merge join 也是类似，看看能不能将某个表物化成 hash table，merge join 要求数据先排序，那么看看有没有索引能消除 SORT 算子诸如此类；最终把这些可能的 join 方式全部列出来，然后分别计划其代价，筛选出代价最低的路径，现在我们就得到了两个表 join 的最优解。
那假如现在又多了一个表，通过前两步骤，现在已知{A B} 、{A C} 、{B C}这三种 JOIN 的最优解，开始求解三张表的最优解，分别求解 {A B} JOIN C、{A C} JOIN B、{B C} JOIN A 这三种 JOIN 的代价，得到代价最小的路径
四个表类似，最终得到四表 JOIN 的最优解。

可以看到，动态规划就是一个依次求最优解的这么一个过程。不难想象，随着表数量的增多，优化器的 planning time 会随着表的数量增加呈指数级增长。所以又引入了遗传算法，借鉴了自然界中的进化理论。

$ SELECT i, (i)! AS num_comparisons FROM generate_series(8, 20) i;
 i  |   num_comparisons   
----+---------------------
  8 |               40320
  9 |              362880
 10 |             3628800
 11 |            39916800
 12 |           479001600
 13 |          6227020800
 14 |         87178291200
 15 |       1307674368000
 16 |      20922789888000
 17 |     355687428096000
 18 |    6402373705728000
 19 |  121645100408832000
 20 | 2432902008176640000
(13 rows)

遗传算法默认是打开的，阈值是 12 (geqo_threshold) ，意味着超过了 12 个表进行关联，就会走到遗传算法，好处是可以减少 planning time，但坏处是可能找到的不是最优解，最优的执行计划，执行效率会有影响。

为此，PostgreSQL 又引入了 join_collapse_limit 这个参数，默认是 8。官网的解释有点晦涩，说白了就是有多少个显式关联操作会被优化器拉平，当做隐式关联，放到 FROM 子句中。

The planner will rewrite explicit JOIN constructs (except FULL JOINs) into lists of FROM items whenever a list of no more than this many items would result. Smaller values reduce planning time but might yield inferior query plans.
规划器会将显式的 JOIN （除了 FULL JOIN）重写为 FROM 项的列表，只要结果是不超过这么多项的列表。较小的值可以减少规划时间，但可能会产生次优的查询计划。

实践

以如下这个 SQL 为例，其涉及到 5 个关联操作

postgres=# EXPLAIN (COSTS OFF) WITH x AS (
    SELECT
        *                                   
    FROM
        generate_series(1, 1000) AS id
)          
SELECT                      
    *                       
FROM                        
    x AS a
    JOIN x AS b ON (a.id = b.id)
    JOIN x AS c ON (b.id = c.id)
    JOIN x AS d ON (c.id = d.id)
    JOIN x AS e ON (d.id = e.id)
    JOIN x AS f ON (e.id = f.id);

那么按照我们之前的分析，当 join_coallpase_limit = 1 的话，SQL 将严格按照我们写的顺序进行关联，即

postgres=# set join_collapse_limit to 1;
SET
postgres=# EXPLAIN (COSTS OFF) WITH x AS (
    SELECT
        *
    FROM
        generate_series(1, 1000) AS id
)
SELECT
    *
FROM
    x AS a
    JOIN x AS b ON (a.id = b.id)
    JOIN x AS c ON (b.id = c.id)
    JOIN x AS d ON (c.id = d.id)
    JOIN x AS e ON (d.id = e.id)
    JOIN x AS f ON (e.id = f.id);
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Merge Join
   Merge Cond: (f.id = a.id)
   CTE x
     ->  Function Scan on generate_series id
   ->  Sort
         Sort Key: f.id
         ->  CTE Scan on x f
   ->  Materialize
         ->  Merge Join
               Merge Cond: (e.id = a.id)
               ->  Sort
                     Sort Key: e.id
                     ->  CTE Scan on x e
               ->  Materialize
                     ->  Merge Join
                           Merge Cond: (d.id = a.id)
                           ->  Sort
                                 Sort Key: d.id
                                 ->  CTE Scan on x d
                           ->  Materialize
                                 ->  Merge Join
                                       Merge Cond: (c.id = a.id)
                                       ->  Sort
                                             Sort Key: c.id
                                             ->  CTE Scan on x c
                                       ->  Materialize
                                             ->  Merge Join
                                                   Merge Cond: (a.id = b.id)
                                                   ->  Sort
                                                         Sort Key: a.id
                                                         ->  CTE Scan on x a
                                                   ->  Sort
                                                         Sort Key: b.id
                                                         ->  CTE Scan on x b
(34 rows)

设为 6 及以上的时候，就不再变化，为最优执行计划。

postgres=# set join_collapse_limit to 6;
SET
postgres=# EXPLAIN (COSTS OFF) WITH x AS (
    SELECT
        *
    FROM
        generate_series(1, 1000) AS id
)
SELECT
    *
FROM
    x AS a
    JOIN x AS b ON (a.id = b.id)
    JOIN x AS c ON (b.id = c.id)
    JOIN x AS d ON (c.id = d.id)
    JOIN x AS e ON (d.id = e.id)
    JOIN x AS f ON (e.id = f.id);
                     QUERY PLAN                      
-----------------------------------------------------
 Merge Join
   Merge Cond: (a.id = d.id)
   CTE x
     ->  Function Scan on generate_series id
   ->  Merge Join
         Merge Cond: (c.id = a.id)
         ->  Sort
               Sort Key: c.id
               ->  CTE Scan on x c
         ->  Materialize
               ->  Merge Join
                     Merge Cond: (a.id = b.id)
                     ->  Sort
                           Sort Key: a.id
                           ->  CTE Scan on x a
                     ->  Sort
                           Sort Key: b.id
                           ->  CTE Scan on x b
   ->  Materialize
         ->  Merge Join
               Merge Cond: (f.id = d.id)
               ->  Sort
                     Sort Key: f.id
                     ->  CTE Scan on x f
               ->  Materialize
                     ->  Merge Join
                           Merge Cond: (d.id = e.id)
                           ->  Sort
                                 Sort Key: d.id
                                 ->  CTE Scan on x d
                           ->  Sort
                                 Sort Key: e.id
                                 ->  CTE Scan on x e
(33 rows)

让我们再看个例子。先建 7 个表，插入点数据：

postgres=# create table t1(id int, info text);
CREATE TABLE
postgres=# create table t2(id int, info text);
CREATE TABLE
postgres=# create table t3(id int, info text);
CREATE TABLE
postgres=# create table t4(id int, info text);
CREATE TABLE
postgres=# create table t5(id int, info text);
CREATE TABLE
postgres=# create table t6(id int, info text);
CREATE TABLE
postgres=# create table t7(id int, info text);
CREATE TABLE
postgres=# insert into t1 select n,md5(random()::text) from generate_series(1,100) as n;
INSERT 0 100
postgres=# insert into t2 select n,md5(random()::text) from generate_series(1,1000) as n;
INSERT 0 1000
postgres=# insert into t3 select n,md5(random()::text) from generate_series(1,10000) as n;
INSERT 0 10000
postgres=# insert into t4 select n,md5(random()::text) from generate_series(1,10000) as n;
INSERT 0 10000
postgres=# insert into t5 select n,md5(random()::text) from generate_series(1,10000) as n;
INSERT 0 10000
postgres=# insert into t6 select n,md5(random()::text) from generate_series(1,10000) as n;
INSERT 0 10000
postgres=# insert into t7 select n,md5(random()::text) from generate_series(1,10000) as n;
INSERT 0 10000

然后构造一个较复杂的查询：

postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN (t3 JOIN (t2 JOIN t1 USING (id)) USING (id))
USING (id);
                                        QUERY PLAN                                        
------------------------------------------------------------------------------------------
 Hash Join
   Hash Cond: (t3.id = t4.id)
   ->  Seq Scan on t3
   ->  Hash
         ->  Hash Join
               Hash Cond: (t5.id = t4.id)
               ->  Seq Scan on t5
               ->  Hash
                     ->  Hash Join
                           Hash Cond: (t6.id = t4.id)
                           ->  Seq Scan on t6
                           ->  Hash
                                 ->  Hash Join
                                       Hash Cond: (t7.id = t4.id)
                                       ->  Seq Scan on t7
                                       ->  Hash
                                             ->  Hash Join
                                                   Hash Cond: (t4.id = t2.id)
                                                   ->  Seq Scan on t4
                                                   ->  Hash
                                                         ->  Hash Join
                                                               Hash Cond: (t2.id = t1.id)
                                                               ->  Seq Scan on t2
                                                               ->  Hash
                                                                     ->  Seq Scan on t1
(25 rows)

这么长一坨的SQL，假如按照我们的"本意"，那么其逻辑应该

首先，t1 和 t2 通过它们的 id 列进行 JOIN 操作，形成一个中间结果。
然后，这个中间结果再与 t3 进行 JOIN 操作，同样是通过 id 列，形成另一个中间结果。
接下来，t5 和 t6 通过它们的 id 列进行 JOIN 操作，形成一个中间结果。
t4 和 t7 也通过它们的 id 列进行 JOIN 操作，形成另一个中间结果。
然后，t4 和 t7 的 JOIN 结果与 t5 和 t6 的 JOIN 结果进行 JOIN 操作，通过 id 列，形成又一个中间结果。
最后，这个中间结果与前面由 t1, t2, 和 t3 形成的 JOIN 结果进行最终的 JOIN 操作，仍然是通过 id 列。

但是查看执行计划的话，可以看到优化器进行了改写，完全进行打乱了

最内层的哈希连接是 t2 和 t1，基于条件 t2.id = t1.id。
结果哈希表被用于与 t4 进行连接，基于条件 t4.id = t2.id。
接着是 t7 与 t4 的连接，基于条件 t7.id = t4.id。
然后是 t6 与 t4 的连接，基于条件 t6.id = t4.id。
接下来是 t5 与 t4 的连接，基于条件 t5.id = t4.id。
最后是 t3 与 t4 的连接，基于条件 t3.id = t4.id。

现在让我们调整一下 join_collapse_limit，看看会发生什么：

postgres=# set join_collapse_limit to 5;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN (t3 JOIN (t2 JOIN t1 USING (id)) USING (id))
USING (id);
                      QUERY PLAN                      
------------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t2.id)
   ->  Hash Join
         Hash Cond: (t4.id = t5.id)
         ->  Hash Join
               Hash Cond: (t4.id = t6.id)
               ->  Hash Join
                     Hash Cond: (t4.id = t7.id)
                     ->  Seq Scan on t4
                     ->  Hash
                           ->  Seq Scan on t7
               ->  Hash
                     ->  Seq Scan on t6
         ->  Hash
               ->  Seq Scan on t5
   ->  Hash
         ->  Hash Join
               Hash Cond: (t3.id = t2.id)
               ->  Seq Scan on t3
               ->  Hash
                     ->  Hash Join
                           Hash Cond: (t2.id = t1.id)
                           ->  Seq Scan on t2
                           ->  Hash
                                 ->  Seq Scan on t1
(25 rows)postgres=# set join_collapse_limit to 3;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN (t3 JOIN (t2 JOIN t1 USING (id)) USING (id))
USING (id);
                      QUERY PLAN                      
------------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t2.id)
   ->  Hash Join
         Hash Cond: (t4.id = t6.id)
         ->  Hash Join
               Hash Cond: (t4.id = t7.id)
               ->  Seq Scan on t4
               ->  Hash
                     ->  Seq Scan on t7
         ->  Hash
               ->  Hash Join
                     Hash Cond: (t6.id = t5.id)
                     ->  Seq Scan on t6
                     ->  Hash
                           ->  Seq Scan on t5
   ->  Hash
         ->  Hash Join
               Hash Cond: (t3.id = t2.id)
               ->  Seq Scan on t3
               ->  Hash
                     ->  Hash Join
                           Hash Cond: (t2.id = t1.id)
                           ->  Seq Scan on t2
                           ->  Hash
                                 ->  Seq Scan on t1
(25 rows)

可以看到，PostgreSQL 会根据 join_collapse_limit 的设置，当需要关联的个数超过阈值时，超出的部分不会继续调整了。让我们省略掉几个关联，然后从 1 开始调整

EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN t3 USING (id);

现在的查询逻辑变成了：

t4 JOIN t7 USING (id): 首先，t4 和 t7 根据它们的 id 列进行 JOIN 操作。
t6 JOIN t5 USING (id): 同时，t6 和 t5 也根据它们的 id 列进行 JOIN 操作。
然后，这两组 JOIN 的结果（t4 和 t7 的结果与 t6 和 t5 的结果）再次根据 id 列进行 JOIN 操作。
接着，上一步的结果与 t3 进行 JOIN 操作，仍然是基于 id 列。

join_collapse_limit = 1

现在从 1 开始调整，可以看到，执行计划严格按照我们的写法进行关联

postgres=# set join_collapse_limit to 1;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN t3 USING (id);
                   QUERY PLAN                   
------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t3.id)
   ->  Hash Join
         Hash Cond: (t4.id = t6.id)
         ->  Hash Join
               Hash Cond: (t4.id = t7.id)
               ->  Seq Scan on t4
               ->  Hash
                     ->  Seq Scan on t7
         ->  Hash
               ->  Hash Join
                     Hash Cond: (t6.id = t5.id)
                     ->  Seq Scan on t6
                     ->  Hash
                           ->  Seq Scan on t5
   ->  Hash
         ->  Seq Scan on t3
(17 rows)

join_collapse_limit = 2

postgres=# set join_collapse_limit to 2;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN t3 USING (id);
                   QUERY PLAN                   
------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t3.id)
   ->  Hash Join
         Hash Cond: (t4.id = t6.id)
         ->  Hash Join
               Hash Cond: (t4.id = t7.id)
               ->  Seq Scan on t4
               ->  Hash
                     ->  Seq Scan on t7
         ->  Hash
               ->  Hash Join
                     Hash Cond: (t6.id = t5.id)
                     ->  Seq Scan on t6
                     ->  Hash
                           ->  Seq Scan on t5
   ->  Hash
         ->  Seq Scan on t3
(17 rows)

join_collapse_limit = 3

postgres=# set join_collapse_limit to 3;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN t3 USING (id);
                   QUERY PLAN                   
------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t3.id)
   ->  Hash Join
         Hash Cond: (t4.id = t6.id)
         ->  Hash Join
               Hash Cond: (t4.id = t7.id)
               ->  Seq Scan on t4
               ->  Hash
                     ->  Seq Scan on t7
         ->  Hash
               ->  Hash Join
                     Hash Cond: (t6.id = t5.id)
                     ->  Seq Scan on t6
                     ->  Hash
                           ->  Seq Scan on t5
   ->  Hash
         ->  Seq Scan on t3
(17 rows)

join_collapse_limit = 4

可以看到，当变成 4 的时候，SQL 的逻辑就不再是我们写的本意那样了。将 4 个关联操作全部展开之后，优化器发现用这种执行计划更加高效。

postgres=# set join_collapse_limit to 4;
SET
postgres=# EXPLAIN (costs off)                      
SELECT
    *
FROM ( (t4 JOIN t7 USING (id))
    JOIN (t6 JOIN t5 USING (id)) USING (id) )
JOIN t3 USING (id);
                   QUERY PLAN                   
------------------------------------------------
 Hash Join
   Hash Cond: (t4.id = t3.id)
   ->  Hash Join
         Hash Cond: (t4.id = t5.id)
         ->  Hash Join
               Hash Cond: (t4.id = t6.id)
               ->  Hash Join
                     Hash Cond: (t4.id = t7.id)
                     ->  Seq Scan on t4
                     ->  Hash
                           ->  Seq Scan on t7
               ->  Hash
                     ->  Seq Scan on t6
         ->  Hash
               ->  Seq Scan on t5
   ->  Hash
         ->  Seq Scan on t3
(17 rows)

from_collapse_limit

还有个类似的参数，仅当子查询的数量小于 from_collapse_limit 时，这些子查询才会被提升。

SELECT ...
FROM a,
 (
  SELECT ... FROM b, c WHERE ...
 ) bc,
 d, e
WHERE ...

技巧

通过 offset 0 可以达到和 join_collapse_limit = 1 类似的效果。

EXPLAIN (COSTS OFF)
SELECT subq.b_id, a.value
FROM a JOIN
   (SELECT a_id, b.b_id, c.c_id
    FROM b
       JOIN c USING (a_id)
    WHERE c.c_id < 300
    OFFSET 0
   ) AS subq
      USING (a_id);                 QUERY PLAN                 
═══════════════════════════════════════════
 Nested Loop
   ->  Hash Join
         Hash Cond: (c.a_id = b.a_id)
         ->  Seq Scan on c
               Filter: (c_id < 300)
         ->  Hash
               ->  Seq Scan on b
   ->  Memoize
         Cache Key: b.a_id
         Cache Mode: logical
         ->  Index Scan using a_pkey on a
               Index Cond: (a_id = b.a_id)
(12 rows)
SET join_collapse_limit = 1;
 EXPLAIN (COSTS OFF)
SELECT b.b_id, a.value
FROM b
   JOIN c USING (a_id)
   JOIN a USING (a_id)
WHERE c.c_id < 300;
                 QUERY PLAN                 
═══════════════════════════════════════════
 Nested Loop
   ->  Hash Join
         Hash Cond: (c.a_id = b.a_id)
         ->  Seq Scan on c
               Filter: (c_id < 300)
         ->  Hash
               ->  Seq Scan on b
   ->  Memoize
         Cache Key: b.a_id
         Cache Mode: logical
         ->  Index Scan using a_pkey on a
               Index Cond: (a_id = b.a_id)
(12 rows)

以及搭配 MATERIALIZED，防止将 CTE 提升至主查询中 (12以前，CTE是无法提升到主查询中的)。

EXPLAIN (COSTS OFF)
WITH subq AS MATERIALIZED (
   SELECT a_id, b.b_id, c.c_id
   FROM b
      JOIN c USING (a_id)
   WHERE c.c_id < 300
)
SELECT subq.b_id, a.value
FROM a
   JOIN subq USING (a_id);                QUERY PLAN               
════════════════════════════════════════
 Hash Join
   Hash Cond: (subq.a_id = a.a_id)
   CTE subq
     ->  Hash Join
           Hash Cond: (c.a_id = b.a_id)
           ->  Seq Scan on c
                 Filter: (c_id < 300)
           ->  Hash
                 ->  Seq Scan on b
   ->  CTE Scan on subq
   ->  Hash
         ->  Seq Scan on a
(12 rows)

小结

通过 join_collapse_limit 参数，可以固定关联顺序，在某些场景下改写 SQL 以提升性能，更高的值可以生成更好的执行计划，但是代价便是规划时间可能变长，另外要注意基因遗传算法的触发阈值是 12，此参数默认是 8。

再次感叹优化器太过于晦涩，其中原理过于复杂，衷心佩服那些优化器内核人员。

参考

https://github.com/duke-lv/blog-2/blob/master/201609/20160926_01.md

https://www.cybertec-postgresql.com/en/forcing-a-join-order-in-postgresql/

https://www.cybertec-postgresql.com/en/postgressql-implicit-vs-explicit-joins/

推荐阅读

📙 PostgreSQL优化器解析

📙 深入剖析PostgreSQL优化器

Feel free to contact me

微信公众号：PostgreSQL学徒
Github：https://github.com/xiongcccc
微信：_xiongcc
知乎：xiongcc
墨天轮：https://www.modb.pro/u/39588

前言

温顾

实践

join_collapse_limit = 1

join_collapse_limit = 2

join_collapse_limit = 3

join_collapse_limit = 4

from_collapse_limit

技巧

小结

参考

Feel free to contact me

来自同一个声音

PGSimCity - PostgreSQL 工作原理可视化解析

从 Lakebase 到 LTAP，是旧饭新炒，还是新的技术范式？

AI 时代首选数据库：PostgreSQL 入门到进阶实战

pg-slide-harvester：自动收集 PG 大会演讲资料