大数据标签查询优化实战之pg_roaringbitmap

2022-01-18 11:36:40 浏览数 (18)

| 导语 在很多场景下都具有关于标签相似查找的需求，业务层固然可以实现，但如果数据库能够天然支持高性能查询，岂不美哉。本文主要基于PostgreSQL实现标签查询的优化实践，供大家参考

一步一步实操，可直接复制粘贴

pg_roaringbitmap是什么？

pg_roaringbitmap是一个基于roaringbitmap而实现的压缩位图存储数据插件，支持roaring bitmap的存取、集合操作，聚合等运算。

roaringbitmap有什么用？

roaringbitmap在在实际的业务当中常使用来存储用户的属性标签，增删改查这些属性标签，以及根据这些存储的用户的标签通过并集，交集等方法来筛选出特定的用户。以达到超大规模属性数据的精准快速查找，既提升了性能的同时亦能降低存储空间，是大数据分析场景下极佳的应用实践。

如在传统模式下如有一张音乐类应用 的用户标签表，如下表：

用户ID

用户名

兴趣标签

1

张三

{古典,爵士,R&B,乡村}

2

李四

{民歌,中国风,纯音乐}

3

王五

{HipHop,爵士,R&B,嘻哈,雷鬼}

……

1000000000

xxx

{摇滚,}

若想要找到喜欢纯音乐的所有用户，就需要根据兴趣标签列进行搜索，找到标签中包含纯音乐的行，然后将此数据返回给应用。

那么我们一般最简单的做法会是怎么样子呢？

我们会按照上表的结构在数据库中建立一张用户兴趣表，然后执行数组查询语句，找到兴趣标签进行包含查找。

但是这么做就会有一个问题，性能，在数据量较大，并且标签值较多的场景下，不仅数据容量占用得更多，而且性能会极差。所以我们更换一种实现方案，将此表拆分为三张表，兴趣标签作为主键，包含此兴趣标签的用户作为bitmap存储。如下表所示：

用户表：

用户ID

用户名

1

张三

2

李四

N

……

标签表：

标签ID

标签名

1

古典

2

民歌

N

……

用户标签表：

标签ID

用户ID

1

[ 1,3,7,123,423 ]

2

[ 5,31]

N

……

当需要根据查找同时喜欢听 古典和民歌的用户时候，直接在 用户标签表对 用户id 做bitmap 查询，能够极大的提升性能。并且容量占用降低极多。

实操准备：

1、创建一个随机字符的函数：

代码语言：javascript复制
create or replace function random_string(length integer) returns text as
代码语言：javascript复制
$$
代码语言：javascript复制
declare
代码语言：javascript复制
chars text[] := '{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}';
代码语言：javascript复制
result text := '';
代码语言：javascript复制
i integer := 0;
代码语言：javascript复制
length2 integer := (select trunc(random() * length   1));
代码语言：javascript复制
begin
代码语言：javascript复制
if length2 < 0 then
代码语言：javascript复制
raise exception 'Given length cannot be less than 0';
代码语言：javascript复制
end if;
代码语言：javascript复制
for i in 1..length2 loop
代码语言：javascript复制
result := result || chars[1 random()*(array_length(chars, 1)-1)];
代码语言：javascript复制
end loop;
代码语言：javascript复制
return result;
代码语言：javascript复制
end;
代码语言：javascript复制
$$ language plpgsql;

2、创建一个生成随机 整形 数组的函数：

代码语言：javascript复制
create or replace function random_int_array(int, int)
代码语言：javascript复制
returns int[] language sql as
代码语言：javascript复制
$$
代码语言：javascript复制
select array_agg(round(random()* $1)::int)
代码语言：javascript复制
from generate_series(1, $2)
代码语言：javascript复制
$$;

3、创建一个生成随机 字符 数组的函数：

代码语言：javascript复制
create or replace function random_string_array(int, int)
代码语言：javascript复制
returns TEXT[] language sql as
代码语言：javascript复制
$$
代码语言：javascript复制
select array_agg(random_string($1)) from generate_series(1, $2);
代码语言：javascript复制
$$;

