本文通過一個案例來看看MySQL優化器如何選擇索引和JOIN順序。表結構和數據準備參考本文最后部分"測試環境"。這里主要介紹MySQL優化器的主要執行流程，而不是介紹一個優化器的各個組件(這是另一個話題)。

   我們知道，MySQL優化器只有兩個自由度：順序選擇；單表訪問方式；這里將詳細剖析下面的SQL，看看MySQL優化器如何做出每一步的選擇。

1. 可能的選擇

   這里看到JOIN的順序可以是A|B或者B|A，單表訪問方式也有多種，對于A表可以選擇：全表掃描和索引`IND_L_D`(A.LastName = 'zhou')或者`IND_DID`(B.DepartmentID = A.DepartmentID)。對于B也有三個選擇：全表掃描、索引IND_D、IND_DN。
2. MySQL優化器如何做
2.1 概述

   MySQL優化器主要工作包括以下幾部分：Query Rewrite(包括Outer Join轉換等)、const table detection、range analysis、JOIN optimization(順序和訪問方式選擇)、plan refinement。這個案例從range analysis開始。
2.2 range analysis

   這部分包括所有Range和index merge成本評估(參考1 參考2)。這里，等值表達式也是一個range，所以這里會評估其成本，計算出found records(表示對應的等值表達式，大概會選擇出多少條記錄)。

   本案例中，range analysis會針對A表的條件A.LastName = 'zhou'和B表的B.DepartmentName = 'TBX'分別做分析。其中：

表A A.LastName = 'zhou' found records: 51
表B B.DepartmentName = 'TBX' found records: 1

   這兩個條件都不是range，但是這里計算的值仍然會存儲，在后面的ref訪問方式評估的時候使用。這里的值是根據records_in_range接口返回，而對于InnoDB每次調用這個函數都會進行一次索引頁的采樣，這是一個很消耗性能的操作，對于很多其他的關系數據庫是使用"直方圖"的統計數據來避免這次操作(相信MariaDB后續版本也將實現直方圖統計信息)。
2.3 順序和訪問方式的選擇：窮舉

   MySQL通過枚舉所有的left-deep樹(也可以說所有的left-deep樹就是整個MySQL優化器的搜索空間)，來找到最優的執行順序和訪問方式。
2.3.1 排序

   優化器先根據found records對所有表進行一個排序，記錄少的放前面。所以，這里順序是B、A。
2.3.2 greedy search

   當表的數量較少(少于search_depth，默認是63)的時候，這里直接蛻化為一個窮舉搜索，優化器將窮舉所有的left-deep樹找到最優的執行計劃。另外，優化器為了減少因為搜索空間龐大帶來巨大的窮舉消耗，所以使用了一個"偷懶"的參數prune_level(默認打開)，具體如何"偷懶"，可以參考JOIN順序選擇的復雜度。不過至少需要有三個表以上的關聯才會有"偷懶"，所以本案例不適用。