摘要：?本文主要是對數據庫查詢優化器的一個綜述，包括查詢優化器分類、查詢優化器執行過程和CBO框架Calcite。

這是MaxCompute有關SQL優化器原理的系列文章之一。我們會陸續推出SQL優化器有關優化規則和框架的其他文章。添加釘釘群“關系代數優化技術”（群號11719083）可以獲取最新文章發布動態。

本文主要是對數據庫查詢優化器的一個綜述，包括：

• 查詢優化器定義、分類

• 查詢優化器執行過程

• 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。

閱讀原文

本文為云棲社區原創內容，未經允許不得轉載。