115

如何在 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 个项目的表进行抽样，我计算行数并将结果抽样到平均 10,000 行的 freeze_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()再次使用。

4

12 回答 12

70

我认为最快的解决方案是

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

这就是为什么我认为这应该完成这项工作。

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

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

我看到有人推荐了该解决方案，但他们在没有证据的情况下被击落......这就是我要说的 -

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

  • mysql 非常有能力为每一行生成随机数。试试这个 -

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

由于有问题的数据库是 mySQL，因此这是正确的解决方案。

于 2013-01-31T15:43:48.617 回答
28

这里有一个关于这类问题的非常有趣的讨论：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) < 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 之外的几乎任何东西都可能在所需的循环和随机数生成方面更好.

于 2008-10-31T03:59:18.233 回答
8

比 ORDER BY RAND() 更快

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

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

非 MSSQL 版本——我没有测试这个

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()将获取 20 个（20 百万）样本记录所需的时间从3 分钟减少到了0.0 秒！

于 2014-09-10T20:29:05.290 回答
6

显然，在某些版本的 SQL 中有一个TABLESAMPLE命令，但并非在所有 SQL 实现中（尤其是 Redshift）。

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

于 2014-05-01T00:24:10.280 回答
5

只需使用

WHERE RAND() < 0.1

获得 10% 的记录或

WHERE RAND() < 0.01

获取 1% 的记录等。

于 2012-05-18T17:11:03.247 回答
2

在 Microsoft SQL Server、PostgreSQL 和 Oracle（但不是 MySQL 或 SQLite）等某些方言中，您可以执行以下操作

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

不这样做的原因(10000 rows)是top逻辑TABLESAMPLE给你的行数非常不准确（有时是 75%，有时是 1.25% 的倍数），所以你想要过采样并选择你想要的确切数字。REPEATABLE (123)用于提供随机种子。

于 2020-10-30T16:20:28.923 回答
1

我想指出，所有这些解决方案似乎都可以在没有替换的情况下进行采样。从随机排序中选择前 K 行或以随机顺序加入包含唯一键的表将产生一个随机样本，无需替换。

如果您希望您的样本是独立的，则需要更换样本。有关如何以类似于 user12861 的解决方案的方式使用 JOIN 执行此操作的一个示例，请参阅问题 25451034 。该解决方案是为 T-SQL 编写的，但该概念适用于任何 SQL 数据库。

于 2014-09-02T20:40:09.130 回答
1

尝试

SELECT TOP 10000 * FROM table ORDER BY NEWID()

这会产生预期的结果，而不会过于复杂吗？

于 2020-10-15T08:58:35.990 回答
0

从我们可以基于集合检索表的 id（例如计数 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(']', ')');

如果 ids 有间隙，那么初始的 arraylistindices是对 ids 的 sql 查询的结果。

于 2013-09-07T07:53:52.193 回答
0

如果您需要确切的m行，实际上您将在 SQL 之外生成 ID 子集。大多数方法有时需要选择“第 n 个”条目，而 SQL 表实际上根本不是数组。假设键是连续的以便仅连接 1 和计数之间的随机整数也很难满足 - 例如 MySQL 本身不支持它，并且锁定条件......棘手。

这是一个O(max(n, m lg n))-time, O(n)-space 解决方案，假设只是普通的 BTREE 键：

  1. 以你喜欢的脚本语言以任意顺序将数据表的键列的所有值提取到数组中O(n)
  2. 执行Fisher-Yates shuffle，交换后停止m，并提取子[0:m-1]数组ϴ(m)
  3. 将子数组与原始数据集（例如SELECT ... WHERE id IN (<subarray>)） “加入”O(m lg n)

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

在 Pythonic 伪代码中：

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])
于 2017-11-22T17:39:40.480 回答
0

在 Netezza 中选择 3000 条随机记录：

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000
于 2020-02-28T19:30:56.777 回答
-4

也许你可以做

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)
于 2008-10-30T05:29:34.837 回答