ORDER BY rand() 为什么慢？大表如何高效随机取 N 行？

考察要点

这道题面试官想看你是否懂 ORDER BY 的内部工作原理、rand() 函数的非确定性对查询优化的影响，以及在大数据量下进行高效随机抽样的工程能力。核心是考察你是否能从数据库执行原理层面分析性能瓶颈，并给出在不同约束条件下（如主键是否连续、随机性要求高低）的多种优化方案。

核心概念

ORDER BY rand() 慢的根源在于它无法利用索引进行排序，并且其执行过程涉及两个非常昂贵的操作：全表扫描和文件排序（filesort）。

1. ORDER BY rand() 的执行过程

当 MySQL 执行 SELECT * FROM users ORDER BY rand() LIMIT 10; 时，其内部流程如下：

1. 全表扫描：MySQL 无法预知 rand() 的值，因为它是一个非确定性函数（Non-deterministic Function），每次调用的结果都不同。因此，优化器无法使用任何索引来满足 ORDER BY 子句。它必须读取 users 表中的所有行。
2. 生成随机值：为从表中读取的每一行数据，都执行一次 rand() 函数，生成一个随机的排序权重。
3. 创建临时表：MySQL 在内存（sort_buffer）或磁盘上创建一个临时表，用于存储每一行的原始数据以及为其生成的随机排序权重。
4. 文件排序 (Filesort)：对这个巨大的临时表，按照随机排序权重列进行排序。如果临时表大小超过了 sort_buffer_size，MySQL 会将数据分块，在磁盘上进行多路归并排序，这会产生大量的 I/O 操作，性能极差。
5. 返回结果：排序完成后，取出前 10 行数据作为最终结果。

这个过程可以用下图表示：

 1graph TD
 2    A[InnoDB 表 (百万/千万行)] -- 全表扫描 --> B{为每一行计算 rand()};
 3    B --> C[创建临时表存储 (row_data, rand_value)];
 4    C --> D{sort_buffer 是否足够?};
 5    D -- 是 --> E[内存中快速排序];
 6    D -- 否 --> F[磁盘上进行 Filesort (极慢)];
 7    E --> G[返回 Top N 结果];
 8    F --> G;

• 复杂度：如果表中有 N 行数据，排序的时间复杂度为 $O(N \log N)$，加上全表扫描的 $O(N)$，整个操作非常耗时。空间复杂度为 $O(N)$，因为需要存储所有行的数据和随机值。

2. 非确定性函数 (Non-deterministic Function)

像 RAND(), NOW(), UUID() 这类函数，在每次调用时返回的结果都可能不同。数据库优化器无法对它们进行有效的优化，比如：

• 无法使用索引：索引 B+ 树中的键值是预先排好序的，而一个动态变化的 rand() 值无法对应到索引的任何一个静态位置。
• 无法缓存查询：开启查询缓存（Query Cache，MySQL 8.0 已废弃）的场景下，包含非确定性函数的 SQL 不会被缓存。

多种解法（高效随机方案）

