PostgreSQL选择随机行的最佳方法

488

我想在PostgreSQL中随机选择行,我尝试了以下代码:

select * from table where random() < 0.01;

但是其他人建议这样做:

select * from table order by random() limit 1000;

我有一个有500万行的非常大的表格,我希望它运行速度很快。

哪种方法更好?它们之间有什么差异?选择随机行的最佳方法是什么?


2
嗨,杰克,感谢您的回复。按顺序执行的时间较慢,但我想知道是否有什么不同... - nanounanue
嗯...不用谢。那么,你尝试过对不同的方法进行基准测试吗? - user554546
还有*更快的方式。这完全取决于您的需求和您拥有的工具。您需要确切地1000行吗?表格是否具有数字ID?没有/很少/有许多间隔吗?速度有多重要?每个时间单位有多少请求?每个请求是否需要不同的设置,或者它们可以在定义的时间片段内相同? - Erwin Brandstetter
10
第一个选项“(random() < 0.01)”在数学上是不正确的,因为如果没有随机数小于0.01,则响应中可能没有行,在任何情况下都可能发生(尽管不太可能),无论表有多大或门槛有多高。第二个选项总是正确的。 - Herme
2
如果您只想选择一行,请参阅此问题:https://dev59.com/HG435IYBdhLWcg3wpxyw - Flimm
显示剩余2条评论
13个回答

332

快速方法

根据您的规格(在评论中提供附加信息),

  • 您有一个数字ID列(整数),只有很少(或适度少)的间隙。
  • 显然没有或很少写操作。
  • 您的ID列必须建立索引!主键非常适合。

以下查询不需要对大表进行顺序扫描,只需要进行索引扫描。

首先,获取主查询的估计值:

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
     , max(id)  AS max_id
     , max(id) - min(id) AS id_span
FROM   big;
唯一可能昂贵的部分是count(*)(对于大表格而言)。 根据上述规范,您不需要它。 用于替换完整计数的估计足以胜任,几乎不需要费用:

唯一可能昂贵的部分是count(*)(对于大表格而言)。 根据上述规范,您不需要它。 用于替换完整计数的估计足以胜任,几乎不需要费用:

SELECT (reltuples / relpages * (pg_relation_size(oid) / 8192))::bigint AS ct
FROM   pg_class
WHERE  oid = 'big'::regclass;  -- your table name

详细说明:

只要ct没有比id_span小太多,这个查询就会比其他方法更快。

WITH params AS (
   SELECT 1       AS min_id           -- minimum id <= current min id
        , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
   SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
   FROM   params p
        , generate_series(1, 1100) g  -- 1000 + buffer
   GROUP  BY 1                        -- trim duplicates
) r
JOIN   big USING (id)
LIMIT  1000;                          -- trim surplus
  • id 空间中生成随机数。你有“少量空缺”,因此将检索行数增加 10%(足以轻松覆盖这些空缺)。

  • 每个 id 可以通过机会被多次选择(虽然在大的 id 空间中很不可能),因此分组生成的数字(或使用 DISTINCT)。

  • id 连接到大表上。如果有索引,则应该非常快速。

  • 最后消除未被重复项和空缺占用的多余 id。每行都有完全相同的机会被选择。

简短版

你可以简化此查询。上面的 CTE 仅供教育目的使用:

SELECT *
FROM  (
   SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
   FROM   generate_series(1, 1100) g
   ) r
JOIN   big USING (id)
LIMIT  1000;

通过rCTE提高精度

尤其是当你对空缺和估算不太确定时。

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
TABLE  random_pick
LIMIT  1000;  -- actual limit

在基本查询中,我们可以使用较小的剩余部分。如果有太多的间隙,导致第一次迭代中找不到足够的行,则递归CTE将继续进行迭代。我们仍然需要相对较少的ID空间间隙,否则递归可能会在达到限制之前停止运行 - 或者我们必须从足够大的缓冲区开始,这违背了优化性能的目的。

重复的值通过rCTE中的UNION被消除。

外部的LIMIT使得CTE尽快停止,一旦我们有足够的行。

此查询经过精心设计,使用可用索引,生成实际上是随机的行,并且在满足限制之前不停止(除非递归停止运行)。如果您要重写它,这里有很多陷阱。

包装成函数

为了在使用相同表但具有不同参数的情况下重复使用:

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big
  LANGUAGE plpgsql VOLATILE ROWS 1000 AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT (reltuples / relpages * (pg_relation_size(oid) / 8192))::bigint
      FROM   pg_class
      WHERE  oid = 'big'::regclass);
