PostgreSQL 图式搜索(graph search)实践 - 百亿级图谱,毫秒响应

本文涉及的产品
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云原生数据库 PolarDB 分布式版,标准版 2核8GB
云数据库 RDS MySQL Serverless,0.5-2RCU 50GB
简介: 标签 PostgreSQL , CTE , 递归查询 , cycle , depth , loop , deep , level , 层级 , array , row array , JSON 背景 图式搜索是PostgreSQL在(包括流计算、全文检索、图式搜索、K-V存储、图像搜索、指纹搜索、空间数据、时序数据、推荐等)诸多特性中的一个。

标签

PostgreSQL , CTE , 递归查询 , cycle , depth , loop , deep , level , 层级 , array , row array , JSON


背景

图式搜索是PostgreSQL在(包括流计算、全文检索、图式搜索、K-V存储、图像搜索、指纹搜索、空间数据、时序数据、推荐等)诸多特性中的一个。

采用CTE语法,可以很方便的实现图式搜索(N度搜索、最短路径、点、边属性等)。

其中图式搜索中的:层级深度,是否循环,路径,都是可表述的。

pic

pic

例子

创建1000万用户,每5万作为一个有牵连的群体,平均每个用户牵连500个用户,形成50亿的大规模关系网。

在此基础上,演示如下

1、如何实现N度搜索,边的属性查看,以及最短路径搜索等需求。

2、如何去除循环点,如何控制深度,如何展示路径等。

3、如何生成绘图数据。

创建50亿测试数据

创建1000万用户,每5万作为一个有牵连的群体,平均每个用户牵连500个用户,形成50亿的大规模关系网。

1、建表,表结构如下,可以描述点、边。

create table a(    
  c1 int,                -- 点1    
  c2 int,                -- 点2    
  prop jsonb,            -- 点1,2对应的边的属性,使用JSON存储,包括权重,关系等等。    
  primary key (c1,c2)    -- 主键    
);    
    
create index idx_a_2 on a(c1, COALESCE(((prop ->> 'weight'::text))::float8, 0));  

2、生成测试数据:

vi test.sql    
    
\set id random(1,10000000)    
insert into a select :id, ((width_bucket(:id,1,10000000,2000)-1)*50000 + (random()*50000)::int) from generate_series(1,1000) on conflict (c1,c2) do nothing;    
pgbench -M prepared -n -r -P 5 -f ./test.sql -c 50 -j 50 -t 100000      

3、数据约340GB

如何去除循环点、控制深度、展示路径

1、当路径中重复出现某个点时,说明发生了循环。

2、每递归一次,深度加1。

3、使用数组存储路径。单列数组,或多列(ROW数组),多列路径参考: https://www.postgresql.org/docs/10/static/queries-with.html

SQL如下:

WITH RECURSIVE search_graph(    
  c1,   -- 点1    
  c2,   -- 点2    
  prop, -- 边的属性    
  depth, -- 深度,从1开始    
  path,  -- 路径,数组存储    
  cycle  -- 是否循环    
) AS (    
        SELECT    -- ROOT节点查询    
          g.c1,   -- 点1    
          g.c2,   -- 点2    
          g.prop,   -- 边的属性    
          1,        -- 初始深度=1    
          ARRAY[g.c1],   -- 初始路径    
          false          -- 是否循环(初始为否)    
        FROM a AS g     
        WHERE     
          c1 = ?         -- ROOT节点=?    
      UNION ALL    
        SELECT     -- 递归子句    
          g.c1,    -- 点1    
          g.c2,    -- 点2    
          g.prop,          -- 边的属性    
          sg.depth + 1,    -- 深度+1    
          path || g.c1,    -- 路径中加入新的点    
          g.c1 = ANY(path)    -- 是否循环,判断新点是否已经在之前的路径中    
        FROM a AS g, search_graph AS sg   -- 循环 INNER JOIN    
        WHERE     
          g.c1 = sg.c2         -- 递归JOIN条件    
          AND NOT cycle        -- 防止循环    
          AND sg.depth <= ?    -- 搜索深度=?       
)    
SELECT * FROM search_graph;    -- 查询递归表,可以加LIMIT输出,也可以使用游标    

