来自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。
我们可以尝试三个假设：
-
表中有一个唯一的索引主键
-
要select的随机行数（m）远小于表（n）中的行数
-
唯一主键是一个整数，范围从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)
