## 課程目標

1. 如何通過 Cost Model 來對查詢計劃進行成本預估

2. 如何根據(jù) Logical Plan 枚舉 執(zhí)行 Plan

3. 內(nèi)嵌子查詢，通過規(guī)則對它們進行重寫，并使其變得更為高效

## Cost Estimation

這種成本可能是由一堆不同的基礎(chǔ)硬件性能的參數(shù)所組成的

但無論如何，都要將要訪問的 tuple 數(shù)量作為成本的參考，也就是說，要確定數(shù)據(jù)從一個 operator 傳遞到下一個 operator 時，這個傳遞的數(shù)據(jù)量大小是多少

## Statistics?

在 DBMS 中，用來預估成本時所使用的基礎(chǔ)組件就是 DBMS 內(nèi)部的 Statistics Catalog

所有主流的數(shù)據(jù)庫系統(tǒng)都會通過某種命令來強制收集新的統(tǒng)計信息

某些系統(tǒng)會設(shè)置定時任務(wù)，定期更新這些統(tǒng)計信息

某些系統(tǒng)在執(zhí)行查詢時，順帶更新這些統(tǒng)計信息

某些系統(tǒng)會通過觸發(fā)器來更新這些統(tǒng)計信息，比如設(shè)置一個觸發(fā)限制，如果表中有 10% 或者 20% 的數(shù)據(jù)發(fā)生了改變，就執(zhí)行 RUNSTATS 命令來做更新

需要注意的是，更新統(tǒng)計信息的成本會很高，因為它需要對整個表進行掃描

有上面的信息，就要想辦法計算或者維護這個信息，以此來獲得每個屬性中不同的值的數(shù)量

通過這個基本信息，可以獲得一個新的數(shù)據(jù)信息，也就是選擇基數(shù)(Selection Cardinality)，定義一個 SC 函數(shù)，然后通過 tuple 數(shù)量除屬性 A 下面的去重后的值的數(shù)量來計算出這個選擇基數(shù)

當然，這里有一個非常重要的假設(shè)，那就是 **數(shù)據(jù)分布均勻**

那么通過這個選擇基數(shù)，還能做哪些事情呢?

如果能弄清楚每個 operator 傳給下一個 operator 的 tuple 的數(shù)量，那么就可以知道這個傳遞實際的工作量有多少，要使用的磁盤空間有多少，以及內(nèi)存量有多少

即通過選擇基數(shù)來計算 子 operator 要提供的數(shù)據(jù)量有多少

例子，在一個 unique key 上使用等價判斷(equality predicate)

上圖中，要查找 id = 123 的 tuple，這是很容易的，因為它的基數(shù)是 1，不管表中有多少個 tuple，總有一個 tuple 符合條件。因為這里用的是主鍵(Primary Key)，是唯一的

難點在于，假如判斷條件變得復雜了，那么這個就不太好做，因為現(xiàn)在就需要將不同判斷條件對應(yīng)的 選擇基數(shù) 以一種特別的方式結(jié)合起來

那么對于復雜的 Predicates 應(yīng)該怎么算呢

就是上圖這些。簡單來講，選擇率就是一個函數(shù)。對于針對該表的一個給定條件來說，這個函數(shù)會計算出該表中有多少符合該條件的 tuple

而這個計算的方式，也取決于實際執(zhí)行的操作類型

例子

在上圖中的例子中 age = 2 的選擇率是這么計算的

通過查看上圖中出現(xiàn)的直方圖，就能準確的知道它(age =? 2)的出現(xiàn)次數(shù)，而其結(jié)果就是 1/5(假設(shè)數(shù)據(jù)分布均勻)

如果來計算 Range Predicate 的選擇率呢?

結(jié)果就是 1/2

但實際上這個結(jié)果是有問題的，正確答案是 3/5，但根據(jù)公式得到的是 1/2

所以公式計算出的結(jié)果也不一定正確，也正是因為如此，當對包含一堆不同條件和 operator 的復雜查詢進行這樣的預估的時候，就會出現(xiàn)很多問題

最后的例子就是 negation

而 age = 2 的選擇基數(shù)是 1

所以 age != 2 的范圍就是 [0, 1] 和 [3, 4]

所以正確答案就是 4/5

在這里，預估的條件選擇率和概率是一回事(Selectivity ~= Probility)

## 一些更復雜的統(tǒng)計

假設(shè)現(xiàn)在要得到一個交集，那么這個時候，就應(yīng)該去計算第一個條件(age = 2)的選擇率，然后再去計算第二個條件(name LIKE 'A%') 的選擇率，然后將這倆概率進行相乘(因為假設(shè)對這倆條件的預估都是相互獨立的)

于是這樣就能得到它們的交集

假設(shè)現(xiàn)在要得到一個并集，并集的計算公式如上，并且假設(shè)對這倆條件的選擇率都是獨立的

