SQL - O（1）時間にランダムな行を選択しますか？

Question

好奇心の質問 - 私はSQLを経由して選択されたランダム行を見てきた時はいつでも、私はこのようにそれを見てきました：うまく動作しますが、nはの大きさをあるO(n)ある

SELECT * FROM table_name ORDER BY RANDOM() LIMIT 1;

を表。 （これは私が持っている実際のパフォーマンスの問題ではなく、DBは十分速く、学問的な質問です）。

他の言語のように、SQLの任意のバージョンでO(1)ランダム選択を実装する方法はありますか？ （たとえば、1〜nの間で乱数rを生成し、r番目の行を選択します）。

Answer 1

ご質問は、データベースクエリは何とかO(n)であるという仮定に基づいている - 彼らはありません（そうでないJOIN sが恐ろしく高価です）。

SQLは、リレーショナル代数に基づいたRDBMシステムに存在するテーブル/ローストアの抽象化であり、参照も請求もしません。実行時の複雑さは良いです。これは、インプリメンテーション・データベース・システムがインデックス、インメモリー・ストア、特殊ケース・ハンドラーおよびその他の最適化を使用してさまざまなランタイム・パフォーマンスで正しい結果を提供できるためです。これは、SQLが物理行番号、ブロックアドレス、Bツリーノードなどの実装の詳細を公開していないことを意味します。クエリを書くときには、これらのことに気を付けるべきではありません。大事なのは、あなたの質問。

したがって、特にスマートなDBMSにはORDER BY RANDOM() LIMIT 1の特殊ケースハンドラがあり、これはO(1)の時間に実行されます。

...しかし、このケースではMySQLが最適化されていないようですので、より良いアプローチが必要です。 clustered_indexex_columnがあなたの主キーまたは上ORDER BYを実行することが非常に安くなってそれ以外の列かもしれコラムです

SELECT @n := COUNT(*) FROM table_name 
SET @offset := ROUND(RAND() * @n) 
SELECT * FROM table_name ORDER BY clustered_indexed_column LIMIT 1 OFFSET @offset 

：

はこれを試してみてください。インデックスが正しく設定されていると仮定すると、このクエリはO(log(n))以上の順に実行されます。

Answer 2

1. ソートはO（N *ログ（n））を
2. は、その列のハッシュインデックスを含むseqential数の列を持つ表を作成し、あなたが示唆したように、乱数を生成し、該当する行を選択しています。

http://logicalread.solarwinds.com/oracle-11g-hash-indexes-mc02/#.WBE0hBmEbqA

Answer 3

O（n）は必ずしも高速であるとは限りません。

• 計算cntはO（n）が全表スキャン、次のとおりです。あなたが欲しいものを行う必要があり、次のようなしインデックス付き

  SELECT t.* 
  FROM (SELECT t.* 
       FROM table_name t CROSS JOIN 
        (SELECT COUNT(*) as cnt FROM table_name) x 
       WHERE RANDOM() <= 100.0/cnt 
      ) t 
  ORDER BY RANDOM() 
  LIMIT 1; 
  

  を、これが処理されます。

• フィルタリングのためにwhere句を処理すると、テーブル全体のサイズに関係なく、約100行が生成されます。
• ORDER BYを行うと、これは依存しないNの大きな値（nが100以下であれば確かに、この「定数」は複数のOに似ている（N）（ログ）

ための「定数」であります