[解決済み] Sqlデータベースからの単純な無作為標本

質問

SQLで効率的に単純な無作為抽出を行うには？問題のデータベースはMySQLを使用しています。私のテーブルは少なくとも20万行で、約1万件の単純無作為抽出をしたいのです。

答えは、quot;learn" です。

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() は、すべての行に対して同じ値を返す可能性があります。 .

edit: 5年後

私はより大きなテーブルでこの問題に再び遭遇し、結局 @ignorant の解決策に2つの微調整を加えたバージョンを使用することにしました。

• 行を希望するサンプルサイズの2～5倍にサンプリングして、安価に ORDER BY RAND()
• の結果を保存します。 RAND() を、挿入/更新のたびにインデックス付きカラムに追加します。(データセットがあまり更新されない場合、このカラムを新鮮に保つための別の方法を見つける必要があるかもしれません)。

あるテーブルの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() また

解決方法は？

この種の問題については、こちらで非常に興味深い議論が展開されています。 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)のソリューションがベストだと思います。 というのも、必ずしも大きな配列全体をソートする必要はなく、最小の m 回を検索すればよいからです。 しかし、あなたが投稿したような数の場合、mはとにかくlg nより大きいです。

試してみたい3つの前提条件

1. テーブルには、ユニークでインデックス付きの主キーが存在します。

2. 選択したいランダムな行の数 (m) は、テーブルの行の数 (n) よりもはるかに小さい。

3. 一意な主キーは1からnまでの隙間のない整数である。

仮定1と2だけならO(n)でできると思います。ただし、仮定3に合わせてテーブルにインデックスを全部書く必要があるので、必ずしも高速なO(n)とは言えません。 もし、テーブルについて何か他の良い仮定が追加的にできれば、このタスクはO(m log m)で実行可能です。 仮定3は、作業しやすい素敵な追加特性でしょう。 m個の数字を連続して生成するときに重複がないことを保証する乱数生成器があれば、O(m)の解決策が可能になります。

3つの前提条件を考えると、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

もし本当に効率を重視するのであれば、ある種の手続き型言語でランダムキー生成を行い、その結果をデータベースに挿入することを検討してもよいでしょう。