N度搜索

N度搜索,如上SQL,输入sg.depth <= N。

例如,搜索ROOT=31208的三度数据。

WITH RECURSIVE search_graph(    
  c1,   -- 点1    
  c2,   -- 点2    
  prop, -- 边的属性    
  depth, -- 深度,从1开始    
  path,  -- 路径,数组存储    
  cycle  -- 是否循环    
) AS (    
        SELECT    -- ROOT节点查询    
          g.c1,   -- 点1    
          g.c2,   -- 点2    
          g.prop,   -- 边的属性    
          1,        -- 初始深度=1    
          ARRAY[g.c1],   -- 初始路径    
          false          -- 是否循环(初始为否)    
        FROM a AS g     
        WHERE     
          c1 = 31208         -- ROOT节点=?    
      UNION ALL    
        SELECT     -- 递归子句    
          g.c1,    -- 点1    
          g.c2,    -- 点2    
          g.prop,          -- 边的属性    
          sg.depth + 1,    -- 深度+1    
          path || g.c1,    -- 路径中加入新的点    
          g.c1 = ANY(path)    -- 是否循环,判断新点是否已经在之前的路径中    
        FROM a AS g, search_graph AS sg   -- 循环 INNER JOIN    
        WHERE     
          g.c1 = sg.c2         -- 递归JOIN条件    
          AND NOT cycle        -- 防止循环    
          AND sg.depth <= 3    -- 搜索深度=?       
)    
SELECT * FROM search_graph;    -- 查询递归表,可以加LIMIT输出,也可以使用游标    

最短路径

去掉搜索深度,并且在查询递归表的语句中,加上WHERE条件(过滤C2)以及LIMIT 1 即可。

SQL如下:

WITH RECURSIVE search_graph(    
  c1,   -- 点1    
  c2,   -- 点2    
  prop, -- 边的属性    
  depth, -- 深度,从1开始    
  path,  -- 路径,数组存储    
  cycle  -- 是否循环    
) AS (    
        SELECT    -- ROOT节点查询    
          g.c1,   -- 点1    
          g.c2,   -- 点2    
          g.prop,   -- 边的属性    
          1,        -- 初始深度=1    
          ARRAY[g.c1],   -- 初始路径    
          false          -- 是否循环(初始为否)    
        FROM a AS g     
        WHERE     
          c1 = ?         -- ROOT节点=?      --(最短路径的起点)    
      UNION ALL    
        SELECT     -- 递归子句    
          g.c1,    -- 点1    
          g.c2,    -- 点2    
          g.prop,          -- 边的属性    
          sg.depth + 1,    -- 深度+1    
          path || g.c1,    -- 路径中加入新的点    
          g.c1 = ANY(path)    -- 是否循环,判断新点是否已经在之前的路径中    
        FROM a AS g, search_graph AS sg   -- 循环 INNER JOIN    
        WHERE     
          g.c1 = sg.c2         -- 递归JOIN条件    
          AND NOT cycle        -- 防止循环    
--        AND sg.depth <= ?    -- 搜索深度=?    
)    
SELECT * FROM search_graph    
  where c2 = ?   -- 最短路径的终点    
  limit 1;       -- 查询递归表,可以加LIMIT输出,也可以使用游标    

例如搜索 1 到 100 的最短路径。

