NLJの最適化戦略
NLJにおいてオプティマイザが決断すべきことは次の2つだ。
ひとつは、どのインデックスを用いてJOINを実行するかということ。複雑な条件でJOINが実行される場合には、内部表から行をフェッチする際に使うことが可能なインデックスが複数存在することがある。もちろんフェッチする行数が最小になるようなインデックスを選択するのが最も望ましい。反対に、最悪のケースは内部表をテーブルスキャンする場合であると言える。
もうひとつは、どのテーブルから先にJOINするかということだ。先にJOINするテーブル（駆動表）からフェッチする行数が少ない場合、実行すべきループの回数が少なくなるので有利になる。駆動表からフェッチする行数が少ない場合というのは、例えばWHERE句の検索条件でかなり行数を絞り込むことが出来る場合や、テーブルスキャンだが駆動表のサイズが小さい場合などが相当する。
例えば2つのテーブルをJOINするとき、どちらのテーブルにも適切なインデックスが設定されてあり、内部表からはユニークなインデックスを用いたルックアップ（eq_ref。詳細後述）で行をフェッチできる場合を考えてみよう。駆動表からフェッチする行数がNとすると、その各行について内部表から1行フェッチされることになるので、2つのテーブルからフェッチされる行数は合計で2N。つまり駆動表からフェッチする行数Nが小さいほうが効率が良い。
一方で、内部表からの行のフェッチにインデックスを利用できるがユニークインデックスではない場合には、内部表から複数の行がフェッチされる可能性がある。内部表から何行フェッチされるかは、インデックスのカーディナリティ（インデックスがとりうる値の種類の個数）次第だ。外部表からN行、内部表から平均M行フェッチされるとすると、トータルでN * M行がフェッチされる。基本的にはこのN * Mが小さいほど効率が良いということになる。内部表からのフェッチでインデックスを利用できない場合は、駆動表から1行フェッチするごとに内部表をスキャンする必要があり、とても効率が悪い。この場合は内部表からフェッチされる平均行数Mは、内部表全体の行数と等しくなる。
すなわち、NLJでは考え得るJOINの順序のバリエーション（順列）と、行の絞り込みや結合条件として使用するインデックスの組み合わせの中から、最も効率の良いものを選ぶのがオプティマイザの課題となる。
このような最適化を行うにはテーブルからフェッチされる行数が事前に分かっていることが必要だが、正確な行数は実際にクエリを実行してみるまでは分からない。鶏と卵の関係ではないが、クエリでテーブルからフェッチする行数を知るためにはクエリを実行しなければいけないし、クエリを実行するにはテーブルからフェッチする行数が分からなければいけないというジレンマが生じてしまう。これを解決するため、オプティマイザはテーブルから何行フェッチされるかの概算値を見積もることになる。MySQLのストレージエンジンには、インデックスのある範囲にマッチする行数の概算値を取得するAPI（records_in_range）があり、見積もりにはこのAPIが利用される。ただし見積もりはあくまでも見積もりなので正確な値ではない。ここで生じる誤差のため、必ずしもオプティマイザが最適な実行計画が選択するとは限らないのである。オプティマイザが非効率な実行計画を選択してしまう場合、DBAが最適な実行計画がどれかということを判断できるならば、STRAIGHT_JOINヒントやFORCE_INDEXヒントでオプティマイザに対してJOINする順序や使用するインデックスを教えるという対処が有効である。
オプティマイザは、使用可能なインデックスが存在するにもかかわらずテーブルスキャンを選択する場合がある。インデックスを使った行のフェッチは、必要な行だけをフェッチできるので行数が少ない場合には効率的だが、テーブルの大半の行をフェッチしなければいけないような場合には、アクセスパターンがランダムアクセスなのでかえって効率が低下してしまう。テーブルスキャンはシーケンシャルアクセスなので、テーブルのほとんどのレコードをフェッチする場合には非常に高速である。オプティマイザはそのような事情も考慮に入れて、各実行計画のコストを計算し、最もコストが低いものを選択するのである。
