## 課程目標(biāo)

1. 如何處理查詢計劃(Query Plan)，即如何組織這個執(zhí)行流程，讓這些 operator 之間的數(shù)據(jù)流以某種方式傳遞，用來快速的產(chǎn)生結(jié)果

2. 訪問方式：用索引還是循序?

3. 對表達(dá)式的評估

## Processing Model

這個 Processing Model 指的是，用某種方式，去執(zhí)行一個查詢計劃

是從上到下，還是從下到上?在每個 operator 之間應(yīng)該傳什么

- Iterator Model(很多數(shù)據(jù)庫系統(tǒng)都在用)

- Materialization Model(Iterator Model 的特定版本，只用在內(nèi)存型數(shù)據(jù)庫系統(tǒng)中)

- Vectorized/Batch Model(基于 Iterator Model，主要用于分析型 workload 中)

### Iterator Model

> 1980 末到 1990 初期有一個非常有影響力的系統(tǒng)叫 Volcano，這個系統(tǒng)是由寫了 B+ Tree 那本書的作者發(fā)明的，這個人也實現(xiàn)了 Volcano 查詢優(yōu)化

對于 Iterator Model 而言，它的工作方式是，對于所有的 operator (Join、Sorting)來說，它們都要去實現(xiàn)一個 Next 函數(shù)

在查詢計劃樹中，父節(jié)點會調(diào)用其子節(jié)點上定義的 Next 函數(shù)，子節(jié)點會返回這個 Next 函數(shù)的結(jié)果(下一個父節(jié)點需要處理的 tuple)，總之，這個是層層的遞歸調(diào)用的過程，對于查詢計劃樹來講，父節(jié)點的 Next 會層層調(diào)用子節(jié)點的 Next，直到達(dá)到這個樹的葉子節(jié)點為止。然后將處理好的結(jié)果(tuple) 層層向上發(fā)送，做逐個處理

這個模型的好處在于，對于一個 tuple 能夠盡可能的被多次使用，在一個 operator 處理完之后能返回傳入下一個 operator 做繼續(xù)處理(能夠減少磁盤 I/O，因為 tuple 是在 page 中，而 page 是在內(nèi)存中)

> 在一個查詢計劃中，對一個給定的 tuple 進(jìn)行一系列加工處理的過程，叫 Pipeline

那么它是如何工作的?

上圖展示的是不同 operator 對應(yīng)用的不同 Next 函數(shù)，本質(zhì)上也都是 for 循環(huán)

步驟 2、3 都是對左邊節(jié)點進(jìn)行處理

步驟 2、4、5 都是對右邊節(jié)點進(jìn)行處理(左邊節(jié)點處理完之后)

當(dāng)進(jìn)行 Join 操作時，如果構(gòu)建的 hash table 中有任何一條 tuple 能匹配上 Join 的條件，就將 Join 之后的結(jié)果發(fā)送給父節(jié)點，即步驟 1

使用 Iterator Model 的數(shù)據(jù)庫有那些呢? 見下圖

但是有些 operator 不允許一直進(jìn)行這種 Pipeline 處理(比如 Joins、SubQueries, ORDER BY 等)

比如在步驟 2 中

```

for t1 in left.Next():

? ? buildHashTable();

```

這個 for 循環(huán)沒執(zhí)行完，hash table 也沒構(gòu)建完的情況下，只能不停的執(zhí)行步驟 3 去拿數(shù)據(jù)，而不是把結(jié)果從步驟 2 向上傳遞到步驟 1，也就是這里的 Pipeline 操作沒有被執(zhí)行

使用 Iterator Model ，對于輸出控制比如 limit ，就很容易實現(xiàn)它

### Materialization Model

基本思路是，每次調(diào)用 Next 函數(shù)時，不讓它只返回一個 tuple，而是返回所有的 tuple。這樣就可以不用一直去調(diào)用 Next 函數(shù)來逐個獲取這些 tuple 了

這個 Model 的輸出結(jié)果可以是一個 materialized row 或者是單個列(這個列上保存了所有的 tuple 值)

例子圖如下(沒有 Next 函數(shù)了，或者說它被封裝在了 out.output 函數(shù)中，返回的都是一個 output buffer，它里面包含了所有的 tuple)

步驟 2、3 都是對左邊節(jié)點進(jìn)行處理

