概要
何人かの同僚と話していると、「大きなデータベース テーブルからランダムな行を抽出する」という問題に遭遇しました。これは古典的なものであり、単純なアプローチ ( SO でも) は通常次のようなものです。
SELECT * FROM mytable ORDER BY RAND() LIMIT 1
問題
また、そのようなクエリは非常に非効率的であり、実際には非常に少ない行でしか使用できないこともわかっています。SO に残っているこれらの方法のように、効率を向上させるために使用できるアプローチがいくつかありますが、それらは任意の主キーでは機能せず、数値の主キーに穴が開くとすぐにランダム性が歪められます。最後に引用された質問への回答は、この記事にリンクされています。この記事には、「マスター データ」テーブルが変更されるたびに維持する必要がある追加の「均等配分」テーブルを含む、優れた説明といくつかの明るい解決策があります。しかし、大きなテーブルで頻繁に DELETE を行うと、追加されたテーブルの絶え間ない更新によって混乱する可能性があります。また、多くのソリューションが依存していることにも注意してくださいCOUNT(*)これは、MyISAM ではとてつもなく高速ですが、InnoDB では「ただ高速」です (他のプラットフォームでどのように動作するかはわかりませんが、InnoDB のケースは他のトランザクション データベース システムの代表であると思われます)。
それに加えて、私が見つけることができた最高のソリューションでさえ高速ですが、Ludicrous Speedは高速ではありません.
アイデア
別のサービスが、ランダム行 ID またはランダム行全体の生成、バッファリング、および配布を担当する場合があります。
- 元の PK の構造に応じて、ランダムな行 ID を抽出する最適な方法を選択できます。キーの順序付けられたリストは、サービスによって RAM で維持できます (PK の実際のサイズに加えて、1 行あたりのバイト数が多すぎてはいけません。標準の PC で最大 100 ~ 1000M 行、最大 1 ~強力なサーバーで 100 億行)
- キーがメモリに格納されると、各キーに暗黙的な「行番号」があり、そこに穴がないため、乱数を選択して対応するキーを直接フェッチするだけです
- 受信リクエストの急増に迅速に対応するために、すぐに使用できるランダム キーのバッファを維持できます。
- サービスのコンシューマは接続し、バッファから N 個のランダムな行を要求します
- 行は単純なキーとして返されるか、サービスは行全体をフェッチするためにデータベース接続 (のプール) を維持できます
- バッファが空の場合、リクエストはブロックされるか、EOF のように返される可能性があります
- データがマスターテーブルに追加された場合、同じデータをそのコピーにも追加するようにサービスに通知する必要があり、ランダムピックのバッファをフラッシュして、そこから続行します
- マスターテーブルからデータが削除された場合、「すべてのキー」リストと「ランダムピック」バッファの両方からそのデータを削除するようにサービスに通知する必要があります
- マスターテーブルでデータが更新された場合、キーリストとランダムピックで対応する行を更新するようにサービスに通知する必要があります
クールだと思う理由
- 起動時またはそうするように指示されたときに、キーの初期ロード以外のディスクに触れない
- 数値かどうかに関係なく、あらゆる種類の主キーで動作します
- 大規模なデータのバッチを更新することがわかっている場合は、完了したときにそれを知らせることができます (つまり、元のデータのすべての挿入/更新/削除ではありません)。ランダムな行のリクエストのみをブロックします
- 元のデータのあらゆる種類の更新が非常に高速
- 一部の作業をリレーショナル データベースから別のメモリのみのプロセスにオフロードします。スケーラビリティに役立ちます
- クエリ、スキャン、ソートを待つことなく、バッファから非常に高速に応答します
- SQL 以外の同様のユースケースに簡単に拡張できます
なぜ私たちはそれがばかげた考えかもしれないと思うのですか
- 第三者の助けを借りずにアイデアを思いついたからです
- 誰も（私たちが聞いたことがある）似たようなことをわざわざやったことがないからです
- 元のデータが変更されるたびに更新を維持するためにミックスが複雑になるためです。
そして問題は...
似たようなものはすでにありますか？そうでない場合、それは実現可能でしょうか？そうでない場合、なぜですか？