## 課程目標

聚合操作可以基于排序算法來做，然后可以應用到下一節(jié)課會講到的 join 算法之中

## 為什么需要排序

因為要確保所有的數(shù)據(jù)都放在了正確的環(huán)境中。畢竟在關(guān)系模型中，所有的 tuple 都是無序的，它們都屬于一種集合代數(shù)(set algebra)

聚簇索引(clustering index) 可以基于某種索引來提供一種強制排序的順序?？梢栽?table 中某個特定的 key 上使用聚簇索引，但如果此時需要另一個 key 來進行排序的話，那么聚簇索引這種預排序就沒有太大幫助了

如果 table 、輸出結(jié)果、key 是有序的，那么去重就很方便了，因為這個時候只需要查一次 table，如果當前的數(shù)據(jù)和上一個數(shù)據(jù)一樣，說明有重復數(shù)據(jù)，就可以將那個重復的數(shù)據(jù)扔掉

對于 GROUPBY 也是一樣的，如果所有數(shù)據(jù)被預排序過，那么只需要查一次 table，然后根據(jù)需要計算出 running total，以此來生成聚合結(jié)果(aggregations)

B+ Tree 中的 bulk loading 會加載大量的數(shù)據(jù)，如果沿著葉子節(jié)點對所有數(shù)據(jù)進行預排序，然后自下而上去構(gòu)建索引，這種方式會更加高效

## 排序算法

快排、堆排序、冒泡排序... 等等都可以用，因為數(shù)據(jù)是放在內(nèi)存中的

但是如果數(shù)據(jù)沒有放在內(nèi)存中，那么快排就是一個很糟糕的選項了

因為快排會進行大量的隨機跳轉(zhuǎn)，它會隨機跳轉(zhuǎn)到內(nèi)存中的不同位置上，它所做的事情屬于隨機 I/O

而對于數(shù)據(jù)庫來說，要跳轉(zhuǎn)的 page 可能不是放在內(nèi)存中的，在最糟糕的情況下，每當對數(shù)據(jù)集進行一次修改，就要進行一次 I/O

那數(shù)據(jù)庫需要的是一種怎樣的算法呢?

需要的是一種，能將 在磁盤上讀寫數(shù)據(jù) 所消耗的成本 考慮進去的算法，這個算法能最大化 序列 I/O 所能獲取到數(shù)據(jù)的數(shù)量

這里會用到 序列 I/O，因為它比 隨機 I/O 的效率要高，即便是在速度很快的 SSD 上也是如此

因為可以通過一次 序列 I/O 就能拿到大量的數(shù)據(jù)，并且在 SSD 中也沒有磁盤尋道(seek)

### 外部歸并排序

基本原理是，將要排序的數(shù)據(jù)集分成更小的數(shù)據(jù)塊(runs)，然后對這些 runs 分別排序

在一個給定的 run 中所有的 key 都是排過序的

而這些個 runs 則是要排序的整個 key 集合中彼此不相交的子集(也即歸并排序的思想)

對這些體積很小的 runs 進行排序，然后將它們合并在一起，并形成更大的排好序的 runs

然后一直重復操作，直到要排序的整個 key 集合排好為止

這里有 2 個階段

1. 排序

? ? 這個階段，將盡可能多的數(shù)據(jù)塊放入內(nèi)存，并對它們進行排序，然后將排完序的結(jié)果 runs 寫回磁盤

2. 歸并

? ? 這個階段，將這些排好序的 runs 合并成更大的 runs，然后將它們從磁盤寫出，不斷重復這個過程，直到排序全部完成

### 2-Way 外部歸并排序

2-way 指的是，在每一輪中要合并的 run 的數(shù)量是 2，即將 2 個 run 合并成一個新的大的 run，這個新的大的 run 再作為下一次的輸入

數(shù)據(jù)集是被分散在 N 個 page 中的，因為排序時需要將數(shù)據(jù)緩存在內(nèi)存中，所以這個時候就需要考慮在執(zhí)行該算法時，可用的內(nèi)存是多少

而這個可以用的內(nèi)存的大小，是可以在數(shù)據(jù)庫系統(tǒng)中作配置來得到

> 在 PostgreSQL 中，這個內(nèi)存被稱之為 working memory。簡單來講就是，對于一個特定的查詢來說，working memory 就是它在進行中間某些操作時被允許使用的內(nèi)存量。可以在這個 working memory 基礎(chǔ)上構(gòu)建一個 hash table，做排序或者其他事情

### 2-Way 外部歸并排序例子

每次要從表中讀 B 個 Page 到內(nèi)存中，在內(nèi)存中對它們進行排序，接著將排完序后的結(jié)果寫出到磁盤

現(xiàn)在把圖中的 Page #1 放到內(nèi)存中

