来自 MySQLSql 数据库的简单随机示例

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

“显而易见”的答案是:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

For large tables, that's too slow: it calls RAND() for every row (which already puts it at O(n)), and sorts them, making it O(n lg n) at best. Is there a way to do this faster than O(n)?

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

5年后

我用一个更大的桌子再次遇到了这个问题，最后使用了一个@际无知的解决方案，并做了两个调整:

  • 对行进行取样，取样大小为我所希望的2-5倍，取样费用为 ORDER BY RAND()
  • 在每次插入/更新时将 RAND()的结果保存到一个索引列。(如果您的数据集不是很多更新，那么您可能需要找到另一种方法来保持这个列的新鲜度。)

为了获取一个包含1000个条目的表示例，我对这些行进行计数，然后对结果进行取样，平均为10,000行，其中包含 zen _ rand 列:

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()。

190340 次浏览
小开

也许你可以

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)
小开
最佳答案

这里有一个关于这类问题的非常有趣的讨论: 不要使用 rand 的订单或者如何获得随机行的 http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

I think with absolutely no assumptions about the table that your O(n lg n) solution is the best. Though actually with a good optimizer or a slightly different technique the query you list may be a bit better, O(m*n) where m is the number of random rows desired, as it wouldn't necesssarily have to sort the whole large array, it could just search for the smallest m times. But for the sort of numbers you posted, m is bigger than lg n anyway.

我们可以尝试三个假设:

  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) < 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 以外的任何东西都可能更适合所需的循环和随机数生成。

小开

用就是了

WHERE RAND() < 0.1

得到10% 的记录或者

WHERE RAND() < 0.01

to get 1% of the records, etc.

小开

我认为最快的解决办法是

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

这就是为什么我认为这个应该起作用。

  • It will create a random number for each row. The number is between 0 and 1
  • 如果生成的数字介于0和.3(30%)之间，则计算是否显示该行。

这里假设 rand ()在均匀分布中生成数字，这是最快的方法。

我看到有人推荐了这个解决方案，结果他们在没有证据的情况下被否决了。.我想说的是

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

  • Mysql 非常有能力为每一行生成随机数

    从 INFORATION _ SCHEMA 中选择 rand ()

因为问题中的数据库是 mySQL，所以这是正确的解决方案。

小开

首先，我们可以根据一个集合检索表的 id (例如 count 5) :

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

我们可以得到这样的结果，如果我们可以生成字符串 "(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 查询的结果。

小开

Apparently in some versions of SQL there's a TABLESAMPLE command, but it's not in all SQL implementations (notably, Redshift).

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

小开

我想指出的是，所有这些解决方案似乎样品没有更换。从随机排序中选择最上面的 K 行，或者连接到一个包含随机顺序的唯一键的表，将生成一个不需要替换的随机样本。

如果你想你的样品是独立的，你将需要与更换样品。有关如何使用类似 user12861解决方案的 JOIN 来实现这一点的示例，请参见 问题25451034。这个解决方案是为 T-SQL 编写的，但是这个概念适用于任何 SQL 数据库。

小开

比 RAND ()的订单更快

我测试了这个方法，它比 ORDER BY RAND()快得多，因此它在 O (n)时间内运行，而且非常快。

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

Non-MSSQL version -- I did not test this

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)

这将选择约1% 的记录。因此，如果您需要精确的百分比 # 或记录来选择，估计您的百分比与一些安全裕度，然后随机从结果集中提取多余的记录，使用更昂贵的 ORDER BY RAND()方法。

更快

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

例如，如果有一个索引列具有均匀分布的整数[0。.Max ] ，可以用它随机选择 N 个小间隔。在程序中动态执行此操作，以便为每次查询运行获取不同的集合。这个子集选择将是 O (N)，它可以比你的完整数据集小很多数量级。

在我的测试中，我使用 ORDER BY RAND ()将从 3分钟获得20个(出20百万)样本记录所需的时间减少到了 0.0秒！

小开

If you need exactly m rows, realistically you'll generate your subset of IDs outside of SQL. Most methods require at some point to select the "nth" entry, and SQL tables are really not arrays at all. The assumption that the keys are consecutive in order to just join random ints between 1 and the count is also difficult to satisfy — MySQL for example doesn't support it natively, and the lock conditions are... 很狡猾.

这里有一个 O(max(n, m lg n))-time，O(n)-space 解决方案，假设只有简单的 BREE 键:

  1. Fetch all values of the key column of the data table in any order into an array in your favorite scripting language in O(n)
  2. 执行 Fisher-Yates 洗牌，在 m交换后停止，并在 ϴ(m)中提取子阵 [0:m-1]
  3. “连接”子数组与 O(m lg n)中的原始数据集(例如 SELECT ... WHERE id IN (<subarray>))

任何在 SQL 之外生成随机子集的方法都必须至少具有这种复杂性。联接不能比 O(m lg n)和 BTREE 快(因此 O(m)的声明对于大多数引擎来说都是幻想) ，并且 shuffle 在 n和 m lg n之下有界，并且不影响渐近行为。

在 Python 伪代码中:

ids = sql.query('SELECT id FROM t')
for i in range(m):
r = int(random() * (len(ids) - i))
ids[i], ids[i + r] = ids[i + r], ids[i]


results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])
小开

在 Netezza 中选择3000个随机记录:

WITH IDS AS (
SELECT ID
FROM MYTABLE;
)


SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000
小开

Try

SELECT TOP 10000 * FROM table ORDER BY NEWID()

这是否会带来预期的结果，而不会过于复杂？

小开

在某些方言中，比如 Microsoft SQL Server、 PostgreSQL 和 Oracle (但不包括 MySQL 或 SQLite) ，你可以这样做

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

没有 top的情况下执行 (10000 rows)的原因是 TABLESAMPLE逻辑给出了一个非常不精确的行数(有时是75% ，有时是1.25%) ，所以你需要过采样并选择你想要的确切数字。REPEATABLE (123)用于提供随机种子。


提交答案