PostgreSQL 家谱、族谱类应用实践 - 图式关系存储与搜索

9 minute read

背景

最近《最强大脑》节目的国际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)  