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

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

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

? Cost based optimizer：通過(guò)計(jì)算查詢代價(jià)對(duì) plan 進(jìn)行優(yōu)化

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

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

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

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

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

? Plan： 所有查詢計(jì)劃的接口

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

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

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

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

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

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

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