传统做法:

一张表解决一切的方法。

1、创建一个表装所有数据：

代码语言：javascript复制
create table account(
代码语言：javascript复制
uin bigint primary KEY,
代码语言：javascript复制
name varchar,
代码语言：javascript复制
tag TEXT []
代码语言：javascript复制
);

2、模拟插入1000W个账号数据（需要使用到准备工作中的函数）,并且创建Gin索引。

代码语言：javascript复制
insert into account select generate_series(1,10000000), random_string(20),random_string_array(5,10);
代码语言：javascript复制
create index tag_inx on account USING GIN(tag);

3、执行查询：查找标签带 GN 和o的用户列表：

代码语言：javascript复制
explain analyze select uin,name from account where tag @>ARRAY['GN','o'];
代码语言：javascript复制
​
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
​
代码语言：javascript复制
----------------------------------------------------------------------------------------------------
代码语言：javascript复制
-----------------
代码语言：javascript复制
Bitmap Heap Scan on account (cost=52.81..466.86 rows=105 width=19) (actual time=4.263..4.502 rows=
代码语言：javascript复制
184 loops=1)
代码语言：javascript复制
Recheck Cond: (tag @> '{GN,o}'::text[])
代码语言：javascript复制
Heap Blocks: exact=184
代码语言：javascript复制
-> Bitmap Index Scan on tag_inx (cost=0.00..52.78 rows=105 width=0) (actual time=4.240..4.240 r
代码语言：javascript复制
ows=184 loops=1)
代码语言：javascript复制
Index Cond: (tag @> '{GN,o}'::text[])
代码语言：javascript复制
Planning Time: 0.108 ms
代码语言：javascript复制
Execution Time: 4.528 ms

3、执行查询：查找标签lvXe和Zt的人有xx个（备注第一次查询会较慢）：

代码语言：javascript复制
explain analyze select count(uin) from account where tag && ARRAY['lvXe','Zt'];
代码语言：javascript复制
​
代码语言：javascript复制
----------------------------------------------------------------------------------------------------
代码语言：javascript复制
--------------------------
代码语言：javascript复制
Aggregate (cost=21816.39..21816.40 rows=1 width=8) (actual time=8.236..8.238 rows=1 loops=1)
代码语言：javascript复制
-> Bitmap Heap Scan on account (cost=109.08..21800.56 rows=6332 width=8) (actual time=1.655..7.
代码语言：javascript复制
901 rows=5390 loops=1)
代码语言：javascript复制
Recheck Cond: (tag && '{lvXe,Zt}'::text[])
代码语言：javascript复制
Heap Blocks: exact=5327
代码语言：javascript复制
-> Bitmap Index Scan on tag_inx (cost=0.00..107.49 rows=6332 width=0) (actual time=0.962.
代码语言：javascript复制
.0.962 rows=5390 loops=1)
代码语言：javascript复制
Index Cond: (tag && '{lvXe,Zt}'::text[])
代码语言：javascript复制
Planning Time: 0.110 ms
代码语言：javascript复制
Execution Time: 8.270 ms

优化方案：

为了降低查询中 标签字段的类型导致的性能减低，所以将上面表中的真实tag 修改为tagid

1、引入一个新的标签字典表：

代码语言：javascript复制
create table tag_dict (
代码语言：javascript复制
tagid int primary key,
代码语言：javascript复制
taginfo text
代码语言：javascript复制
);

2、假设一共有10W种字典类型：

insert into tag_dict select generate_series(1,100000), md5(random()::text);

3、创建一个新表用以存储用户和标签信息：

代码语言：javascript复制
create table account1(
代码语言：javascript复制
uin bigint primary KEY,
代码语言：javascript复制
name varchar,
代码语言：javascript复制
tag INT []
代码语言：javascript复制
);

4、插入1000W个账号数据：

代码语言：javascript复制
insert into account1 select generate_series(1,10000000), random_string(20),random_int_array(100000,10);

5、查找同时有 标签id 为 100 和5711的用户列表：

索引前：