BEGIN
   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   TABLE  random_pick
   LIMIT  _limit;
END
$func$;

调用:

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

通用函数

我们可以将它泛型化,使其适用于任何具有唯一整数列(通常是主键)的表格:将表格作为多态类型传递,以及(可选)PK列的名称,并使用EXECUTE

CREATE OR REPLACE FUNCTION f_random_sample(_tbl_type anyelement
                                         , _id text = 'id'
                                         , _limit int = 1000
                                         , _gaps real = 1.03)
  RETURNS SETOF anyelement
  LANGUAGE plpgsql VOLATILE ROWS 1000 AS
$func$
DECLARE
   -- safe syntax with schema & quotes where needed
   _tbl text := pg_typeof(_tbl_type)::text;
   _estimate int := (SELECT (reltuples / relpages
                          * (pg_relation_size(oid) / 8192))::bigint
                     FROM   pg_class  -- get current estimate from system
                     WHERE  oid = _tbl::regclass);
BEGIN
   RETURN QUERY EXECUTE format(
   $$
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * $1)::int
         FROM   generate_series(1, $2) g
         LIMIT  $2                 -- hint for query planner
         ) r(%2$I)
      JOIN   %1$s USING (%2$I)     -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * $1)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  $3                 -- hint for query planner
         ) r(%2$I)
      JOIN   %1$s USING (%2$I)     -- eliminate misses
   )
   TABLE  random_pick
   LIMIT  $3;
   $$
 , _tbl, _id
   )
   USING _estimate              -- $1
       , (_limit * _gaps)::int  -- $2 ("surplus")
       , _limit                 -- $3
   ;
END
$func$;

使用默认参数进行调用(重要!):

SELECT * FROM f_random_sample(null::big);  --!

更具体地说:

SELECT * FROM f_random_sample(null::"my_TABLE", 'oDD ID', 666, 1.15);

与静态版本性能相当。

相关信息:

这是安全的,不容易受到SQL注入攻击。请参见:

可能的替代方案

如果您的要求允许重复调用时相同的集合(我们在谈论重复调用),可以考虑使用MATERIALIZED VIEW。执行上面的查询一次并将结果写入表中。用户以闪电般的速度获取准随机选择。在您选择的间隔或事件刷新随机选择。

Postgres 9.5引入了TABLESAMPLE SYSTEM (n)

其中n是一个百分比。手册:

伯努利和系统抽样方法各接受一个参数,即要抽样的表的分数,表示为0到100之间的百分比。该参数可以是任何实值表达式。

加粗强调是我的。这很快,但结果不完全随机。手册再次阐述:

当指定较小的抽样百分比时,SYSTEM方法比BERNOULLI方法快得多,但由于聚类效应,它可能返回表的较不随机的样本。

返回的行数可能差别很大。对于我们的示例,要获取大约1000行:

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

相关:

或者安装附加模块tsm_system_rows以确切地获取所请求的行数(如果有足够的行)并允许使用更方便的语法:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

详细信息请参见Evan的答案

但这仍然不是完全随机的。


t 表在哪里定义的?它应该是 r 而不是 t 吗? - Luc M
1
@LucM:在这里定义了 JOIN bigtbl t,它是 JOIN bigtbl AS t 的简写。tbigtbl表别名,其目的是缩短语法,但在这种特定情况下不需要。我在我的答案中简化了查询并添加了一个简单版本。 - Erwin Brandstetter
generate_series(1,1100) 的值域是什么意思? - Awesome-o
2
@Awesome-o: 目标是检索1000行,我会额外增加10%以弥补一些空缺或(虽然不太可能但仍有可能)重复的随机数...详细解释在我的回答中。 - Erwin Brandstetter
Erwin,我发布了你的“可能的替代方案”的变体:https://dev59.com/4Woy5IYBdhLWcg3wQrxh#23634212。很想听听你的想法。 - Raman
显示剩余2条评论

138

postgresql按random()排序,以随机顺序选择行:

这些方法都很慢,因为它们需要进行表扫描,以确保每一行被选择的机会完全相等:

select your_columns from your_table ORDER BY random()

select * from 
  (select distinct your_columns from your_table) table_alias
ORDER BY random()

select your_columns from your_table ORDER BY random() limit 1

