content
- 查詢優化概述1
- 查詢優化概述2
- 查詢分解
- 資料本地化
查詢優化概述1
▍代價
優化的目标就是指局部執行代價和網絡傳輸代價的和最小。
- 局部執行代價 = I/O代價 + CPU處理代價
- 網絡傳輸代價 = 啟動代價 + 傳輸代價
▍執行政策
▍優化思路
- 執行運算的次序
- 執行運算的方法
- 執行運算本身所在的場地
- 執行運算所需資料的場地
查詢優化概述2
▍問題
分布式查詢處理器需要考慮的問題是查詢分解（query decomposition）和資料局部化（data localization） —— 這也是接下來兩個子產品的内容
▍因素
- 兩個方面 —— 轉換（ transformation）和優化（optimization）
- 三個代價 —— CPU Time + I/O Time + Communication Time（和上面的優化代價是對應的～）
▍時機
- 靜态的（Static）：編譯時進行優化；是基于統計資訊的窮舉優化
- 動态的（Dynamic）：執行中進行優化；準确性好但代價高
▍層次
查詢分解
▍步驟
- 規範化（Normalization）—— 轉化為标準的and或or形式
- 分析（Analysis）—— 對于不正确的語義，盡早拒絕
- 約簡（Simplification）—— 删除備援謂詞
- 查詢重寫（Restruction）—— 重點題型，下有例題
▍Demo（約簡）
select name
from LoliHouse
where (not(name = "Alice") and (name = "Cocoa" or name = "Alice") and not(name = "Cocoa")) or name = "Hana"
// 設 P1: name = "Alice"
// 設 P2: name = "Cocoa"
// 設 P3: name = "Hana"
(非P1 ∧ (P1 ∨ P2) ∧ 非P2) ∨ P3
= (非P1 ∧ P1 ∧ 非P2) ∨ (非P1 ∧ P2 ∧ 非P2) ∨ P3
= false ∨ false ∨ P3
= P3
select name
from LoliHouse
where name = "Hana"
▍Demo（查詢重寫）
| 運算類型 | 執行代價 |
|---|---|
| σ, Л(不消重) | O(n) |
| Л(消重), group | O(nlogn) |
| × × × | O(n2) |
| ∞ 、 ∪ 、 ∩ 、 − 、 ∝ 、 ÷ ∞、∪、∩、-、∝、÷ ∞、∪、∩、−、∝、÷ | O(nlogn) |
準則1：盡可能将一進制運算移到查詢樹的底部（樹葉），即優先執行一進制運算
準則2：利用一進制運算規則，縮減每一關系，減小關系尺寸，降低I/O代價和網絡傳輸代價
select sanme
from supplier as ser, supply as sp, part as p
where ser.sno = sp.sno and sp.pno = p.pno
and ser.area = "北方"
and sp.num > 5000
and p.pname = "PPP"
資料本地化
▍定義
資料本地化讨論的是從全局查詢到片段查詢的變換。
利用的是全局關系與片段關系的等價變換。
其查詢樹被稱為片段查詢樹
▍步驟
- 将分片樹的水準（h）節點轉換為查詢樹的并集（ ∪ ∪ ∪）節點
- 将分片樹的垂直（v）節點轉換為查詢樹的連接配接（ ∞ ∞ ∞）節點
▍片段查詢優化（準則）
- 準則1：一進制運算下沉到葉子的片段上（再看看可否消去一部分？）
- 準則2：對于出現連接配接的地方，若連接配接條件不滿足，則置空消去
- 準則3：将連接配接運算（ ∞ ∞ ∞）下沉到并運算（ ∪ ∪ ∪）的下面
- 準則4：消去不影響查詢的垂直片段
▍片段查詢優化（Demo）
M o r e More More