PostgreSQL 实践 - 实时广告位推荐 2 (任意字段组合、任意维度组合搜索、输出TOP-K)
背景
任意字段组合查询的几种优化方法：
1、列存
2、RUM
3、GIN
| 4、多个INDEX的BITMAP AND | OR SCAN |
5、BLOOM FILTER
《PostgreSQL 实践 - 广告位推荐 1》 采用了RUM的方法，采用rum的目的是避免GIN的CPU RECHECK，但是当我们查询时如果业务方允许使用GIN的采样限制，则没有必要使用RUM了。
《[未完待续] PostgreSQL 全文检索 大结果集优化 - fuzzy match》
本例子采用一种新的设计来实现电商个性化推荐（例如，打开首页，打开一个店铺，打开一个页面时，根据用户的行为，实时推荐对应页面涉及的内容中的优选内容（被推荐的可能是商品、类目等））。
设计1
基本思想是使用GIN倒排索引，同时引入fuzzy match参数来过滤海量数据，在一个较小的结果集内排序输出。
注意此法需要业务方允许在采样中输出才可以。
1、字典表
create table tbl_dict (
dim text, -- 维度
val int8 not null unique, -- 维度内的映射值(为了让所有维度可以打到一个数组里面，取值空间唯一)
info text -- 原始值、描述
);
create index idx_tbl_dict_1 on tbl_dict(dim,info);
获得维度值
select val from tbl_dict where dim=? and info=?;
2、行为标签表
create table tbl_lab (
id serial8 primary key, -- 主键
dict int8[], -- N个dim，则有N个元素
score float4, -- 打分
itemid int8 -- 比如商品ID(或其他最终用户要的ID)
);
-- 不能颗粒化的维度，依旧保留放在tbl_lab表中。
筛选数据原始方法：
select itemid from tbl_lab where dim1=? and dim10=? and dim12=? order by score desc limit 100;
转换为
set gin_fuzzy_search_limit=2000;
select * from tbl_lab where dict = any (array(
select val from tbl_dict where (dim,info) in (('1',?), ('10',?), ('12',?))
))
order by score desc limit 100;
3、创建GIN索引
create index idx_tbl_lab_dict on tbl_lab using gin (dict);
4、写入测试数据
假设有100个维度，每个维度有若干个取值空间的值，总共构成了1000万个取值。
insert into tbl_dict select (random()*99)::int, generate_series(1,10000000), md5(random()::text);
create or replace function get_val(text) returns int8 as $$
select val from tbl_dict tablesample system (0.1) where dim=$1 limit 1;
$$ language sql strict;
create or replace function get_vals() returns int8[] as $$
select array_agg(get_val(id::text)) from generate_series(0,99) t(id);
$$ language sql strict;
写入1亿标签记录
vi test.sql
insert into tbl_lab select get_vals(), random()*1000, random()*100000000 from generate_series(1,100);
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 56 -j 56 -t 17857
空间占用
public | tbl_lab | table | postgres | 81 GB |
public | idx_tbl_lab_dict | index | postgres | tbl_lab | 425 GB |
5、筛选数据，同时使用fuzzy match缩小结果集，根据分值排序输出TOP N
create or replace function get_vals1(int) returns int8[] as $$
select array_agg(get_val(id::text)) from (select generate_series(0,99) order by random() limit $1) t(id);
$$ language sql strict stable;
set gin_fuzzy_search_limit=2000;
select * from tbl_lab where dict @> get_vals1(5)
order by score desc limit 100;
postgres=# set gin_fuzzy_search_limit =1;
SET
Time: 0.213 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
80
(1 row)
Time: 647.802 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
76
(1 row)
Time: 1087.094 ms (00:01.087)
postgres=# set gin_fuzzy_search_limit =10;
SET
Time: 0.174 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
83
(1 row)
Time: 198.663 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
3244
(1 row)
Time: 78.824 ms
postgres=# set gin_fuzzy_search_limit =100;
SET
Time: 0.202 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
4718
(1 row)
Time: 54.961 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
4881
(1 row)
Time: 49.879 ms
postgres=# set gin_fuzzy_search_limit =1000;
SET
Time: 0.176 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
5783
(1 row)
Time: 46.311 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
5784
(1 row)
Time: 45.930 ms
postgres=# set gin_fuzzy_search_limit =5000;
SET
Time: 0.219 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
9156
(1 row)
Time: 48.888 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
9382
(1 row)
Time: 49.479 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
9265
(1 row)
Time: 48.514 ms
postgres=# set gin_fuzzy_search_limit =20000;
SET
Time: 0.231 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
22432
(1 row)
Time: 58.063 ms
postgres=# select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
count
-------
22746
(1 row)
Time: 56.720 ms
5000左右较好，数值太少，访问的数据反而多。应该是个算法问题：
postgres=# set gin_fuzzy_search_limit =10;
SET
Time: 0.188 ms
postgres=# explain (analyze,verbose,timing,costs,buffers) select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1702903.64..1702903.65 rows=1 width=8) (actual time=135.104..135.104 rows=1 loops=1)
Output: count(*)
Buffers: shared hit=145266
-> Bitmap Heap Scan on public.tbl_lab (cost=3868.90..1701675.35 rows=491316 width=0) (actual time=135.044..135.082 rows=78 loops=1)
Recheck Cond: (tbl_lab.dict @> '{122562}'::bigint[])
Heap Blocks: exact=78
Buffers: shared hit=145266
-> Bitmap Index Scan on idx_tbl_lab_dict (cost=0.00..3746.07 rows=491316 width=0) (actual time=96.252..96.252 rows=78 loops=1)
Index Cond: (tbl_lab.dict @> '{122562}'::bigint[])
Buffers: shared hit=145248
Planning Time: 0.190 ms
JIT:
Functions: 5
Generation Time: 1.091 ms
Inlining: true
Inlining Time: 5.746 ms
Optimization: true
Optimization Time: 22.590 ms
Emission Time: 10.321 ms
Execution Time: 136.271 ms
(20 rows)
Time: 136.887 ms
postgres=# set gin_fuzzy_search_limit =5000;
SET
Time: 0.222 ms
postgres=# explain (analyze,verbose,timing,costs,buffers) select count(*) from tbl_lab where dict @> array[122562]::int8[] ;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=1702903.64..1702903.65 rows=1 width=8) (actual time=48.953..48.953 rows=1 loops=1)
Output: count(*)
Buffers: shared hit=187
-> Bitmap Heap Scan on public.tbl_lab (cost=3868.90..1701675.35 rows=491316 width=0) (actual time=45.491..48.031 rows=9290 loops=1)
Recheck Cond: (tbl_lab.dict @> '{122562}'::bigint[])
Heap Blocks: exact=9223
Buffers: shared hit=187
-> Bitmap Index Scan on idx_tbl_lab_dict (cost=0.00..3746.07 rows=491316 width=0) (actual time=5.027..5.027 rows=9290 loops=1)
Index Cond: (tbl_lab.dict @> '{122562}'::bigint[])
Buffers: shared hit=166
Planning Time: 0.165 ms
JIT:
Functions: 5
Generation Time: 1.154 ms
Inlining: true
Inlining Time: 6.152 ms
Optimization: true
Optimization Time: 22.501 ms
Emission Time: 10.273 ms
Execution Time: 50.183 ms
(20 rows)
Time: 50.771 ms
6、性能测试
vacuum tbl_lab;
vi test.sql
select * from tbl_lab where dict @> get_vals1(5)
order by score desc limit 100;
pgbench -M extended -n -r -P 1 -f ./test.sql -c 56 -j 56 -T 120
7、更新、删除维度内容、分值
例子
update tbl_lab set score=? where id=?
update tbl_lab set dict=array_replace(dict,old_val,new_val) where id=?
设计2
使用分段rum索引，在不损伤精度的情况下，提高最大吞吐的任意维度TOP-K输出。
1、使用rum阶梯（类似分段、分区）索引
假设score的取值范围是0到100，我们将score分为100段，每段1个百分点. （实际可按业务的阶段来设置步长）
同样的手法，在以下案例中也使用过。
《PostgreSQL 相似搜索设计与性能 - 地址、QA、POI等文本 毫秒级相似搜索实践》
《PostgreSQL 相似搜索分布式架构设计与实践 - dblink异步调用与多机并行(远程 游标+记录 UDF实例)》
如果业务上可以定一个指标，比如说打分在50以下的完全不需要展示，那么索引甚至可以只需要针对50以上的记录。
do language plpgsql $$
declare
begin
for i in 1..100 loop
execute format('create index idx_tbl_lab__%s on tbl_lab using rum (dict rum_anyarray_ops) where score >%s and score <=%s', i, (i-1), i);
end loop;
end;
$$;
2、使用UDF进行查询，分阶段查询，从高到低
如果业务上可以定一个指标，比如说打分在50以下的完全不需要展示，那么查询LOOP也只需要针对50以上的。
create or replace function get_dict (
int8[], -- 维度值
int -- 返回多少行
) returns setof tbl_lab as $$
declare
r_cnt int := 0;
v_tmp int := 0;
begin
for i in 1..100 loop
return query select * from tbl_lab where dict @> $1 and score >(100-i) and score<=(101-i)
order by score desc limit $2;
GET DIAGNOSTICS v_tmp = ROW_COUNT;
r_cnt := r_cnt + v_tmp ;
if r_cnt >= $2 then
return;
end if;
end loop;
return;
end;
$$ language plpgsql strict;
3、测试性能
postgres=# select score,itemid from get_dict(get_vals1(1),100)
;
score | itemid
---------+----------
99.9529 | 36742578
99.9507 | 69844786
99.941 | 83415934
99.9284 | 46894536
99.9181 | 24389328
...
98.105 | 62905250
98.1028 | 83484134
98.1006 | 67573139
98.0984 | 19020938
98.0983 | 90873124
98.093 | 4732945
98.0885 | 25186764
98.0316 | 97861252
98.0246 | 50682057
(173 rows)
Time: 6.397 ms
postgres=# select score,itemid from get_dict(get_vals1(1),20) ;
score | itemid
---------+----------
99.991 | 27411195
99.9559 | 20090883
99.9478 | 55444281
99.9341 | 70071418
99.9255 | 632316
99.9252 | 70685672
99.8897 | 36828714
99.8714 | 48261720
99.8506 | 92092732
99.811 | 57477121
99.7868 | 52143704
99.7526 | 13161677
99.7496 | 92728450
99.7318 | 73244372
99.6917 | 1948099
99.6274 | 48124431
99.5875 | 76672257
99.5636 | 7682029
99.5593 | 4137987
99.5535 | 93647650
(20 rows)
Time: 1.252 ms
压测
vi test.sql
select score,itemid from get_dict(get_vals1(1),100);
压测结果
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 56 -j 56 -T 120
number of transactions actually processed: 964316
latency average = 6.969 ms
latency stddev = 14.058 ms
tps = 8029.326932 (including connections establishing)
tps = 8029.687576 (excluding connections establishing)
小结
1、gin_fuzzy_search_limit 起到了限流效果(具备一定随机性，并不精确)，同时性能的提升不明显(5000左右性能较佳)，并且测试中发现gin_fuzzy_search_limit设置为很小时，性能并不好。
2、使用rum分段索引，可以实现高效率的过滤，本轮测试1亿数据(81 GB数据，81 GB索引)，100个维度，按SCORE排序，随机获取TOP 100，8029的QPS，得到精准的排序后的数据。
如果需要更好的并发，需要更多的只读节点来支持。
测试实例为6140 RMB每月的RDS PG 10最高规格。（56核, 480G内存, 2T存储.）
本方案与《PostgreSQL ADHoc(任意字段组合)查询 与 字典化 (rum索引加速) - 实践与方案1》 不同之处，仅仅在于本例输出的结果需要按SCORE排序，所以我们使用分段索引，以及UDF输出，巧妙的提升了整体的处理吞吐。
同样的分段加速手法，在以下案例中也使用过。
《PostgreSQL 相似搜索设计与性能 - 地址、QA、POI等文本 毫秒级相似搜索实践》
《PostgreSQL 相似搜索分布式架构设计与实践 - dblink异步调用与多机并行(远程 游标+记录 UDF实例)》
参考
《PostgreSQL ADHoc(任意字段组合)查询 与 字典化 (rum索引加速) - 实践与方案1》
《HTAP数据库 PostgreSQL 场景与性能测试之 20 - (OLAP) 用户画像圈人场景 - 多个字段任意组合条件筛选与透视》
《时间、空间、对象多维属性 海量数据任意多维 高效检索 - 阿里云RDS PostgreSQL最佳实践》
《多字段，任意组合条件查询(无需建模) - 毫秒级实时圈人 最佳实践》
《宝剑赠英雄 - 任意组合字段等效查询, 探探PostgreSQL多列展开式B树 (GIN)》
《[未完待续] PostgreSQL 全文检索 大结果集优化 - fuzzy match》