Sorting & Aggregations Algorithms
這堂課會深入探討資料庫中查詢計畫的構建、Sorting 與聚合 Aggregation 演算法的原理與實作。
Query Plan
在 RDBMS 中,當使用者送出一段 SQL,會先經過 query optimizer 分析與重寫,最終轉換為一棵 query plan tree,這棵查詢計畫樹會由一連串的 operators 組成,每個 operator 都代表一個資料庫操作,如掃描表格、過濾條件、連接等。
對於 disk-oriented 的 DBMS 來說,查詢執行時勢必要將部分資料從磁碟載入到記憶體中處理,並可能需要將中間結果回寫至磁碟。 因此,查詢演算法設計的一個重要原則,盡量減少 I/O 的次數,特別是避免隨機存取。
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 : 將排序好的資料合併
頁面的排序可以使用 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,並透過不斷的合併來完成排序。
其複雜度如下 :
- pass 的數量 :
- I/O 數量 : pass 的數量
External Merge Sort Optimizations
Double Buffering Optimization
預處理接下來要使用的 page,將其讀入另一個 buffer 中來減少 IO 停頓。
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 是順序的,比外部排序效率更高
- unclustered B+tree
I/O 是隨機的,效率極低
Aggregations
為了將多個 tuple 的單個屬性合併成一個值,DBMS 需要能將資料快速分組的方法。
Sorting
將資料依照 grouping key 排序,然後進行聚合,這種方法的好處是可以利用排序的結果來加速聚合運算,但缺點是排序的成本較高,特別是當資料量大於記憶體時。
Hashing
在計算聚合時,進行 hash 運算遠比排序快,我們只需要去除重複的 key 即可,而不需要排序。
我們需要先掃描表格並填入臨時的 hash table,接著再檢查該 key 是否已經存在,並進行適當修改。
當哈希表過大無法放入 memory 時,我們可以使用 external hashing 來實現
- Phase 1 : Partition
使用 hash function h1 來將 tuple 分配到 B - 1 個 partition 中,剩下的一個 partition 用來存放輸入的資料。
- Phase 2 : ReHash
對每個 partition 利用 hash table 計算聚合的內容。
在 rehash 的過程中,存在一組 grouping key -> return value 的 hash table,我們只需要更新這個 key-value pair 即可。