于是這樣就能得到它們的并集

## Selection Cardinality

除了之前提到過的 Uniform Data 以及 Indipendent Predicates 假設(shè)外，還有一種假設(shè)叫做 Inclusion Principle

在計算條件選擇率時有很多假設(shè)前題，而這會使得計算變得簡單，但這容易得出錯誤的預測結(jié)果

Uniform Data 假設(shè)的時所有數(shù)據(jù)的出現(xiàn)概率都是相同的

> Heavy-Hitter: 如果有一些 Skewed(傾斜) Data，它出現(xiàn)的頻率非常高，此時可以通過維護一個單獨的 hash table 或者直方圖來跟蹤這些 data(但是只可能會去保存每列中前 10 或者前 20 個不同的值)，對于其他數(shù)據(jù)來說，可以假設(shè)它們出現(xiàn)的頻率是統(tǒng)一的，可以根據(jù)這個來預測 Cardinality (基數(shù))。這是用來解決這種均勻數(shù)據(jù)問題的標準手段

Indipendent Predicates 假設(shè)倆預測的條件是獨立的，如果要取交集，就將其計算出的概率進行相乘來生成組合基數(shù)

Inclusion Principle 是這樣一個假設(shè)，比如要對 2 個表進行 Join 操作，然后對于 Inner Table 中的每個 tuple 來說，在 Outer Table 中都會有一個與之對應(yīng)的 tuple

## Correlated Attributes

但是 Uniform Data 以及 Indipendent Predicates 假設(shè)往往回導致估算的不準確

比如在下面的例子中，對于選擇率的計算

上圖的公式和最終實際的結(jié)果差了一個數(shù)量級(因為從現(xiàn)實角度來講，Makes 和 Models 這倆條件是相關(guān)的)

那么解決辦法是什么呢

可以聲明 makes 和 models 這些列是相關(guān)的，那么數(shù)據(jù)庫系統(tǒng)就可以將它們當作特殊案例來進行處理，以此規(guī)避掉這些問題

## Cost Estimations

數(shù)據(jù)庫系統(tǒng)會在內(nèi)部維護這些直方圖來跟蹤這些信息

縱坐標是值的出現(xiàn)頻率，橫坐標是屬性的值

但是真實數(shù)據(jù)不長這樣

真實數(shù)據(jù)更具備傾向性

那么這樣的數(shù)據(jù)怎么追蹤呢

就是將這些數(shù)據(jù)劃分到不同的 bucket 中，一個 bucket 只保存一個值，不會為一個 bucket 中的每個元素都去保存一個值

比如

這個就被稱之為等寬直方圖(Equi-Width Histogram)，下面的值是這個 bucket 中每個值出現(xiàn)的次數(shù)的總和

那么新的直方圖中顯示的就是這些聚合后的值

當然這種方式雖然節(jié)省空間，但是問題也存在，就是不知道這些值中哪個值得出現(xiàn)次數(shù)是比較高的

那么怎么解決這個問題呢? 用分位數(shù)(Quantiles)

## Histograms with Quantiles

主要是通過調(diào)整 bucket 的寬度，使每個 bucket 的 count 總和都大致相等

就像上圖中表示的這樣

那么結(jié)果就是

## Sampling?

本質(zhì)上就是，通過維護一個樣本表，然后根據(jù)該樣本來衍生出統(tǒng)計信息

直方圖就像是數(shù)據(jù)庫中的表的數(shù)據(jù)的一種低解析度副本，它是對其他內(nèi)容的一種近似縮略表達

那么在不通過用直方圖來衍生統(tǒng)計信息的情況下，該如何拿到基于該表本身的一個更小的副本呢?

先從表中進行取樣，拿到一個 tuple，然后將它們復制到一個樣本表(table sample)中

這個時候計算 age > 50 的選擇率

計算出來的結(jié)果就是 1/3，那么此時可以假設(shè)，在完整的表中，不同值的選擇率會與之相符

在查詢時，就可以對這個表進行維護，或者當表中有很大一部分數(shù)據(jù)發(fā)生改變，比如批量加載表中數(shù)據(jù)，或者批量刪除表中數(shù)據(jù)，此時就可以觸發(fā)更新這些數(shù)據(jù)了

## Observation

通過粗略的估計這些條件的條件的選擇率，我們還能做到什么呢?

當然是可以通過成本模型或者 Cost-based search 來進行查詢優(yōu)化

## Single-Relation Query Planning

對于 single-relation query 這種情況而言，最難的就是選擇對應(yīng)的 access method

而另一件事情就是預估條件時的順序

如何去選擇最優(yōu)的 access method 呢? 在查詢優(yōu)化器中使用一些簡單的啟發(fā)式規(guī)則就好了。這對于那些 OLTP 類的查詢來說是最簡單的，因為這種查詢本身訪問的數(shù)據(jù)量并不多

