PostgreSQL 随机记录返回 - 300倍提速实践 (随机数组下标代替order by random())

2 minute read

背景

在业务系统中,有些场景会用到随机返回的功能,例如论坛,有很多帖子(比如有100万贴),有些是精华帖(比如有5万贴),为了让精华帖可以均衡的被访问,需要将5万贴随机的分页返回给用户。

通常的做法是这样的

select xx from tbl where xx order by random() limit xx;    

传统做法,由于需要随机排序,性能会比较差。

传统做法

1、建表

create table tbl_doc (id int primary key, info text, crt_time timestamp, tag int);     

2、写入测试数据

tag=1表示精选帖子

insert into tbl_doc select id, md5(random()::text), clock_timestamp(), 0 from generate_series(1,1000000) t(id);    
insert into tbl_doc select id, md5(random()::text), clock_timestamp(), 1 from generate_series(1000001,1050000) t(id);    

3、测试

vi test1.sql    
    
begin;    
declare abc cursor for select * from tbl_doc where tag=1 order by random() ;    
fetch 10 from abc;    
end;    

QPS不过200.

pgbench -M prepared -n -r -P 1 -f ./test1.sql -c 64 -j 64 -T 120    
progress: 1.0 s, 190.9 tps, lat 272.908 ms stddev 42.231    
progress: 2.0 s, 212.1 tps, lat 284.494 ms stddev 44.371    
progress: 3.0 s, 211.9 tps, lat 325.806 ms stddev 58.453    
progress: 4.0 s, 172.0 tps, lat 340.460 ms stddev 71.527    

优化方法 - 数组随机

周期性将帖子ID放入数组,查询时从数组取随机位置的ID,再从主表反查,避免排序。

1、创建一个存储周期性最新精选帖子的表(数组ID)。

create table tbl_hot_doc (id serial primary key, ids int[], crt_time timestamp);     

通过这种方法写入当前最新帖子

insert into tbl_hot_doc (ids,crt_time)     
      select array_agg(id), now() from tbl_doc where tag=1     

2、创建一个函数,用于自动的更新最新帖子(根据超时时间),同时返回游标,用户通过游标分页。

create or replace function get_ids (    
  ts_timeout interval,   -- 超时时间    
  rands int,   -- 返回随机多少条    
  refname name  -- 游标名    
) returns refcursor as $$    
declare    
  len int;  -- 数组长度,有多少精华帖    
  hotid int;  -- tbl_hot_id表的最新状态ID    
  ts timestamp;  -- 最新状态的时间    
  hotids int[];  -- 最新状态的数组    
  res refcursor := refname;  -- 游标名    
begin    
-- 获取最新状态    
select array_length(ids,1),id,crt_time,ids into len,hotid,ts,hotids from tbl_hot_doc order by id desc limit 1;     
    
-- 如果没有最新状态,或者最新状态已超时    
if now()-ts >= ts_timeout or not found then    
  -- 如果不存在则设置HOTID=0     
  if not found then hotid := 0; end if;    
  -- 使用ad lock抢锁,只有一个会话拿锁,从原始表tbl_doc生成最新数据并写入tbl_hot_doc    
  if pg_try_advisory_xact_lock(hotid) then     
    insert into tbl_hot_doc (ids,crt_time)     
      select array_agg(id), now() from tbl_doc where tag=1     
      returning array_length(ids,1),id,crt_time,ids into len,hotid,ts,hotids;     
        
    -- 使用这条SQL,用数组下标随机,代替之前的order by random()    
    open res for select * from tbl_doc where id in (select hotids[(random()*(len-1))::int+1] from generate_series(1,rands));    
    return res;    
  end if;     
end if;    
    
open res for select * from tbl_doc where id in (select hotids[(random()*(len-1))::int+1] from generate_series(1,rands));    
return res;     
end;    
$$ language plpgsql strict;    

3、优化后的性能测试

vi test.sql    
begin;    
select * from get_ids(interval '5 min', 1000, 'abc');    
fetch 10 from abc;    
end;    

4、QPS上到6万,提升了300倍。

pgbench -M prepared -n -r -P 1 -f ./test.sql -c 64 -j 64 -T 120    
progress: 1.0 s, 57260.4 tps, lat 1.045 ms stddev 0.211    
progress: 2.0 s, 60444.9 tps, lat 1.059 ms stddev 0.050    
progress: 3.0 s, 60467.5 tps, lat 1.058 ms stddev 0.045    
progress: 4.0 s, 60520.2 tps, lat 1.057 ms stddev 0.039    
progress: 5.0 s, 60561.8 tps, lat 1.057 ms stddev 0.045    

5、如果需要在修改tbl_doc原始数据后,立即反映(不等查询get_ids输入的超时参数),实时更新tbl_hot_doc的值,可以采用类似如下方法

begin;     
update tbl_doc set tag=0 where id=?;     
update tbl_hot_doc set ids=array_remove(ids,?) where id=(select max(id) from tbl_hot_doc) and ids<>array_remove(ids,?);     
end;     

小结

使用本文提供的方法,使得随机数据的查询,性能提升了300倍。

其他方法

还有一些方法,例如将满足条件的数据使用独立分区来存储,然后使用采样的方法来避免排序,但是精确度和性能还是没有办法与先前的方法相比。

postgres=# select * from tbl_doc tablesample BERNOULLI (0.1) where tag=1 limit 10;
   id    |               info               |          crt_time          | tag 
---------+----------------------------------+----------------------------+-----
 1000398 | 7f232df084bf24a71ccaac9f496639bb | 2018-10-09 23:32:45.761598 |   1
 1000806 | 97095bdfdd0ef1d209515728a078ffc3 | 2018-10-09 23:32:45.762841 |   1
 1001949 | d7733a8b4bc5b5b26bb147fab3cc62d6 | 2018-10-09 23:32:45.766116 |   1
 1002227 | 1feb7e972b7206a0ab909cee0a07e41d | 2018-10-09 23:32:45.766917 |   1
 1003609 | 60223d7a74c51cde4a8b017bf9a3e712 | 2018-10-09 23:32:45.770809 |   1
 1006387 | 89c9cb8b4dbd46b3e0c0606e7e1e6947 | 2018-10-09 23:32:45.778873 |   1
 1006533 | f57808f0f15140bbc5429929a4b8d4b5 | 2018-10-09 23:32:45.779258 |   1
 1007279 | 03fedf609f2e85658a98195daabac2b1 | 2018-10-09 23:32:45.781323 |   1
 1007880 | 298bee6992ca255cbc8d0a299f00166a | 2018-10-09 23:32:45.783055 |   1
 1008073 | bf1b8354692cde77765babc56a9f06a2 | 2018-10-09 23:32:45.783605 |   1
(10 rows)

Time: 11.125 ms

分区表时,块级采样无法满足业务需求,因为随机性不够。而非分区时,则引入了IO放大并且可能访问不到足够的满足条件的记录。

《PostgreSQL 任意列组合条件 行数估算 实践 - 采样估算》

《秒级任意维度分析1TB级大表 - 通过采样估值满足高效TOP N等统计分析需求》

《PostgreSQL Oracle 兼容性 之 - 数据采样与脱敏》

《PostgreSQL 巧妙的数据采样方法》

[《PostgreSQL 9.5 new feature - table mview data sample》](../201505/20150525_01.md)

参考

《PostgreSQL 随机查询优化》

Flag Counter

digoal’s 大量PostgreSQL文章入口