这里有一个关于此类问题的非常有趣的讨论： 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。
我们可以尝试以下三种假设：
表中有一个唯一的，已索引的主键
您要选择的随机行数（m）比表中的行数（n）小得多
唯一主键是一个整数，范围是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 nfor i = 1 to m insert RandomKeysAttempt select rand()*n + 1-- eliminate duplicatesinsert 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 necessarywhile count(RandomKeys) < m NextAttempt = rand()*n + 1 if not exists (select * from RandomKeys where RandomKey = NextAttempt) insert RandomKeys select NextAttempt-- get our random rowsselect *from RandomKeys rjoin table t ON r.RandomKey = t.UniqueKey
如果您真的担心效率，则可以考虑使用某种过程语言来生成随机密钥，并将结果插入数据库中，因为除SQL以外，几乎任何其他方法都可能在所需的循环和随机数生成方面更好。