如果您知道表中有多少行N
通过向下取整的随机偏移是常数时间。然而,我并不确信OFFSET能够产生真正的随机样本。它通过获取“下一批”并进行表扫描来模拟,所以您可以逐步执行,这与上述不完全相同。
SELECT myid FROM mytable OFFSET floor(random() * N) LIMIT 1;

使用周期表扫描自行生成常数时间随机选择的N行,以确保完全随机:

如果您的表非常庞大,则上述表扫描会成为一个绊脚石,需要长达5分钟才能完成。

为了更快地进行操作,您可以安排在幕后每晚进行表扫描重建,这将保证以O(1)恒定时间速度进行完美随机选择,但在每晚重建表扫描期间,必须等待维护完成才能接收到另一行随机数据。

--Create a demo table with lots of random nonuniform data, big_data 
--is your huge table you want to get random rows from in constant time. 
drop table if exists big_data;  
CREATE TABLE big_data (id serial unique, some_data text );  
CREATE INDEX ON big_data (id);  
--Fill it with a million rows which simulates your beautiful data:  
INSERT INTO big_data (some_data) SELECT md5(random()::text) AS some_data
FROM generate_series(1,10000000);
 
--This delete statement puts holes in your index
--making it NONuniformly distributed  
DELETE FROM big_data WHERE id IN (2, 4, 6, 7, 8); 
 
 
--Do the nightly maintenance task on a schedule at 1AM.
drop table if exists big_data_mapper; 
CREATE TABLE big_data_mapper (id serial, big_data_id int); 
CREATE INDEX ON big_data_mapper (id); 
CREATE INDEX ON big_data_mapper (big_data_id); 
INSERT INTO big_data_mapper(big_data_id) SELECT id FROM big_data ORDER BY id;
 
--We have to use a function because the big_data_mapper might be out-of-date
--in between nightly tasks, so to solve the problem of a missing row, 
--you try again until you succeed.  In the event the big_data_mapper 
--is broken, it tries 25 times then gives up and returns -1. 
CREATE or replace FUNCTION get_random_big_data_id()  
RETURNS int language plpgsql AS $$ 
declare  
    response int; 
BEGIN
    --Loop is required because big_data_mapper could be old
    --Keep rolling the dice until you find one that hits.
    for counter in 1..25 loop
        SELECT big_data_id 
        FROM big_data_mapper OFFSET floor(random() * ( 
            select max(id) biggest_value from big_data_mapper 
            )
        ) LIMIT 1 into response;
        if response is not null then
            return response;
        end if;
    end loop;
    return -1;
END;  
$$; 
 
--get a random big_data id in constant time: 
select get_random_big_data_id(); 
 
--Get 1 random row from big_data table in constant time: 
select * from big_data where id in ( 
    select get_random_big_data_id() from big_data limit 1 
); 
┌─────────┬──────────────────────────────────┐ 
│   id    │            some_data             │ 
├─────────┼──────────────────────────────────┤ 
│ 8732674 │ f8d75be30eff0a973923c413eaf57ac0 │ 
└─────────┴──────────────────────────────────┘ 

--Get 4 random rows from big_data in constant time: 
select * from big_data where id in ( 
    select get_random_big_data_id() from big_data limit 3 
);
┌─────────┬──────────────────────────────────┐ 
│   id    │            some_data             │ 
├─────────┼──────────────────────────────────┤ 
│ 2722848 │ fab6a7d76d9637af89b155f2e614fc96 │ 
│ 8732674 │ f8d75be30eff0a973923c413eaf57ac0 │ 
│ 947561136ac3eeb6b3e171cacd475e7f9dade56 │ 
└─────────┴──────────────────────────────────┘ 

--Test what happens when big_data_mapper stops receiving 
--nightly reindexing.
delete from big_data_mapper where 1=1; 
select get_random_big_data_id();   --It tries 25 times, and returns -1
                                   --which means wait N minutes and try again.

改编自:https://www.gab.lc/articles/bigdata_postgresql_order_by_random

或者如果上述都太复杂了。

一个更简单的好用解决方案是在你的大表上创建一个名为big_data.mapper_int的新列,使其非空并具有唯一索引。每晚将该列重置为介于1和max(n)之间的唯一整数。要获取随机行,可以"选择一个介于0max(id)之间的随机整数",然后返回 mapper_int 为该整数的行。如果不存在该 ID 的行,因为重新索引后行已发生变化,则选择另一行来获取随机行。如果向 big_data.mapper_int 添加一行,则将其填充为 max(id) + 1

或者使用 TableSample 解决:

如果您使用的是 PostgreSQL 版本> 9.5,那么 TABLESAMPLE 可以在没有繁重的表扫描的情况下进行常数时间的随机抽样。 https://wiki.postgresql.org/wiki/TABLESAMPLE_Implementation

--Select 1 percent of rows from yourtable, 
--display the first 100 rows, order by column a_column
select * from yourtable TABLESAMPLE SYSTEM (1)
order by a_column 
limit 100;

TableSample在幕后进行一些耗时的操作,我不喜欢这样,但比随机排序(order by random())要快。好、快、便宜,对于这项工作,选择其中两个。
恒定时间随机,在热备用中保留随机选择:
你有一个拥有十亿行的大表,你想要在恒定时间内得到一个完美的随机行。将其放入后台任务中,并每12小时运行一次后台任务:
drop table if exists random_nextpick_bigtable; 
CREATE TABLE IF NOT EXISTS random_nextpick_bigtable as (
   select your_columns from your_bigtable ORDER BY random()
)

在预定任务期间,获取选择需要5分钟,但是一旦完成后,可以立即获得一个完全随机的行:

select * from random_nextpick_bigtable limit 1;
delete from random_nextpick_bigtable where id = your_used_id;

在计划任务时间和现在之间,如果有可能id已被删除,则删除它并选择下一个。在计划任务之间添加的行不会出现在随机样本中。

14
从您的表中选择您的列,按随机顺序排列并限制只返回1行。在4500万行上执行需要约2分钟的时间。 - nguyên
2
有没有办法加速这个? - CpILL

131
你可以使用以下方法来检查和比较两者的执行计划:
EXPLAIN select * from table where random() < 0.01;
EXPLAIN select * from table order by random() limit 1000;

在一个大表上进行快速测试1,显示ORDER BY首先对整个表进行排序,然后选择前1000项。对于大表的排序不仅需要读取该表,还涉及读写临时文件。而where random() < 0.1只扫描整个表一次。

对于大表来说,即使进行一次完整的表扫描也可能太慢,这可能并不是您想要的。

第三个建议是:

select * from table where random() < 0.01 limit 1000;

这个方法在找到1000行后立即停止表扫描,因此会更快地返回结果。当然,这会稍微降低随机性,但在某些情况下也许已经足够了。 编辑: 除了这些考虑因素之外,您还可以查看已经提出的相关问题。使用查询[postgresql] random会返回很多结果。
以下是一些已回答的问题:
- Postgres中快速随机行选择 - 如何从postgreSQL表中检索随机数据行? - postgres:从表中获取随机条目-速度太慢 此外,depez的一篇文章链接了几种更多的方法。

1 "large" 意味着 "完整的表格无法全部存入内存"。


1
关于编写临时文件以进行排序的观点很好。这确实是一个大问题。我想我们可以做 random() < 0.02 然后洗牌那个列表,然后 limit 1000!在几千行上进行排序会更加经济实惠(哈哈)。 - Donald Miner
“select * from table where random() < 0.05 limit 500;” 是PostgreSQL中较为简单的方法之一。我们在一个项目中使用了它,该项目需要选择结果的5%,每次最多不超过500行进行处理。 - tgharold
为什么你会考虑在一个500m行的表中使用O(n)全表扫描来检索样本呢?这在大型表上非常缓慢,而且完全没有必要。 - mafu

80

6
文档中的重要说明:"SYSTEM方法使用块级采样,每个块具有指定被选中的概率;返回每个选中块中的所有行。当指定小的采样百分比时,SYSTEM方法显著比BERNOULLI方法更快,但由于聚类效应的影响,可能会返回一个不太随机的表样本。" - Tim
3
有没有办法指定行数而不是百分比? - Flimm
11
您可以使用 TABLESAMPLE SYSTEM_ROWS(400) 获取 400 行随机样本。您需要启用内置的 tsm_system_rows 扩展程序来使用此语句。 - Mickaël Le Baillif
适用于40亿行的数据表。其他方法需要很长时间。 - undefined

41

带有ORDER BY语句的查询将会更慢。

select * from table where random() < 0.01; 按记录一个一个地进行筛选,并决定是否随机过滤。这将是O(N),因为它只需要检查每个记录一次。

select * from table order by random() limit 1000; 将对整个表进行排序,然后选择前1000条记录。除了任何幕后神秘操作外,此ORDER BY将是O(N * log N)

使用random() < 0.01的缺点是你将获得可变数量的输出记录。