步驟 2、4、5 都是對右邊節(jié)點進(jìn)行處理(左邊節(jié)點處理完之后)

當(dāng)進(jìn)行 Join 操作時，如果構(gòu)建的 hash table 中有任何一條 tuple 能匹配上 Join 的條件，就將 Join 之后的結(jié)果發(fā)送給父節(jié)點，即步驟 1

那么又有哪些數(shù)據(jù)庫使用了這個

使用 Materialization Model 的數(shù)據(jù)庫有那些呢? 見下圖

Materialization Model 適用于 OLTP 場景，因為在這個場景中，都是一次獲取少量的記錄

記錄少 -> (在內(nèi)存中)調(diào)用 Next 函數(shù)次數(shù)少 -> CPU 跳到硬盤上寫數(shù)據(jù)次數(shù)少(CPU 有 latch ，保證事務(wù)) -> 函數(shù)阻塞時間短 -> 減少 CPU 阻塞

> 數(shù)據(jù)量一多，如果有跨事務(wù)的數(shù)據(jù)很容易出現(xiàn)死鎖問題

### Vectorization Model?

那么每次調(diào)用 Next 函數(shù)時，如果傳遞的是一些 tuple 而不是單個 tuple，是不是會更高效?對于 Vectorization Model 來講，是的

> 在現(xiàn)代 CPU 中有一些指令允許一次對一堆數(shù)據(jù)進(jìn)行多個操作，比如 simd

一個對 Vectorization Model 優(yōu)化的處理是，用一個 output buffer 對要發(fā)送的數(shù)據(jù)量做一個檢查，如果 output buffer 的容量足夠大，那么就可以向上返回一堆 tuple(其實就是先將tuple 放到這個 output buffer 中，等這個 buffer

滿了再向上傳遞)

如下圖所示

這個優(yōu)化使得 Vectorization Model 支持 OLAP 了，因為它減少了每個 operator 調(diào)用 Next 的次數(shù)

而上圖中也有很多數(shù)據(jù)庫支持

顯而易見，Vectorization Model 就是 Iterator Model 的一種增強版本

## Plan Processing Direction

上述所使用的 3 種 Model 都是 top-down 方案，即從根節(jié)點開始，調(diào)用 Next 方法來得到輸出，整體上它會自上而下的調(diào)用 Next，然后將數(shù)據(jù)向上傳遞到根節(jié)點處

當(dāng)然這個數(shù)據(jù)流也可以從(Query Plan)底部開始，將數(shù)據(jù)向上推(雖然很少見，但 VoltDB /德國的 HyPer 都使用了這個方案)。但是這種方式必須確保正在處理的數(shù)據(jù)能夠放在 CPU 緩存和寄存器中(也就是說這種方式需要對內(nèi)存位置和內(nèi)存分配的操作足夠地細(xì)致才行)

1. top-down 方式適用于面向磁盤的數(shù)據(jù)庫系統(tǒng)

2. bottom-top 方式適用于面向內(nèi)存的數(shù)據(jù)庫系統(tǒng)

## Access Methods

Access Methods，即一種通過它從數(shù)據(jù)庫系統(tǒng)的表里面查數(shù)據(jù)的方法，這個方法會伴隨整個 Next 函數(shù)(因為 Next 函數(shù)里面也需要查數(shù)據(jù))

基本上有 3 種 Access Methods

1. 循序掃描

2. 索引掃描

3. 多索引/bit map 掃描

### 循序掃描

簡單來說，就是在 operator 中有一大堆 for 循環(huán)

在獲取下一個 page 中的 tuple 時，operator 需要去維護(hù)迭代 for 循環(huán)中調(diào)用 Next 函數(shù)結(jié)束時的狀態(tài)(每一次返回時，那個 tuple 所在的位置)，這樣每次回頭再次調(diào)用 Next 時，就可以從上次結(jié)束時的狀態(tài)的地方繼續(xù)處理

這通常被稱之為游標(biāo)(cursor)

### 循序掃描-優(yōu)化

一些能讓循序掃描變快的方法如上

1. Prefetching(用 2 個 buffer 來進(jìn)行 Join 操作)

2. Buffer Pool Bypass(用 1 個小 buffer 對查詢進(jìn)行緩存，而不是去污染 buffer pool 緩存)

