PostgreSQL14递归语法增强

在PG中使用递归查询遍历表时，你可能希望以深度优先或广度优先的顺序对结果进行呈现。在PG14之前没有直接的语法来实现这个需求，但是变向的也能实现，只是写法稍显复杂点，下面分别介绍实现方法

--先构建测试数据
postgres=# create table sys_cbp_test (id int,parent_id int);
CREATE TABLE
postgres=# INSERT INTO sys_cbp_test VALUES (1 , NULL ) ,(2, 1) ,(3 , 2) ,(4 , 3) ,(5 , 1) ,(6 , 5) ,(7 , 2) ,(20 , NULL ) ,(21 , 20) ,(22 , 21);
INSERT 0 10
postgres=# SELECT * FROM sys_cbp_test;
 id | parent_id 
----+-----------
  1 |          
  2 |         1
  3 |         2
  4 |         3
  5 |         1
  6 |         5
  7 |         2
 20 |          
 21 |        20
 22 |        21
(10 rows)

--PG14之前以深度优先的顺序对结果进行呈现
--这里我们利用一个数组来记录遍历的节点，然后通过数组路径来进行排序
postgres=# WITH RECURSIVE x ( id , parent_id , path , root ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id ,array[id] , id as root
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , x.path || b.id , x.root
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# )
postgres-# SELECT id , parent_id ,'/' || array_to_string( path , '/' ) AS path, root
postgres-#   FROM x 
postgres-#  ORDER BY x.path;
 id | parent_id |   path    | root 
----+-----------+-----------+------
  1 |           | /1        |    1
  2 |         1 | /1/2      |    1
  3 |         2 | /1/2/3    |    1
  4 |         3 | /1/2/3/4  |    1
  7 |         2 | /1/2/7    |    1
  5 |         1 | /1/5      |    1
  6 |         5 | /1/5/6    |    1
 20 |           | /20       |   20
 21 |        20 | /20/21    |   20
 22 |        21 | /20/21/22 |   20
(10 rows)

--PG14以深度优先的顺序对结果进行呈现
--增加新的语法：SEARCH { BREADTH | DEPTH } FIRST BY column_name [, ...] SET search_seq_col_name ]
--SEARCH { BREADTH | DEPTH } 指定使用哪种SEARCH子句计算一个搜索序列列
--column_name [, ...] 提供的列名列表指定用于跟踪访问行的row key
--search_seq_col_name 搜索序列列，该列可用于按广度优先或深度优先顺序对递归查询的结果排序
--下面的数组不是必须的，只是为了观察结果更加友好
postgres=# WITH RECURSIVE x ( id , parent_id , path , root ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id ,array[id] , id as root
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , x.path || b.id , x.root
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) SEARCH DEPTH FIRST BY id SET order_col
postgres-# SELECT id , parent_id ,'/' || array_to_string( path , '/' ) AS path, root
postgres-#   FROM x 
postgres-#  ORDER BY order_col;
 id | parent_id |   path    | root 
----+-----------+-----------+------
  1 |           | /1        |    1
  2 |         1 | /1/2      |    1
  3 |         2 | /1/2/3    |    1
  4 |         3 | /1/2/3/4  |    1
  7 |         2 | /1/2/7    |    1
  5 |         1 | /1/5      |    1
  6 |         5 | /1/5/6    |    1
 20 |           | /20       |   20
 21 |        20 | /20/21    |   20
 22 |        21 | /20/21/22 |   20
(10 rows)

--PG14之前以广度优先的顺序对结果进行呈现
--这里我们增加一个跟踪搜索深度的列，然后通过深度列和主键进行稳定排序
postgres=# WITH RECURSIVE x ( id , parent_id , level , path , root ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id , 1 ,array[id] , id as root
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , level +1 , x.path || b.id , x.root
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# )
postgres-# SELECT id , parent_id , level ,'/' || array_to_string( path , '/' ) AS path, root
postgres-#   FROM x 
postgres-#  ORDER BY level,id;
 id | parent_id | level |   path    | root 