WITH RECURSIVE search_graph(    
  c1,   -- 点1    
  c2,   -- 点2    
  prop, -- 边的属性    
  depth, -- 深度,从1开始    
  path,  -- 路径,数组存储    
  cycle  -- 是否循环    
) AS (    
        SELECT    -- ROOT节点查询    
          g.c1,   -- 点1    
          g.c2,   -- 点2    
          g.prop,   -- 边的属性    
          1,        -- 初始深度=1    
          ARRAY[g.c1],   -- 初始路径    
          false          -- 是否循环(初始为否)    
        FROM a AS g     
        WHERE     
          c1 = 1         -- ROOT节点=?      --(最短路径的起点)    
      UNION ALL    
        SELECT     -- 递归子句    
          g.c1,    -- 点1    
          g.c2,    -- 点2    
          g.prop,          -- 边的属性    
          sg.depth + 1,    -- 深度+1    
          path || g.c1,    -- 路径中加入新的点    
          g.c1 = ANY(path)    -- 是否循环,判断新点是否已经在之前的路径中    
        FROM a AS g, search_graph AS sg   -- 循环 INNER JOIN    
        WHERE     
          g.c1 = sg.c2         -- 递归JOIN条件    
          AND NOT cycle        -- 防止循环    
--        AND sg.depth <= ?    -- 搜索深度=?    
)    
SELECT * FROM search_graph    
  where c2 = 100   -- 最短路径的终点    
  limit 1;         -- 查询递归表,可以加LIMIT输出,也可以使用游标    

如果要控制深度,比如5度以内搜不到就不搜了,把搜索深度的条件再加进去即可。

如何生成绘图数据

为了提高响应速度,使用游标返回。

begin;    
declare cur1 cursor for $query;    
FETCH 1000 from cur1;    
....    
close cur1;    
end;    

响应时间飞快,毫秒级响应。

控制每一层的返回记录数

层级越深,返回的记录就越多,而实际上在图搜索中,并不需要返回每个层级的所有记录,(例如只返回相关性较高的前N条,或者是满足权重大于多少的,前N条),从而控制每个层级的记录数。

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 coalesce((prop->>'weight')::float8,0) >= ?        -- 相关性权重    
          -- ORDER BY coalesce((prop->>'weight')::float8,0) 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 coalesce((prop->>'weight')::float8,0) >= ?   -- 相关性权重    
          -- ORDER BY coalesce((prop->>'weight')::float8,0) desc   -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit ?            -- 每个层级限制多少条?               
        ) t    
)    
SELECT * FROM search_graph;    -- 查询递归表,可以加LIMIT输出,也可以使用游标    

例如,搜索root=31208的3度数据,同时限制每个层级返回100条。

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 = 31208             -- ROOT节点=?    
          -- AND coalesce((prop->>'weight')::float8,0) >= ?   -- 相关性权重    
          -- ORDER BY coalesce((prop->>'weight')::float8,0) desc   -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit 100            -- 每个层级限制多少条?    
        ) 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 <= 3    -- 搜索深度=?      
          -- AND coalesce((g.prop->>'weight')::float8,0) >= ?   -- 相关性权重    
          -- ORDER BY coalesce((g.prop->>'weight')::float8,0) desc   -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit 100            -- 每个层级限制多少条?               
        ) t    
)    
SELECT * FROM search_graph;    -- 查询递归表,可以加LIMIT输出,也可以使用游标    
   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    
.................
 3032152 | 30347906 |      |     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    

响应速度3.2毫秒。(理由很简单,因为每一个层级都是索引命中,结合PG的cluster特性(按c1排序存储),可以降低块数,再次提高性能)

                                                                      QUERY PLAN                                                                         