3. Parallelization(下節(jié)課會介紹)

重點是下面 3 個

### Zone Maps

Zone Maps 是用來提前計算好關(guān)于 page 的一些信息，后續(xù)訪問時就可以決定要不要去訪問這些 page

基本思想是，對于數(shù)據(jù)庫表中每個 page 來說，它會根據(jù) page 來計算生成一些額外的元數(shù)據(jù)，這些元數(shù)據(jù)是關(guān)于該 page 中給定屬性相關(guān)值的信息

例子

比如在上圖的表中，只有 5 個 tuple

對此，Zone Map 會提前計算出這個表中這一列的一些聚合信息

如果現(xiàn)在有這么一個查詢，即

```

SELECT * FROM table WHERE val > 600;

```

有了 Zone Map 之后，這個查詢會先去查 Zone Map 上的數(shù)據(jù)，發(fā)現(xiàn)這個 table 中沒有一個 tuple 的值是 > 400 的，于是直接跳過這個 table

Zone Map 可以保存在一個專門的 Zone Map block/page 中，上面保存了不同 page 下的 Zone Map

> Vertica、MemSQL、Amazon RedShift、Oracle、DB2、Cloudera Impala、Netezza 等有應(yīng)用 Zone Map

但是要維護(hù)這些 Zone Map 數(shù)據(jù)會是一個麻煩，因為假如 page 中的數(shù)據(jù)不斷更新的話，就得不停維護(hù)這些 Zone Map，所以 Zone Map 在 OLTP 數(shù)據(jù)庫中是不適用的，因為維護(hù)成本很高

但對于 OLAP 數(shù)據(jù)庫來說，因為其 寫少讀多 的特性，適合應(yīng)用 Zone Map

### Late Materialization

在列存儲數(shù)據(jù)庫中，可以將 operator 間的數(shù)據(jù)做延遲傳遞

SIMD 指令會將這些數(shù)據(jù)的 offset 值或者 column ID 給出來，從而做到延遲傳遞/獲取的功能

為什么列儲存需要做這些?

因為在列存儲中，為了獲取單個 tuple 的所有數(shù)據(jù)，需要做一大堆不同的讀操作，因為這些數(shù)據(jù)被拆散到不同的列中了，所以為了提升性能，需要盡可能延遲這些讀操作

例子

假設(shè)要對 foo 和 bar 這 2 張表進(jìn)行 Join

在對應(yīng)的查詢計劃樹中，首先要處理的就是 filter operator，即只需要 a 這一列

根據(jù)查詢計劃樹，后面就不需要 a 這個列了，那么這個時候只需要將 b 和 c 相對于 a 的 offset 值或者判斷條件上傳即可，并不需要后面將整個 b 和 c 上傳

對于 b 的 Join 操作來說也是如此

對于 c 來說，由于 offset 的關(guān)系，它知道 c 在哪里，所以直接就根據(jù)這個拿到磁盤中 c 這一列，計算出最終結(jié)果

### Heap Clustering

### Index Scan

索引掃描，主要是為了識別在表中有哪些索引，方便快速查找數(shù)據(jù)，避免不必要的操作，在查詢計劃樹中傳遞更少的數(shù)據(jù)給下一個 operator

選擇索引也是一項技術(shù)活，取決于上面那個圖中所提到的

例子

假設(shè)有這么一個查詢

已經(jīng)為 age 和 dept 建立了索引的情況下，在這個查詢中，要使用哪些索引呢?這取決于表中這些數(shù)據(jù)的值

場景 1，肯定是要根據(jù) dept 索引來查，因為一共就 2 個人在 cs，直接查就能查到，而如果使用 age 索引來查，那基本和循序掃描沒啥區(qū)別

場景 2，這種情況就可以使用 age 索引了，因為它更具有選擇性(selective)(當(dāng)然這里直接做循序掃描會更好，因為還要遍歷一遍索引著實沒有那個必要)

### Muti-Index Scan

多索引掃描指的是通過不同的索引進(jìn)行多次查找，基于判斷條件，將查找結(jié)果進(jìn)行合并

例子

依然是前面那個語句

先找出 age < 30 的 record ID

再找出 dept 為 CS 的所有 record ID

最后在其交集里面取 country 為 US 的數(shù)據(jù)

