标签
PostgreSQL , CTE , 递归查询 , cycle , depth , loop , deep , level , 层级 , array , row array
背景
Oracle connect by语法支持异构查询，其中包含了一些特殊的变量：CONNECT_BY_ROOT、CONNECT_BY_ISLEAF、SYS_CONNECT_BY_PATH、CONNECT_BY_ISCYCLE、LEVEL。
https://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm#i2053935
https://docs.oracle.com/cd/B19306_01/server.102/b14200/pseudocolumns001.htm
PostgreSQL通过CTE语法同样可以实现异构查询，同样能支持：
1、层级
2、路径
3、规避循环
4、限制每个层级返回的条数
CTE 例子
https://www.postgresql.org/docs/10/static/queries-with.html
《PostgreSQL 图式搜索(graph search)实践 - 百亿级图谱，毫秒响应》
1、层级，路径，规避循环的例子：
背景，图式搜索是PostgreSQL在（包括流计算、全文检索、图式搜索、K-V存储、图像搜索、指纹搜索、空间数据、时序数据、推荐等）诸多特性中的一个。
采用CTE语法，可以很方便的实现图式搜索（N度搜索、最短路径、点、边属性等）。
其中图式搜索中的：层级深度，是否循环，路径，都是可表述的。
表结构，
create table a(
c1 int, -- 点1
c2 int, -- 点2
prop jsonb, -- 点1,2对应的边的属性，使用JSON存储
primary key (c1,c2) -- 主键
);
CTE SQL及解释如下：
WITH RECURSIVE search_graph(
c1, -- 点1
c2, -- 点2
prop, -- 边的属性
depth, -- 深度，从1开始
path, -- 路径，数组存储
cycle -- 是否循环
) AS (
select c1,c2,prop,depth,path,cycle from (
SELECT -- ROOT节点查询
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
1 depth, -- 初始深度=1
ARRAY[g.c1] path, -- 初始路径
false as cycle -- 是否循环(初始为否)
FROM a AS g
WHERE
c1 = ? -- ROOT节点=?
-- AND prop->>weight >= ? -- 相关性权重
-- ORDER BY prop->>weight desc -- 可以使用ORDER BY，例如返回权重排在前面的N条。
limit ? -- 每个层级限制多少条？
) t
UNION ALL
select c1,c2,prop,depth,path,cycle from (
SELECT -- 递归子句
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
sg.depth + 1 depth, -- 深度+1
path || g.c1 path, -- 路径中加入新的点
(g.c1 = ANY(path)) as cycle -- 是否循环，判断新点是否已经在之前的路径中
FROM a AS g, search_graph AS sg -- 循环 INNER JOIN
WHERE
g.c1 = sg.c2 -- 递归JOIN条件
AND NOT cycle -- 防止循环
AND sg.depth <= ? -- 搜索深度=?
-- AND prop->>weight >= ? -- 相关性权重
-- ORDER BY prop->>weight desc -- 可以使用ORDER BY，例如返回权重排在前面的N条。
limit ? -- 每个层级限制多少条？
) t
)
SELECT * FROM search_graph; -- 查询递归表，可以加LIMIT输出，也可以使用游标
查询举例：
3级递归，每级限制输出100条，输出层级，路径等。
c1 | c2 | prop | depth | path | cycle
---------+----------+------+-------+------------------------+-------
31208 | 300008 | | 1 | {31208} | f
31208 | 300040 | | 1 | {31208} | f
31208 | 300046 | | 1 | {31208} | f
31208 | 300050 | | 1 | {31208} | f
31208 | 300061 | | 1 | {31208} | f
31208 | 300082 | | 1 | {31208} | f
31208 | 300093 | | 1 | {31208} | f
31208 | 300116 | | 1 | {31208} | f
31208 | 300135 | | 1 | {31208} | f
31208 | 300201 | | 1 | {31208} | f
31208 | 300215 | | 1 | {31208} | f
31208 | 300218 | | 1 | {31208} | f
31208 | 300304 | | 1 | {31208} | f
31208 | 300333 | | 1 | {31208} | f
31208 | 300352 | | 1 | {31208} | f
31208 | 300375 | | 1 | {31208} | f
31208 | 300390 | | 1 | {31208} | f
31208 | 300423 | | 1 | {31208} | f
31208 | 300457 | | 1 | {31208} | f
31208 | 300531 | | 1 | {31208} | f
31208 | 300560 | | 1 | {31208} | f
31208 | 300565 | | 1 | {31208} | f
31208 | 300596 | | 1 | {31208} | f
31208 | 300691 | | 1 | {31208} | f
31208 | 300722 | | 1 | {31208} | f
31208 | 300739 | | 1 | {31208} | f
31208 | 300774 | | 1 | {31208} | f
31208 | 300798 | | 1 | {31208} | f
31208 | 300806 | | 1 | {31208} | f
31208 | 300814 | | 1 | {31208} | f
31208 | 300860 | | 1 | {31208} | f
31208 | 300880 | | 1 | {31208} | f
31208 | 300902 | | 1 | {31208} | f
31208 | 300958 | | 1 | {31208} | f
31208 | 301003 | | 1 | {31208} | f
31208 | 301020 | | 1 | {31208} | f
31208 | 301109 | | 1 | {31208} | f
31208 | 301151 | | 1 | {31208} | f
31208 | 301155 | | 1 | {31208} | f
31208 | 301194 | | 1 | {31208} | f
31208 | 301235 | | 1 | {31208} | f
31208 | 301255 | | 1 | {31208} | f
31208 | 301264 | | 1 | {31208} | f
31208 | 301270 | | 1 | {31208} | f
31208 | 301276 | | 1 | {31208} | f
31208 | 301283 | | 1 | {31208} | f
31208 | 301303 | | 1 | {31208} | f
31208 | 301306 | | 1 | {31208} | f
31208 | 301367 | | 1 | {31208} | f
31208 | 301405 | | 1 | {31208} | f
31208 | 301446 | | 1 | {31208} | f
31208 | 301474 | | 1 | {31208} | f
31208 | 301529 | | 1 | {31208} | f
31208 | 301534 | | 1 | {31208} | f
31208 | 301575 | | 1 | {31208} | f
31208 | 301592 | | 1 | {31208} | f
31208 | 301609 | | 1 | {31208} | f
31208 | 301640 | | 1 | {31208} | f
31208 | 301680 | | 1 | {31208} | f
31208 | 301685 | | 1 | {31208} | f
31208 | 301686 | | 1 | {31208} | f
31208 | 301713 | | 1 | {31208} | f
31208 | 301824 | | 1 | {31208} | f
31208 | 301832 | | 1 | {31208} | f
31208 | 301852 | | 1 | {31208} | f
31208 | 301858 | | 1 | {31208} | f
31208 | 301863 | | 1 | {31208} | f
31208 | 301872 | | 1 | {31208} | f
31208 | 301882 | | 1 | {31208} | f
31208 | 301970 | | 1 | {31208} | f
31208 | 302024 | | 1 | {31208} | f
31208 | 302140 | | 1 | {31208} | f
31208 | 302150 | | 1 | {31208} | f
31208 | 302153 | | 1 | {31208} | f
31208 | 302200 | | 1 | {31208} | f
31208 | 302218 | | 1 | {31208} | f
31208 | 302276 | | 1 | {31208} | f
31208 | 302346 | | 1 | {31208} | f
31208 | 302397 | | 1 | {31208} | f
31208 | 302400 | | 1 | {31208} | f
31208 | 302474 | | 1 | {31208} | f
31208 | 302507 | | 1 | {31208} | f
31208 | 302565 | | 1 | {31208} | f
31208 | 302574 | | 1 | {31208} | f
31208 | 302589 | | 1 | {31208} | f
31208 | 302593 | | 1 | {31208} | f
31208 | 302602 | | 1 | {31208} | f
31208 | 302605 | | 1 | {31208} | f
31208 | 302660 | | 1 | {31208} | f
31208 | 302686 | | 1 | {31208} | f
31208 | 302721 | | 1 | {31208} | f
31208 | 302780 | | 1 | {31208} | f
31208 | 302806 | | 1 | {31208} | f
31208 | 302843 | | 1 | {31208} | f
31208 | 302894 | | 1 | {31208} | f
31208 | 302908 | | 1 | {31208} | f
31208 | 302961 | | 1 | {31208} | f
31208 | 302971 | | 1 | {31208} | f
31208 | 302975 | | 1 | {31208} | f
31208 | 302988 | | 1 | {31208} | f
300008 | 3001645 | | 2 | {31208,300008} | f
300008 | 3037289 | | 2 | {31208,300008} | f
300008 | 3032152 | | 2 | {31208,300008} | f
300008 | 3024717 | | 2 | {31208,300008} | f
300008 | 3014555 | | 2 | {31208,300008} | f
300008 | 3040396 | | 2 | {31208,300008} | f
300008 | 3032492 | | 2 | {31208,300008} | f
300008 | 3047950 | | 2 | {31208,300008} | f
300008 | 3031417 | | 2 | {31208,300008} | f
300008 | 3005462 | | 2 | {31208,300008} | f
300008 | 3047212 | | 2 | {31208,300008} | f
300008 | 3015890 | | 2 | {31208,300008} | f
300008 | 3004061 | | 2 | {31208,300008} | f
300008 | 3034108 | | 2 | {31208,300008} | f
300008 | 3020085 | | 2 | {31208,300008} | f
300008 | 3032992 | | 2 | {31208,300008} | f
300008 | 3000726 | | 2 | {31208,300008} | f
300008 | 3043559 | | 2 | {31208,300008} | f
300008 | 3013642 | | 2 | {31208,300008} | f
300008 | 3018378 | | 2 | {31208,300008} | f
300008 | 3010610 | | 2 | {31208,300008} | f
300008 | 3038619 | | 2 | {31208,300008} | f
300008 | 3003777 | | 2 | {31208,300008} | f
300008 | 3001058 | | 2 | {31208,300008} | f
300008 | 3020331 | | 2 | {31208,300008} | f
300008 | 3006217 | | 2 | {31208,300008} | f
300008 | 3016217 | | 2 | {31208,300008} | f
300008 | 3046372 | | 2 | {31208,300008} | f
300008 | 3032365 | | 2 | {31208,300008} | f
300008 | 3015589 | | 2 | {31208,300008} | f
300008 | 3049638 | | 2 | {31208,300008} | f
300008 | 3034010 | | 2 | {31208,300008} | f
300008 | 3002878 | | 2 | {31208,300008} | f
300008 | 3031789 | | 2 | {31208,300008} | f
300008 | 3008727 | | 2 | {31208,300008} | f
300008 | 3017432 | | 2 | {31208,300008} | f
300008 | 3022185 | | 2 | {31208,300008} | f
300008 | 3041219 | | 2 | {31208,300008} | f
300008 | 3015383 | | 2 | {31208,300008} | f
300008 | 3003602 | | 2 | {31208,300008} | f
300008 | 3046681 | | 2 | {31208,300008} | f
300008 | 3012595 | | 2 | {31208,300008} | f
300008 | 3019492 | | 2 | {31208,300008} | f
300008 | 3000742 | | 2 | {31208,300008} | f
300008 | 3046703 | | 2 | {31208,300008} | f
300008 | 3039577 | | 2 | {31208,300008} | f
300008 | 3033734 | | 2 | {31208,300008} | f
300008 | 3047429 | | 2 | {31208,300008} | f
300008 | 3033136 | | 2 | {31208,300008} | f
300008 | 3047377 | | 2 | {31208,300008} | f
300008 | 3015807 | | 2 | {31208,300008} | f
300008 | 3043746 | | 2 | {31208,300008} | f
300008 | 3035995 | | 2 | {31208,300008} | f
300008 | 3019584 | | 2 | {31208,300008} | f
300008 | 3044804 | | 2 | {31208,300008} | f
300008 | 3006327 | | 2 | {31208,300008} | f
300008 | 3025801 | | 2 | {31208,300008} | f
300008 | 3011021 | | 2 | {31208,300008} | f
300008 | 3002699 | | 2 | {31208,300008} | f
300008 | 3008166 | | 2 | {31208,300008} | f
300008 | 3026610 | | 2 | {31208,300008} | f
300008 | 3002337 | | 2 | {31208,300008} | f
300008 | 3042177 | | 2 | {31208,300008} | f
300008 | 3029488 | | 2 | {31208,300008} | f
300008 | 3034126 | | 2 | {31208,300008} | f
300008 | 3000904 | | 2 | {31208,300008} | f
300008 | 3046920 | | 2 | {31208,300008} | f
300008 | 3006311 | | 2 | {31208,300008} | f
300008 | 3042123 | | 2 | {31208,300008} | f
300008 | 3012303 | | 2 | {31208,300008} | f
300008 | 3009913 | | 2 | {31208,300008} | f
300008 | 3038805 | | 2 | {31208,300008} | f
300008 | 3024898 | | 2 | {31208,300008} | f
300008 | 3029405 | | 2 | {31208,300008} | f
300008 | 3039547 | | 2 | {31208,300008} | f
300008 | 3021601 | | 2 | {31208,300008} | f
300008 | 3018982 | | 2 | {31208,300008} | f
300008 | 3023281 | | 2 | {31208,300008} | f
300008 | 3019031 | | 2 | {31208,300008} | f
300008 | 3002117 | | 2 | {31208,300008} | f
300008 | 3020658 | | 2 | {31208,300008} | f
300008 | 3034837 | | 2 | {31208,300008} | f
300008 | 3045863 | | 2 | {31208,300008} | f
300008 | 3006653 | | 2 | {31208,300008} | f
300008 | 3004421 | | 2 | {31208,300008} | f
300008 | 3040668 | | 2 | {31208,300008} | f
300008 | 3012980 | | 2 | {31208,300008} | f
300008 | 3030222 | | 2 | {31208,300008} | f
300008 | 3001689 | | 2 | {31208,300008} | f
300008 | 3015679 | | 2 | {31208,300008} | f
300008 | 3038388 | | 2 | {31208,300008} | f
300008 | 3028300 | | 2 | {31208,300008} | f
300008 | 3018016 | | 2 | {31208,300008} | f
300008 | 3030565 | | 2 | {31208,300008} | f
300008 | 3007787 | | 2 | {31208,300008} | f
300008 | 3002142 | | 2 | {31208,300008} | f
300008 | 3031469 | | 2 | {31208,300008} | f
300008 | 3004708 | | 2 | {31208,300008} | f
300008 | 3008453 | | 2 | {31208,300008} | f
300008 | 3023592 | | 2 | {31208,300008} | f
3032152 | 30327610 | | 3 | {31208,300008,3032152} | f
3032152 | 30347138 | | 3 | {31208,300008,3032152} | f
3032152 | 30324805 | | 3 | {31208,300008,3032152} | f
3032152 | 30309501 | | 3 | {31208,300008,3032152} | f
3032152 | 30318027 | | 3 | {31208,300008,3032152} | f
3032152 | 30300820 | | 3 | {31208,300008,3032152} | f
3032152 | 30310825 | | 3 | {31208,300008,3032152} | f
3032152 | 30305623 | | 3 | {31208,300008,3032152} | f
3032152 | 30336901 | | 3 | {31208,300008,3032152} | f
3032152 | 30321303 | | 3 | {31208,300008,3032152} | f
3032152 | 30304624 | | 3 | {31208,300008,3032152} | f
3032152 | 30343224 | | 3 | {31208,300008,3032152} | f
3032152 | 30321132 | | 3 | {31208,300008,3032152} | f
3032152 | 30308929 | | 3 | {31208,300008,3032152} | f
3032152 | 30329000 | | 3 | {31208,300008,3032152} | f
3032152 | 30319366 | | 3 | {31208,300008,3032152} | f
3032152 | 30341162 | | 3 | {31208,300008,3032152} | f
3032152 | 30349290 | | 3 | {31208,300008,3032152} | f
3032152 | 30315173 | | 3 | {31208,300008,3032152} | f
3032152 | 30302537 | | 3 | {31208,300008,3032152} | f
3032152 | 30328276 | | 3 | {31208,300008,3032152} | f
3032152 | 30328416 | | 3 | {31208,300008,3032152} | f
3032152 | 30305538 | | 3 | {31208,300008,3032152} | f
3032152 | 30331586 | | 3 | {31208,300008,3032152} | f
3032152 | 30338438 | | 3 | {31208,300008,3032152} | f
3032152 | 30302040 | | 3 | {31208,300008,3032152} | f
3032152 | 30318870 | | 3 | {31208,300008,3032152} | f
3032152 | 30347906 | | 3 | {31208,300008,3032152} | f
3032152 | 30333042 | | 3 | {31208,300008,3032152} | f
3032152 | 30322289 | | 3 | {31208,300008,3032152} | f
3032152 | 30344294 | | 3 | {31208,300008,3032152} | f
3032152 | 30310653 | | 3 | {31208,300008,3032152} | f
3032152 | 30319427 | | 3 | {31208,300008,3032152} | f
3032152 | 30319099 | | 3 | {31208,300008,3032152} | f
3032152 | 30320154 | | 3 | {31208,300008,3032152} | f
3032152 | 30337454 | | 3 | {31208,300008,3032152} | f
3032152 | 30319919 | | 3 | {31208,300008,3032152} | f
3032152 | 30330979 | | 3 | {31208,300008,3032152} | f
3032152 | 30343077 | | 3 | {31208,300008,3032152} | f
3032152 | 30306820 | | 3 | {31208,300008,3032152} | f
3032152 | 30302283 | | 3 | {31208,300008,3032152} | f
3032152 | 30347701 | | 3 | {31208,300008,3032152} | f
3032152 | 30300044 | | 3 | {31208,300008,3032152} | f
3032152 | 30323415 | | 3 | {31208,300008,3032152} | f
3032152 | 30306630 | | 3 | {31208,300008,3032152} | f
3032152 | 30329044 | | 3 | {31208,300008,3032152} | f
3032152 | 30342781 | | 3 | {31208,300008,3032152} | f
3032152 | 30347792 | | 3 | {31208,300008,3032152} | f
3032152 | 30328334 | | 3 | {31208,300008,3032152} | f
3032152 | 30307954 | | 3 | {31208,300008,3032152} | f
3032152 | 30300329 | | 3 | {31208,300008,3032152} | f
3032152 | 30306609 | | 3 | {31208,300008,3032152} | f
3032152 | 30336370 | | 3 | {31208,300008,3032152} | f
3032152 | 30305867 | | 3 | {31208,300008,3032152} | f
3032152 | 30338195 | | 3 | {31208,300008,3032152} | f
3032152 | 30324808 | | 3 | {31208,300008,3032152} | f
3032152 | 30307907 | | 3 | {31208,300008,3032152} | f
3032152 | 30307065 | | 3 | {31208,300008,3032152} | f
3032152 | 30322714 | | 3 | {31208,300008,3032152} | f
3032152 | 30340949 | | 3 | {31208,300008,3032152} | f
3032152 | 30329354 | | 3 | {31208,300008,3032152} | f
3032152 | 30317008 | | 3 | {31208,300008,3032152} | f
3032152 | 30301602 | | 3 | {31208,300008,3032152} | f
3032152 | 30348782 | | 3 | {31208,300008,3032152} | f
3032152 | 30336107 | | 3 | {31208,300008,3032152} | f
3032152 | 30321756 | | 3 | {31208,300008,3032152} | f
3032152 | 30336236 | | 3 | {31208,300008,3032152} | f
3032152 | 30306026 | | 3 | {31208,300008,3032152} | f
3032152 | 30302735 | | 3 | {31208,300008,3032152} | f
3032152 | 30329312 | | 3 | {31208,300008,3032152} | f
3032152 | 30312846 | | 3 | {31208,300008,3032152} | f
3032152 | 30305018 | | 3 | {31208,300008,3032152} | f
3032152 | 30327013 | | 3 | {31208,300008,3032152} | f
3032152 | 30312890 | | 3 | {31208,300008,3032152} | f
3032152 | 30328433 | | 3 | {31208,300008,3032152} | f
3032152 | 30333643 | | 3 | {31208,300008,3032152} | f
3032152 | 30341934 | | 3 | {31208,300008,3032152} | f
3032152 | 30321213 | | 3 | {31208,300008,3032152} | f
3032152 | 30331435 | | 3 | {31208,300008,3032152} | f
3032152 | 30320267 | | 3 | {31208,300008,3032152} | f
3032152 | 30329167 | | 3 | {31208,300008,3032152} | f
3032152 | 30331764 | | 3 | {31208,300008,3032152} | f
3032152 | 30326876 | | 3 | {31208,300008,3032152} | f
3032152 | 30315537 | | 3 | {31208,300008,3032152} | f
3032152 | 30337631 | | 3 | {31208,300008,3032152} | f
3032152 | 30315071 | | 3 | {31208,300008,3032152} | f
3032152 | 30340345 | | 3 | {31208,300008,3032152} | f
3032152 | 30345538 | | 3 | {31208,300008,3032152} | f
3032152 | 30322136 | | 3 | {31208,300008,3032152} | f
3032152 | 30313059 | | 3 | {31208,300008,3032152} | f
3032152 | 30336487 | | 3 | {31208,300008,3032152} | f
3032152 | 30301491 | | 3 | {31208,300008,3032152} | f
3032152 | 30330067 | | 3 | {31208,300008,3032152} | f
3032152 | 30338088 | | 3 | {31208,300008,3032152} | f
3032152 | 30300272 | | 3 | {31208,300008,3032152} | f
3032152 | 30316175 | | 3 | {31208,300008,3032152} | f
3032152 | 30309844 | | 3 | {31208,300008,3032152} | f
3032152 | 30336508 | | 3 | {31208,300008,3032152} | f
3032152 | 30322201 | | 3 | {31208,300008,3032152} | f
3032152 | 30312579 | | 3 | {31208,300008,3032152} | f
(300 rows)
Time: 3.245 ms
多列路径和CYCLE判断，语法修改如下，使用ROW数组：
WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
SELECT g.id, g.link, g.data, 1,
ARRAY[ROW(g.f1, g.f2)],
false
FROM graph g
UNION ALL
SELECT g.id, g.link, g.data, sg.depth + 1,
path || ROW(g.f1, g.f2),
ROW(g.f1, g.f2) = ANY(path)
FROM graph g, search_graph sg
WHERE g.id = sg.link AND NOT cycle
)
SELECT * FROM search_graph;