然后對它進行排序，現(xiàn)在它就是一個排好序的 run

然后把這個排好序的 run 寫回到磁盤上

然后對其他的 Page 也做類似的處理

放到內(nèi)存中 -> 排好序 -> 將這個排好序的 run 寫回磁盤

上述操作使得要排序的 pages 完成之后，會對排好序的 run 進行遞歸合并，然后將這些結(jié)果合并成一起，最終生成的 run 的大小是最開始輸入的 2 倍大

對于這種情況而言，至少需要 3 個 buffer page，因為需要 2 個 buffer page 來放那些載入到內(nèi)存中的 run，1 個 run 對應 1 個 buffer page

另 1 個 buffer page 用來保存要寫出的輸出結(jié)果

要對下圖中 2 個 run 進行排序，就將它們?nèi)拥絻?nèi)存中

然后將排好序的結(jié)果放入到 1 個 page 中，一旦這個 page 寫滿了，就把它寫出到磁盤

然后就是遞歸地去執(zhí)行上述過程

### Double Buffering 優(yōu)化

通過 prefetch 來最小化 I/O 成本，是一種很簡單的優(yōu)化方式

基本原理是，當要對 2 個 page 進行合并時，通過使用 shadow page/buffer 來接收要排序的下一個 run/page，這可以減少異步 I/O 的次數(shù)，這樣在后臺就可以獲取到接下來需要的 page(也就是說一邊在對第一個 page 排序，另一邊同時從磁盤寫出第二個要排序的 page 到內(nèi)存，這樣第一個 page 排序完成之后就可以接著第二個 page 的排序了)

比如對 Page #1 進行排序

在對 Page #1 進行排序時，后臺就開始獲取 Page #2

在對 Page #1 的操作結(jié)束時，就可以立即去操作 Page #2 了

### 2-Way 算法總結(jié)

#### 例子

使用 5 個 buffer page 對 108 個 page 上的數(shù)據(jù)進行排序

在第一輪中，要做的 I/O 數(shù)量如下

在接下來的幾輪中，用上一輪算出來的 run 的數(shù)量來計算

接著，不斷操作，直到結(jié)束為止

### 使用 B+ Tree 來排序

目前這種方式適用于大部分數(shù)據(jù)集，當然前題是這些數(shù)據(jù)集中的值都是 均勻分布 的，即數(shù)據(jù)沒有經(jīng)過排序，而是隨機分布

在某些情況下，可以使用 B+ Tree 來提升排序的速度

那么 B+ Tree 在這個里面起到什么作用了呢?

它在數(shù)據(jù)結(jié)構(gòu)中讓 key 變得有序了

雖然當 table 被修改時，B+ Tree 需要做對應的 split/merge 操作，需要付出點代價去維護，但由于 key 在 B+ Tree 中是有序的，那么在做范圍查詢時，也就沒必要去做排序操作了，直接就能查(這里我理解的是，因為構(gòu)建 B+ Tree 的過程就已經(jīng)是一個排序的過程，所以在做查詢時就可以直接去查)

如果要排序的 key 和 B+ Tree 上索引中的 key 是一樣的話，那么就可以復用這個 B+ Tree，就不用像之前展示的 N-Way merge sort 那樣去遍歷整個數(shù)據(jù)集了

但這只適用于 Clustered B+ Tree 的情況，并不適用于 Unclustered B+ Tree?

### Clustered B+ Tree

Clusterd B+ Tree 的作用是: 各個 tuple page 中 tuple 的物理位置和在 B+ Tree 索引中定義的順序相匹配

上圖可以看到，能夠直接通過 B+ Tree index 找到對應的 tuple pages，并且這個就是有序的

在查詢優(yōu)化器(query optimizer)中也有對應的應用。比如要基于某個 key 進行排序時，如果已經(jīng)存在關(guān)于這個 key 的 聚簇索引(clustered index)，那么這個查詢優(yōu)化器就會去使用這個聚簇索引來生成正確的排序，而不會再去執(zhí)行前面提到的 外部歸并排序

> 但在 PostgreSQL 中，它并不會強制使用上述方式。比如在上圖中，要通過在 B+ Tree 中的某個 key 找到某個對應的 tuple page，但在這個 tuple page 里面的 tuple 它并不是排好序的

### Unclustered B+ Tree

Unclustered B+ Tree 的作用是: 各個 tuple page 中 tuple 的物理位置和在 B+ Tree 索引中定義的順序不匹配

這是幾乎就是個 bad idea，為什么?

因為對于每個記錄，都得進行一次 I/O 操作

如上圖所示，葉子節(jié)點的數(shù)據(jù)(tuple page)與 B+ Tree index 中數(shù)據(jù)排列的順序并沒有什么關(guān)系