-------------------------------------------------------------------------------------------------------------------------------------------------------  
 CTE Scan on search_graph  (cost=25460.78..25482.78 rows=1100 width=77) (actual time=0.044..2.009 rows=300 loops=1)  
   Output: search_graph.c1, search_graph.c2, search_graph.prop, search_graph.depth, search_graph.path, search_graph.cycle  
   Buffers: shared hit=522  
   CTE search_graph  
     ->  Recursive Union  (cost=0.58..25460.78 rows=1100 width=77) (actual time=0.042..1.755 rows=300 loops=1)  
           Buffers: shared hit=522  
           ->  Limit  (cost=0.58..402.52 rows=100 width=77) (actual time=0.040..0.183 rows=100 loops=1)  
                 Output: g.c1, g.c2, g.prop, 1, (ARRAY[g.c1]), false  
                 Buffers: shared hit=97  
                 ->  Index Scan using a_pkey on public.a g  (cost=0.58..393024.56 rows=97782 width=77) (actual time=0.038..0.166 rows=100 loops=1)  
                       Output: g.c1, g.c2, g.prop, 1, ARRAY[g.c1], false  
                       Index Cond: (g.c1 = 31208)  
                       Buffers: shared hit=97  
           ->  Limit  (cost=2249.76..2502.53 rows=100 width=77) (actual time=0.372..0.473 rows=67 loops=3)  
                 Output: g_1.c1, g_1.c2, g_1.prop, ((sg.depth + 1)), ((sg.path || g_1.c1)), ((g_1.c1 = ANY (sg.path)))  
                 Buffers: shared hit=425  
                 ->  Nested Loop  (cost=2249.76..41872589.09 rows=16564685 width=77) (actual time=0.372..0.462 rows=67 loops=3)  
                       Output: g_1.c1, g_1.c2, g_1.prop, (sg.depth + 1), (sg.path || g_1.c1), (g_1.c1 = ANY (sg.path))  
                       Buffers: shared hit=425  
                       ->  WorkTable Scan on search_graph sg  (cost=0.00..22.50 rows=167 width=40) (actual time=0.001..0.011 rows=35 loops=3)  
                             Output: sg.c1, sg.c2, sg.prop, sg.depth, sg.path, sg.cycle  
                             Filter: ((NOT sg.cycle) AND (sg.depth <= 3))  
                       ->  Bitmap Heap Scan on public.a g_1  (cost=2249.76..248006.21 rows=99190 width=40) (actual time=0.010..0.010 rows=2 loops=104)  
                             Output: g_1.c1, g_1.c2, g_1.prop  
                             Recheck Cond: (g_1.c1 = sg.c2)  
                             Heap Blocks: exact=3  
                             Buffers: shared hit=425  
                             ->  Bitmap Index Scan on a_pkey  (cost=0.00..2224.96 rows=99190 width=0) (actual time=0.009..0.009 rows=19 loops=104)  
                                   Index Cond: (g_1.c1 = sg.c2)  
                                   Buffers: shared hit=422  
 Planning time: 0.436 ms  
 Execution time: 2.128 ms  
(32 rows)  
  
Time: 3.301 ms  

压测,TPS:1.2万,平均响应时间5.2毫秒。

transaction type: ./test.sql  
scaling factor: 1  
query mode: prepared  
number of clients: 64  
number of threads: 64  
duration: 120 s  
number of transactions actually processed: 1463760  
latency average = 5.239 ms  
latency stddev = 1.171 ms  
tps = 12196.876360 (including connections establishing)  
tps = 12201.718092 (excluding connections establishing)  
script statistics:  
 - statement latencies in milliseconds:  
         5.295  WITH RECURSIVE search_graph(  

图式搜索UDF封装例子

将冗长的SQL封装成UDF,可以简化应用调用的接口。

1、UDF1 ,返回记录

create or replace function graph_search1(  
  IN i_root int,                       -- 根据哪个节点开始搜    
  IN i_depth int  default 99999,       -- 搜索层级、深度限制  
  IN i_limit int8 default 2000000000,  -- 限制每一层返回的记录数  
  IN i_weight float8 default 0,        -- 限制权重  
  OUT o_path int[],                    -- 输出:路径, ID 组成的数组  
  OUT o_point1 int,                    -- 输出:点1 ID  
  OUT o_point2 int,                    -- 输出:点2 ID  
  OUT o_link_prop jsonb,               -- 输出:当前两点之间的连接属性  
  OUT o_depth int                      -- 输出:当前深度、层级  
) returns setof record as $$  
declare  
  sql text;  
begin  
sql := format($_$  
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 = %s                                                    -- ROOT节点=?    
          AND coalesce((g.prop->>'weight')::float8,0) >= %s          -- 相关性权重    
          ORDER BY coalesce((g.prop->>'weight')::float8,0) desc      -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit %s                           -- 每个层级限制多少条?    
        ) 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 <= %s                 -- 搜索深度=?      
          AND coalesce((g.prop->>'weight')::float8,0) >= %s          -- 相关性权重    
          ORDER BY coalesce((g.prop->>'weight')::float8,0) desc      -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit %s                           -- 每个层级限制多少条?               
        ) t    
)    
SELECT path||c2 as o_path, c1 as o_point1, c2 as o_point2, prop as o_link_prop, depth as o_depth  
FROM search_graph;                           -- 查询递归表,可以加LIMIT输出,也可以使用游标   
$_$, i_root, i_weight, i_limit, i_depth, i_weight, i_limit  
);  
  
