一、問題 & 目標(biāo)
數(shù)據(jù)庫/大數(shù)據(jù)引擎主要由三部分組成昔汉，分別是解析器、優(yōu)化器和執(zhí)行引擎拴清，如下圖所示：
其中靶病，優(yōu)化器在很大程度上決定了性能，其作用好比找到兩點(diǎn)之間的最短路徑口予。優(yōu)化器主要分為兩類：
RBO: Rule Based Optimizer
- 根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換娄周，同時(shí)原有的表達(dá)式會(huì)被裁剪掉，經(jīng)過一系列轉(zhuǎn)換后生成最終執(zhí)行計(jì)劃
- 包含一套有著嚴(yán)格順序的優(yōu)化規(guī)則沪停，同樣一條 SQL昆咽，無論讀取的表中的數(shù)據(jù)怎么樣，最終生成的執(zhí)行計(jì)劃都是一樣的牙甫。即數(shù)據(jù)不敏感
CBO: Cost Based Optimizer
- 根據(jù)優(yōu)化規(guī)則對(duì)關(guān)系表達(dá)式進(jìn)行轉(zhuǎn)換掷酗，這里的轉(zhuǎn)換是說一個(gè)關(guān)系表達(dá)式經(jīng)過優(yōu)化規(guī)則后會(huì)生成另一個(gè)關(guān)系表達(dá)式，同時(shí)原有表達(dá)式也會(huì)保留窟哺，經(jīng)過一系列轉(zhuǎn)換后會(huì)生成多個(gè)執(zhí)行計(jì)劃
- 然后根據(jù)數(shù)據(jù)統(tǒng)計(jì)信息和代價(jià)模型計(jì)算每個(gè)執(zhí)行計(jì)劃的 cost
- 從眾多執(zhí)行計(jì)劃中挑選出 cost 最小的執(zhí)行計(jì)劃
從上面的描述可知泻轰，CBO 是優(yōu)于 RBO 的，原因是 RBO 是一種只認(rèn)規(guī)則且轨，對(duì)數(shù)據(jù)不敏感的呆板的優(yōu)化器浮声，而在實(shí)際過程中虚婿，數(shù)據(jù)往往是有變化的，通過 RBO 生成的執(zhí)行計(jì)劃很有可能不是最優(yōu)的泳挥。
舉個(gè)例子：如下圖然痊，A、B屉符、C 三個(gè)表的 join 順序可以有多種剧浸，如下圖分別是 (A join B) join C 和(B join C) join A。
例如 A 有 1000 條數(shù)據(jù)矗钟，B 有 1000 條唆香，C 有 10 條數(shù)據(jù)，三個(gè)表之間存在一定的 join 謂詞使得：
A JOIN B 返回 10000 條數(shù)據(jù)吨艇，B JOIN C 返回 200 條數(shù)據(jù)躬它；那么前一個(gè)執(zhí)行計(jì)劃需要處理
1000 * 1000 + 1000 * 10 = 101w次循環(huán)，而后一個(gè)執(zhí)行計(jì)劃則需要處理1000 * 10 + 200 * 1000 = 21w次循環(huán)东涡，因此后者會(huì)更優(yōu)A JOIN B 返回 10 條數(shù)據(jù)冯吓，B JOIN C 返回 9000 條數(shù)據(jù)；那么前一個(gè)執(zhí)行計(jì)劃需要處理
1000 * 1000 + 10 * 10 = 100.01w次循環(huán)疮跑，而后一個(gè)執(zhí)行計(jì)劃則需要處理1000 * 10 + 9000 * 1000 = 901w次循環(huán)组贺，因此前者會(huì)更優(yōu)更進(jìn)一步，join 的策略還有 MapJoin祸挪、HashJoin、SortMergeJoin 等多種策略可選
那么此時(shí)就會(huì)面臨選擇贞间，需要從多個(gè)執(zhí)行計(jì)劃中選擇出最優(yōu)的。這個(gè)選擇的過程可以分解為三部分：
- Statistics：收集/維護(hù)統(tǒng)計(jì)信息
- Cost model：基于統(tǒng)計(jì)信息，對(duì)具體的執(zhí)行計(jì)劃進(jìn)行代價(jià)評(píng)估
- Plan enumeration：對(duì)可能得執(zhí)行計(jì)劃進(jìn)行搜索勺像，對(duì)其代價(jià)進(jìn)行比較滔驾，選擇最優(yōu)執(zhí)行計(jì)劃
二、業(yè)界思路
一個(gè)成熟的優(yōu)化器峻仇，可能有幾百條規(guī)則公黑，每條規(guī)則都會(huì)作用于執(zhí)行計(jì)劃，并產(chǎn)生另一個(gè)邏輯等價(jià)的執(zhí)行計(jì)劃摄咆，因此我們可以把優(yōu)化的問題理解為一個(gè)搜索的問題凡蚜。業(yè)界主要使用動(dòng)態(tài)規(guī)劃的思想，即可以把原問題分解成子問題來解決復(fù)雜問題吭从。
如上圖：
- 對(duì)于 Join 來說可以有多種實(shí)現(xiàn)朝蜘，例如 NestLoop 和 HashJoinJoin，即 Join 可以分解為兩個(gè)子問題
- 而對(duì)于 NestLoop 來說涩金，需要求解其子節(jié)點(diǎn) Scan A 和 Scan B谱醇，Scan 也有多種實(shí)現(xiàn)暇仲，例如 SeqScan 和 IndexScan
- 同時(shí)，這里遇到了重疊子問題副渴，在求解 HashJoin 的時(shí)候也需要計(jì)算 Scan A
就這樣奈附，將原問題分解為子問題求解，并配合統(tǒng)計(jì)信息及代價(jià)模型煮剧，就能找到那個(gè)最優(yōu)的執(zhí)行計(jì)劃了斥滤。
目前，也就對(duì)于搜索的實(shí)現(xiàn)主要有兩種：
自下而上：有哪些引擎用的這個(gè)轿秧？
自上而下：一般稱為 Volcano/Cascades
2.1中跌、自下而上
Calcite 的 CBO 使用了 Volcano/Cascades 思路，這部分我們配合 Calcite 的實(shí)現(xiàn)來講菇篡。
三漩符、Calcite 實(shí)現(xiàn) - VolcanoPlanner
VolcanoPlanner 在搜索過程中涉及幾個(gè)主要概念：
- RelNode：Calcite 的關(guān)系表達(dá)式，一個(gè)執(zhí)行計(jì)劃是 RelNode驱还，執(zhí)行計(jì)劃上的節(jié)點(diǎn)也是 RelNode
-
RelTrait：定義關(guān)系表達(dá)式的物理屬性嗜暴，共有三類：
-
Convention：Calcite 特有的概念，為了支持多（異構(gòu)）數(shù)據(jù)源议蟆。每種 Convention 表示一種物理實(shí)現(xiàn)闷沥，比如：-
Convention.NONE：不可實(shí)現(xiàn)的，必須轉(zhuǎn)換成其他東西才能實(shí)現(xiàn)咐容，cost 為正無窮大 -
EnumerableConvention：能返回 Enumerable 的 Convention 實(shí)現(xiàn)舆逃，一般默認(rèn)用這個(gè)。通過 codegen 的方式來生成 linq4j 代碼來訪問并在本地內(nèi)存操作數(shù)據(jù)- 注：LINQ4J 是 LINQ 的 java 實(shí)現(xiàn)戳粒。LINQ 提供一種統(tǒng)一的方式路狮，支持在 C# 編程語言內(nèi)直接創(chuàng)建被稱為“查詢表達(dá)式”的實(shí)體，在廣義的數(shù)據(jù)上獲取和操作數(shù)據(jù)蔚约。支持各種數(shù)據(jù)源：數(shù)據(jù)庫奄妨、XML文檔、內(nèi)存集合等苹祟。
-
SparkRel.CONVENTION：通過 Enumerable 去訪問/操作 Spark RDD 數(shù)據(jù)的實(shí)現(xiàn) - ......
-
-
RelCollation：描述 ordering 信息砸抛，包含 ordering 列（可以多個(gè)）和 ordering 順序 -
RelDistribution：用來定義數(shù)據(jù)在物理存儲(chǔ)上的分布方式（比如：single、hash树枫、range直焙、random 等）
-
-
RelSet：
- 一組邏輯上相等的 RelNode 的集合（這些 RelNode 都是經(jīng)過一個(gè)個(gè)規(guī)則轉(zhuǎn)換而來的）。所有的等價(jià)的 RelNode 都會(huì)記錄在
List<RelNode> rels中 -
rels語義等價(jià)砂轻，但可以有不同的 Trait箕般，比如
- 一組邏輯上相等的 RelNode 的集合（這些 RelNode 都是經(jīng)過一個(gè)個(gè)規(guī)則轉(zhuǎn)換而來的）。所有的等價(jià)的 RelNode 都會(huì)記錄在
-
RelSubset：
在一個(gè) RelSet 中相同的 RelTraitSet 的 RelNode 會(huì)在同一個(gè) RelSubset 內(nèi)
添加一個(gè) Rel 到 RelSubset 會(huì)天際到 rel 到對(duì)應(yīng)的 RelSet 中
一個(gè) RelSet 可能有多個(gè) trait（一組 RelNode 邏輯上等價(jià)，物理上可以不等價(jià)）舔清，比如在
[X]和[Y, Z]進(jìn)行排序丝里，那么對(duì)于這個(gè) RelSet 有兩個(gè) RelSubset
VolcanoRuleMatch：優(yōu)化規(guī)則與一組特定的目標(biāo)表達(dá)式的匹配（一組是因?yàn)榭梢云ヅ鋯蝹€(gè)或連續(xù)的表達(dá)式曲初，比如
Project/Flilter/Join）
3.1、VolcanoPlanner 初始化
當(dāng)通過 addRule 將這些 rules 都添加進(jìn)來的時(shí)候杯聚，會(huì)在 Multimap<Class<? extends RelNode>, RelOptRuleOperand> classOperands 中緩存每個(gè) Rule 可 apply 的 RelNode 類型臼婆，以加速后續(xù)的匹配
將物化視圖添加到 Planner
在 HepPlanner 和 VocanoPlanner 中都有一個(gè) List<RelOptMaterialization> materializations 成員，來持有可以用來識(shí)別的物化視圖幌绍。
RelOptMaterialization 三個(gè)最核心的成員：
List<String> qualifiedTableName：mv 全名RelNode tableRel：這個(gè) mv 對(duì)應(yīng)的LogicalTableScan颁褂，后續(xù)要改寫替換的時(shí)候用到RelNode queryRel：mv 對(duì)應(yīng)的 DDL 的 RelNode 表達(dá)
3.2、VolcanoPlanner#setRoot(...): 基于 originalRoot 構(gòu)建 RelSubset Graph
接下來我們以如下 RelNode 為例傀广，來介紹 VolcanoPlanner 是如何進(jìn)行 CBO 的颁独，VolcanoPlanner.originalRoot: RelNode 如下
LogicalAggregate(group=[{0}], C=[COUNT()])
LogicalProject(DEPTNO=[$2])
LogicalValues(tuples=[[{ 100, 'Fred', 10, null, null, 40, 25, true, false, 1996-08-03 }, { 110, 'Eric', 20, 'M', 'San Francisco', 3, 80, null, false, 2001-01-01 }, { 110, 'John', 40, 'M', 'Vancouver', 2, null, false, true, 2002-05-03 }, { 120, 'Wilma', 20, 'F', null, 1, 5, null, true, 2005-09-07 }, { 130, 'Alice', 40, 'F', 'Vancouver', 2, null, false, true, 2007-01-01 }]])
接下來執(zhí)行 VolcanoPlanner#setRoot(RelNode rel) 來為 rel 的每個(gè)節(jié)點(diǎn)創(chuàng)建對(duì)應(yīng)的 RelSet 和 RelSubset，偽代碼如下：
planner#registerImpl(RelNode rel, RelSet set)
rel#onRegister(VolcanoPlanner planner)
// input 為 rel.getInputs 的每個(gè)元素（循環(huán)）
// setRoot 的時(shí)候伪冰，因?yàn)楦鲗?rel 對(duì)應(yīng)的 subset 都不存在
// 結(jié)合下面的遞歸邏輯誓酒，會(huì)一直遞歸到葉子節(jié)點(diǎn)
planner#ensureRegistered(input)
if (如果 rel 對(duì)應(yīng)的 subset 不存在):
planner#register(input, null)
planner#registerImpl(input, set)
else:
// setRoot 的流程中不會(huì)走到這
if (rel 的等價(jià) set 為 null):
// 創(chuàng)建 rel 的等價(jià) RelSet
set = new RelSet(...)
// 構(gòu)建 rel, set, subset 的關(guān)聯(lián)關(guān)系
RelSubset subset = addRelToSet(rel, set)
// 對(duì)于 rel 的每個(gè) input，構(gòu)建 input 的 set 與 rel 的 set 的父子關(guān)系
((RelSubset) input).set.parents.add(rel)
// 找出所有該 rel 能 match 的 rules
// 構(gòu)建 VolcanoRuleMatch 添加到 RuleQueue 中
// 注意：這里可以看到是越底層的節(jié)點(diǎn)的 VolcanoRuleMatch 在 RuleQueue 的越前面
fireRules(rel)
總結(jié)來說贮聂，做了這么幾個(gè)事：
- 自上而下遞歸的為每個(gè) relation expression（后文簡稱 rel） 創(chuàng)建對(duì)應(yīng)的 RelSet 及 RelTraitSet 為 None.[]（NONE 表示 Convention 為空靠柑，即不做任何物理實(shí)現(xiàn)；[] 表示不額外做排序）的 RelSubset（觸發(fā)是自上而下吓懈，實(shí)際上是越底層的 rel 越早創(chuàng)建相應(yīng)的 set 和 subset）
- 構(gòu)建 rel歼冰、set、subset 之間的關(guān)聯(lián)關(guān)系耻警；構(gòu)建 input 的 set（RelSet）和 parent 的 set 的父子關(guān)系（只有 Convention 相同能作為父子隔嫡，以及非 None 的 Convention 可作為 None 的 parent）
-
自下而上的為每個(gè) rel 篩選出 match 的 rules，封裝成 VolcanoRuleMatch 添加到 RuleQueue 中（注意甘穿，這里只是將 Rules 添加到 Queue 中腮恩，并沒有執(zhí)行），在 Queue 中越底層的 rel 的 match 的 VolcanoRuleMatch 在越前面扒磁，如：
- setRoot 得到的 RelSubset 的樹存放在
RelSubset VolcanoPlanner.root成員中
3.3庆揪、VolcanoPlanner#findBestExp() Part1: 應(yīng)用優(yōu)化規(guī)則構(gòu)建搜索空間
代碼主要在
VolcanoPlanner#findBestExp的 ruleDriver.drive()
其中 ruleDriver 有兩種實(shí)現(xiàn)：
-
IterativeRuleDriver：對(duì)應(yīng)IterativeRuleQueue式曲，該算法不斷的從 RuleQueue 中取出優(yōu)化規(guī)則并執(zhí)行妨托。退出條件有兩種：- Queue 中沒有規(guī)則需要執(zhí)行了
- 在規(guī)則執(zhí)行時(shí)拋出
VolcanoTimeoutException異常，當(dāng) VolcanoPlanner 的cancelFlag設(shè)置為 true 時(shí)會(huì)拋出這個(gè)異常吝羞，所以在使用如果覺得優(yōu)化時(shí)間太長兰伤，超過一定時(shí)間可設(shè)置cancleFlag為 true 強(qiáng)制優(yōu)化結(jié)束
TopDownRuleDriver：對(duì)應(yīng)TopDownRuleQueue，是 Cascades 論文的實(shí)現(xiàn)钧排，也參考了 Columbia 優(yōu)化器敦腔，其內(nèi)部并非是一個(gè)簡單的遞歸函數(shù)，而是用棧tasks模擬了整個(gè) top-down 的過程：不斷從棧頂取出 Task 執(zhí)行恨溜，Task 執(zhí)行中又會(huì)產(chǎn)生新的 Task符衔，重復(fù)這一過程直到棧為空找前。實(shí)現(xiàn)了遞歸的效果，但是可以不用每次“遞歸到底”判族，來實(shí)現(xiàn)剪枝的效果
分別詳見：
[VolcanoPlanner 之 IterativeRuleDriver]
[VolcanoPlanner 之 TopDownRuleDriver]
3.4躺盛、VolcanoPlanner#findBestExp() Part2: 找出 cost 最小的執(zhí)行計(jì)劃
代碼主要在 VolcanoPlanner#findBestExp 的 RelNode cheapest = root.buildCheapestPlan(this)
不管使用 IterativeRuleDrvier 還是 TopDownRuleDriver，buildCheapestPlan 的邏輯都是一樣的
核心邏輯主要封裝在 CheapestPlanReplacer 中形帮，該類用于：以遞歸的方式槽惫，遍歷上一步生成的 RelSet Tree，用 cheapest 的 expression 替換每一個(gè) RelSet辩撑。
findBestExp 中通過調(diào)用 RelNode cheapest = replacer.visit(root, -1, null)來獲取最終的 best plan界斜，其邏輯如下：
