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

Question

如何在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倍，以便宜的价格订购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（）。

Answer 1

这里有一个关于此类问题的非常有趣的讨论： 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。

我们可以尝试以下三种假设：

1. 表中有一个唯一的，已索引的主键

2. 您要选择的随机行数（m）比表中的行数（n）小得多

3. 唯一主键是一个整数，范围是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) &lt 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以外，几乎任何其他方法都可能在所需的循环和随机数生成方面更好。