return query execute sql;  
  
end;  
$$ language plpgsql strict;  

使用举例:

postgres=# select * from graph_search1(31208, 3, 100, 0);  
             o_path              | o_point1 | o_point2 | o_link_prop | o_depth   
---------------------------------+----------+----------+-------------+---------  
 {31208,344710}                  |    31208 |   344710 |             |       1  
 {31208,319951}                  |    31208 |   319951 |             |       1  
 {31208,340938}                  |    31208 |   340938 |             |       1  
 {31208,325272}                  |    31208 |   325272 |             |       1  
 {31208,346519}                  |    31208 |   346519 |             |       1  
 {31208,314594}                  |    31208 |   314594 |             |       1  
 {31208,307217}                  |    31208 |   307217 |             |       1  
 {31208,348009}                  |    31208 |   348009 |             |       1  
 {31208,300046}                  |    31208 |   300046 |             |       1  
 {31208,344359}                  |    31208 |   344359 |             |       1  
 {31208,318790}                  |    31208 |   318790 |             |       1  
 {31208,321034}                  |    31208 |   321034 |             |       1  
 {31208,301609}                  |    31208 |   301609 |             |       1  
 {31208,344339}                  |    31208 |   344339 |             |       1  
 {31208,314087}                  |    31208 |   314087 |             |       1  
......  
 {31208,319951,3199647,31991191} |  3199647 | 31991191 |             |       3  
 {31208,319951,3199647,31954904} |  3199647 | 31954904 |             |       3  
 {31208,319951,3199647,31986691} |  3199647 | 31986691 |             |       3  
 {31208,319951,3199647,31986448} |  3199647 | 31986448 |             |       3  
 {31208,319951,3199647,31993624} |  3199647 | 31993624 |             |       3  
 {31208,319951,3199647,31997771} |  3199647 | 31997771 |             |       3  
 {31208,319951,3199647,31982764} |  3199647 | 31982764 |             |       3  
 {31208,319951,3199647,31993420} |  3199647 | 31993420 |             |       3  
 {31208,319951,3199647,31962666} |  3199647 | 31962666 |             |       3  
 {31208,319951,3199647,31957536} |  3199647 | 31957536 |             |       3  
(300 rows)  

2、UDF2,返回游标

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,  -- 限制每一层返回的记录数  
  IN i_weight float8 default 0         -- 限制权重  
) returns refcursor as $$  
declare  
  sql text;  
  res refcursor := i_res;  
begin  
sql := format($_$  
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 = %s                                                    -- ROOT节点=?    
          AND coalesce((g.prop->>'weight')::float8,0) >= %s          -- 相关性权重    
          ORDER BY coalesce((g.prop->>'weight')::float8,0) desc      -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit %s                           -- 每个层级限制多少条?    
        ) 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 <= %s                 -- 搜索深度=?      
          AND coalesce((g.prop->>'weight')::float8,0) >= %s          -- 相关性权重    
          ORDER BY coalesce((g.prop->>'weight')::float8,0) desc      -- 可以使用ORDER BY,例如返回权重排在前面的N条。    
          limit %s                           -- 每个层级限制多少条?               
        ) t    
)    
SELECT path||c2 as o_path, c1 as o_point1, c2 as o_point2, prop as o_link_prop, depth as o_depth  
FROM search_graph;                           -- 查询递归表,可以加LIMIT输出,也可以使用游标   
$_$, i_root, i_weight, i_limit, i_depth, i_weight, i_limit  
);  
  
