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

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

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

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

圖 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

審核編輯：黃飛