join 語句用于實現多表查詢。

Index Nested-Loop Join

select * from a join b on a.id=b.id。對于兩張表 a 和 b，Mysql 優化器會選擇其中一張表執行全表掃描，稱為驅動表。對于驅動表每一數據行，在被驅動表查詢數據，將結果組合返回數據集。
假設驅動表行數是M，則時間復雜度為 M。
對于每一行，在 N 行被驅動表的非聚簇索引和局促索引各搜索一次。則時間復雜度為 M * 2 * log2(N)。
兩者相加 M + M * 2 * log2(N)。可以看出應選擇小表執行全表掃描，即作驅動表。這種使用索引的 join 語句稱為 Index Nested-Loop Join(NLJ) ，性能不錯。

Block Nested-Loop Join

如果被驅動表用不上索引，那么時間復雜度就是 M * N。mysql 對于這種 join 語句也有優化，稱為 Block Nested-Loop Join。具體操作是：兩張表都是全表掃描，用一塊內存區域 join_buffer 存儲其中一張表(驅動表)所有行的所選字段。掃描另一張表(被驅動表)，與 Join_buffer 數據對比，滿足則存入結果集。在內存執行 M * N 次操作比在磁盤執行 M * N 次操作快。

如果 join_buffer 不夠大，放不下驅動表所有數據。則分段存放(這就是 Block Nested-Loop Join 中 Block 的含義)。多次將驅動表的不同數據存入 join_buffer，再全表掃描被驅動表。為了降低 join_buffer 替換次數，選擇結果集更小的表作為驅動表。比如：表 a 有 30 行，查詢 3 個 int 字段，表b 有 10 行，查詢 10 個 int 字段。此時就應該選擇 a 表。
優化方案可以是：增加 join_buffer 空間。

Batched Key Access

Multi-Range Read

之前我們提及回表：在非聚簇索引查到主鍵 id，再到聚簇索引查詢數據行。如果在非聚簇索引查詢大量 id，Mysql 提供 Multi-Range Read 機制優化回表。它將非聚簇索引查詢到到的 id 集合在內存區域 read_rnd_buffer 排序并且按順序在聚簇索引查詢數據行。這樣可以將隨機訪問變為順序訪問，提升讀性能。

Index Nested-Loop Join 的優化

Index Nested-Loop Join 的被驅動表也有回表，Batched Key Access = Index Nested-Loop Join + Multi-Range Read。
具體來說：用 join_buffer 批量緩存驅動表的數據，在被驅動表回表查詢時利用 MRR 提升讀性能。

Block Nested-Loop Join 的優化

如果某些 join 查詢使用頻率很低，或者 where 條件過濾后表的數據行非常少，那么不適合建立索引。

但是不建立索引，時間復雜度 M * N。此時可以用臨時表，在臨時表為字段建立索引，將 Block Nested-Loop Join 變為 Index Nested-Loop Join