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

如何在SQL中进行高效的简单随机样本? 有问题的数据库正在运行MySQL; 我的桌子至less有20万行,我想要一个简单的约10,000个随机样本。

“明显的”答案是:

SELECT * FROM table ORDER BY RAND() LIMIT 10000 

对于大型表来说,这太慢了:它为每一行调用RAND()(它已经把它放在O(n)),并对它们进行sorting,最好使它成为O(n lg n)。 有没有办法比O(n)更快地做到这一点?

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

编辑:5年后

我再次遇到了一个更大的表,并最终使用@愚昧的解决scheme版本,有两个调整:

  • 将行以2-5倍我所需的样本大小进行采样,以便宜的方式ORDER BY RAND()
  • 将RAND()的结果保存到每个插入/更新的索引列中。 (如果你的数据集不是非常重要的,你可能需要find另一种方法来保持这个列的新鲜。)

要获取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()。

这里有一个关于这种types的问题的非常有趣的讨论: http : //www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-行从-表/

我想绝对没有关于这个表的假设,你的O(n lg n)解决scheme是最好的。 尽pipe实际上使用了一个好的优化器或者稍微不同的技术,但是您所列出的查询可能会更好一些,O(m * n)其中m是所需的随机行数,因为它不一定需要对整个大数组进行sorting,它可以只search最小的m次。 但是对于你发布的那种数字,无论如何m都大于lg。

我们可以尝试三个假设:

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

  2. 要select的随机行数(m)远小于表(n)中的行数

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

只有假设1和2我认为这可以在O(n)中完成,但是你需要写一个完整的索引来匹配假设3,所以它不是一个快速的O(n)。 如果我们可以额外地假设一些其他的表格,我们可以在O(m log m)中完成任务。 假设3将是一个很好的附加财产来处理。 随着一个很好的随机数发生器,当连续产生m个数字时保证不会有重复,O(m)解决scheme将是可能的。

给出三个假设,其基本思想是在1到n之间生成m个唯一的随机数,然后从表中select具有这些键的行。 我现在没有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以外,几乎任何其他的东西都可能会更好地满足循环和随机数生成的要求。

我认为最快的解决scheme是

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

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

  • 它会为每一行创build一个随机数。 该数字在0和1之间
  • 如果生成的数字介于0和.3(30%)之间,它将评估是否显示该行。

这假设rand()正在生成统一分布的数字。 这是最快捷的方法。

我看到有人推荐这个解决scheme,他们没有证据就被击落了。这就是我要说的 –

  • 这是O(n),但不需要sorting,因此它比O(n lg n)
  • MySQL非常有能力为每一行生成随机数字。 尝试这个 –

    从INFORMATION_SCHEMA.TABLES中selectrand(),限制为10;

由于有问题的数据库是mySQL,这是正确的解决scheme。

比ORDER BY RAND()更快

我testing了这个方法,比ORDER BY RAND()快得多,因此它运行在O(n)时间,而且速度非常快。

http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx

非MSSQL版本 – 我没有testing这个

 SELECT * FROM Sales.SalesOrderDetail WHERE 0.01 >= RAND() 

MSSQL版本:

 SELECT * FROM Sales.SalesOrderDetail WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int) 

这将select约1%的logging。 因此,如果您需要精确的百分比或loggingselect,请使用一些安全余量来估计您的百分比,然后使用更昂贵的ORDER BY RAND()方法从结果集中随机抽取多余logging。

甚至更快

我能够进一步改进这种方法,因为我有一个众所周知的索引列值范围。

例如,如果您有一个统一分布的整数[0..max]的索引列,则可以使用它来随机selectN个小区间。 在您的程序中dynamic执行此操作,以便为每个查询运行获取不同的集合。 这个子集的select将是O(N) ,它可以比你的全部数据集小许多个数量级。

在我的testing中,我减less了使用ORDER BY RAND()从3分钟获得20(20万个)样本logging到0.0秒的时间

显然,在某些版本的SQL中有一个TABLESAMPLE命令,但并不是所有的SQL实现(尤其是Redshift)。

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

只是使用

 WHERE RAND() < 0.1 

获得10%的logging或

 WHERE RAND() < 0.01 

获得1%的logging等

从观察结果开始,我们可以根据一个集合检索一个表(例如,计数5)的ID:

 select * from table_name where _id in (4, 1, 2, 5, 3) 

我们可以得出这样的结果:如果我们能够生成string"(4, 1, 2, 5, 3)" ,那么我们就会比RAND()有更高效的方法。

例如,在Java中:

 ArrayList<Integer> indices = new ArrayList<Integer>(rowsCount); for (int i = 0; i < rowsCount; i++) { indices.add(i); } Collections.shuffle(indices); String inClause = indices.toString().replace('[', '(').replace(']', ')'); 

如果ID有空位,那么初始数组列表indices是在ID上进行SQL查询的结果。

我想指出的是,所有这些解决scheme似乎都是在不更换的情况下进行抽样。 从随机sorting中select排在前面的K行或按随机顺序连接到包含唯一键的表将产生一个随机样本,不会产生replace。

如果你想要你的样品是独立的,你需要更换样品。 有关如何使用类似于user12861的解决scheme的JOIN执行此操作的示例,请参阅问题25451034 。 该解决scheme是为T-SQL编写的,但是这个概念可以在任何SQL数据库中使用。

也许你可以做

 SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)