跳至主要内容

Sorting & Aggregations Algorithms

Query Plan​

DBMS 會將 SQL 編譯成 query plan，query plan 是一種由 operator 組成的樹狀結構。

Query Plan

對於 disk-oriented 的 DBMS，我們會使用 buffer pool 來實現需要溢出到 disk 的演算法，並且最小化 I/O。

Sorting​

在 DBMS 中，tuple 在 page 中是無序的，因此我們在執行以下操作時可能會需要排序 :

  • 在 SQL 中使用 ORDER BY
  • 使用 DISTINCT 去除重複的 tuple 時，如果有排序就可以加快運算
  • 將大量排序好的資料插入到 B+Tree 中
  • Aggregations (GROUP BY)

如果資料的大小很小 (可以放入 memory)，我們可以使用如 quick sort 的方式來進行排序，否則我們就必須考慮到 disk I/O 的成本來選擇排序演算法。

TOP-N Heap Sort​

如果我們的 SQL 指令中有 LIMIT N 和 ORDER BY，我們可以使用 heap sort 來實現 TOP-N 的功能。

External Merge Sort​

外部排序通常會使用 divide and conquer 的方式來實現，主要包含 2 個步驟 :

  • sorting : 將資料分割成小塊，並且在 memory 中進行排序
  • merging : 將排序好的資料合併

External Merge Sort

頁面的排序可以使用 early materialization 或 late materialization 來實現

  • early materialization : 排序頁面中會儲存完整的資料
  • late materialization : 只儲存 record id 或指針

General (K-way) Merge Sort​

我們假設 file 被分成 N 個 page，且 DBMS 有 B 個 fixed-size buffers。 需要把每個 page 讀入 buffer，並且進行排序，最後再將排序好的 page 寫回 disk，並透過不斷的合併來完成排序。

General Merge Sort

其複雜度如下 :

  • pass 的數量 : 1+⌈log⁡B−1N⌉1 + \lceil \log_{B-1} N \rceil
  • I/O 數量 : 2N×2N \times pass 的數量

Optimizations​

Double Buffering Optimization​

Double Buffering

預處理接下來要使用的 page，將其讀入另一個 buffer 中來減少 IO 停頓。

Comparison Optimizations​

  • Code Specialization : 將比較器 hard code 到特定的類型，而不使用 function pointer，如 C++ 的 template
  • Suffix Truncation : 只比較 VARCHAR 的前幾個字元

Using B+tree​

如果已經有 B+tree 的索引，我們可以使用 B+tree 來加速排序，我們只需遍歷 leaf node 即可得到排序好的資料，會分成兩種情況 :

  • clustered B+tree I/O 是順序的，比外部排序效率更高

Clustered B+tree

  • unclustered B+tree

I/O 是隨機的，效率極低

Unclustered B+tree

Aggregations​

為了將多個 tuple 的單個屬性合併成一個值，DBMS 需要能將資料快速分組的方法。

Sorting​

Sorting

Hashing​

在計算聚合時，進行 hash 運算遠比排序快，我們只需要去除重複的 key 即可，而不需要排序。

我們需要先掃描表格並填入臨時的 hash table，接著再檢查該 key 是否已經存在，並進行適當修改。

當哈希表過大無法放入 memory 時，我們可以使用 external hashing 來實現

  • Partition

使用 hash function h1 來將 tuple 分配到 disk 中

Partition

  • ReHash

對每個 partition 利用 hash table 計算聚合的內容。

在 rehash 的過程中，存在一組 grouping key -> return value 的 hash table，我們只需要更新這個 key-value pair 即可。

ReHash ReHash

References​