mysql - 2 つのインデックスでの内部結合のビッグ オー パフォーマンス

Question

次のクエリの Big-Oh パフォーマンスを把握しようとしています。

SELECT * 
FROM table1 INNER JOIN table2 ON table1.a = table2.b
GROUP BY table1.a

table1.a はテーブルの主キーです。table2.b には一意でないインデックスがあります。

私の考えでは、各インデックスは O(log n) で検索できるため、このクエリは O(log n * log m) で実行されます。ここで、n はテーブル 1 の行数、m はテーブル 2 の行数です。

任意の入力をいただければ幸いです。

Answer 1

クエリのパフォーマンスは、SQL ステートメントが内部でどのように実行されるかによって異なります。

EXPLAIN (MySQL の場合: http://dev.mysql.com/doc/refman/5.1/en/explain.html ) を調べると、より正確な結果が得られる可能性があるため、クエリの実行方法に関する詳細情報を取得できます。ビッグオーを見るよりも。

ところで：あなたが本当にビッグオーを探しているなら、ゴードン・リノフの答えは良さそうです！