此時如果要去查 B+ Tree index 中它的某個葉子節(jié)點中偏前面的 key，可能就需要一次磁盤 I/O，因為需要的 page 可能并不在內(nèi)存中。在內(nèi)存中找不到那只能從磁盤中找，獲取到它之后放入 buffer 池

此時如果要查 B+ Tree index 中這個葉子節(jié)點偏后面的 key，發(fā)現(xiàn)它在另一個 page 上，那就必須要把剛放入到 buffer 池中的那個 page 移除掉，把這個找到的 page 放入 buffer 池中(又是一次磁盤 I/O)

## 聚合(Aggregations)

聚合操作的實現(xiàn)，可以有 2 種選擇

1. sorting

2. hasing

他們之間有不同的 trade-off，并且性能上也有所不同

因為 sorting 所做的是大量的循序訪問(sequential access)，而 hashing 所做的則是隨機訪問，在有的情況下一個可能比另一個性能要好

一般情況下，不管磁盤的速度有多快，hashing 這種方式的效果會更好

所以在 hashing aggregation 的例子中，會做更多的循序 I/O 而不是隨機 I/O

hashing 的速度一直很快，因為所有的數(shù)據(jù)都是在內(nèi)存中的

那么聚合操作的過程是怎樣的呢?

是這樣的，先拿到一堆的值，然后將它們合并到一起，最后生成一個標量值(scalar value)

### Sorting Aggregation

如果數(shù)據(jù)已經(jīng)預先排好序了，那么在掃描這堆數(shù)據(jù)時，就不需要回過頭去做聚合計算

因為只需要掃描一輪就可以得到想要的結(jié)果，下圖是一個例子，enrolled 表已經(jīng)根據(jù) sid 排好序了

對于接下來的 Query Plan Tree 來說，最先要的做的事情就是 過濾

首先需要過濾出所有 grade 不是 B 或 C 的 tuple

然后在進行下一個 operator 操作之前，移除掉輸出結(jié)果中不需要的列

然后用 DISTINCT 聚合操作完成排序

最后進行去重處理

可以看出在這一整條流程中，基本上都是在盡可能盡早的移除掉無用數(shù)據(jù)

對于 Projection 操作也是如此，SELECT 想要查什么屬性的值，就只查那個對應的屬性的列就行，后續(xù)在進行排序時，就不用去復制這些額外的數(shù)據(jù)了(Projection 允許扔掉不需要的列)

> Zone maps 的作用是它可以提前知道它對應的 page 中要進行的查找值得不值得，因為這個里面保存著每個屬性可能存在的數(shù)據(jù)范圍是多少

### Aternatives to Sorting

實際上在很多例子中，并不需要排好序的輸出結(jié)果

但如果不使用 GROUP BY 或者 DISTINCT 來進行排序的話，數(shù)據(jù)庫就會使用它自己的排序，并且付出的代價并不低

在這種情況下，hashing 就能起到作用了

hashing 是另一種分治的算法，通過 hashing，可以對數(shù)據(jù)集進行拆分，并將正在檢查的 tuple 或 key 引導到特定 page 中，然后在內(nèi)存中處理這些 page?

hashing 這種方式會移除掉所有的局部性和排序順序，因為它會拿到 key，并對 key 進行 hash 處理，然后跳到某個隨機位置。而好處就是不需要進行排序了

### Hashing Aggregation

基本原理是，在數(shù)據(jù)庫系統(tǒng)中掃描某個 table ，然后將掃描得到的結(jié)果填充到一個臨時的 hash table 中。后面在進行查找時，會根據(jù)聚合操作類型做不同操作。

比如要插入一個 key

1. 如果這個 key 并不在這個 hash table 中，那么這個 key 就會被填充進這個臨時的 hash table?

2. 如果這個 key 在這個 hash table 中，就需要通過修改這個 key 或者這個 key 對應的值，來生成所需要的聚合操作的結(jié)果

對于 DISTINCT 來講，它就是通過 hashing 的這種方式來判斷是否有重復的 key

對于 GROUP BY 來講，它就會去執(zhí)行聚合計算，可能要去更新 RUNNING_TOTAL

注意，這個臨時的 hash table 只用于當前對應的這個查詢，當這個查詢結(jié)束時，這個 hash table 會被銷毀掉

如果數(shù)據(jù)庫中的所有數(shù)據(jù)的寫入寫出都在內(nèi)存中，而這個 hash table 也在內(nèi)存里面，那么毫無疑問是最好的，因為復雜度(插入、更新)基本都是 O(1)

