跳轉到

8.2 查詢處理與 I/O 優化#

概念說明#

查詢最佳化器在候選執行計畫之間做選擇，選擇依據正是 3.3 節建立的 I/O 成本模型。以最常見的連接（join）為例，設外表 R 有 N_R 頁、內表 S 有 N_S 頁，緩衝 B 頁：

  1. 巢狀迴圈連接（block nested loop）：外表逐塊讀入，內表每輪全掃。 成本 = N_R + ⌈N_R/(B−2)⌉ × N_S。外表越小越便宜——最佳化器會自動交換內外表。
  2. 索引巢狀迴圈：外表逐筆，內表走 B+tree。 成本 = N_R + T_R × (h + 匹配頁數)。適合內表命中少量記錄的選擇性連接。
  3. Grace hash join：兩表用同一雜湊函數分成 k 個分區（partition），分區 i 只與分區 i 連接。每個分區裝得下記憶體就一次連接完成；裝不下就遞迴再分。 成本 = 3(N_R + N_S)（讀入、寫分區、逐分區連接）。
  4. 排序歸併連接（sort-merge join）：兩表各排序後歸併。 成本 = 排序成本之和 + N_R + N_S。若輸入本來就有序（例如索引掃描），可降到 N_R + N_S——這是範圍連接與大資料量下常勝的選擇。

掃描本身也有優化：區域映射（zone maps / min-max 索引）在每個區塊記錄鍵的範圍，WHERE id > 10000 可整段跳過；列存與欄存的取捨則影響掃描要讀多少頁——欄存分析查詢只需讀涉及的欄位，I/O 可少 10 倍以上。

演算法步驟：Grace hash join#

  1. 選分區數 k ≈ ⌈min(N_R, N_S)/(B−2)⌉，雜湊鍵模 k。
  2. 第一階段：讀 R 與 S 各一次，寫出 2k 個分區檔案（2(N_R+N_S) 次 I/O）。
  3. 第二階段：對每個 i，把 R_i 載入記憶體建雜湊表，掃 S_i 探測（N_R+N_S 次 I/O）。
  4. 某分區仍過大 → 遞迴用第二個雜湊函數再分。

Python 範例：join 成本比較與模擬#

import math

def bnl_cost(nr, ns, B):
    return nr + math.ceil(nr / (B - 2)) * ns

def grace_cost(nr, ns, B):
    k = max(2, math.ceil(min(nr, ns) / (B - 2)))
    return 3 * (nr + ns) + (math.ceil(math.log(k, B - 2)) > 1) * 0  # 忽略遞迴

def index_cost(nr, ns, h=3, sel=0.01):
    return nr + ns * (h + 1) * sel * ns / ns  # 簡化：每外表筆數 × (h+1)

def sort_merge_cost(nr, ns, B):
    def sort_c(n):
        runs = math.ceil(n / B)
        rounds = math.ceil(math.log(runs, B - 1)) if runs > 1 else 0
        return 2 * n * (1 + rounds)
    return sort_c(nr) + sort_c(ns) + nr + ns

NR, NS, B = 1000, 10000, 101
print(f"R={NR}頁, S={NS}頁, B={B}")
print(f"區塊巢狀迴圈: {bnl_cost(NR, NS, B):>8} 次 I/O")
print(f"Grace hash:   {grace_cost(NR, NS, B):>8} 次 I/O")
print(f"排序歸併:     {sort_merge_cost(NR, NS, B):>8} 次 I/O")

# 模擬 zone map 跳過
pages = [{"pid": i, "min": i * 100, "max": i * 100 + 99} for i in range(100)]
def scan_with_zonemap(lo, hi):
    read, skipped = 0, 0
    for p in pages:
        if p["max"] < lo or p["min"] > hi:
            skipped += 1
        else:
            read += 1
    return read, skipped

read, skipped = scan_with_zonemap(5000, 5200)
print(f"zone map: 讀 {read} 頁、跳過 {skipped} 頁（全掃需 100 頁）")

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

  • 區塊巢狀迴圈：O(N_R + N_R·N_S/B)，適合小外表或緩衝極大。
  • Grace hash：O(3(N_R+N_S))，等值連接的穩健首選。
  • 排序歸併：O(N log N) 但輸出有序，可省去上層排序節點；輸入有序時 O(N)。
  • 決策規則：等值連接 + 無索引 → hash join；有選擇性索引 → index nested loop；範圍連接或已排序 → sort-merge。

練習#

  1. R=100 頁、S=100,000 頁、B=52，計算四種連接的成本，說明最佳化器應選哪個。
  2. 在 Grace hash join 中，若最大分區有 500 頁而 B=52，需要幾層遞迴分區？
  3. 修改 zone map 範例，統計查詢選擇性（範圍大小/總範圍）與跳過頁數的關係。