## 課程前沿

### Query 優(yōu)化

第一個(gè)查詢優(yōu)化器的實(shí)現(xiàn)可以追溯到 1970 年代，也就是 IBM 的 System R

當(dāng)時(shí) Ted Codd 寫了第一篇關(guān)于關(guān)系模型的 paper，然后有倆波人，一波是 IBM ，另一波是 UC Berkeley 的，構(gòu)建出了史上最著名的關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)，UC Berkeley 那波人開發(fā)出來(lái)的叫 Ingres(Postgres 是 Ingres 的后續(xù)產(chǎn)品)，IBM 那群人開發(fā)出來(lái)的叫 System R

Ted Codd 在第一次提出關(guān)系模型時(shí)，并沒(méi)有提出相關(guān)的類似 SQL 的語(yǔ)言，SQL 是后來(lái)才出現(xiàn)的

UC Berkeley 那波人使用的是一種叫 Quel 的語(yǔ)言，看起來(lái)像 SQL，但語(yǔ)法不一樣

查詢優(yōu)化有 2 個(gè)方面可以進(jìn)行討論

1. 使用靜態(tài)規(guī)則/條件觸發(fā)(比如在 SQL 中定義了 `1 = 0` 這樣的玩意兒，那就可以通過(guò)一條規(guī)則將它去除掉，以及，在不用直接看數(shù)據(jù)庫(kù)表的情況下，可以通過(guò)數(shù)據(jù)庫(kù)的 system catalog 文件這種類似的規(guī)則就可以知道這個(gè)數(shù)據(jù)庫(kù)里面的 tuple 實(shí)際包含的頭信息)

2. Cost-based Search(枚舉 SQL 中所有可能的查詢方案，通過(guò)某種方式去掉那些多余、愚蠢、耗費(fèi)成本的方案，至于如何判斷這個(gè)成本，就是用某種成本模型來(lái)做預(yù)估)

一個(gè)查詢優(yōu)化的 Pipeline 長(zhǎng)這樣

1. SQL Rewriter 通過(guò)某種轉(zhuǎn)換規(guī)則來(lái)對(duì) SQL 進(jìn)行重寫(比如用一些額外的信息對(duì)數(shù)據(jù)庫(kù)里面某些表進(jìn)行標(biāo)記，表示可以在這個(gè)節(jié)點(diǎn)或者磁盤上找到這些表)，這個(gè)是可選的

2. 再通過(guò)一個(gè) SQL Parser，將 SQL 解析成 ast

3. 將 ast 傳入 Binder 中，Binder 負(fù)責(zé)將 SQL 查詢中引用的那些命名對(duì)象 轉(zhuǎn)換 成某種內(nèi)部標(biāo)識(shí)符，而它是通過(guò) System Catalog 來(lái)做到這一點(diǎn)的(比如 SQL 為 `SELECT * FROM foo`，如果不想讓查詢計(jì)劃中的剩下部分對(duì) foo 表 進(jìn)行處理，那就需要在 System Catalog 里面去查有沒(méi)有一個(gè)叫做 foo 的表，如果存在，那么就從 System Catalog 里面拿到 foo 表對(duì)應(yīng)的內(nèi)部標(biāo)識(shí)符，使得后面能夠找到這個(gè) foo 表；如果 foo 表不存在，System Catalog 就會(huì)直接表明 foo 表不存在，并拋出一個(gè)錯(cuò)誤)

4. Binder 要輸出 Logical Plan(Logical Plan 指的是，從一個(gè)高級(jí)層面來(lái)講，這個(gè)查詢想干的事情是什么，比如要查表數(shù)據(jù)，或者對(duì)表進(jìn)行 Join 操作，但并不會(huì)表明在實(shí)際中該怎么去執(zhí)行這個(gè)查詢，具體如何執(zhí)行這個(gè)查詢是 Physical Plan 所需要干的事情)，然后傳入一個(gè) Tree Rewriter (這個(gè)也是可選的)。然后為了對(duì) ast 進(jìn)行重寫，需要從 System Catalog 處拿到 Schema Info，表的一些屬性都在這個(gè)里面

5. Tree Rewriter 會(huì)輸出和 Binder 輸出的一樣的 Logical Plan，然后將 Logical Plan 傳入查詢優(yōu)化器。然后在這個(gè)查詢優(yōu)化器中，使用 Cost Model 來(lái)找出最佳查詢方案。查詢優(yōu)化器會(huì)使用 System Catalog 提供的 Schema Info 以及 Cost Model 來(lái)對(duì)這些方案進(jìn)行成本預(yù)估

6. 成本預(yù)估完成后，查詢優(yōu)化器就可以生成一個(gè) Physical Plan(Physical Plan 就是數(shù)據(jù)庫(kù)系統(tǒng)實(shí)際執(zhí)行查詢語(yǔ)句的方式)

### Logical Plan 和 Physical Plan

Logical Plan 是包含 SELECT/FILTER/PROJECTION/JOIN 等操作的，使用這些的時(shí)候不代表要使用哪種算法實(shí)現(xiàn)

Physical Plan 定義如何去執(zhí)行查詢方案，即在一個(gè)查詢計(jì)劃中要怎么使用這些不同的 operator

### Query 優(yōu)化是一個(gè) NP 問(wèn)題級(jí)別的問(wèn)題

