标签
PostgreSQL , 家谱 , 族谱 , 图式搜索
背景
最近《最强大脑》节目的国际PK赛中，来自谷歌的一位国际选手展示了他在谷歌时做的一套系统，把三国人物关系整理并展示成了一张大图，属于非常典型的图式应用。
PostgreSQL非常适合于这类场景，有着丰富的SQL接口和良好的性能。下面这些都是PG在图式搜索方面的应用：
《小微贷款、天使投资(风控助手)业务数据库设计(图式搜索\图谱分析) - 阿里云RDS PostgreSQL, HybridDB for PostgreSQL最佳实践》
《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》
《PostgreSQL 图式搜索(graph search)实践 - 百亿级图谱，毫秒响应》
《PostgreSQL 实践 - 内容社区(如论坛)图式搜索应用》
今天这篇文档与之类似，来自一位社区朋友的问题，如何存储家族关系，并快速提取N级信息。是不是和我之前写的社交类用户关系，风控类企业关系相似呢？
设计表结构
1、个人信息表，描述个人的详细信息、出生年月、住址、城市、等等。因为无法列举全个人的信息，所以我们可以用JSON来扩展这个等等，是不是很爽呢。
create table tbl_p_detail -- 个人信息
(
id int primary key, -- 人物ID
info jsonb, -- 人物描述
crt_time timestamp -- 创建时间
);
2、关系的元数据表，例如父亲，母亲，丈夫，妻子，儿子，女儿，养女，继父，干爹，干女儿，等等。
create table tbl_er_desc -- 关系描述
(
id int2 primary key, -- 关系ID
info text -- 描述
);
3、关系表，这里面为了保证查询的准确性（或者说简化查询语句），我们使用双向冗余存储，例如父亲、儿子一对，存两条。
create table tbl_er -- id1是id2的谁
(
c1 int references tbl_p_detail(id),
c2 int references tbl_p_detail(id),
prop int2[], -- 可能存在多种关系，我们使用数组存储。这个就是边，当然我们也可以用JSON来存储边。请参考我写的另一篇文档
crt_time timestamp,
check (c1<>c2),
unique (c1,c2)
-- FOREIGN KEY (EACH ELEMENT OF prop) REFERENCES tbl_er_desc(id) -- 数组外键, PG 11会支持，很不错
);
4、创建索引加速
create index idx_tbl_er_c1 on tbl_er(c1);
create index idx_tbl_er_c2 on tbl_er(c2);
5、写入一些测试数据
insert into tbl_p_detail select generate_series(1,10000);
insert into tbl_er values (1,2,array[10],now()); -- 比如 1是2的父亲
insert into tbl_er values (2,1,array[9],now()); -- 比如 2是1的女儿
insert into tbl_er values (1,3,array[10],now()); -- 比如 1是3的父亲
insert into tbl_er values (3,1,array[9],now()); -- 比如 3是1的女儿
insert into tbl_er values (5,2,array[11],now()); -- 比如 5是2的母亲
insert into tbl_er values (2,5,array[9],now()); -- 比如 2是5的女儿
insert into tbl_er values (5,3,array[11],now()); -- 比如 5是3的母亲
insert into tbl_er values (3,5,array[9],now()); -- 比如 3是5的女儿
insert into tbl_er values (4,1,array[10],now()); -- 比如 4是1的父亲
insert into tbl_er values (1,4,array[8],now()); -- 比如 1是4的儿子
insert into tbl_er values (6,5,array[10],now()); -- 比如 6是5的父亲
insert into tbl_er values (5,6,array[9],now()); -- 比如 5是6的女儿
insert into tbl_er values (7,1,array[11],now()); -- 比如 7是1的母亲
insert into tbl_er values (1,7,array[8],now()); -- 比如 1是7的儿子
insert into tbl_er values (8,5,array[11],now()); -- 比如 8是5的母亲
insert into tbl_er values (5,8,array[9],now()); -- 比如 5是8的女儿
定义搜索函数
1、搜索某个用户的N层关系数据，以及每一层的限制记录数。（通常家族数据不会那么恐怖，所以限制层级即可，每一层输出所有也无所谓）
create or replace function graph_search1(
IN i_root int, -- 根据哪个节点开始搜
IN i_depth int default 99999, -- 搜索层级、深度限制
IN i_limit int8 default 2000000000, -- 限制每一层返回的记录数
OUT o_path int[], -- 输出：路径, ID 组成的数组
OUT o_point1 int, -- 输出：点1 ID
OUT o_point2 int, -- 输出：点2 ID
OUT o_link_prop int2[], -- 输出：当前两点之间的连接属性
OUT o_link_prop_all text, -- 输出：从开始到当前点的连接属性
OUT o_depth int -- 输出：当前深度、层级
) returns setof record as $$
declare
sql text;
begin
sql := format($_$
WITH RECURSIVE search_graph(
c1, -- 点1
c2, -- 点2
prop, -- 当前边的属性
all_prop, -- all 边的属性
depth, -- 当前深度，从1开始
path -- 路径，数组存储
) AS (
select c1,c2,prop,all_prop,depth,path from (
SELECT -- ROOT节点查询
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
g.prop::text as all_prop, -- all 边的属性
1 depth, -- 初始深度=1
ARRAY[g.c1, g.c2] path -- 初始路径
FROM tbl_er AS g
WHERE
c1 = %s -- ROOT节点=?
limit %s -- 每个层级限制多少条？
) t
UNION ALL
select c1,c2,prop,all_prop,depth,path from (
SELECT -- 递归子句
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
sg.all_prop || g.prop::text as all_prop, -- all 边的属性
sg.depth + 1 depth, -- 深度+1
sg.path || g.c2 path -- 路径中加入新的点
FROM tbl_er AS g, search_graph AS sg -- 循环 INNER JOIN
WHERE
g.c1 = sg.c2 -- 递归JOIN条件
AND (g.c2 <> ALL(sg.path)) -- 防止循环 , 是否循环，判断新点是否已经在之前的路径中
AND sg.depth <= %s -- 搜索深度=?
limit %s -- 每个层级限制多少条？
) t
)
SELECT path as o_path, c1 as o_point1, c2 as o_point2, prop as o_link_prop, all_prop as o_link_prop_all, depth as o_depth
FROM search_graph; -- 查询递归表，可以加LIMIT输出，也可以使用游标
$_$, i_root, i_limit, i_depth, i_limit
);
return query execute sql;
end;
$$ language plpgsql strict;
例子
postgres=# select * from graph_search1(1);
o_path | o_point1 | o_point2 | o_link_prop | o_link_prop_all | o_depth
-----------+----------+----------+-------------+-----------------+---------
{1,2} | 1 | 2 | {10} | {10} | 1
{1,3} | 1 | 3 | {10} | {10} | 1
{1,4} | 1 | 4 | {8} | {8} | 1
{1,7} | 1 | 7 | {8} | {8} | 1
{1,2,5} | 2 | 5 | {9} | {10}{9} | 2
{1,3,5} | 3 | 5 | {9} | {10}{9} | 2
{1,2,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
{1,2,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,2,5,3} | 5 | 3 | {11} | {10}{9}{11} | 3
{1,3,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
{1,3,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,3,5,2} | 5 | 2 | {11} | {10}{9}{11} | 3
(12 rows)
Time: 1.120 ms
2、定义类似的搜索函数，但是返回游标。（家族图谱关系没有那么多，所以不需要游标返回，如果是社交类图谱，数据量大，建议用游标返回。）
create or replace function graph_search2(
IN i_root int, -- 根据哪个节点开始搜
IN i_res name, -- 游标名
IN i_depth int default 99999, -- 搜索层级、深度限制
IN i_limit int8 default 2000000000 -- 限制每一层返回的记录数
) returns refcursor as $$
declare
sql text;
res refcursor := i_res;
begin
sql := format($_$
WITH RECURSIVE search_graph(
c1, -- 点1
c2, -- 点2
prop, -- 当前边的属性
all_prop, -- all 边的属性
depth, -- 当前深度，从1开始
path -- 路径，数组存储
) AS (
select c1,c2,prop,all_prop,depth,path from (
SELECT -- ROOT节点查询
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
g.prop::text as all_prop, -- all 边的属性
1 depth, -- 初始深度=1
ARRAY[g.c1, g.c2] path -- 初始路径
FROM tbl_er AS g
WHERE
c1 = %s -- ROOT节点=?
limit %s -- 每个层级限制多少条？
) t
UNION ALL
select c1,c2,prop,all_prop,depth,path from (
SELECT -- 递归子句
g.c1, -- 点1
g.c2, -- 点2
g.prop, -- 边的属性
sg.all_prop || g.prop::text as all_prop, -- all 边的属性
sg.depth + 1 depth, -- 深度+1
sg.path || g.c2 path -- 路径中加入新的点
FROM tbl_er AS g, search_graph AS sg -- 循环 INNER JOIN
WHERE
g.c1 = sg.c2 -- 递归JOIN条件
AND (g.c2 <> ALL(sg.path)) -- 防止循环 , 是否循环，判断新点是否已经在之前的路径中
AND sg.depth <= %s -- 搜索深度=?
limit %s -- 每个层级限制多少条？
) t
)
SELECT path as o_path, c1 as o_point1, c2 as o_point2, prop as o_link_prop, all_prop as o_link_prop_all, depth as o_depth
FROM search_graph; -- 查询递归表，可以加LIMIT输出，也可以使用游标
$_$, i_root, i_limit, i_depth, i_limit
);
open res for execute sql;
return res;
end;
$$ language plpgsql strict;
使用举例
postgres=# begin;
BEGIN
Time: 0.096 ms
postgres=# select * from graph_search2(1,'a');
graph_search2
---------------
a
(1 row)
Time: 1.110 ms
postgres=# fetch 10 from a;
o_path | o_point1 | o_point2 | o_link_prop | o_link_prop_all | o_depth
-----------+----------+----------+-------------+-----------------+---------
{1,2} | 1 | 2 | {10} | {10} | 1
{1,3} | 1 | 3 | {10} | {10} | 1
{1,4} | 1 | 4 | {8} | {8} | 1
{1,7} | 1 | 7 | {8} | {8} | 1
{1,2,5} | 2 | 5 | {9} | {10}{9} | 2
{1,3,5} | 3 | 5 | {9} | {10}{9} | 2
{1,2,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
{1,2,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,2,5,3} | 5 | 3 | {11} | {10}{9}{11} | 3
{1,3,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
(10 rows)
Time: 0.256 ms
postgres=# fetch 10 from a;
o_path | o_point1 | o_point2 | o_link_prop | o_link_prop_all | o_depth
-----------+----------+----------+-------------+-----------------+---------
{1,3,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,3,5,2} | 5 | 2 | {11} | {10}{9}{11} | 3
(2 rows)
Time: 0.103 ms
3、定义两点的最短路径，比如搜索张三与李四的关系。当关系超过N级时，不返还，以免出现长时间搜索。（当然，我们也可以定义语句超时，当执行时间超过N秒后退出）
create or replace function graph_search3(
IN i_p1 int, -- 节点1
IN i_p2 int, -- 节点2
IN i_depth int default 99999, -- 搜索层级、深度限制
OUT o_path int[], -- 输出：路径, ID 组成的数组
OUT o_link_prop text, -- 输出：当前两点之间的连接属性
OUT o_depth int -- 输出：当前深度、层级
) returns record as $$
declare
sql text;
begin
sql := format($_$
WITH RECURSIVE search_graph(
c1, -- 点1
c2, -- 点2
prop, -- 边的属性
depth, -- 深度，从1开始
path -- 路径，数组存储
) AS (
SELECT -- ROOT节点查询
g.c1, -- 点1
g.c2, -- 点2
g.prop::text, -- 边的属性
1 depth, -- 初始深度=1
ARRAY[g.c1, g.c2] path -- 初始路径
FROM tbl_er AS g
WHERE
c1 = %s -- ROOT节点=? --（最短路径的起点）
UNION ALL
SELECT -- 递归子句
g.c1, -- 点1
g.c2, -- 点2
sg.prop::text || g.prop::text, -- 边的属性
sg.depth + 1 as depth, -- 深度+1
sg.path || g.c2 path -- 路径中加入新的点
FROM tbl_er AS g, search_graph AS sg -- 循环 INNER JOIN
WHERE
g.c1 = sg.c2 -- 递归JOIN条件
AND (g.c2 <> ALL(sg.path)) -- 防止循环 , 是否循环，判断新点是否已经在之前的路径中
AND sg.depth <= %s -- 搜索深度=?
)
SELECT
path as o_path,
prop as o_link_prop,
depth as o_depth
FROM search_graph
where c2 = %s -- 最短路径的终点
limit 1 -- 查询递归表，可以加LIMIT输出，也可以使用游标
$_$, i_p1, i_depth, i_p2);
execute sql into o_path,o_link_prop,o_depth;
return;
end;
$$ language plpgsql strict;
使用举例
postgres=# select * from graph_search3(1,2);
o_path | o_link_prop | o_depth
--------+-------------+---------
{1,2} | {10} | 1
(1 row)
Time: 0.907 ms
postgres=# select * from graph_search3(1,5);
o_path | o_link_prop | o_depth
---------+-------------+---------
{1,2,5} | {10}{9} | 2
(1 row)
Time: 0.854 ms
postgres=# select * from graph_search3(1,8);
o_path | o_link_prop | o_depth
-----------+-------------+---------
{1,2,5,8} | {10}{9}{9} | 3
(1 row)
扩展一些关系，再度搜索
insert into tbl_er values (2,3,array[12],now()); -- 比如 2是3的姐姐
insert into tbl_er values (3,2,array[13],now()); -- 比如 3是2的妹妹
postgres=# select * from graph_search1(1);
o_path | o_point1 | o_point2 | o_link_prop | o_link_prop_all | o_depth
-------------+----------+----------+-------------+-----------------+---------
{1,2} | 1 | 2 | {10} | {10} | 1
{1,3} | 1 | 3 | {10} | {10} | 1
{1,4} | 1 | 4 | {8} | {8} | 1
{1,7} | 1 | 7 | {8} | {8} | 1
{1,2,3} | 2 | 3 | {12} | {10}{12} | 2
{1,2,5} | 2 | 5 | {9} | {10}{9} | 2
{1,3,2} | 3 | 2 | {13} | {10}{13} | 2
{1,3,5} | 3 | 5 | {9} | {10}{9} | 2
{1,2,3,5} | 3 | 5 | {9} | {10}{12}{9} | 3
{1,2,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
{1,2,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,2,5,3} | 5 | 3 | {11} | {10}{9}{11} | 3
{1,3,2,5} | 2 | 5 | {9} | {10}{13}{9} | 3
{1,3,5,8} | 5 | 8 | {9} | {10}{9}{9} | 3
{1,3,5,6} | 5 | 6 | {9} | {10}{9}{9} | 3
{1,3,5,2} | 5 | 2 | {11} | {10}{9}{11} | 3
{1,2,3,5,8} | 5 | 8 | {9} | {10}{12}{9}{9} | 4
{1,2,3,5,6} | 5 | 6 | {9} | {10}{12}{9}{9} | 4
{1,3,2,5,8} | 5 | 8 | {9} | {10}{13}{9}{9} | 4
{1,3,2,5,6} | 5 | 6 | {9} | {10}{13}{9}{9} | 4
(20 rows)
postgres=# select * from graph_search1(3);
o_path | o_point1 | o_point2 | o_link_prop | o_link_prop_all | o_depth
-------------+----------+----------+-------------+-----------------+---------
{3,1} | 3 | 1 | {9} | {9} | 1
{3,5} | 3 | 5 | {9} | {9} | 1
{3,2} | 3 | 2 | {13} | {13} | 1
{3,1,7} | 1 | 7 | {8} | {9}{8} | 2
{3,1,4} | 1 | 4 | {8} | {9}{8} | 2
{3,1,2} | 1 | 2 | {10} | {9}{10} | 2
{3,5,8} | 5 | 8 | {9} | {9}{9} | 2
{3,5,6} | 5 | 6 | {9} | {9}{9} | 2
{3,5,2} | 5 | 2 | {11} | {9}{11} | 2
{3,2,5} | 2 | 5 | {9} | {13}{9} | 2
{3,2,1} | 2 | 1 | {9} | {13}{9} | 2
{3,1,2,5} | 2 | 5 | {9} | {9}{10}{9} | 3
{3,5,2,1} | 2 | 1 | {9} | {9}{11}{9} | 3
{3,2,5,8} | 5 | 8 | {9} | {13}{9}{9} | 3
{3,2,5,6} | 5 | 6 | {9} | {13}{9}{9} | 3
{3,2,1,7} | 1 | 7 | {8} | {13}{9}{8} | 3
{3,2,1,4} | 1 | 4 | {8} | {13}{9}{8} | 3
{3,1,2,5,8} | 5 | 8 | {9} | {9}{10}{9}{9} | 4
{3,1,2,5,6} | 5 | 6 | {9} | {9}{10}{9}{9} | 4
{3,5,2,1,7} | 1 | 7 | {8} | {9}{11}{9}{8} | 4
{3,5,2,1,4} | 1 | 4 | {8} | {9}{11}{9}{8} | 4
(21 rows)
参考
《小微贷款、天使投资(风控助手)业务数据库设计(图式搜索\图谱分析) - 阿里云RDS PostgreSQL, HybridDB for PostgreSQL最佳实践》
《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》
《PostgreSQL 图式搜索(graph search)实践 - 百亿级图谱，毫秒响应》
