PostgreSQL 家族图谱、社交图谱、树状关系、藤状分佣、溯源、等场景实践 - 递归,with recursive query (有向无环 , 有向有环)

digoal 2020-03-29

329

作者

digoal

日期

2020-03-29

背景

家族图谱、社交图谱、树状关系、藤状分佣、溯源场景有个特点, 数据树状分布, 有的是有向无环图(还有的是有向有环图).

以古武侠小说里的门派为例子:

1、开山鼻祖, 收弟子
2、弟子自立门户, 继续收弟子
久而久之就会出现藤状数据.

例子

数据结构如下:

```
create table rand_tree (
pid int8 primary key, -- 掌门
cids int8[] -- 弟子
);

-- 序列
create sequence seq;
```

pid 表示开山鼻祖或自立门户的人
cids 表示弟子

说明:
- 一个人最多只有一个师傅
- 一定有人没有师傅(祖师)

生成数据的算法如下:

1、seq: 序列保证全局唯一性

2、pid:

取 10*random() 个 nextval(seq) (开山祖师) 从已有pid里随机取10行, 从这些记录的cids 里随机取 100*random() 个值 (自立门户)

3、cids:

为以上每个PID指派弟子: 取 1001*random() 个 nextval(seq)

创建一个函数, 用于实现以上算法

```
create or replace function ins() returns void as $$
declare
v_blkid int;
v_ctids tid[];

-- 100random() 个值 (自立门户)
v_limit int := (100random())::int;
v_pid int8;
begin
-- 1. 开山鼻祖
for v_pid in
-- 取 10random() 个 nextval(seq) (开山祖师)
select nextval('seq'::regclass) from generate_series(1,1+(10random())::int)
loop
-- 为以上每个PID指派弟子: 取 1001random() 个 nextval(seq)
insert into rand_tree select v_pid,array(select nextval('seq'::regclass) from generate_series(1,1+(1001random())::int)) on conflict(pid) do nothing;
end loop;

-- 2. 自立门户
select floor(relpages*random())::int into v_blkid from pg_class where relname='rand_tree';
-- 假设一个block最多400条记录
select array_agg(('('||v_blkid||','||id||')')::tid) into v_ctids from generate_series(1,400) t(id);
-- 从已有pid里随机取10行,
select array(select ctid from rand_tree where ctid=any(v_ctids) order by random() limit 10) into v_ctids;

for v_pid in
-- 从已有pid里随机10行的 cids 里随机取 100random() 个值 (自立门户)
select unnest(cids) from rand_tree where ctid=any(v_ctids) order by random() limit v_limit
loop
-- 为以上每个PID指派弟子: 取 1001random() 个 nextval(seq)
insert into rand_tree select v_pid, array(select nextval('seq'::regclass) from generate_series(1,1+(1001*random())::int)) on conflict(pid) do nothing;
end loop;
return;
end;
$$ language plpgsql strict;
```

使用pgbench调用以上函数, 生成数据:

```
vi test.sql
select ins();

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 3 -j 3 -T 300
```

将数据展开:

```
create table rtree(pid int8, cid int8);
insert into rtree select pid,unnest(cids) from rand_tree;

INSERT 0 500586221

alter table rtree add constraint pk_rtree primary key (pid,cid);
alter table rtree add constraint uk1_rtree unique (cid);
```

插入一些极端数据, 例如指定深度的树, 深度100000的树如下:

do language plpgsql $$ declare v_pid int8 := nextval('seq'::regclass); v_cid int8; begin for v_cid in select nextval('seq'::regclass) from generate_series(1,100000) loop insert into rtree values (v_pid, v_cid); v_pid := v_cid; end loop; end; $$;

数状查询测试:

找到某人的师傅, 师傅的师傅, 师傅的师傅的师傅, ... 直到祖师

id 取值范围如下

```
1 ~ nextval('seq')-1

postgres=# select min(pid),max(pid),min(cid),max(cid) from rtree ;
min | max | min | max
-----+-----------+-----+-----------
1 | 526815045 | 6 | 526815046
(1 row)
```

使用递归查询方法: 所有上游, 即: 找到某人的师傅, 师傅的师傅, 师傅的师傅的师傅, ... 直到祖师

性能数据(总记录5亿条+), 与深度有关:

树状深度为10万时, 查询耗时: 208.503 ms

```
with recursive a as (
select * from rtree where cid=526815046
union all
select t.pid,t.cid from rtree t join a on (t.cid=a.pid) where t. is not null
)
select count() from a ;

count

100000
(1 row)

Time: 208.503 ms
```

树状深度为6时, 耗时: 0.562 ms

```
postgres=# with recursive a as (
select * from rtree where cid=526715045
union all
select t.pid,t.cid from rtree t join a on (t.cid=a.pid) where t.* is not null
)
select * from a ;
pid | cid
-----------+-----------
134350347 | 526715045
99065963 | 134350347
16542946 | 99065963
15545 | 16542946
13 | 15545
1 | 13
(6 rows)

Time: 0.562 ms
```

并发压测性能如下:

``` vi test.sql \set id random(1,526815046) with recursive a as (
select * from rtree where cid=:id union all
select t.pid,t.cid from rtree t join a on (t.cid=a.pid) where t. is not null
)
select count() from a ;

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 52 -j 52 -T 120

progress: 1.0 s, 186649.5 tps, lat 0.240 ms stddev 3.042 progress: 2.0 s, 125672.3 tps, lat 0.393 ms stddev 10.809 progress: 3.0 s, 160436.1 tps, lat 0.321 ms stddev 9.789 progress: 4.0 s, 154129.2 tps, lat 0.335 ms stddev 10.767 progress: 5.0 s, 138896.0 tps, lat 0.389 ms stddev 13.390 progress: 6.0 s, 142040.0 tps, lat 0.358 ms stddev 11.066 progress: 7.0 s, 173043.7 tps, lat 0.313 ms stddev 8.911 progress: 8.0 s, 128719.0 tps, lat 0.360 ms stddev 10.405 progress: 9.0 s, 130560.6 tps, lat 0.405 ms stddev 13.241 progress: 10.0 s, 72816.8 tps, lat 0.825 ms stddev 22.125 progress: 11.0 s, 164034.5 tps, lat 0.261 ms stddev 4.543 progress: 12.0 s, 142551.6 tps, lat 0.302 ms stddev 10.368 progress: 13.0 s, 160882.5 tps, lat 0.401 ms stddev 17.471 progress: 14.0 s, 128789.7 tps, lat 0.351 ms stddev 12.543 progress: 15.0 s, 120965.7 tps, lat 0.389 ms stddev 15.641 progress: 16.0 s, 133133.1 tps, lat 0.385 ms stddev 17.125 progress: 17.0 s, 135483.2 tps, lat 0.381 ms stddev 17.681 ```