来自Sql数据库的简单随机样本

如何在SQL中使用高效的简单随机样本？有问题的数据库正在运行MySQL; 我的表至少有200,000行,我想要一个大约10,000的简单随机样本.

"明显"的答案是:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

对于大型表来说,这太慢了:它为每一行调用RAND()(已经将它放在O(n)处)并对它们进行排序,最多使它成为O(n lg n).有没有办法比O(n)更快地做到这一点？

注意:正如Andrew Mao在评论中指出的那样,如果您在SQL Server上使用此方法,则应使用T-SQL函数NEWID(),因为RAND()可能会为所有行返回相同的值.

编辑:5年后

我用更大的表再次遇到了这个问题,并最终使用了@ ignorant的解决方案,并进行了两次调整:

将行采样到2-5倍我想要的样本大小,以便宜的ORDER BY RAND()

在每次插入/更新时将RAND()的结果保存到索引列.(如果您的数据集不是非常大,那么您可能需要找到另一种方法来保持此列的新鲜度.)

要获取表的1000项样本,我计算行并使用frozen_rand列将结果平均下降到10,000行:

SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high

  SELECT *
    FROM table
   WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000

(我的实际实现涉及更多的工作,以确保我没有欠采样,并手动包裹rand_high,但基本的想法是"随机削减你的N到几千.")

虽然这会做出一些牺牲,但它允许我使用索引扫描对数据库进行采样,直到它再次小到ORDER BY RAND()为止.

我认为最快的解决方案是

select * from table where rand() <= .3

这就是为什么我认为这应该做的工作.

它将为每一行创建一个随机数.数字介于0和1之间

如果生成的数字介于0和.3(30%)之间,它将评估是否显示该行.

这假设rand()以均匀分布生成数字.这是最快捷的方式.

我看到有人推荐了这个解决方案而且没有证据就被击落了......这就是我要说的 -

这是O(n),但不需要排序,因此它比O(n lg n)更快

mysql非常能够为每一行生成随机数.试试这个 -

从INFORMATION_SCHEMA.TABLES限制10中选择rand();

由于有问题的数据库是mySQL,这是正确的解决方案.

这里有一个非常有趣的讨论这类问题: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

我认为绝对没有关于表格的假设,你的O(n lg n)解决方案是最好的.虽然实际上有一个好的优化器或稍微不同的技术,但是你列出的查询可能会更好一些,O(m*n)其中m是所需的随机行数,因为它不必对整个大型数组进行排序,它可以只搜索最小的m次.但对于你发布的那种数字,m大于lg n无论如何.

我们可能会尝试三种假设:

表中有一个唯一的索引主键

要选择的随机行数(m)远小于表中的行数(n)

唯一主键是一个整数,范围从1到n,没有间隙

假设只有假设1和2,我认为这可以在O(n)中完成,尽管你需要在表中写一个完整的索引来匹配假设3,所以它不一定是快速的O(n).如果我们可以另外假设关于表的其他好处,我们可以在O(m log m)中执行任务.假设3将是一个简单的好的额外属性来使用.使用一个很好的随机数生成器,在连续生成m个数字时保证没有重复,可以使用O(m)解决方案.

给出三个假设,基本思想是生成介于1和n之间的m个唯一随机数,然后从表中选择具有这些键的行.我现在没有mysql或任何东西在我面前,所以在略微伪代码中,这看起来像:

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

如果您真的关心效率,可以考虑使用某种过程语言进行随机密钥生成并将结果插入到数据库中,因为除了SQL之外的任何其他内容都可能更好地处理所需的循环和随机数生成.