open res for execute sql;  
return res;  
  
end;  
$$ language plpgsql strict;  

使用举例,

postgres=# begin;  
BEGIN  
postgres=# select * from graph_search2(31208, 'cur1', 3, 100, 0);  
 graph_search2   
---------------  
 cur1  
(1 row)  
  
postgres=# fetch 10 from cur1;  
     o_path     | o_point1 | o_point2 | o_link_prop | o_depth   
----------------+----------+----------+-------------+---------  
 {31208,344710} |    31208 |   344710 |             |       1  
 {31208,319951} |    31208 |   319951 |             |       1  
 {31208,340938} |    31208 |   340938 |             |       1  
 {31208,325272} |    31208 |   325272 |             |       1  
 {31208,346519} |    31208 |   346519 |             |       1  
 {31208,314594} |    31208 |   314594 |             |       1  
 {31208,307217} |    31208 |   307217 |             |       1  
 {31208,348009} |    31208 |   348009 |             |       1  
 {31208,300046} |    31208 |   300046 |             |       1  
 {31208,344359} |    31208 |   344359 |             |       1  
(10 rows)  
  
postgres=# close cur1;  
CLOSE CURSOR  
postgres=# end;  
COMMIT  

小结

使用PostgreSQL的CTE语法,可以非常方便的实现图式搜索的需求,包括N度搜索、最短路径搜索,路径、点、边属性(边的属性使用JSON存储,方便架构设计。)展示,层级深度控制和展示,控制每一层的返回数,控制每一层的返回顺序和权重等 等)。

性能方面,PG 10 ON ECS的环境,50亿的点边网络,N度搜索、最短路径搜索,响应时间都在毫秒级(其中3度搜索,每层100条限制,仅2.1毫秒,TPS达到1.2万)。

以上查询,可以封装成PostgreSQL的plpgsql UDF接口,便于业务调用(暴露一些输入条件即可)。

参考

《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》