----+-----------+-------+-----------+------
  1 |           |     1 | /1        |    1
 20 |           |     1 | /20       |   20
  2 |         1 |     2 | /1/2      |    1
  5 |         1 |     2 | /1/5      |    1
 21 |        20 |     2 | /20/21    |   20
  3 |         2 |     3 | /1/2/3    |    1
  6 |         5 |     3 | /1/5/6    |    1
  7 |         2 |     3 | /1/2/7    |    1
 22 |        21 |     3 | /20/21/22 |   20
  4 |         3 |     4 | /1/2/3/4  |    1
(10 rows)

--PG14以广度优先的顺序对结果进行呈现
postgres=# WITH RECURSIVE x ( id , parent_id , path , root ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id ,array[id] , id as root
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , x.path || b.id , x.root
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) SEARCH BREADTH FIRST BY id SET order_col
postgres-# SELECT id , parent_id ,'/' || array_to_string( path , '/' ) AS path, root
postgres-#   FROM x 
postgres-#  ORDER BY order_col;
 id | parent_id |   path    | root 
----+-----------+-----------+------
  1 |           | /1        |    1
 20 |           | /20       |   20
  2 |         1 | /1/2      |    1
  5 |         1 | /1/5      |    1
 21 |        20 | /20/21    |   20
  3 |         2 | /1/2/3    |    1
  6 |         5 | /1/5/6    |    1
  7 |         2 | /1/2/7    |    1
 22 |        21 | /20/21/22 |   20
  4 |         3 | /1/2/3/4  |    1
(10 rows)

注意：不管指定的是广度优先搜索还是深度优先搜索，如果不指定排序列，默认都是广度优先的搜索顺序生成其输出结果。

在PG14中还增量了语法对循环节点的判断，示例如下：

postgres=# SELECT * FROM sys_cbp_test;
 id | parent_id 
----+-----------
  1 |          
  2 |         1
  3 |         2
  4 |         3
  5 |         1
  6 |         5
  7 |         2
 20 |          
 21 |        20
 22 |        21
(10 rows)

--在以上的测试数据中增加一条数据，构造数据循环
postgres=# INSERT INTO sys_cbp_test VALUES(1, 4);
INSERT 0 1
postgres=# SELECT * FROM sys_cbp_test;
 id | parent_id 
----+-----------
  1 |          
  2 |         1
  3 |         2
  4 |         3
  5 |         1
  6 |         5
  7 |         2
 20 |          
 21 |        20
 22 |        21
  1 |         4
(11 rows)

--如果不判断循环，那么语句就陷入死循环，直到临时文件占满整个存储空间                                                 ^
postgres=# WITH RECURSIVE x ( id , prior_id , parent_id , level , path , root ) AS
postgres-# ( SELECT id , NULL::INT AS prior_id , NULL::INT AS parent_id , 1 ,array[id] , id as root
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , x.id AS prior_id , b.parent_id , level +1 , x.path || b.id , x.root
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# )
postgres-# SELECT id , prior_id , parent_id , level ,'/' || array_to_string( path , '/' ) AS path, root, path
postgres-#   FROM x;
^CCancel request sent
ERROR:  canceling statement due to user request

