Cascades查詢優(yōu)化器基本原理分析

數(shù)據(jù)庫中查詢優(yōu)化器是數(shù)據(jù)庫的核心組件，其決定著 SQL 查詢的性能。Cascades 優(yōu)化器是 Goetz 在 volcano optimizer generator 的基礎(chǔ)上優(yōu)化之后誕生的一個搜索框架。 本期技術(shù)貼將帶大家了解 Cascades 查詢優(yōu)化器。首先介紹 SQL 查詢優(yōu)化器，接著分析查詢優(yōu)化基本原理，最后對 Cascades 查詢優(yōu)化器進行重點介紹。

一、SQL 查詢優(yōu)化器

用戶與數(shù)據(jù)庫交互時只需要輸入聲明式 SQL 語句，數(shù)據(jù)庫優(yōu)化器則負責將用戶輸入的 SQL 語句進行各種規(guī)則優(yōu)化，生成最優(yōu)的執(zhí)行計劃，并交由執(zhí)行器執(zhí)行。優(yōu)化器對于 SQL 查詢具有十分重要的意義。 如圖 1 所示，SQL 語句經(jīng)過語法和詞法解析生成抽象語法樹(AST)，經(jīng)過基于規(guī)則的查詢優(yōu)化（Rule-Based Optimizer）和基于代價的查詢優(yōu)化（Cost-Based Optimizer）生成可執(zhí)行計劃。

圖 1

基于規(guī)則的優(yōu)化算法:基于規(guī)則的優(yōu)化方法的要點在于結(jié)構(gòu)匹配和替換。應(yīng)用規(guī)則的算法一般需要先在關(guān)系代數(shù)結(jié)構(gòu)上匹配一部分局部的結(jié)構(gòu)，再根據(jù)結(jié)構(gòu)的特點進行變換乃至替換操作。

基于成本的優(yōu)化算法:現(xiàn)階段主流的方法都是基于成本（Cost）估算的方法。給定某一關(guān)系代數(shù)代表的執(zhí)行方案，對這一方案的執(zhí)行成本進行估算，最終選擇估算成本最低的方案。盡管被稱為基于成本的方法，這類算法仍然往往要結(jié)合規(guī)則進行方案的探索。基于成本的方法其實是通過不斷的應(yīng)用規(guī)則進行變換得到新的執(zhí)行方案，然后對比方案的成本優(yōu)劣進行最終選擇。

二、查詢優(yōu)化的基本原理

優(yōu)化器一般由三個組件組成：統(tǒng)計信息收集、開銷模型、計劃列舉。 如圖 2 所示，開銷模型使用收集到的統(tǒng)計信息以及構(gòu)造的不同開銷公式，估計某個特定查詢計劃的成本，幫助優(yōu)化器從眾多備選方案中找到開銷最低的計劃。

圖 2 SQL 語句查詢優(yōu)化基于關(guān)系代數(shù)這一模型：

SQL 查詢可以轉(zhuǎn)化為關(guān)系代數(shù)；

關(guān)系代數(shù)可以進行局部的等價變換，變換前后返回的結(jié)果不變但是執(zhí)行成本不同；

通過尋找執(zhí)行成本最低的關(guān)系代數(shù)表示，我們就可以將一個 SQL 查詢優(yōu)化成更為高效的方案。

尋找執(zhí)行成本最低的關(guān)系代數(shù)表示，可以分為基于動態(tài)規(guī)劃的自底向上和基于 Cascades/Volcano 的自頂向下兩個流派。

自底向上搜索：從葉子節(jié)點開始計算最低成本，并利用已經(jīng)計算好的子樹成本計算出母樹的成本，就可以得到最優(yōu)方案；

自頂向下搜索：先從關(guān)系算子樹的頂層開始，以深度優(yōu)先的方式來向下遍歷，遍歷過程中進行剪枝。

自底向上的優(yōu)化器從零開始構(gòu)建最優(yōu)計劃，這類方法通常采用動態(tài)規(guī)劃策略進行優(yōu)化，采用這類方法的優(yōu)化器包括IBMSystem R。自頂向下的優(yōu)化策略的優(yōu)化器包括基于 Volcano 和 Cascades 框架的優(yōu)化器。

三、Cascades 查詢優(yōu)化器

Cascades 查詢優(yōu)化器采用自頂向下的搜索策略，并在搜索過程中利用 Memo 結(jié)構(gòu)保存搜索的狀態(tài)。

Cascades 關(guān)鍵組件構(gòu)成：

Expression：Expression 表示一個邏輯算子或物理算子。如 Scan、Join 算子；

