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 でこのアプローチを使用している場合は、NEWID()RAND()がすべての行に対して同じ値を返す可能性があるため、T-SQL 関数を使用する必要があります。

編集：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()。

4

12 に答える 12

70

最速の解決策は

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

これが私がこれが仕事をするべきだと思う理由です。

  • 行ごとに乱数が作成されます。番号は0から1の間です
  • 生成された数が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 よりも大きいです。

試してみたい 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

効率が本当に気になる場合は、ある種の手続き型言語でランダム キーの生成を行い、その結果をデータベースに挿入することを検討してください。SQL 以外のほとんどのものは、必要なループと乱数の生成に適している可能性があります。 .

于 2008-10-31T03:59:18.233 に答える
5

使うだけ

WHERE RAND() < 0.1

レコードの 10% を取得するには、または

WHERE RAND() < 0.01

レコードの 1% などを取得します。

于 2012-05-18T17:11:03.247 に答える
1

これらのソリューションはすべて、置換なしでサンプリングしているように見えることを指摘したいと思います。ランダムな並べ替えから上位 K 行を選択するか、ランダムな順序で一意のキーを含むテーブルに結合すると、置換なしで生成されたランダムなサンプルが生成されます。

サンプルを独立させたい場合は、置換でサンプリングする必要があります。user12861 のソリューションと同様の方法で JOIN を使用してこれを行う方法の 1 つの例については、質問 25451034を参照してください。ソリューションは T-SQL 用に書かれていますが、その概念はどの SQL データベースでも機能します。

于 2014-09-02T20:40:09.130 に答える
-4

多分あなたはできる

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