本文主要是對數(shù)據(jù)庫查詢優(yōu)化器的一個綜述，包括：
查詢優(yōu)化器定義、分類
查詢優(yōu)化器執(zhí)行過程
CBO框架Calcite簡介
1.查詢優(yōu)化器是什么
數(shù)據(jù)庫主要由三部分組成，分別是解析器、優(yōu)化器和執(zhí)行引擎，如下圖所示：
其中優(yōu)化器是數(shù)據(jù)庫中用于把關(guān)系表達式轉(zhuǎn)換成執(zhí)行計劃的核心組件，很大程度上決定了一個系統(tǒng)的性能。
2.查詢優(yōu)化器分類
查詢優(yōu)化器分為兩類：基于規(guī)則的優(yōu)化器(Rule-Based Optimizer，RBO) 和基于代價的優(yōu)化器(Cost-Based Optimizer，CBO) ：
-
基于規(guī)則的優(yōu)化器(Rule-Based Optimizer，RBO)
根據(jù)優(yōu)化規(guī)則對關(guān)系表達式進行轉(zhuǎn)換，這里的轉(zhuǎn)換是說一個關(guān)系表達式經(jīng)過優(yōu)化規(guī)則后會變成另外一個關(guān)系表達式，同時原有表達式會被裁剪掉，經(jīng)過一系列轉(zhuǎn)換后生成最終的執(zhí)行計劃。
RBO中包含了一套有著嚴格順序的優(yōu)化規(guī)則，同樣一條SQL，無論讀取的表中數(shù)據(jù)是怎么樣的，最后生成的執(zhí)行計劃都是一樣的。同時，在RBO中SQL寫法的不同很有可能影響最終的執(zhí)行計劃，從而影響腳本性能。
-
基于代價的優(yōu)化器(Cost-Based Optimizer，CBO)
根據(jù)優(yōu)化規(guī)則對關(guān)系表達式進行轉(zhuǎn)換，這里的轉(zhuǎn)換是說一個關(guān)系表達式經(jīng)過優(yōu)化規(guī)則后會生成另外一個關(guān)系表達式，同時原有表達式也會保留，經(jīng)過一系列轉(zhuǎn)換后會生成多個執(zhí)行計劃，然后CBO會根據(jù)統(tǒng)計信息和代價模型(Cost Model)計算每個執(zhí)行計劃的Cost，從中挑選Cost最小的執(zhí)行計劃。由上可知，CBO中有兩個依賴：統(tǒng)計信息和代價模型。統(tǒng)計信息的準確與否、代價模型的合理與否都會影響CBO選擇最優(yōu)計劃。
從上述描述可知，CBO是優(yōu)于RBO的，原因是RBO是一種只認規(guī)則，對數(shù)據(jù)不敏感的呆板的優(yōu)化器，而在實際過程中，數(shù)據(jù)往往是有變化的，通過RBO生成的執(zhí)行計劃很有可能不是最優(yōu)的。
事實上目前各大數(shù)據(jù)庫和大數(shù)據(jù)計算引擎都傾向于使用CBO，例如從Oracle 10g開始，Oracle已經(jīng)徹底放棄RBO，轉(zhuǎn)而使用CBO；而Hive在0.14版本中也引入了CBO。
3.查詢優(yōu)化器執(zhí)行過程
無論是RBO，還是CBO都包含了一系列優(yōu)化規(guī)則，這些優(yōu)化規(guī)則可以對關(guān)系表達式進行等價轉(zhuǎn)換，常見的優(yōu)化規(guī)則包含：
謂詞下推
列裁剪
常量折疊
其他
在這些優(yōu)化規(guī)則的基礎(chǔ)上，就能對關(guān)系表達式做相應(yīng)的等價轉(zhuǎn)換，從而生成執(zhí)行計劃。下面將介紹RBO和CBO兩種優(yōu)化器的執(zhí)行過程。
- RBO
RBO的執(zhí)行過程比較簡單，主要包含兩個步驟：
1）Transformation
遍歷關(guān)系表達式，只要模式能夠滿足特定優(yōu)化規(guī)則就進行轉(zhuǎn)換。
2）Build Physical Plan
經(jīng)過Step1之后就生成了一個邏輯執(zhí)行計劃，但這只是邏輯上可行，還需要將邏輯執(zhí)行計劃build成物理執(zhí)行計劃，即決定各個Operator的具體實現(xiàn)。如Join算子的具體實現(xiàn)選擇BroadcastHashJoin還是SortMergeJoin。
-
CBO
CBO查詢優(yōu)化主要包含三個步驟：
1）Exploration
根據(jù)優(yōu)化規(guī)則進行等價轉(zhuǎn)換，生成等價關(guān)系表達式，此時原有關(guān)系表達式會被保留。
2）Build Physical Plan
決定各個Operator的具體實現(xiàn)。
3）Find Best Plan
根據(jù)統(tǒng)計信息計算各個執(zhí)行計劃的Cost，選擇Cost最小的執(zhí)行計劃。
CBO實現(xiàn)有兩種模型，即Volcano模型[1]和Cascades模型[2]，其中Calcite使用的是Volcano模型，而Orca[3]使用的是Cascades模型。這兩種模型的思想基本相同，不同點在于Cascades模型并不是先Explore、后Build，而是邊Explore邊Build，從而進一步裁剪掉一些執(zhí)行計劃。在這里就不展開了，對此感興趣的同學(xué)可以看下相關(guān)的論文。
4.CBO框架Calcite簡介
Apache Calcite 是一個獨立于存儲與執(zhí)行的SQL優(yōu)化引擎，廣泛應(yīng)用于開源大數(shù)據(jù)計算引擎中，如Flink、Drill、Hive、Kylin等。另外，MaxCompute也使用了Calcite作為優(yōu)化器框架。Calcite的架構(gòu)如下圖所示：
其中Operator Expressions 指的是關(guān)系表達式，一個關(guān)系表達式在Calcite中被表示為RelNode，往往以根節(jié)點代表整個查詢樹。Calcite中有兩種方法生成RelNode：
-
通過Parser直接解析生成
從上述架構(gòu)圖可以看到，Calcite也提供了Parser用于SQL解析，直接使用Parser就能得到RelNode Tree。
-
通過Expressions Builder轉(zhuǎn)換生成
不同系統(tǒng)語法有差異，所以Parser也可能不同。針對這種情況，Calcite提供了Expressions Builder來對抽象語法樹(或其他數(shù)據(jù)結(jié)構(gòu))進行轉(zhuǎn)換得到RelNode Tree。如Hive(某一種Data Processing System)就是通過這種方法來生成的。
Query Optimizer 根據(jù)優(yōu)化規(guī)則(Pluggable Rules)對Operator Expressions進行一系列的等價轉(zhuǎn)換，生成不同的執(zhí)行計劃，最后選擇代價最小的執(zhí)行計劃，其中代價計算時會用到Metadata Providers提供的統(tǒng)計信息。
事實上，Calcite提供了RBO和CBO兩種優(yōu)化方式，分別對應(yīng)HepPlanner和VolcanoPlanner。對此，本文也不進行展開，后續(xù)有時間再詳細介紹Calcite的具體實現(xiàn)。
5.總結(jié)
本文是對查詢優(yōu)化器的一個綜述，介紹了查詢優(yōu)化器的分類、執(zhí)行過程，以及優(yōu)化器通用框架Calcite。