對(duì)于查詢優(yōu)化來(lái)說(shuō)，機(jī)器學(xué)習(xí)確實(shí)是一種潛在的改善手段，但它并不是哪種能夠解決一切問(wèn)題的黑科技

## 課程目標(biāo)

## Relational Algebra Equivalences

可以對(duì)關(guān)系代數(shù)或者查詢計(jì)劃進(jìn)行轉(zhuǎn)換，讓它們變成相同效果的不同關(guān)系代數(shù)語(yǔ)句

只要查詢的結(jié)果是相同的，比如一組 tuple 的集合，雖然表達(dá)式不同，但只要結(jié)果一樣，這倆表達(dá)式就是等同的

> 注意這里 tuple 的順序可以不一致，只要內(nèi)容相同就行

可以使用關(guān)系代數(shù)中的傳遞性的特性，通過(guò)不同的方式改變表達(dá)式的標(biāo)準(zhǔn)邏輯，通過(guò)移動(dòng) operator 來(lái)生成更為高效的計(jì)劃

這種高級(jí)的技術(shù)，就叫做查詢重寫(Query Rewriting)

例子

上面的 SQL 語(yǔ)句可以寫出下面的這種關(guān)系代數(shù)語(yǔ)句

那么對(duì)于這條語(yǔ)句能做哪些簡(jiǎn)單的優(yōu)化呢?

可以將 filter 這一步放在 enrolled 里面做

將 filter 操作放在 Join 操作之前，可以減少很多 Join 的操作

操作更少 -> 成本更低 -> 執(zhí)行速度更快 -> 所用硬件資源也更少

可以在不查看數(shù)據(jù)的情況下，通過(guò)比較 filter 函數(shù)和 Join 函數(shù)的成本，就可以做到這種 push down

關(guān)系代數(shù)轉(zhuǎn)換和等同如上圖

通過(guò)選擇和比較這些不同的 operator，來(lái)對(duì)查詢計(jì)劃做相關(guān)的優(yōu)化

對(duì)于上圖中的例子來(lái)說(shuō)，可以將這個(gè)復(fù)雜的判斷條件進(jìn)行拆分，使其變得易于計(jì)算

因?yàn)檫@比起從 tuple 中拿到 Y 屬性的值，然后將它復(fù)制到某個(gè)寄存器或者變量中再進(jìn)行比較，這種做法成本更低

對(duì)于 Projection 操作來(lái)說(shuō)，也可以將它們盡早 push down

思路是，當(dāng)將數(shù)據(jù)從一個(gè) operator 傳遞到下一個(gè) operator 時(shí)，要最小化需要復(fù)制的數(shù)據(jù)

例子

在數(shù)據(jù)傳給 Join operator 之前，引入一個(gè) Projection 操作，這樣就可以去掉那些不需要的列信息，只傳遞需要的幾列數(shù)據(jù)給 Join operator

更多例子

首先移除掉愚蠢的和不必要的條件，比如 SQL 語(yǔ)句 `SELECT * FROM? A WHERE 1 = 0;`

這個(gè)語(yǔ)句意味著什么呢? 意味著，對(duì)于在 A 表中掃描到的每個(gè) tuple 來(lái)說(shuō)，會(huì)對(duì) `1 = 0` 這個(gè)條件進(jìn)行檢查，而因?yàn)檫@個(gè)條件的結(jié)果永遠(yuǎn)不可能為 true，所以沒(méi)有任何一個(gè) tuple 能匹配上這個(gè)條件。那么優(yōu)化就是，直接跳過(guò)掃描，返回一個(gè)空結(jié)果給用戶

對(duì)于 `SELECT * FROM A WHERE 1 = 1;` 那么就可以重寫為 `SELECT * FROM A;`

同樣的，也可以在 Join 操作中使用類似的優(yōu)化，比如上圖中的條件就是無(wú)用的，所以可以直接優(yōu)化成

那么還能繼續(xù)做哪些優(yōu)化呢?

可以將那些不必要的 Projection 操作給忽略掉

還有一個(gè)就是條件合并

可以把上圖優(yōu)化成

那么最后討論下如何進(jìn)行估算

對(duì)于一個(gè)查詢來(lái)說(shuō)，如果要對(duì) n 個(gè)表進(jìn)行 Join，那么可以使用不同的 Join 順序的數(shù)量就是 4^n

要枚舉的數(shù)量一大，這也是一個(gè)問(wèn)題，所以就需要減少枚舉出來(lái)的 Join 順序的數(shù)量

## Cost Estimation

成本模型能夠預(yù)估在數(shù)據(jù)庫(kù)系統(tǒng)化中執(zhí)行操作時(shí)所需要的成本

然后通過(guò)犧牲預(yù)測(cè)的正確性來(lái)獲得效率

> mongoDB 貌似沒(méi)有成本模型和查詢優(yōu)化器

## Statistics

預(yù)估執(zhí)行查詢的成本是通過(guò)在內(nèi)部維護(hù)表相關(guān)的信息來(lái)做的，這些信息大多都是索引、表以及 tuple 中的值相關(guān)的元數(shù)據(jù)

不同數(shù)據(jù)庫(kù)系統(tǒng)，獲取到這些元信息的語(yǔ)法也不同

然后將數(shù)據(jù)帶入公式來(lái)預(yù)估這些值