跳轉到

3.3 排序的 I/O 成本分析#

概念說明#

磁碟排序的效能不能只看 CPU 演算法複雜度，因為 I/O 比記憶體運算慢 4~5 個數量級（見 1.2 節）。本節建立一套標準成本記法，之後在第 8 章查詢最佳化中會反覆使用：

  • N：資料總頁數。
  • B：緩衝池可用的分頁數。
  • T：一次隨機 I/O 的時間（HDD 約 10ms；SSD 約 0.1ms）。
  • t：一次順序 I/O 每頁的時間（HDD 約 0.1ms/頁；SSD 約 0.02ms/頁）。

外部合併排序若把隨機與順序 I/O 混為一談，會嚴重高估成本。實務上：排序階段與合併階段都是大段順序讀寫，成本應以 t 計；只有 run 數超過緩衝而需要「多輪」時，每輪仍是順序的，但排程不佳的系統（例如每頁單獨讀寫）會退化到 T。

另一個重要觀念是 雙緩衝（double buffering）：為每個輸入 run 保留「讀取緩衝」與「計算緩衝」各一，讓 CPU 在讀第 i+1 塊時合併第 i 塊，把 I/O 等待時間與計算重疊，實測可提升 30%~50% 吞吐。

成本公式彙整#

項目 公式
初始 run 產生 讀 N 頁 + 寫 N 頁
每輪合併 讀 N 頁 + 寫 N 頁
合併輪數 ⌈log_{B-1}(⌈N/B⌉)⌉
總 I/O（頁） 2N·(1 + 合併輪數)
總時間（順序 I/O） 2N·(1+輪數)·t
最終輸出可省略寫回 −N 頁（若結果直接串流給下個算子）

Python 範例：成本計算器與雙緩衝模擬#

import math

def sort_io_cost(N, B, T_ms=10, t_ms=0.1):
    """回傳 (總I/O頁數, 順序I/O估計時間, 隨機I/O估計時間)"""
    runs = math.ceil(N / B)
    rounds = max(0, math.ceil(math.log(runs, B - 1))) if runs > 1 else 0
    pages = 2 * N * (1 + rounds)
    return pages, pages * t_ms, pages * T_ms

for N, B in [(1000, 11), (10000, 101), (1000000, 101)]:
    p, seq, rnd = sort_io_cost(N, B)
    print(f"N={N:>8}, B={B}: 輪數成本 {p:>10} 頁 | "
          f"順序 {seq/1000:>8.1f}s | 若退化成隨機 {rnd/1000:>8.1f}s")

# 雙緩衝模擬：合併時 I/O 與計算重疊
import heapq, time
def merge_with_buffering(k, chunk_ms=1.0, compute_ms=0.5, double=True):
    elapsed, t_io, t_cpu = 0.0, 0.0, 0.0
    for _ in range(k):
        if double:
            t_io += chunk_ms          # 讀下一塊與計算重疊
            t_cpu = max(t_cpu, chunk_ms)  # 計算被 I/O 覆蓋
        else:
            t_io += chunk_ms
            t_cpu += compute_ms
    return t_io + (0 if double else t_cpu)

print("單緩衝:", merge_with_buffering(100, double=False), "ms")
print("雙緩衝:", merge_with_buffering(100, double=True), "ms")

複雜度與 I/O 成本分析#

  • 演算法下界：磁碟排序至少要讀一次寫一次，Ω(N) 頁 I/O 不可避免；外部合併排序在合理 B 下已非常接近下界。
  • 敏感度：B 從 11 增到 101，輪數通常從 3 降到 1，總 I/O 減半以上——「多買記憶體」往往比「換更快的磁碟」便宜有效。
  • 快取預讀：Linux 的 readahead 讓連續讀取實際延遲遠低於 t 的理論值。

練習#

  1. N=500,000 頁、B=1001，求合併輪數與總 I/O 頁數；換成 B=101 呢？
  2. 用範例的成本計算器畫出「總時間 vs B」曲線，找出 B 增加的邊際效益遞減點。
  3. 說明為何最後一輪合併的寫回可以省略，這對成本公式影響多少百分比。