作者
digoal
日期
2021-09-17
标签
PostgreSQL , 递归
递归查询一般被用于社交关系、医患关系、学生与老师、家族、上下游传感器等关系搜索.
https://www.postgresql.org/docs/14/queries-with.html#QUERIES-WITH-SEARCH
PostgreSQL递归查询支持深度优先与广度优先搜索, 采用BREADTH DEPTH关键字语法.
注意:
- 深度、广度优先搜索是搜索完所有结果后再排序得到深度、广度优先的结果, 而不是在搜索方法上实现的, 所以会损耗性能, 一定要注意.
- 如果不加排序, 实际上就是广度优先(逐级搜索).
想象一下一颗树根:
- 如果树根是空心的, 往里面倒有颜色的液体, 液体流入树根的动画, 就类似是广度优先, 逐级向下渗透.
- 不可能先留到最底部, 然后上面再分叉流入另一个分支.
- 如果要实现深度优先, 可能要在搜索过程中对分叉加状态标记(并存储下来), 在到达末梢后再回过头来继续.
好友关系链, uid 1 加 uid 2为好友时, 表示lkuid是uid的好友, 写入1,2
create table bs (uid int, lkuid int, primary key(uid,lkuid)); insert into bs select * from (select (random()*10)::int c1, (random()*10)::int c2 from generate_series(1,100)) t where c1<>c2 on conflict do nothing;复制
广度优先搜索
with recursive tmp as ( select uid, lkuid, 0 as depth, array[uid,lkuid] as path, false as cycle from bs where uid=1 union all select bs.uid, bs.lkuid, tmp.depth+1, tmp.path||bs.lkuid, bs.lkuid=any(tmp.path) from bs , tmp where bs.uid=tmp.lkuid and not bs.lkuid=any(tmp.path) ) SEARCH BREADTH FIRST BY uid SET ordercol select * from tmp order by ordercol; uid | lkuid | depth | path | cycle | ordercol -----+-------+-------+--------------------------+-------+---------- 1 | 8 | 0 | {1,8} | f | (0,1) 1 | 3 | 0 | {1,3} | f | (0,1) 1 | 7 | 0 | {1,7} | f | (0,1) 1 | 10 | 0 | {1,10} | f | (0,1) 1 | 5 | 0 | {1,5} | f | (0,1) 1 | 2 | 0 | {1,2} | f | (0,1) 1 | 4 | 0 | {1,4} | f | (0,1) 2 | 6 | 1 | {1,2,6} | f | (1,2) 2 | 4 | 1 | {1,2,4} | f | (1,2) 2 | 3 | 1 | {1,2,3} | f | (1,2) 3 | 0 | 1 | {1,3,0} | f | (1,3) 3 | 8 | 1 | {1,3,8} | f | (1,3) 3 | 9 | 1 | {1,3,9} | f | (1,3) 3 | 2 | 1 | {1,3,2} | f | (1,3) 3 | 6 | 1 | {1,3,6} | f | (1,3) 4 | 6 | 1 | {1,4,6} | f | (1,4) 4 | 10 | 1 | {1,4,10} | f | (1,4) 4 | 9 | 1 | {1,4,9} | f | (1,4) 4 | 0 | 1 | {1,4,0} | f | (1,4) 4 | 3 | 1 | {1,4,3} | f | (1,4) 5 | 7 | 1 | {1,5,7} | f | (1,5) 5 | 6 | 1 | {1,5,6} | f | (1,5) 5 | 2 | 1 | {1,5,2} | f | (1,5) 5 | 4 | 1 | {1,5,4} | f | (1,5) 7 | 2 | 1 | {1,7,2} | f | (1,7) 7 | 6 | 1 | {1,7,6} | f | (1,7) 7 | 0 | 1 | {1,7,0} | f | (1,7) 7 | 5 | 1 | {1,7,5} | f | (1,7) 7 | 10 | 1 | {1,7,10} | f | (1,7) 7 | 8 | 1 | {1,7,8} | f | (1,7) 7 | 3 | 1 | {1,7,3} | f | (1,7) 8 | 7 | 1 | {1,8,7} | f | (1,8) 8 | 2 | 1 | {1,8,2} | f | (1,8) 8 | 4 | 1 | {1,8,4} | f | (1,8) 8 | 5 | 1 | {1,8,5} | f | (1,8) 8 | 9 | 1 | {1,8,9} | f | (1,8) 8 | 3 | 1 | {1,8,3} | f | (1,8) 10 | 5 | 1 | {1,10,5} | f | (1,10) 10 | 8 | 1 | {1,10,8} | f | (1,10) 10 | 9 | 1 | {1,10,9} | f | (1,10) 0 | 5 | 2 | {1,7,0,5} | f | (2,0)复制
深度优先搜索
with recursive tmp as ( select uid, lkuid, 0 as depth, array[uid,lkuid] as path, false as cycle from bs where uid=1 union all select bs.uid, bs.lkuid, tmp.depth+1, tmp.path||bs.lkuid, bs.lkuid=any(tmp.path) from bs , tmp where bs.uid=tmp.lkuid and not bs.lkuid=any(tmp.path) ) SEARCH DEPTH FIRST BY uid SET ordercol select * from tmp order by ordercol; uid | lkuid | depth | path | cycle | ordercol -----+-------+-------+--------------------------+-------+-------------------------------------------- 1 | 8 | 0 | {1,8} | f | {(1)} 1 | 7 | 0 | {1,7} | f | {(1)} 1 | 4 | 0 | {1,4} | f | {(1)} 1 | 2 | 0 | {1,2} | f | {(1)} 1 | 5 | 0 | {1,5} | f | {(1)} 1 | 10 | 0 | {1,10} | f | {(1)} 1 | 3 | 0 | {1,3} | f | {(1)} 2 | 4 | 1 | {1,2,4} | f | {(1),(2)} 2 | 3 | 1 | {1,2,3} | f | {(1),(2)} 2 | 6 | 1 | {1,2,6} | f | {(1),(2)} 3 | 8 | 2 | {1,2,3,8} | f | {(1),(2),(3)} 3 | 0 | 2 | {1,2,3,0} | f | {(1),(2),(3)} 3 | 9 | 2 | {1,2,3,9} | f | {(1),(2),(3)} 3 | 6 | 2 | {1,2,3,6} | f | {(1),(2),(3)} 0 | 8 | 3 | {1,2,3,0,8} | f | {(1),(2),(3),(0)} 0 | 5 | 3 | {1,2,3,0,5} | f | {(1),(2),(3),(0)} 0 | 9 | 3 | {1,2,3,0,9} | f | {(1),(2),(3),(0)} 5 | 7 | 4 | {1,2,3,0,5,7} | f | {(1),(2),(3),(0),(5)} 5 | 4 | 4 | {1,2,3,0,5,4} | f | {(1),(2),(3),(0),(5)} 5 | 6 | 4 | {1,2,3,0,5,6} | f | {(1),(2),(3),(0),(5)} 4 | 9 | 5 | {1,2,3,0,5,4,9} | f | {(1),(2),(3),(0),(5),(4)} 4 | 6 | 5 | {1,2,3,0,5,4,6} | f | {(1),(2),(3),(0),(5),(4)} 4 | 10 | 5 | {1,2,3,0,5,4,10} | f | {(1),(2),(3),(0),(5),(4)} 6 | 8 | 6 | {1,2,3,0,5,4,6,8} | f | {(1),(2),(3),(0),(5),(4),(6)} 6 | 10 | 6 | {1,2,3,0,5,4,6,10} | f | {(1),(2),(3),(0),(5),(4),(6)} 8 | 7 | 7 | {1,2,3,0,5,4,6,8,7} | f | {(1),(2),(3),(0),(5),(4),(6),(8)} 8 | 9 | 7 | {1,2,3,0,5,4,6,8,9} | f | {(1),(2),(3),(0),(5),(4),(6),(8)} 7 | 10 | 8 | {1,2,3,0,5,4,6,8,7,10} | f | {(1),(2),(3),(0),(5),(4),(6),(8),(7)} 10 | 9 | 9 | {1,2,3,0,5,4,6,8,7,10,9} | f | {(1),(2),(3),(0),(5),(4),(6),(8),(7),(10)} ....... 3 | 8 | 1 | {1,3,8} | f | {(1),(3)} 3 | 0 | 1 | {1,3,0} | f | {(1),(3)} 3 | 9 | 1 | {1,3,9} | f | {(1),(3)} 3 | 2 | 1 | {1,3,2} | f | {(1),(3)} 3 | 6 | 1 | {1,3,6} | f | {(1),(3)} 0 | 8 | 2 | {1,3,0,8} | f | {(1),(3),(0)} 0 | 9 | 2 | {1,3,0,9} | f | {(1),(3),(0)} 0 | 5 | 2 | {1,3,0,5} | f | {(1),(3),(0)} 5 | 7 | 3 | {1,3,0,5,7} | f | {(1),(3),(0),(5)} 5 | 4 | 3 | {1,3,0,5,4} | f | {(1),(3),(0),(5)} 5 | 2 | 3 | {1,3,0,5,2} | f | {(1),(3),(0),(5)} 5 | 6 | 3 | {1,3,0,5,6} | f | {(1),(3),(0),(5)} 2 | 4 | 4 | {1,3,0,5,2,4} | f | {(1),(3),(0),(5),(2)} 2 | 6 | 4 | {1,3,0,5,2,6} | f | {(1),(3),(0),(5),(2)} 4 | 9 | 5 | {1,3,0,5,2,4,9} | f | {(1),(3),(0),(5),(2),(4)} 4 | 10 | 5 | {1,3,0,5,2,4,10} | f | {(1),(3),(0),(5),(2),(4)} 4 | 6 | 5 | {1,3,0,5,2,4,6} | f | {(1),(3),(0),(5),(2),(4)}复制
广度优先和深度优先通过排序得到, 实际上是在排序列上做的手脚. 一个是record类型, 一个是record[]类型.
广度优先record
with recursive tmp as ( select uid, lkuid, 0 as depth, array[uid,lkuid] as path, false as cycle from bs where uid=1 union all select bs.uid, bs.lkuid, tmp.depth+1, tmp.path||bs.lkuid, bs.lkuid=any(tmp.path) from bs , tmp where bs.uid=tmp.lkuid and not bs.lkuid=any(tmp.path) ) SEARCH BREADTH FIRST BY uid SET ordercol select pg_typeof(ordercol), * from tmp limit 1; pg_typeof | uid | lkuid | depth | path | cycle | ordercol -----------+-----+-------+-------+-------+-------+---------- record | 1 | 7 | 0 | {1,7} | f | (0,1) (1 row)复制
深度优先record[]
with recursive tmp as ( select uid, lkuid, 0 as depth, array[uid,lkuid] as path, false as cycle from bs where uid=1 union all select bs.uid, bs.lkuid, tmp.depth+1, tmp.path||bs.lkuid, bs.lkuid=any(tmp.path) from bs , tmp where bs.uid=tmp.lkuid and not bs.lkuid=any(tmp.path) ) SEARCH DEPTH FIRST BY uid SET ordercol select pg_typeof(ordercol), * from tmp limit 1; pg_typeof | uid | lkuid | depth | path | cycle | ordercol -----------+-----+-------+-------+-------+-------+---------- record[] | 1 | 7 | 0 | {1,7} | f | {(1)} (1 row)复制
深度优先的实现方法, 排序:
explain with recursive tmp as ( select uid, lkuid, 0 as depth, array[uid,lkuid] as path, false as cycle from bs where uid=1 union all select bs.uid, bs.lkuid, tmp.depth+1, tmp.path||bs.lkuid, bs.lkuid=any(tmp.path) from bs , tmp where bs.uid=tmp.lkuid and not bs.lkuid=any(tmp.path) ) SEARCH DEPTH FIRST BY uid SET ordercol select * from tmp order by ordercol; QUERY PLAN ------------------------------------------------------------------------------------------- Sort (cost=111.18..112.52 rows=537 width=77) Sort Key: tmp.ordercol CTE tmp -> Recursive Union (cost=0.00..76.09 rows=537 width=77) -> Seq Scan on bs (cost=0.00..1.70 rows=7 width=77) Filter: (uid = 1) -> Hash Join (cost=2.28..6.37 rows=53 width=77) Hash Cond: (bs_1.uid = tmp_1.lkuid) Join Filter: (bs_1.lkuid <> ALL (tmp_1.path)) -> Seq Scan on bs bs_1 (cost=0.00..1.56 rows=56 width=8) -> Hash (cost=1.40..1.40 rows=70 width=72) -> WorkTable Scan on tmp tmp_1 (cost=0.00..1.40 rows=70 width=72) -> CTE Scan on tmp (cost=0.00..10.74 rows=537 width=77) (13 rows)复制
PostgreSQL 许愿链接
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
9.9元购买3个月阿里云RDS PostgreSQL实例
PostgreSQL 解决方案集合
德哥 / digoal's github - 公益是一辈子的事.
「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」
关注作者
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文章的来源（墨天轮），文章链接，文章作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
