Skip to main content

Sorting & Aggregations Algorithms

這堂課會深入探討資料庫中查詢計畫的構建、Sorting 與聚合 Aggregation 演算法的原理與實作。

Query Plan​

在 RDBMS 中，當使用者送出一段 SQL，會先經過 query optimizer 分析與重寫，最終轉換為一棵 query plan tree，這棵查詢計畫樹會由一連串的 operators 組成，每個 operator 都代表一個資料庫操作，如掃描表格、過濾條件、連接等。

對於 disk-oriented 的 DBMS 來說，查詢執行時勢必要將部分資料從磁碟載入到記憶體中處理，並可能需要將中間結果回寫至磁碟。 因此，查詢演算法設計的一個重要原則，盡量減少 I/O 的次數，特別是避免隨機存取。

Query Plan

Sorting​

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

  • ORDER BY
  • 使用 DISTINCT 去除重複的 tuple 時，如果有排序就可以加快運算
  • 當需要大量插入資料到 B+Tree 時，如果有排序就能加快速度
  • Aggregations (GROUP BY)

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

TOP-N Heap Sort​

如果我們的 SQL 指令中有 LIMIT N 和 ORDER BY 時，我們就可以使用 heap sort 來實現。 這種方法的好處是我們只需要掃一次所有資料並且維護一個大小為 N 的 heap 即可。

External Merge Sort​

當資料量大於記憶體時，我們就需要使用外部排序 (External 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 的數量

External Merge Sort Optimizations​

Double Buffering Optimization​

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

Double Buffering

Comparison Optimizations​

  • Code Specialization : 將 comparator hardcode 到特定的類型，而不使用 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​

將資料依照 grouping key 排序，然後進行聚合，這種方法的好處是可以利用排序的結果來加速聚合運算，但缺點是排序的成本較高，特別是當資料量大於記憶體時。

Sorting

Hashing​

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

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

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

  • Phase 1 : Partition

使用 hash function h1 來將 tuple 分配到 B - 1 個 partition 中，剩下的一個 partition 用來存放輸入的資料。

Partition

  • Phase 2 : ReHash

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

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

ReHash ReHash