但是如果數(shù)據(jù)庫中所有的數(shù)據(jù)都要寫出到磁盤上，那就不行了，因為 hash table 帶來的隨機性會很糟糕(在插入、更新數(shù)據(jù)時，可能需要跳轉(zhuǎn)到 hash table 中對應的 page 下，這個時候要拿到這個 page 就需要從磁盤寫入數(shù)據(jù)到內(nèi)存，需要一次 I/O 操作。每跳轉(zhuǎn)一次，就可能需要一次 I/O，有 I/O 操作，就會降低性能)

那么有沒有更好的方案?

### External Hashing Aggeragation

答案是有的，基本原理就是盡可能地減少隨機 I/O，盡可能地增加循序 I/O，也就是說將大部分操作盡可能都在內(nèi)存中完成，然后再將結(jié)果寫出到磁盤

注意到這其實也是一種分治的策略:?

1. 傳入數(shù)據(jù)，然后將數(shù)據(jù)分開，放進一個個 bucket 里，所有具有相同 key 的 tuple 都會被放在同一個分區(qū)(partition)中

2. 每個分區(qū)都會構(gòu)建一個在內(nèi)存中的 hash table，然后再做聚合操作，最后扔掉這個 hash table，再接著處理下一個分區(qū)，如此循環(huán)往復

以上就是最大化循序 I/O 的操作，即在每次進行 I/O 時，都必須將這堆數(shù)據(jù)放入內(nèi)存中完成整個過程

#### 階段 1 - 分區(qū)

這里主要做的事情就是將這些 tuple 拆分到不同的分區(qū)中，然后根據(jù)需要將其寫出到磁盤中

而步驟是

1. 用第一個 hash 函數(shù)將數(shù)據(jù)進行拆分。因為 hash 函數(shù)是確定的，(即對同一個 key 進行 hash 所得到的 hash 值都是相同的)那么在這里，擁有相同 key 的 tuple 會落在同一個分區(qū)

2. 當這些分區(qū)存滿了之后，buffer 管理器就開始干活了，這個管理器會將這些分區(qū)里面存的數(shù)據(jù)寫出到磁盤中。

那么 buffer 管理器是如何管理呢

假設(shè)有 n 個 buffer，用 n-1 個 buffer 來保存分區(qū)的數(shù)據(jù)，用至少 1 個 buffer 來保存輸入的數(shù)據(jù)。即

1. 從 table 中拿到一個 page

2. 對該 page 進行循序掃描，查看在 page 中的每個 tuple

3. 將這些 tuple 寫出到這個 n-1 個 buffer 分區(qū)中

4. 對于這 n-1 個 buffer 分區(qū)來講，他們都需要一個 buffer 來做數(shù)據(jù)的傳輸

比如下面的例子

所有 `15-445` 的 cid 會落到上面那個分區(qū)，所有 `15-826` 的 cid 會落到中間那個分區(qū)(能這么做的原因是做了對 hash 過后的地址用 n-1 做了取模處理)，諸如此類

> 注意，如果某個分區(qū)的當前的 page 溢出了，那么就直接將這個 page 寫出到磁盤，然后分配一個新的 page，再接著填充數(shù)據(jù)

能這么做這種分區(qū)的前提條件是，數(shù)據(jù)在每個分區(qū)都呈現(xiàn)大致均勻分布的狀態(tài)

如果數(shù)據(jù)分布不均勻，那最好還是用循序掃描

#### 階段 2 - 重新 hash

這里主要做的事情就是對每個分區(qū)進行重新 hash，然后將這些 page 放入到內(nèi)存中，接著在內(nèi)存中構(gòu)建一個 hash table，去尋找相同的 key

此時，所有相同的 key 都會在同一個分區(qū)，那么在掃描該分區(qū)內(nèi)的所有 page 時，把期望的結(jié)果計算出來，就可以扔掉這個 hash table(因為在該分區(qū)更新過的 key，永遠不會在其他分區(qū)中被更新了，hash 處理保證了局部性)

比如下面的例子

所有 `15-445` 的 cid 所在的分區(qū)的 key，經(jīng)過 hash 處理會落到一個 hash table 上，接著繼續(xù)掃描，`15-826` 的也是，然后根據(jù)這個 hash table 生成最終的結(jié)果

而這里的要點在于，當移動到下一個分區(qū)時，上一個分區(qū)的 hash table 就會被扔掉，比如對 `15-721` 的操作

#### 小結(jié)

對于階段 2 中用過的 hash table，它是可以維護在聚合函數(shù)中的 `Running_Total`，然后 `Running_Val` 的值取決于聚合操作

比如下面的例子

拿到 cid，并計算每門課的平均 GPA

在 hash table 中，可以為每門課生成對應的平均 GPA

然后拿到 hash table 的 `value` 這部分，用 `Running_Toal` 除以 tuple 的個數(shù)，就能算出平均數(shù)

### 成本分析

(下周學 hash join 的時候再來講這節(jié))

## 總結(jié)