☰

MySQL SQL データベースからの単純なランダムサンプル 質問する

tag-icon • tag-icon mysql sql random
MySQL SQL データベースからの単純なランダムサンプル 質問する

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 つの調整を加えました。

  • 希望するサンプルサイズの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()再び十分に小さくなるまでサンプリングすることができます。

ベストアンサー1

一番早い解決策は

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

これが私がこの方法でうまくいくと考える理由です。

  • 各行にランダムな数字を作成します。数字は0から1の間です。
  • 生成された数値が 0 から .3 (30%) の間の場合にその行を表示するかどうかを評価します。

これは、rand() が均一分布で数値を生成していることを前提としています。これがこれを行う最も早い方法です。

誰かがその解決策を推奨したのを見たのですが、証拠もなく却下されました。これに対して私が言いたいのは、

  • これはO(n)ですが、ソートは必要ないのでO(n lg n)よりも高速です。

  • mysqlは各行に乱数を生成する能力に優れています。これを試してみてください -

    INFORMATION_SCHEMA.TABLES から rand() を選択し、制限を 10 にします。

問題のデータベースは mySQL なので、これが正しい解決策です。

おすすめ記事