代码语言：javascript复制
test=> explain analyze select uin,name from account1 where tag @> ARRAY[100,5711];
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
-----------------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
Gather (cost=1000.00..191007.68 rows=250 width=19) (actual time=982.585..1000.806 rows=0 loops=1)
代码语言：javascript复制
Workers Planned: 2
代码语言：javascript复制
Workers Launched: 2
代码语言：javascript复制
-> Parallel Seq Scan on account1 (cost=0.00..189982.68 rows=104 width=19) (actual time=962.640..962.640 rows=0 loops=3)
代码语言：javascript复制
Filter: (tag @> '{100,5711}'::integer[])
代码语言：javascript复制
Rows Removed by Filter: 3333333
代码语言：javascript复制
Planning Time: 0.205 ms
代码语言：javascript复制
JIT:
代码语言：javascript复制
Functions: 12
代码语言：javascript复制
Options: Inlining false, Optimization false, Expressions true, Deforming true
代码语言：javascript复制
Timing: Generation 2.280 ms, Inlining 0.000 ms, Optimization 1.176 ms, Emission 14.189 ms, Total 17.645 ms
代码语言：javascript复制
Execution Time: 1001.574 ms
代码语言：javascript复制
(12 rows)

加索引：

create index tag_inx_2 on account1 USING GIN(tag);

索引后：

代码语言：javascript复制
test=> explain analyze select uin,name from account1 where tag @> ARRAY[100,5711];
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
---------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
Bitmap Heap Scan on account1 (cost=49.94..1021.13 rows=250 width=19) (actual time=0.126..0.127 rows=0 loops=1)
代码语言：javascript复制
Recheck Cond: (tag @> '{100,5711}'::integer[])
代码语言：javascript复制
-> Bitmap Index Scan on tag_inx_2 (cost=0.00..49.87 rows=250 width=0) (actual time=0.124..0.124 rows=0 loops=1)
代码语言：javascript复制
Index Cond: (tag @> '{100,5711}'::integer[])
代码语言：javascript复制
Planning Time: 0.410 ms
代码语言：javascript复制
Execution Time: 0.171 ms
代码语言：javascript复制
(6 rows)

6、查找同时有 标签id 为 61568 97350 的用户列表：

代码语言：javascript复制
test=> explain analyze select uin,name from account1 where tag @> ARRAY[61568,97350];
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
---------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
Bitmap Heap Scan on account1 (cost=49.94..1021.13 rows=250 width=19) (actual time=0.130..0.131 rows=1 loops=1)
代码语言：javascript复制
Recheck Cond: (tag @> '{61568,97350}'::integer[])
代码语言：javascript复制
Heap Blocks: exact=1
代码语言：javascript复制
-> Bitmap Index Scan on tag_inx_2 (cost=0.00..49.87 rows=250 width=0) (actual time=0.125..0.125 rows=1 loops=1)
代码语言：javascript复制
Index Cond: (tag @> '{61568,97350}'::integer[])
代码语言：javascript复制
Planning Time: 0.071 ms
代码语言：javascript复制
Execution Time: 0.151 ms
代码语言：javascript复制
(7 rows)

7、或者与xx 有共同爱好(标签100和5711)的人有xx个：

代码语言：javascript复制
test=> explain analyze select count(uin) from account1 where tag && ARRAY[61568,97350];
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
​
代码语言：javascript复制
---------------------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
------
代码语言：javascript复制
Gather (cost=1961.06..173801.15 rows=99750 width=19) (actual time=5.020..28.885 rows=2066 loops=1)
代码语言：javascript复制
Workers Planned: 2
代码语言：javascript复制
Workers Launched: 2
代码语言：javascript复制
-> Parallel Bitmap Heap Scan on account1 (cost=961.06..162826.15 rows=41562 width=19) (actual time=1.623..3.305 rows=689 loo
代码语言：javascript复制
ps=3)
代码语言：javascript复制
Recheck Cond: (tag && '{61568,97350}'::integer[])
代码语言：javascript复制
Heap Blocks: exact=2053
代码语言：javascript复制
-> Bitmap Index Scan on tag_inx_2 (cost=0.00..936.12 rows=99750 width=0) (actual time=0.685..0.685 rows=2066 loops=1)
代码语言：javascript复制
Index Cond: (tag && '{61568,97350}'::integer[])
代码语言：javascript复制
Planning Time: 0.082 ms
代码语言：javascript复制
JIT:
代码语言：javascript复制
Functions: 12
代码语言：javascript复制
Options: Inlining false, Optimization false, Expressions true, Deforming true
代码语言：javascript复制
Timing: Generation 2.078 ms, Inlining 0.000 ms, Optimization 0.270 ms, Emission 3.489 ms, Total 5.836 ms
代码语言：javascript复制
Execution Time: 29.725 ms
代码语言：javascript复制
(14 rows)

