digoal
2020-06-10
PostgreSQL , 推荐系统 , offset , 浪费
推荐系统.
User 10亿级别
video 10亿级别
给 User 推送 video, 按weight权重排序选择vids, 并且过滤已读(获取后到客户端已读表示已读), 采用HLL记录vid hash, 通过hash判断是否已读. hll_val || vid_hash <> hll_val 表示未读.
create table t (vid int8, weight float4, ts timestamp);
insert into t select generate_series(1,10000000), random();
create index idx_t_1 on t (weight);
随着已读列表越来越大, 每次按weight倒排查出来的记录有大量是已读的, 浪费了大量的时间在hll运算上. 使用offset可以模拟hll计算, 例如offset过滤20万条
select * from t order by weight desc offset 200000 limit 100;
耗费 Time: 147.740 ms
视频权重会因为大赏、观看等情况不断变化, 所以没有办法使用记录weight 位点来加速offset. 也没有办法使用ts结合weight来跟踪offset位点, 因为热vid会越来越热.
每个人观看、喜好的vid都不一样, 所以没有办法统一处理加速.
降低每次hll计算已读的量, 将table强行进行随机索引分区, 每次只查询一个分区, 这样与业务可能有一丝丝不符, 因为查询到的记录是部分记录.
但是从整体拉平来看, 只要用户请求次数足够多, 随机能覆盖到所有的记录.
例如按20个分区索引来进行随机选择.
do language plpgsql $$
declare
sql text;
begin
for i in 0..19 loop
sql := format($_$
create index idx_t_p_%s on t (weight) where mod(abs(hashint8(vid)),20)=%s;
$_$, i, i);
execute sql;
end loop;
end;
$$;
那么查询的范围将缩小到20分之一, 因为用户已读列表的总量不变, 所以在这个分区中的已读量也会变成20分之一. 那么offset量就会降低20倍. 性能明显提升.
select * from t
where mod(abs(hashint8(vid)),20) = 0
order by weight desc offset 10000 limit 100;
耗费 Time: 12.139 ms
《PostgreSQL 大量IO扫描、计算浪费的优化 - 推荐模块, 过滤已推荐. (热点用户、已推荐列表超大)》
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议,奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等,奖品丰富,快来许愿。开不开森.