请注意,有一种比按随机顺序排序更好的数据集洗牌方法:Fisher-Yates随机置乱算法,其复杂度为O(N)。不过在SQL中实现这种置乱算法似乎是相当具有挑战性的。


5
你可以在第一个例子的结尾添加"Limit 1",没有任何问题。但是有可能会返回零条记录,所以你需要在代码中考虑这种情况。 - Relequestual
1
Fisher-Yates算法的问题在于需要将整个数据集存储在内存中才能从中进行选择。对于非常大的数据集来说,这是不可行的 :( - CpILL

24
select * from table order by random() limit 1000;

如果您知道需要多少行,请查看tsm_system_rows

tsm_system_rows

该模块提供了表采样方法SYSTEM_ROWS,可在SELECT命令的TABLESAMPLE子句中使用。

此表采样方法接受一个整数参数,即要读取的最大行数。结果样本将始终包含完全相同数量的行,除非表中不包含足够的行,在这种情况下会选择整个表。像内置的SYSTEM采样方法一样,SYSTEM_ROWS执行块级采样,因此样本并不完全随机,而是可能受到聚类效应的影响,特别是如果只请求少量行。

首先安装扩展程序

CREATE EXTENSION tsm_system_rows;

然后是您的查询,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);

3
我已经在你添加的答案中加入了一个链接,这比内置的“SYSTEM”方法更加显著地改进了它。 - Erwin Brandstetter
我刚刚在这里回答了一个问题(随机单个记录),期间我对 tsm_system_rowstsm_system_time 扩展进行了相当大量的基准测试。就我所看到的,它们除了绝对最小的随机行选择之外,几乎没有任何用处。如果您能快速查看并评论我的分析的有效性或无效性,我将不胜感激。 - Vérace
1
为了减轻聚集效应,你可以这样做: SELECT * FROM "users" TABLESAMPLE SYSTEM_ROWS(n*10) ORDER BY RANDOM() LIMIT n; 其中 n 是你想要的行数。这样它将使用 tsm_system_rows 来获取比你需要的多10倍的行,仅对这些行进行随机排序,然后从中获取 n 行。相比于 SELECT * FROM "users" ORDER BY RANDOM() LIMIT n; 这种方式,速度仍然快得多,因为它不会对每一行进行排序。 - Starscream512
@ErwinBrandstetter 你对我用 tsm_system_rows 扩展来减轻聚集效应的解决方案有什么看法? - Starscream512
@Starscream512 通常情况下,如果您需要减轻聚类效应的影响,最好的解决方案可能是完全不依赖于它,但在某些使用情况下也可以正常工作。在这种情况下,如果相应的行n * 10列适合一个块(8kb),则知道它不起作用。 - Evan Carroll

19

这是一个对我有用的决定。我想这很容易理解和执行。

SELECT 
  field_1, 
  field_2, 
  field_2, 
  random() as ordering
FROM 
  big_table
WHERE 
  some_conditions
ORDER BY
  ordering 
LIMIT 1000;

11
我认为这个解决方案就像在一个大表上使用ORDER BY random(),虽然能够正常工作,但可能不是很高效。 - Anh Cao

9
如果你只想要一行,你可以使用一个由 count 推导出的计算出来的 offset
select * from table_name limit 1
offset floor(random() * (select count(*) from table_name));

5

我的经验告诉我一个教训:

offset floor(random() * N) limit 1 并不比 order by random() limit 1 更快。

我本以为使用 offset 方法会更快,因为它应该可以节省在Postgres中排序的时间。结果证明并非如此。


1
你能解释一下为什么吗? - Stuck
因为当您请求偏移量时,它仍会计算到您的偏移量之前的行。例如,如果您请求偏移量100和限制20,则它将处理您的查询前120行,然后丢弃前100行并返回最后20行。因此,使用偏移量不会节省任何东西。 - aeskreis
@aeskries,你在哪里看到这个信息的?能否提供一些官方来源的链接? - GooDeeJAY
@GooDeeJAY 我没有文档链接,但这是逻辑上显而易见的。为了获取查询结果中的第100行,您需要知道前99行是什么。唯一的例外可能是如果您的表按静态顺序索引,并且您执行的是没有变化的查询,只是一个带有限制/偏移量的纯选择查询。也许在这种情况下,Postgres可以进行优化以智能地跳过某些行,但这显然不会发生在随机排序的情况下。 - aeskreis

5
我认为在PostgreSQL中最好和最简单的方法是:
SELECT * FROM tableName ORDER BY random() LIMIT 1

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接