これらの列を持つ 2 つのテーブルがあるとします。
FirstName Id
Joe 3
Sarah 5
LastName Id
Smith 5
Rodriguez 3
で結合した場合に一致する各テーブルに 3000 の他の名前があると仮定しIdます。またId、主キーではなく、インデックスやその他の制約のない通常の整数列であると見なします。
Idインデックスなしでの結合のパフォーマンスが O(n^2) であると仮定するのは正しいですか? MySQL は、この結合を実行する前に自動的にインデックスを作成し、それがどれほど効率的であるかを認識しますか? ほとんどの場合、O(n*log(n) + n) (並べ替えてから各テーブルを反復する) は、自明でない n に対して O(n^2) を打ち負かすため、明確な勝利になると思います。この仮定は正しいですか？