## OLTP Query Planning

對于 OLTP 查詢來說，首先要做的就是試著鑒定這個查詢是否是 Search Argumentable 的。即在執(zhí)行查詢時，可以使用一個索引來幫助查詢，而對于這個查詢來說，使用這個索引是一個最佳選擇

例子

SQL 語句如上圖所示

這里有一個啟發(fā)式規(guī)則: `id INT PRIMARY KEY`，表示 id 是一個主鍵

如果這里有一個索引，用它就完事了(可以使用這個索引來做索引掃描)

## Multi-Relation Query Planning

隨著要 Join 的表的數(shù)量增加，Join 操作時產(chǎn)生的備選方案的數(shù)量也會增加。所以這里就需要對這些方案做一個剪枝處理

System R 一個基礎(chǔ)假設(shè)是，只考慮左連接樹的情況(left-deep join tree)

那么什么是 left-deep join tree?

它實際上長這樣

join 操作會沿著這棵樹的左邊進行(左一就是 left-deep join tree)

左二像是大雜燴(有些在左邊 Join，有些在右邊 Join)

左三為 bushy tree

IBM 的 System R 不會考慮左二和左三

這樣做有什么好處呢?

使用 left-deep join tree，就像一個 pipeline，在過程中不需要延后生成某個 Join operator 的輸出結(jié)果，因為它始終是下一個 Join operator 的輸入，就不用中間產(chǎn)生一些臨時數(shù)據(jù)寫到磁盤中，那么就可以最小化寫入磁盤的數(shù)據(jù)量

即

那么如何枚舉查詢計劃呢

首先要做的就是，從邏輯層面來枚舉所有可能的不同的執(zhí)行 Join 操作的順序

但是有可能這個順序會非常之多

在 1970 年代，IBM 那幫人就提出了一種叫動態(tài)編程的技術(shù)，即通過將一個大問題分解為一些較小的小問題，然后讓問題變得更容易解決

例子

首先要做的就是計算出，在使用不同的 Join 算法的情況下，第一步的成本是多少(可以使用 Hash Join 或者 SortMerge Join)

然后通過之前講的那些公式來計算出這些 Join 操作的執(zhí)行成本

成本比較之后，選擇執(zhí)行成本最低的那個 Join 算法

????下一步繼續(xù) Join 之前，執(zhí)行類似的操作

同樣的，只保留執(zhí)行成本最低的那個 Join 算法

那么最終這個查詢計劃要使用的執(zhí)行方案，就是下面這個

以上就是 動態(tài)編程 基本思想的體現(xiàn)

## Candidate Plan Example

在對 R S T 這 3 個表進行 Join 時，列出可能會使用的 Join 順序

過濾掉一些不需要的，然后查看每個查詢計劃樹

然后對于某個查詢計劃樹，列出所有可以使用的不同的 Join 算法

> NLJ: Nest-Loop Join?

HJ: Hash Join

然后再選擇一個 Join 算法

然后列出所有可以使用的 access method

## Postgres Optimizer

pg 除了有之前提到的那個動態(tài)編程算法之外，它還有一個自己的遺傳查詢優(yōu)化器，它這個遺傳查詢優(yōu)化能應(yīng)對更大的搜索范圍

例子

首先列出查詢計劃相關(guān)的一堆不同的隨機配置(Join 順序、索引/循序掃描、要使用的 Join 算法等)

然后計算出這些配置的執(zhí)行成本

選出一個最低成本的，然后將最高成本的丟棄，保留中間的方案，并且基于除了最高成本的那些方案進行隨機處理，以此生成新的查詢計劃

接下來做一些類似的操作

然后生成下一個方案

這有點像模擬退火遺傳算法?

## Nested Sub-Queries

對每一個在外部查詢中看到的 tuple 放到內(nèi)部查詢?nèi)プ鲈u估，MySQL 以前是這樣做的

如何做嵌套的子查詢?

1. 通過重寫查詢來去掉彼此關(guān)聯(lián)性，做扁平化處理

2. 將內(nèi)部查詢提取出來，作為一個單獨的查詢來執(zhí)行，然后將這個查詢的結(jié)果傳入外層查詢

例子

### Rewrite

在這個例子中，外部查詢 S 和內(nèi)部查詢 R 是相關(guān)聯(lián)的，所以需要將他重寫為 Join

### Decompose

當在畫橘色圈的位置進行查找時，對于 Outer Table(sailor 表) 上的每個 tuple 來說，就需要不斷反復執(zhí)行這段邏輯，但是這個很操蛋

所以這個時候需要將它提取出來，這樣就無需每次都執(zhí)行一遍了

那么怎么做呢? 就是把這個內(nèi)嵌的語句拿出來，保存為某個變量

然后用這個變量去做一個對應(yīng)的替換

## 結(jié)論