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