如果使用roaringbitmap的方法：

1、首先需要创建插件，云数据库PostgreSQL天然集成了此插件，无需关注编译等操作，直接进入数据库中创建即可。

代码语言：javascript复制
create extension roaringbitmap;

2、创建标签用户对应表

代码语言：javascript复制
create table tag_uin_list(
代码语言：javascript复制
tagid int primary key,
代码语言：javascript复制
uin_offset int,
代码语言：javascript复制
uinbits roaringbitmap
代码语言：javascript复制
);

3、根据之前的 标签表 插入10W条标签以及标签对应的用户数据。

代码语言：javascript复制
insert into tag_uin_list
代码语言：javascript复制
select tagid, uin_offset, rb_build_agg(uin::int) as uinbits from
代码语言：javascript复制
(
代码语言：javascript复制
select
代码语言：javascript复制
unnest(tag) as tagid,
代码语言：javascript复制
(uin / (2^31)::int8) as uin_offset,
代码语言：javascript复制
mod(uin, (2^31)::int8) as uin
代码语言：javascript复制
from account1
代码语言：javascript复制
) t
代码语言：javascript复制
group by tagid, uin_offset;

4、查询 标签有 1，3，10，200 的用户个数：

代码语言：javascript复制
explain analyze select sum(ub) from
代码语言：javascript复制
(
代码语言：javascript复制
select uin_offset,rb_or_cardinality_agg(uinbits) as ub
代码语言：javascript复制
from tag_uin_list
代码语言：javascript复制
where tagid in (1,3,10,200)
代码语言：javascript复制
group by uin_offset
代码语言：javascript复制
) t;
代码语言：javascript复制
​
代码语言：javascript复制
​
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
​
代码语言：javascript复制
---------------------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
------------
代码语言：javascript复制
Aggregate (cost=32.47..32.48 rows=1 width=32) (actual time=0.964..0.966 rows=1 loops=1)
代码语言：javascript复制
-> GroupAggregate (cost=32.42..32.46 rows=1 width=12) (actual time=0.955..0.956 rows=1 loops=1)
代码语言：javascript复制
Group Key: tag_uin_list.uin_offset
代码语言：javascript复制
-> Sort (cost=32.42..32.43 rows=4 width=22) (actual time=0.107..0.109 rows=4 loops=1)
代码语言：javascript复制
Sort Key: tag_uin_list.uin_offset
代码语言：javascript复制
Sort Method: quicksort Memory: 25kB
代码语言：javascript复制
-> Bitmap Heap Scan on tag_uin_list (cost=17.20..32.38 rows=4 width=22) (actual time=0.044..0.067 rows=4 loops=1
代码语言：javascript复制
)
代码语言：javascript复制
Recheck Cond: (tagid = ANY ('{1,3,10,200}'::integer[]))
代码语言：javascript复制
Heap Blocks: exact=4
代码语言：javascript复制
-> Bitmap Index Scan on tag_uin_list_pkey (cost=0.00..17.20 rows=4 width=0) (actual time=0.031..0.031 rows
代码语言：javascript复制
=4 loops=1)
代码语言：javascript复制
Index Cond: (tagid = ANY ('{1,3,10,200}'::integer[]))
代码语言：javascript复制
Planning Time: 0.289 ms
代码语言：javascript复制
Execution Time: 1.083 ms
代码语言：javascript复制
(13 rows)

