摘要：?本文主要是對數(shù)據(jù)庫查詢優(yōu)化器的一個綜述，包括查詢優(yōu)化器分類、查詢優(yōu)化器執(zhí)行過程和CBO框架Calcite。

這是MaxCompute有關(guān)SQL優(yōu)化器原理的系列文章之一。我們會陸續(xù)推出SQL優(yōu)化器有關(guān)優(yōu)化規(guī)則和框架的其他文章。添加釘釘群“關(guān)系代數(shù)優(yōu)化技術(shù)”（群號11719083）可以獲取最新文章發(fā)布動態(tài)。

本文主要是對數(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)系表達(dá)式轉(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)系表達(dá)式進(jìn)行轉(zhuǎn)換，這里的轉(zhuǎn)換是說一個關(guān)系表達(dá)式經(jīng)過優(yōu)化規(guī)則后會變成另外一個關(guān)系表達(dá)式，同時原有表達(dá)式會被裁剪掉，經(jīng)過一系列轉(zhuǎn)換后生成最終的執(zhí)行計劃。

RBO中包含了一套有著嚴(yán)格順序的優(yōu)化規(guī)則，同樣一條SQL，無論讀取的表中數(shù)據(jù)是怎么樣的，最后生成的執(zhí)行計劃都是一樣的。同時，在RBO中SQL寫法的不同很有可能影響最終的執(zhí)行計劃，從而影響腳本性能。

• 基于代價的優(yōu)化器(Cost-Based Optimizer，CBO)

根據(jù)優(yōu)化規(guī)則對關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換，這里的轉(zhuǎn)換是說一個關(guān)系表達(dá)式經(jīng)過優(yōu)化規(guī)則后會生成另外一個關(guān)系表達(dá)式，同時原有表達(dá)式也會保留，經(jīng)過一系列轉(zhuǎn)換后會生成多個執(zhí)行計劃，然后CBO會根據(jù)統(tǒng)計信息和代價模型(Cost Model)計算每個執(zhí)行計劃的Cost，從中挑選Cost最小的執(zhí)行計劃。由上可知，CBO中有兩個依賴：統(tǒng)計信息和代價模型。統(tǒng)計信息的準(zhǔn)確與否、代價模型的合理與否都會影響CBO選擇最優(yōu)計劃。

從上述描述可知，CBO是優(yōu)于RBO的，原因是RBO是一種只認(rèn)規(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)系表達(dá)式進(jìn)行等價轉(zhuǎn)換，常見的優(yōu)化規(guī)則包含：

• 謂詞下推

• 列裁剪

• 常量折疊

• 其他

在這些優(yōu)化規(guī)則的基礎(chǔ)上，就能對關(guān)系表達(dá)式做相應(yīng)的等價轉(zhuǎn)換，從而生成執(zhí)行計劃。下面將介紹RBO和CBO兩種優(yōu)化器的執(zhí)行過程。

• RBO
  RBO的執(zhí)行過程比較簡單，主要包含兩個步驟：

1）Transformation
遍歷關(guān)系表達(dá)式，只要模式能夠滿足特定優(yōu)化規(guī)則就進(jìn)行轉(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ī)則進(jìn)行等價轉(zhuǎn)換，生成等價關(guān)系表達(dá)式，此時原有關(guān)系表達(dá)式會被保留。
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，從而進(jìn)一步裁剪掉一些執(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)系表達(dá)式，一個關(guān)系表達(dá)式在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))進(jìn)行轉(zhuǎn)換得到RelNode Tree。如Hive(某一種Data Processing System)使用的就是這種方法。

Query Optimizer 根據(jù)優(yōu)化規(guī)則(Pluggable Rules)對Operator Expressions進(jìn)行一系列的等價轉(zhuǎn)換，生成不同的執(zhí)行計劃，最后選擇代價最小的執(zhí)行計劃，其中代價計算時會用到Metadata Providers提供的統(tǒng)計信息。

事實上，Calcite提供了RBO和CBO兩種優(yōu)化方式，分別對應(yīng)HepPlanner和VolcanoPlanner。對此，本文也不進(jìn)行展開，后續(xù)有時間再詳細(xì)介紹Calcite的具體實現(xiàn)。

5.總結(jié)

本文是對查詢優(yōu)化器的一個綜述，介紹了查詢優(yōu)化器的分類、執(zhí)行過程，以及優(yōu)化器通用框架Calcite。

閱讀原文

本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。