--PG14以前的解决方法
--检查循环节点SQL
postgres=# WITH RECURSIVE x ( id , parent_id , path , is_cycle ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id ,array[id] , false
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , x.path || b.id , b.id = ANY(path)
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id AND NOT is_cycle
postgres(# )
postgres-# SELECT id , parent_id ,'/' || array_to_string( path , '/' ) AS path
postgres-#   FROM x 
postgres-#  WHERE is_cycle;
 id | parent_id |    path    
----+-----------+------------
  1 |         4 | /1/2/3/4/1
(1 row)

--排除循环节点
postgres=# WITH RECURSIVE x ( id , parent_id , path , is_cycle ) AS
postgres-# ( SELECT id , NULL::INT AS parent_id ,array[id] , false
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id , x.path || b.id , b.id = ANY(path)
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id AND NOT is_cycle
postgres(# )
postgres-# SELECT id , parent_id ,'/' || array_to_string( path , '/' ) AS path
postgres-#   FROM x 
postgres-#  WHERE NOT is_cycle;
 id | parent_id |   path    
----+-----------+-----------
  1 |           | /1
 20 |           | /20
  2 |         1 | /1/2
  5 |         1 | /1/5
 21 |        20 | /20/21
  3 |         2 | /1/2/3
  6 |         5 | /1/5/6
  7 |         2 | /1/2/7
 22 |        21 | /20/21/22
  4 |         3 | /1/2/3/4
(10 rows)

--PG14新增循环检测语法
--CYCLE column_name [, ...] SET cycle_mark_col_name [ TO cycle_mark_value DEFAULT cycle_mark_default ] USING cycle_path_col_name
--column_name [, ...] 提供的列名列表指定用于跟踪访问行的row key
--cycle_mark_col_name 此列将添加到WITH查询的结果列列表中，当检测到循环时，此列将设置为循环标记值cycle_mark_value（默认为布尔值TRUE），否则设置为循环标记默认值cycle_mark_default（默认为FLASE）
--cycle_path_col_name 此列将添加到WITH查询的结果列列表中，在内部用于跟踪访问的行
--查找循环节点
postgres=# WITH RECURSIVE x ( id , parent_id) AS
postgres-# ( SELECT id , parent_id
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) CYCLE id SET is_cycle USING path
postgres-# SELECT id , parent_id , path
postgres-#   FROM x 
postgres-#  WHERE is_cycle;
 id | parent_id |         path          
----+-----------+-----------------------
  1 |         4 | {(1),(2),(3),(4),(1)}
(1 row)

--排除循环节点
postgres=# WITH RECURSIVE x ( id , parent_id) AS
postgres-# ( SELECT id , parent_id
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) CYCLE id SET is_cycle USING path
postgres-# SELECT id , parent_id , path
postgres-#   FROM x 
postgres-#  WHERE NOT is_cycle;
 id | parent_id |       path        
----+-----------+-------------------
  1 |           | {(1)}
 20 |           | {(20)}
  2 |         1 | {(1),(2)}
  5 |         1 | {(1),(5)}
 21 |        20 | {(20),(21)}
  3 |         2 | {(1),(2),(3)}
  6 |         5 | {(1),(5),(6)}
  7 |         2 | {(1),(2),(7)}
 22 |        21 | {(20),(21),(22)}
  4 |         3 | {(1),(2),(3),(4)}
(10 rows)

--自定义循环标记值
postgres=# WITH RECURSIVE x ( id , parent_id) AS
postgres-# ( SELECT id , parent_id
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) CYCLE id SET is_cycle TO 1 DEFAULT 0 USING path
postgres-# SELECT id , parent_id , is_cycle , path
postgres-#   FROM x 
postgres-#  WHERE is_cycle = 1;
 id | parent_id | is_cycle |         path          
----+-----------+----------+-----------------------
  1 |         4 |        1 | {(1),(2),(3),(4),(1)}
(1 row)

postgres=# WITH RECURSIVE x ( id , parent_id) AS
postgres-# ( SELECT id , parent_id
postgres(#     FROM sys_cbp_test
postgres(#    WHERE parent_id IS NULL
postgres(#    UNION ALL
postgres(#   SELECT b.id , b.parent_id
postgres(#     FROM x, sys_cbp_test b
postgres(#    WHERE x.id = b.parent_id
postgres(# ) CYCLE id SET is_cycle TO 1 DEFAULT 0 USING path
postgres-# SELECT id , parent_id , is_cycle , path
postgres-#   FROM x 
postgres-#  WHERE is_cycle = 0;
 id | parent_id | is_cycle |       path        
----+-----------+----------+-------------------
  1 |           |        0 | {(1)}
 20 |           |        0 | {(20)}
  2 |         1 |        0 | {(1),(2)}
  5 |         1 |        0 | {(1),(5)}
 21 |        20 |        0 | {(20),(21)}
  3 |         2 |        0 | {(1),(2),(3)}
  6 |         5 |        0 | {(1),(5),(6)}
  7 |         2 |        0 | {(1),(2),(7)}
 22 |        21 |        0 | {(20),(21),(22)}
  4 |         3 |        0 | {(1),(2),(3),(4)}
(10 rows)