5、查看标签有1，3，10，200的用户列表：

代码语言：javascript复制
explain analyze select uin_offset,rb_or_agg(uinbits) as ub
代码语言：javascript复制
from tag_uin_list
代码语言：javascript复制
where tagid in (1,3,10,200)
代码语言：javascript复制
group by uin_offset;
代码语言：javascript复制
QUERY PLAN
代码语言：javascript复制
​
代码语言：javascript复制
---------------------------------------------------------------------------------------------------------------------------------
代码语言：javascript复制
------
代码语言：javascript复制
GroupAggregate (cost=32.42..32.46 rows=1 width=36) (actual time=0.246..0.246 rows=1 loops=1)
代码语言：javascript复制
Group Key: uin_offset
代码语言：javascript复制
-> Sort (cost=32.42..32.43 rows=4 width=22) (actual time=0.043..0.045 rows=4 loops=1)
代码语言：javascript复制
Sort Key: uin_offset
代码语言：javascript复制
Sort Method: quicksort Memory: 25kB
代码语言：javascript复制
-> Bitmap Heap Scan on tag_uin_list (cost=17.20..32.38 rows=4 width=22) (actual time=0.029..0.036 rows=4 loops=1)
代码语言：javascript复制
Recheck Cond: (tagid = ANY ('{1,3,10,200}'::integer[]))
代码语言：javascript复制
Heap Blocks: exact=4
代码语言：javascript复制
-> Bitmap Index Scan on tag_uin_list_pkey (cost=0.00..17.20 rows=4 width=0) (actual time=0.021..0.021 rows=4 loops=1)
代码语言：javascript复制
Index Cond: (tagid = ANY ('{1,3,10,200}'::integer[]))
代码语言：javascript复制
Planning Time: 0.119 ms
代码语言：javascript复制
Execution Time: 0.310 ms
代码语言：javascript复制
(12 rows)

总结

查看索引以及表占用大小：

代码语言：javascript复制
test=> select relname, pg_size_pretty(pg_relation_size(relid)) from pg_stat_user_tables where schemaname='public' order by pg_relation_size(relid) desc;
代码语言：javascript复制
   relname    | pg_size_pretty
代码语言：javascript复制
-------------- ----------------
代码语言：javascript复制
 account      | 1545 MB
代码语言：javascript复制
 account1     | 1077 MB
代码语言：javascript复制
 t_user       | 651 MB
代码语言：javascript复制
 tag_dict     | 6672 kB
代码语言：javascript复制
 tag_uin_list | 5888 kB
代码语言：javascript复制
(5 rows)
代码语言：javascript复制
​
代码语言：javascript复制
test=> select indexrelname, pg_size_pretty(pg_relation_size(relid)) from pg_stat_user_indexes where schemaname='public' order by pg_relation_size(relid) desc;
代码语言：javascript复制
   indexrelname    | pg_size_pretty
代码语言：javascript复制
------------------- ----------------
代码语言：javascript复制
 tag_inx           | 1545 MB
代码语言：javascript复制
 account_pkey      | 1545 MB
代码语言：javascript复制
 tag_inx_2         | 1077 MB
代码语言：javascript复制
 account1_pkey     | 1077 MB
代码语言：javascript复制
 t_user_pkey       | 651 MB
代码语言：javascript复制
 tag_dict_pkey     | 6672 kB
代码语言：javascript复制
 tag_uin_list_pkey | 5888 kB
代码语言：javascript复制
(7 rows)

不同方案的查询性能对比：

方案1

方案2

roaringbitmap方案

查询包含指定标签的用户列表

4.528ms

0.151 ms

0.310 ms

查询具备共同标签的用户个数

8.27ms

29.725 ms

1.083 ms

数据容量统计

4635MB

3244.344MB

1237.12MB

基于上述方案可以明显看到 ，优化效果非常明显。无论是容量还是性能都强于传统方案。

TDSQLPostgreSQL版TDSQL tdsql 国产数据库

0 人点赞