關係資料庫查詢優化：代數等價變換、啟發式查詢樹優化與實戰案例

關係資料庫查詢優化：代數等價變換、啟發式查詢樹優化與實戰案例

查詢優化是 RDBMS 效能關鍵。優化器透過代價模型從數百執行計劃中選擇最優，自動適應統計變化，釋放開發者負擔。

一、查詢處理四階段

1. 查詢分析：掃描、詞法/語法分析。
2. 查詢檢查：語義檢查、權限檢查、SQL → 關係代數表達式 (查詢樹)。
3. 查詢優化：代數優化 + 物理優化，產出執行計劃。
4. 查詢執行：代碼生成器生成可執行代碼。

二、代數優化：11 條等價變換規則

核心規則 (E1,E2,E3 為關係代數表達式)：

• 交換律：E1 × E2 ≡ E2 × E1、E1 ⋈ E2 ≡ E2 ⋈ E1
• 結合律：(E1 × E2) × E3 ≡ E1 × (E2 × E3)
• 投影串接：πA(πB(E)) ≡ πA(E) (A⊆B)
• 選擇串接：σF1(σF2(E)) ≡ σF1∧F2(E)
• 選擇-投影交換：σF(πA(E)) ≡ πA(σF(E)) (F 僅涉及 A)
• 選擇-笛卡爾積下推：σF(E1×E2) ≡ σF(E1)×E2 (F 僅涉及 E1)
• 選擇分配律：σF(E1∪E2) ≡ σF(E1)∪σF(E2)、σF(E1-E2) ≡ σF(E1)-σF(E2)
• 選擇-自然連接分配：σF(E1⋈E2) ≡ σF(E1)⋈σF(E2) (F 僅涉及公共屬性)
• 投影分配律：πA(E1×E2) ≡ πA1(E1)×πA2(E2)、πA(E1∪E2) ≡ πA(E1)∪πA(E2)

三、查詢樹啟發式優化算法

1. 選擇條件拆解：σF1∧F2∧...∧Fn(E) → σF1(σF2(...(σFn(E))...))。
2. 選擇下推：利用規則 4-9 移至葉節點。
3. 投影下推：利用規則 3,5,10,11 移至葉節點 (可分裂投影)。
4. 合併串接：多選擇/投影合併為單節點 (Pipelining)。
5. 分組：每雙目操作與其直接祖先單目操作成組 (笛卡爾積非等值連接除外)。

四、實戰案例：查詢選修「MATH」課程的女學生學號姓名

初始代數：πS#,SNAME(σCNAME='MATH'∧SEX='F'(C ⋈ SC ⋈ S))

優化後：先對 C 做 σCNAME='MATH'、S 做 σSEX='F'，大幅縮減 Join 輸入；若 C.C#、SC.C#、SC.S#、S.S# 有索引，再用 Index Join，代價極低。

五、關鍵啟發式規則口訣

選擇早做、投影早做、公共子表達式提取、Pipelining 避免中間物化、索引輔助 Join。