### Index Scan Page Sorting

如果使用的是非聚簇索引，那么查詢時只需要沿著葉子節(jié)點掃描就行，掃描時隨機跳到不同 page 上的不同 record ID 上，因為這些 tuple 排列的方式和索引中葉子節(jié)點的排列方式不一樣

在最糟糕的情況下，假設(shè)只有一個 buffer page，同時往這個 buffer pool 里面放入一個 page，然后每次沿著葉子節(jié)點進(jìn)行掃描時，都會讀取一個 page，如果查看的 page 和接受到的 page 不同，那就必須要做一次磁盤 I/O 來重新獲取下這個 page

如果輸出結(jié)果不是基于索引的 id 來排序，即可能是基于其他屬性進(jìn)行的排序，但沒有根據(jù)這個創(chuàng)建索引，那么在對數(shù)據(jù)進(jìn)行查找之前，數(shù)據(jù)庫引擎會沿著葉子節(jié)點掃描，獲取到所有的 record ID，然后根據(jù) page ID 先對它們進(jìn)行排序

那么對于每個組中的每個 page 來說，都需要一次 I/O 來獲取它，并且會先把當(dāng)前 page 中所有 tuple 處理完畢后再去處理下一個 page

> 如果在聚簇索引葉子節(jié)點中間做插入，會引發(fā)頁分裂(合并的 page 需要進(jìn)行 split 處理)，而聚簇索引依賴主鍵來快速的做順序插入，但一旦中間插入，整個主鍵就會被重建，樹的中間節(jié)點都會發(fā)生改變，葉子節(jié)點里面的 key/value 也會做移動，也就是說在 split 時，這些葉子節(jié)點就無法準(zhǔn)確的和底層這些 page 鏈接起來(原來的 key/value 對應(yīng)的 page 就變了)

## Expression Evaluation

最后就是怎么樣對這些判斷條件(比如 WHERE 子句)進(jìn)行評估了

那么怎么做呢?

將 WHERE 子句表示為一個表達(dá)式樹(expression tree) 來做。這個表達(dá)式樹上的所有節(jié)點代表來條件判斷中不同類型的表達(dá)式

比如如下圖

例子

> Prepared Statement 是一種聲明查詢模板的方式，提前告訴數(shù)據(jù)庫系統(tǒng)，要不斷執(zhí)行這個查詢，然后會有一個占位符，可以在運行時將值填入，這樣這個查詢就變得跟一個函數(shù)調(diào)用一樣。在運行時，只需要將值傳入，然后替換掉這個占位符就行

比如這個語句

```

SELECT * FROM S

? ? WHERE B.value = ? + 1;

```

這個表達(dá)式，它的表達(dá)式樹長這樣

Query Parameters 就是這個查詢需要傳入的參數(shù)，Table Schema 就是這個表所包含的一些信息(有 record ID 就能查)

而工作方式，基本就是做深度遞歸，dfs

先從左邊 Attributes(S.value) 開始，它表示獲取當(dāng)前 tuple 的 S.value，并且生成 1000，因為 Current Tuple 里面的這個屬性值就是 1000

繼續(xù)往下遞歸，遞歸到 Parameter(0) 這個節(jié)點，這個節(jié)點表示 offset 在 0 處的值為 999

繼續(xù)做遞歸操作，遞歸到 Constant(1) 這個節(jié)點，這個節(jié)點表示常量值為 1

然后遞歸返回到 +

最終遞歸返回到 =，1000 === 1000，那么這里就會是 true

但是這種方式是很慢的，假設(shè)有 10 億個 tuple，那么通過調(diào)用函數(shù)的方式來評估并遍歷這個表達(dá)式樹，就得做 10 億次

那么怎么優(yōu)化呢?

答案就是 JIT(Just in Time) 編譯

怎么做?

就是對確切的條件進(jìn)行編譯，然后用它來對給定的 tuple 進(jìn)行評估

比如直接在 CPU 上寫這樣一條指令 1=1，這樣會比對這個樹進(jìn)行遍歷和查找更快，即如果能簡化判斷條件，有些能用指令的盡量用指令來做，那么這個查詢就會走的更快

這里也不僅僅只是將判斷條件編譯成指令，而是將整個查詢計劃編譯為 pipeline

## 結(jié)論