假设我们有一张用户表 users，主键 id 是自增整数。

 1CREATE TABLE `users` (
 2  `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
 3  `name` VARCHAR(50) NOT NULL,
 4  `email` VARCHAR(100) NOT NULL,
 5  PRIMARY KEY (`id`)
 6) ENGINE=InnoDB;

解法 1：主键范围法（适用于自增主键且基本连续）

思路：如果主键是数字类型且大致连续，我们可以先获取主键的范围，然后随机生成 N 个主键 ID，再通过 IN 子句查询。

步骤：

1. 在业务代码中，获取 users 表的 MIN(id) 和 MAX(id)。
2. 在该范围内，随机生成 N 个不重复的整数 ID。
3. 使用 IN 子句一次性查询出这些 ID 对应的行。

 1-- 步骤 1 & 2: 在应用层完成
 2-- min_id = 1, max_id = 10000000
 3-- random_ids = [123, 4567, 8910, ...] // 生成 N 个随机 ID
 4
 5-- 步骤 3: SQL 查询
 6SELECT id, name, email
 7FROM users
 8WHERE id IN (123, 4567, 8910, ...);

• 复杂度：时间复杂度主要为 N 次主键索引的查找，约为 $O(N \log M)$（M为表总行数），在 B+ 树上效率极高。空间复杂度为 $O(N)$。
• 索引依赖：严重依赖主键索引。
• 优点：性能极高，避免了全表扫描和排序。
• 缺点：如果主键存在大量删除导致空洞，可能无法精确取到 N 行，需要业务代码进行重试或取样时取略多于 N 的样本。

解法 2：索引定位法（适用于大数据量下的近似随机）

思路：随机选择一个起始点，然后向后取 N 行。这是一种牺牲部分随机性换取极高性能的方法。

步骤：

1. 获取表的总行数 COUNT(*) 和主键 MAX(id)。
2. 生成一个随机数 rand_id，使其落在 [MIN(id), MAX(id) - N] 的范围内。
3. 从这个随机 ID 开始，向后取 N 行。

 1-- 步骤 1 & 2: 在应用层完成
 2-- total_rows = SELECT COUNT(*) FROM users;
 3-- max_id = SELECT MAX(id) FROM users;
 4-- random_offset = rand(0, total_rows - N);
 5
 6-- 步骤 3: SQL 查询 (推荐)
 7SELECT id, name, email
 8FROM users
 9WHERE id >= (
10    SELECT id FROM users
11    ORDER BY id
12    LIMIT #{random_offset}, 1
13)
14LIMIT N;

或者一个更简化的版本（但随机性更差）：

 1-- 简化版
 2-- rand_id = rand(min_id, max_id)
 3SELECT id, name, email
 4FROM users
 5WHERE id >= #{rand_id}
 6LIMIT N;

• 复杂度：时间复杂度为一次索引范围扫描，性能很高，接近 $O(N)$。
• 索引依赖：依赖主键或某个有序索引。
• 优点：非常快，即使在千万、亿级表中也能在毫秒级完成。
• 缺点：随机性不均匀。ID 靠前的行被选中的概率低于 ID 靠后的行。结果是“局部连续”的，而非“全局离散”的。

解法 3：分段扫描法（性能与随机性的最佳平衡）

思路：这是对 ORDER BY rand() 的一个巧妙优化。先通过一个较快的、非精确的随机过滤，将数据量大幅减少，再对这个小结果集使用 ORDER BY rand()。

 1-- 假设要从 1000 万行中取 10 行
 2-- 预估采样率，比如取 100 行作为候选集 (100 / 10,000,000 = 0.00001)
 3-- 为了保证能取够，可以适当放大采样率，比如放大 2-5 倍
 4SELECT *
 5FROM users
 6WHERE rand() <= 0.00005
 7ORDER BY rand()
 8LIMIT 10;

更优化的纯 SQL 方案：结合 JOIN，先在索引上随机，再回表。

 1-- ✅ MySQL 5.6+
 2SELECT u.id, u.name, u.email
 3FROM users AS u
 4JOIN (
 5    SELECT id FROM users ORDER BY rand() LIMIT 10
 6) AS t2 ON u.id = t2.id;

这个方案的子查询 (SELECT id FROM users ORDER BY rand() LIMIT 10) 仍然需要排序，但它只对 id 列进行排序。如果 id 是主键，InnoDB 表中这相当于对 (rand_value, id) 进行排序，避免了携带庞大的行数据，sort_buffer 可能足以容纳，从而在内存中完成排序，速度远快于对 SELECT * 的结果排序。

• 复杂度：取决于子查询的性能。虽然仍是 $O(N \log N)$，但常数因子和 I/O 成本大大降低。
• 索引依赖：子查询可以利用覆盖索引（如果只 SELECT id）。
• 优点：纯 SQL 实现，随机性非常好，性能远高于直接 ORDER BY rand()。
• 缺点：性能不如解法1和2，但随机性最好。

常见低分回答

1. 只说 rand() 慢，但说不清原理：无法解释 filesort、临时表和非确定性函数的概念，只停留在表面。
2. 提出 LIMIT offset, N 方案：SELECT * FROM users LIMIT #{random_offset}, 10;。这是一个巨大的坑，因为 LIMIT 大偏移量会导致 MySQL 扫描 offset + 10 行然后丢弃前面的 offset 行，在 offset 很大时，这和全表扫描几乎一样慢。
3. 在子查询中滥用 ORDER BY rand()：认为 WHERE id IN (SELECT id FROM users ORDER BY rand() LIMIT 10) 就万事大吉了。虽然比对全列排序好，但没有意识到子查询本身仍然是性能瓶颈。
4. 忽略主键不连续的问题：在推荐主键范围法时，不提及 ID 删除造成的空洞会导致取不足 N 行，没有给出相应的解决方案（如循环重试）。
5. 使用 WHERE rand() < 0.01：这种方式返回的行数是不确定的，可能多于或少于 N，不满足“精确取 N 行”的要求。

工程实践与优化

• 看执行计划：EXPLAIN SELECT * FROM users ORDER BY rand() LIMIT 10; 的结果中，Extra 列会明确显示 Using temporary; Using filesort，这是性能问题的直接证据。而优化后的方案，如主键范围法，EXPLAIN 结果会显示 type: range 或 type: eq_ref，表明用上了索引。
• 业务场景权衡：没有完美的方案，只有最适合的方案。
  • 对随机性要求不高（如“猜你喜欢”的初始推荐）：用解法2（索引定位法），性能最好。
  • 对随机性要求高，且主键连续（如抽奖）：用解法1（主键范围法），在应用层做逻辑控制。
  • 对随机性要求高，主键不连续或无序：用解法3（分段扫描法），在性能和随机性之间取得平衡。
• 缓存应用：对于不需要实时强随机性的场景（如首页随机展示商品），可以定时任务跑一个脚本，用上述高效方法抽取一批数据（如 1000 条）放入 Redis 缓存，线上业务直接从 Redis 中随机取 N 条。这能将数据库的 QPS 压力降为零。

常见追问与延伸题目

1. 追问：如果数据量增长 100 倍，达到 10 亿级别，你的方案性能会怎样？

   • 回答要点：
     • ORDER BY rand() 将完全不可用，可能导致数据库长时间夯死。
     • 解法1（主键范围法）：性能几乎不受影响。因为 MAX(id) 和 MIN(id) 获取很快，后续的 IN (...) 查询是 N 次独立的索引查找，其耗时与表总大小 M 的对数 $\log M$ 相关，增长非常缓慢。
     • 解法2（索引定位法）：性能也几乎不受影响。COUNT(*) 在 InnoDB 上虽然慢，但可以维护在计数表里。核心的 LIMIT offset, 1 依然可以通过索引高效定位。
     • 解法3（分段扫描法）：性能会线性下降，因为子查询的 ORDER BY rand() 成本与 N 成正比。虽然比原始方案好，但在 10 亿级别也可能变得无法接受。

2. 追问：如果表的主键不是自增整数，而是 UUID 或组合主键，你的方案怎么调整？

   • 回答要点：
     • 这使得解法1和2直接失效，因为无法在 UUID 字符串上进行简单的范围随机。
     • 此时可以寻找其他有序的列，比如 create_time (DATETIME 或 BIGINT 时间戳)，并建立索引。然后可以在 create_time 列上应用**解法2（索引定位法）**的变种，随机一个时间点去取数据。
     • 如果没有任何合适的有序数值/时间列，那么**解法3（分段扫描法）**或其变种是最佳选择。即先通过覆盖索引扫描主键列 (SELECT uuid FROM users)，在应用层随机抽样 N 个 uuid，再通过 IN 子句查回数据。这避免了对海量数据的 filesort，代价是多了一次网络来回和一次索引全扫描。

3. 追问：如果换成 PostgreSQL 或 TiDB，答案有什么不同？

   • 回答要点：
     • PostgreSQL：ORDER BY RANDOM() 同样慢。但 PostgreSQL 提供了内建的高效抽样方法 TABLESAMPLE。
       • SELECT * FROM users TABLESAMPLE SYSTEM (0.1);：基于数据块的抽样，速度极快，但随机性稍差，可能受数据存储物理位置影响。
       • SELECT * FROM users TABLESAMPLE BERNOULLI (0.1);：基于行的抽样，对每一行按指定概率（这里是 0.1%）判断是否选取，更随机，但需要全表扫描，速度比 SYSTEM 慢。在实践中，可以结合两者优点，先用 SYSTEM 大范围采样，再精确 LIMIT。
     • TiDB / OceanBase (分布式数据库)：ORDER BY rand() 的问题被急剧放大。它需要将所有分片（Region）的数据拉到同一个计算节点（TiDB Server）上进行排序，产生巨大的网络开销和计算瓶颈。主键范围法（解法1）和索引定位法（解法2）依然是最高效的，因为它们是点查或小范围扫描，可以被精确地下推到对应的存储节点（TiKV）执行，避免了大规模数据移动。