為什么說優(yōu)化器是數(shù)據(jù)庫的核心？

優(yōu)化器是數(shù)據(jù)庫的核心，決定了每條語句如何執(zhí)行。如果將數(shù)據(jù)庫比作一支軍隊，那么優(yōu)化器就是這支軍隊的主將、軍師，需要運籌帷幄，決勝于千里之外。俗話說一將無能累死三軍，同樣的一條語句，選擇不同的查詢計劃，最終的運行時間可能會相差很大。對優(yōu)化器的研究一直是學術(shù)界比較活躍的領(lǐng)域，優(yōu)化是永無止境，可以說在這塊投入多大的精力都不為過。 從優(yōu)化方法上，大致可以分為三類：

? Rule based optimizer：通過啟發(fā)式規(guī)則對 plan 進行優(yōu)化

? Cost based optimizer：通過計算查詢代價對 plan 進行優(yōu)化

? History based optimizer：通過歷史查詢信息對 plan 進行優(yōu)化

基于規(guī)則的優(yōu)化器比較容易實現(xiàn)，只要選取一些常用的規(guī)則，就可以對大多數(shù)常用的查詢有較好的效果。但是其缺陷也比較明顯：無法根據(jù)數(shù)據(jù)的真實情況，選擇最優(yōu)的方案。比如對于查詢語句 “select * from t where c1 = 10 and c2 > 100” 在選擇索引時，如果只根據(jù)規(guī)則，那么一定是選擇 c1 上面的索引進行查詢，但是如果 t 中 c1 所有的值都是 10，那么這個查詢計劃就很差。這個時候如果有表中數(shù)據(jù)分布的信息，對選擇好的查詢計劃很有幫助。

基于代價的優(yōu)化器復(fù)雜一些，其核心問題有兩個，一個是如何獲取數(shù)據(jù)的真實分布信息，另一個是如何根據(jù)這些信息，估算出某一個查詢計劃所需的代價。

基于歷史信息的查詢優(yōu)化器用的比較少，一般 OLTP 數(shù)據(jù)庫中不會涉及。

TiDB 的優(yōu)化器相關(guān)代碼在 plan 包中，這個包的主要工作是將 AST 轉(zhuǎn)換為查詢計劃樹，樹中的節(jié)點是各種邏輯算子或者是物理算子，對查詢計劃化的各種優(yōu)化都是通過調(diào)用樹根節(jié)點的各種方法，遞歸地對所有節(jié)點進行優(yōu)化，并且會不斷的對樹中的節(jié)點進行轉(zhuǎn)換和裁剪。 最重要的幾個接口在 plan.go 中，包括：

? Plan： 所有查詢計劃的接口

? LogicalPlan：邏輯查詢計劃，所有的邏輯算子都需要實現(xiàn)這個接口

? PhysicalPlan：物理查詢計劃，所有的物理算子都需要實現(xiàn)這個接口

邏輯優(yōu)化的入口是 planbuilder.build()，輸入是 AST，輸出是邏輯查詢計劃樹。然后在這棵樹上進行邏輯查詢優(yōu)化：

? 調(diào)用 LogicalPlan 的 PredicatePushDown 接口，將謂詞盡可能下推

? 調(diào)用 LogicalPlan 的 PruneColumns 接口，將不需要的列裁減掉

? 調(diào)用 aggPushDownSolver.aggPushDown，將聚合算子下推到 Join 之前

拿到邏輯優(yōu)化后的查詢計劃樹之后，會進行物理優(yōu)化，代碼的入口是對邏輯查詢計劃樹的根節(jié)點調(diào)用。  convert2PhysicalPlan(&requiredProperty{})，其中 requiredProperty 是對下層返回結(jié)果順序、行數(shù)的要求。 邏輯查詢計劃樹從根節(jié)點開始，不斷的遞歸調(diào)用，將每個節(jié)點從邏輯算子轉(zhuǎn)成物理算子，并且根據(jù)每個節(jié)點的查詢代價找到一條比較好的查詢路徑。