Group：表示等價 Expression 的集合，即同一個 Group 中的 Expression 在邏輯上等價。Expression 的每個子節(jié)點都是以一個 Group 表示的。一個邏輯算子可能對應(yīng)多個物理算子，例如一個邏輯算子 Join(a,b)，它對應(yīng)的物理算子包括{HJ(a, b), HJ(b, a), MJ(a, b), MJ(b, a), NLJ(a, b), NLJ(b, a)}。我們將這些邏輯上等價的物理算子稱為一個 Group（組）。注：HJ 表示 HashJoin 算子，MJ 表示 MergeJoin 算子，NLJ 表示 NestLoopJoin 算子；

Memo：由于 Cascades 框架采用自頂向下的方式進行枚舉，因此，枚舉過程中可能產(chǎn)生大量的重復(fù)計劃。為了防止出現(xiàn)重復(fù)枚舉，Cascades 框架采用 Memo 數(shù)據(jù)結(jié)構(gòu)。Memo 采用一個類似樹狀（實際是一個圖狀）的數(shù)據(jù)結(jié)構(gòu)，它的每個節(jié)點對應(yīng)一個組，每個組的成員通過鏈表組織起來；

Transformation Rule：是作用于 Expression 和 Group 上的等價變化規(guī)則，用來擴大優(yōu)化器搜索空間。

Cascades 首先將整個 Operator Tree 按節(jié)點拷貝到一個 Memo 的數(shù)據(jù)結(jié)構(gòu)中，Memo 由一系列的 Group 構(gòu)成，每個算子放在一個 Group，對于有子節(jié)點的算子來說，將原本對算子的直接引用，變成對 Group 的引用。

圖 3 如圖 3 所示，生成該語法樹的 Memo 初始結(jié)構(gòu)。Memo 結(jié)構(gòu)中一個圓角框代表一個算子，圓角框右下角是對其 Children’s Groups 的引用，左下角是唯一標識符。生成初始的 Memo 結(jié)構(gòu)后，可以采用 transform rule 進行邏輯等價轉(zhuǎn)換，規(guī)則如下：

對于一個邏輯算子，其所有基于關(guān)系代數(shù)的等價表達式保存在同一個 Group 內(nèi)，例如 join(A,B) -> join(B,A)；

在一個 Group 內(nèi)，對于一個邏輯算子，會生成一個或多個物理算子，例如 join -> hash join,merge join，NestLoop join；

一個 Group 內(nèi)，一個算子，其輸入（也可以理解為subplan）可以來自多個 Group 的表達式。

在圖 4 中，描述了一個部分擴展的 Memo結(jié)構(gòu)，與圖 1 中的初始 Memo 相比，在同一個 Group 內(nèi)，增加了等價的邏輯算子，以及對應(yīng)的物理算子。

圖 4 在探索的過程中，優(yōu)化器就會通過開銷模型 Coster 借助統(tǒng)計信息來計算子步驟的開銷，遍歷完每個 Memo Group之后，歸總得到每個完整計劃的總開銷，最終選擇 Memo 中開銷最低的計劃。

圖5 圖 5 中有三個 Group，分別對應(yīng)三個邏輯算子：Join(a, b), GET(a) 和 GET(b)。Group 1（Group 2）中包含了所有對應(yīng) GET(a) （GET(b)）的物理算子，我們可以估算每個物理算子的代價，選取其中最優(yōu)的算子保留下來。 為了防止枚舉過程出現(xiàn)重復(fù)枚舉某個表達式，Memo 結(jié)構(gòu)體中還包含一個哈希表（exprHT），它以表達式為哈希表的鍵，用來快速查找某個表達式是否已經(jīng)存在于 Memo 結(jié)構(gòu)體中。

Cascades 采用自頂向下的方式來進行優(yōu)化，以計劃樹的根節(jié)點為輸入，遞歸地優(yōu)化每個節(jié)點或表達式組。如圖所示，整個優(yōu)化過程從 Group 0 開始，實際上要先遞歸地完成兩個子節(jié)點（Group 1 和 Group 2）的優(yōu)化。 因此，實際的優(yōu)化完成次序是 Group 1 -> Group2 -> Group 0。在優(yōu)化每個 Group 時，依次優(yōu)化每個組員；在優(yōu)化每個組員時，依次遞歸地優(yōu)化每個子節(jié)點。依次估算當前組里每個表達式 e 的代價 cost(e)，選擇最低得代價結(jié)果保存在 bestHT 中。優(yōu)化結(jié)束時，查詢 Join(a,b)對應(yīng)的 Memo 結(jié)構(gòu)體，獲取最低的執(zhí)行計劃。

審核編輯：黃飛