https://www.postgresql.org/docs/10/static/queries-with.html

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
相关文章
|
3月前
|
存储 SQL Cloud Native
深入了解云原生数据库CockroachDB的概念与实践
作为一种全球领先的分布式SQL数据库,CockroachDB以其高可用性、强一致性和灵活性等特点备受关注。本文将深入探讨CockroachDB的概念、设计思想以及实践应用,并结合实例演示其在云原生环境下的优越表现。
|
3月前
|
Cloud Native 关系型数据库 大数据
CockroachDB:云原生数据库的新概念与实践
本文将介绍CockroachDB,一种先进的云原生数据库,它具备分布式、强一致性和高可用性等特点。我们将探讨CockroachDB的基本原理、架构设计以及在实际应用中的种种优势和挑战。
|
6月前
|
负载均衡 监控 关系型数据库
百度搜索:蓝易云【PostgreSQL 主从复制方案】
请注意,上述仅为一种主从复制方案的概述,实际实施时可能需要根据特定环境和需求进行调整。建议参考PostgreSQL官方文档和其他可靠资源获取更详细的指南和说明。
89 1
|
6月前
|
Ubuntu 关系型数据库 数据库
百度搜索:蓝易云【Ubuntu系统安装 PostgreSQL详细教程。】
现在,你已经成功在Ubuntu系统上安装了PostgreSQL,并创建了一个新的数据库和用户。你可以使用所创建的用户凭据连接到数据库并开始使用。记得根据你的具体需求进行进一步的配置和安全性调整。
251 2
|
4月前
|
存储 关系型数据库 MySQL
存储成本最高降至原来的5%,PolarDB分布式冷数据归档的业务实践
国内某家兼具投资理财、文化旅游、票务为一体的大型综合型集团公司,2015年成立至今,由于业务高速发展,业务数据增长非常快,数据库系统屡次不堪重负。该公司数据库运维总监介绍,他们目前业务压力比较大的是票务和订单系统,他们的平台每天新增几千万的订单数据,订单的数据来自于各个终端,近几年每个月以300G的数据规模在高速增长,由于数据不断增加,数据库系统迄今为止迭代过了3次。
|
6月前
|
SQL 缓存 关系型数据库
PolarDB-X 混沌测试实践:如何衡量数据库索引选择能力
随着PolarDB分布式版的不断演进,功能不断完善,新的特性不断增多,整体架构扩大的同时带来了测试链路长,出现问题前难发现,出现问题后难排查等等问题。原有的测试框架已经难以支撑实际场景的复杂模拟测试。因此,我们实现了一个基于业务场景面向优化器索引选择的混沌查询实验室,本文之后简称为CEST(complex environment simulation test)。
|
7月前
|
存储 SQL 关系型数据库
AnalyticDB PostgreSQL构建一站式实时数仓实践
本文介绍通过 AnalyticDB PostgreSQL 版基于实时物化视图,构建流批一体的一站式实时数仓解决方案,实现一套系统、一份数据、一次写入,即可在数仓内完成实时数据源头导入到实时分析全流程。
1874 5
AnalyticDB PostgreSQL构建一站式实时数仓实践
|
7月前
|
关系型数据库 分布式数据库 数据库
沉浸式学习PostgreSQL|PolarDB 10: 社交、刑侦等业务, 关系图谱搜索
业务场景1 介绍: 社交、刑侦等业务, 关系图谱搜索 - 营销、分销、流量变现、分佣、引爆流行、裂变式传播、家谱、选课、社交、人才库、刑侦、农产品溯源、药品溯源 图式搜索是PolarDB | PostgreSQL在(包括流计算、全文检索、图式搜索、K-V存储、图像搜索、指纹搜索、空间数据、时序数据、推荐等)诸多特性中的一个。 采用CTE语法,可以很方便的实现图式搜索(N度搜索、最短路径、点、边属性等)。 其中图式搜索中的:层级深度,是否循环,路径,都是可表述的。
202 0
沉浸式学习PostgreSQL|PolarDB 10: 社交、刑侦等业务, 关系图谱搜索
|
8月前
|
分布式数据库 调度 数据库
直播预告 | PolarDB-X 备份恢复原理与实践
备份恢复是生产级数据库必不可少的功能,而PolarDB-X 作为一款分布式数据库,备份数据的全局一致也是最基本的要求。本期分享将介绍PolarDB-X 开源版备份恢复功能的背景与原理,以及如何使用 PolarDB-X Operator 实现备份调度。
直播预告 | PolarDB-X 备份恢复原理与实践
|
8月前
|
关系型数据库 测试技术 分布式数据库
PolarDB | PostgreSQL 高并发队列处理业务的数据库性能优化实践
在电商业务中可能涉及这样的场景, 由于有上下游关系的存在, 1、用户下单后, 上下游厂商会在自己系统中生成一笔订单记录并反馈给对方, 2、在收到反馈订单后, 本地会先缓存反馈的订单记录队列, 3、然后后台再从缓存取出订单并进行处理. 如果是高并发的处理, 因为大家都按一个顺序获取, 容易产生热点, 可能遇到取出队列遇到锁冲突瓶颈、IO扫描浪费、CPU计算浪费的瓶颈. 以及在清除已处理订单后, 索引版本未及时清理导致的回表版本判断带来的IO浪费和CPU运算浪费瓶颈等. 本文将给出“队列处理业务的数据库性能优化”优化方法和demo演示. 性能提升10到20倍.
595 4

相关产品

  • 云原生数据库 PolarDB