• 區分啟發式（規則式）重寫與成本式最佳化，知道兩者在最佳化器中各自的位置。

  • 列舉常見的邏輯重寫：述詞下推、投影下推、子查詢去相關、view 合併、外部 join 簡化。

  • 說明統計資訊（n_distinct、MCV、直方圖、相關性）如何轉成選擇率與基數估計，以及獨立性假設為何常常失靈。

  • 用 PostgreSQL 的成本常數手算一個 Seq Scan 與 Index Scan 的成本。

  • 解釋 Selinger 動態規劃的 join 排序法與「interesting order」，以及為何表數太多時要改用啟發式/遺傳演算法。

  • 診斷估計錯誤的計畫，並知道對應的修正手段。

為什麼需要最佳化器

SQL 是宣告式語言：使用者說「要什麼」，系統決定「怎麼做」。同一個查詢的不同實體計畫，執行時間可以相差好幾個數量級—— 例如 10 表 join 的左深計畫有 \(10! \approx 3.6 \times 10^6\) 種排列，再乘上每個 join 的演算法與存取路徑選擇。 最佳化器的目標並非找到最佳計畫（那本身就是 NP-hard），而是在可接受的時間內避開糟糕的計畫。

現代最佳化器幾乎都源自 IBM System R（Selinger et al. 1979）的架構：

  1. 邏輯重寫：套用一定有益的代數等價轉換（啟發式）。

  2. 成本式搜尋：對候選實體計畫用統計資訊估計成本，選最便宜者。

邏輯重寫：啟發式最佳化

這些轉換不需要統計，因為幾乎永遠有益（第 1 章的等價規則是其理論基礎）：

  • 述詞下推（predicate pushdown）：把 \(\sigma\) 盡量推向葉節點，越早過濾越好；也推進 view、子查詢與分割表（partition pruning）。

  • 投影下推（projection pushdown）：只往上傳需要的欄位，縮小中間結果——對行式儲存尤其重要。

  • 常數摺疊與表達式簡化：、、 \(\to\) ； \(\to\) 。

  • 子查詢去相關（decorrelation / unnesting）：把 改寫成 semi-join， 避免「每筆外層執行一次子查詢」。PostgreSQL 會把 / 子查詢拉平成 semi-join， 成 anti-join；但相關的純量子查詢多半仍以 SubPlan 執行。

  • View 合併與子查詢拉平：把 view 定義內嵌進外層查詢，讓述詞可以穿越。

  • 外部 join 簡化： 等價於 inner join；也允許更多的重排。

  • Join 消除：若只用到左表欄位、右表以主鍵/唯一鍵關聯，LEFT JOIN 可直接刪除。

  • OR 展開： 可改成兩個索引掃描的 bitmap OR。

統計資訊

成本式最佳化的燃料是統計資訊。PostgreSQL 的 （手動或由 autovacuum 觸發）隨機抽樣表中的列 （約 \(300 \times\) 列，預設 target 為 100，即 30,000 列），為每個欄位計算並存入 （可讀 view 為 ）：

lP9.6cm 統計量 & 意義與用途
& NULL 的比例； 的選擇率。
& 相異值個數；負值表示佔總列數的比例（如 \(-1\) 代表每列唯一）。等值條件的預設選擇率 \(1/n_{distinct}\)。
& 最常見值（MCV）清單與各自頻率（最多 target 個）；資料傾斜時的救星。
& 排除 MCV 後、以等高（equi-depth）方式切成 target 個 bucket 的邊界值；用於範圍條件。
& 欄位值順序與實體儲存順序的相關係數（\(-1 \sim 1\)）；接近 \(\pm 1\) 表示 index scan 幾乎是循序 I/O。
& 平均欄寬，用於估計中間結果大小（決定 hash join 是否放得進 work_mem）。

表層級的 （列數）與 （頁數）存在 。 可對特定欄位提高 target； （擴充統計，PostgreSQL 10+）可對多個欄位收集 、函數相依（）與多欄 MCV， 修正下一節將看到的獨立性假設問題。

選擇率與基數估計

選擇率（selectivity） \(sel(p) \in [0,1]\) 是述詞 \(p\) 讓多少比例的列通過；基數（cardinality）是估計的輸出列數。 教科書（與 ）的基本公式：

lP4.2cmP6.0cm 述詞 & 估計 & 說明
\(a = c\) & MCV 中有 \(c\)：其頻率；否則 \((1 - \sum \text{MCV freq}) / (n_{distinct} - |MCV|)\) & 無統計時預設 \(0.005\)。
\(a < c\) & 由直方圖內插：\(c\) 落在第 \(k\) 個 bucket 的位置 & 加上 MCV 中 \(< c\) 的頻率。
\(p_1 \wedge p_2\) & \(sel(p_1) \cdot sel(p_2)\) & 獨立性假設；相關欄位會嚴重低估。
\(p_1 \vee p_2\) & \(sel(p_1) + sel(p_2) - sel(p_1)\,sel(p_2)\) & 同樣假設獨立。
\(\neg p\) & \(1 - sel(p)\) &
\(R \bowtie_{R.a = S.b} S\) & \(|R| \cdot |S| \,/\, \max(V(R,a), V(S,b))\) & 包含假設：值域較小者包含於較大者；外鍵 join 最準確。
& 轉成範圍 & 無法用直方圖，預設低選擇率。

  • 相關欄位： 兩者高度相關，相乘後低估數個數量級， 導致選了 nested loop 而實際跑了幾百萬次。解法：。

  • 述詞中的函數或運算：、 沒有統計可用， 只能套預設值。解法：建表達式索引（ 會為它收集統計）或改寫為可 sargable 的形式。

  • 過時的統計：大量載入後未 ， 仍是舊值。解法：載入後手動 ； 調低 。

Leis et al. (VLDB 2015) 用 IMDB 真實資料（Join Order Benchmark）證明：主流資料庫的基數估計在多表 join 後常偏差 \(10^2 \sim 10^4\) 倍， 而估計錯誤比成本模型的誤差對計畫品質影響大得多。

成本模型

PostgreSQL 的成本是無單位的相對值，以一次循序讀一頁為 \(1.0\)，各常數可在 調整：

lrP7.2cm 參數 & 預設 & 意義
& 1.0 & 循序讀一頁
& 4.0 & 隨機讀一頁；SSD 上常調為 1.1–1.5，否則最佳化器過度偏好 Seq Scan
& 0.01 & 處理一筆 tuple
& 0.005 & 處理一筆索引項目
& 0.0025 & 執行一個運算子或函數
& 4GB & 估計 OS + shared_buffers 可快取的量；只影響 index scan 的成本估計，不配置記憶體
& 4MB & 每個排序/雜湊運算子可用的記憶體；超過即溢出

Seq Scan 成本： \[\text{cost} = \text{relpages} \times \text{seq\_page\_cost} + \text{reltuples} \times (\text{cpu\_tuple\_cost} + \text{cpu\_operator\_cost} \times n_{quals})\] 以 （1670 頁、20 萬列、一個過濾條件）為例：\(1670 + 200000 \times (0.01 + 0.0025) = 4170\)。

Index Scan 成本更複雜：索引部分為 B+Tree 高度（隨機 I/O）加上掃過的葉頁與索引項目； heap 部分依相關性在「全隨機」（每筆一次 ）與「全循序」之間內插， 並用 Mackert–Lohman 公式考慮重複存取同一頁時的快取效果（受 影響）。 每個計畫都有 startup cost（輸出第一筆前的成本）與 total cost； 查詢偏好低 startup 的計畫（如 index scan 而非 sort）。

Join 排序

搜尋空間

\(n\) 表 join 的左深樹（每個 join 的右側都是基本表）有 \(n!\) 種順序；允許濃密樹（bushy）則是 \(\frac{(2(n-1))!}{(n-1)!}\) 種—— 10 表就超過 \(1.7 \times 10^{10}\)。System R 只考慮左深樹（適合管線化、內層可用索引），現代系統多數也考慮濃密樹但設上限。

Selinger 動態規劃

  1. 對每個單表，列舉所有存取路徑（seq scan、各索引），記下每種輸出順序的最便宜者。

  2. 對每個大小為 2 的表集合，嘗試所有 join 順序與演算法，只保留每個集合（每種「interesting order」）的最佳子計畫—— 最佳子結構：全域最佳計畫的子計畫也必須是該子集合的最佳。

  3. 重複至大小 \(n\)。複雜度 \(O(3^n)\)（濃密）或 \(O(n \cdot 2^n)\)（左深），遠小於 \(n!\)。

  4. Interesting order：排序過的子計畫雖然較貴，但可能讓上層的 merge join 或 免費——所以不能只留一個。

  5. 預設避免 cross product（沒有 join 條件的組合），除非無其他選擇。

表數太多時

PostgreSQL 在 FROM 中的項目數 \(\le\) （預設 8）時做完整的動態規劃； 超過 （預設 12）則改用遺傳演算法（GEQO）隨機搜尋。 其他系統採貪婪（每次加入成本最低的表）或 Cascades 框架（Graefe 1995；SQL Server、CockroachDB、Calcite 使用）—— 由上而下、以記憶化的轉換規則搜尋，並支援剪枝。Neumann 與 Radke（2018）展示了針對數百表 join 的自適應演算法。

實體計畫的其他決策

  • 避免排序：若某個索引的順序就是 或 的順序，走索引就能省掉排序節點；interesting order 的實際應用。

  • 平行度：表大於 （8 MB）時才考慮 Gather；worker 數依表大小以對數成長。

  • CTE：PostgreSQL 12 起 子查詢預設可被內嵌（inline），除非寫 或被引用多次。

  • 計畫快取：prepared statement 前 5 次用自訂計畫（帶入實際參數），之後若泛型計畫（generic plan）成本不明顯更高就改用它—— 參數分佈傾斜時會踩雷（parameter sniffing），可用 強制。

  • 分割表：規劃期與執行期（run-time）的 partition pruning；partition-wise join/aggregate。

診斷與修正錯誤的計畫

  1. ：找 估計與實際差距最大的節點（以 loops 乘算）。那就是問題源頭，因為錯誤會往上層放大。

  2. 看估計錯的節點是哪種述詞：相關欄位 \(\to\) 擴充統計；函數 \(\to\) 表達式索引；、JSON \(\to\) 考慮 GIN/trigram；過時 \(\to\) 。

  3. 檢查 、——調 （可只在 session 內調）。

  4. 隨機 I/O 的設定是否合理：SSD 上 ； 設為實際記憶體的 50–75%。

  5. 最後手段：改寫查詢（拆成兩段、 阻擋拉平、）或擴充套件 ； 參數只應用於實驗，不要在生產環境永久關閉。

  6. 用 自動記錄慢查詢的實際計畫、 找最耗資源的查詢樣板。

是必讀文件。主要流程： \(\to\) （拉平子查詢、簡化表達式、 ）\(\to\) \(\to\) ： 先 為每個基本表產生 Path（、）， 再 （）動態規劃， 是遺傳演算法。 成本在 ，選擇率在 。最後 把最便宜的 Path 轉為 Plan 樹。

v6 把 v1 的規則式規劃器升級：(1) 指令對每欄收集 n_distinct 與 100-bucket 等高直方圖； (2) 以本章公式估計選擇率；(3) 成本模型採 PostgreSQL 的五個常數；(4) 以左深 Selinger DP 排 join 順序（表數 \(\le 6\)）， 每個子集保留最佳與每個 interesting order 的最佳；(5) 實作 印出估計與實際列數。 這會讓你親身體會「估計錯誤如何沿樹向上放大」。

  1. 表 有 100 萬列、 欄 MCV 為 {active: 0.9, closed: 0.08}、n_distinct = 5。估計 、、 的列數。

  2. 承上， 的直方圖有 100 個 bucket， 落在第 73 個 bucket 的 40% 處。 估計 與加上 後的列數；指出所用假設。

  3. 以本章的常數計算：表 5000 頁、50 萬列、索引高度 3、條件選擇率 0.001、相關性 0（全隨機）， Index Scan 的粗略成本是多少？與 Seq Scan 相比何者勝出？若 呢？

  4. 4 表鏈狀 join \(A \bowtie B \bowtie C \bowtie D\)（只有相鄰表有 join 條件），列出 Selinger DP 第 2 層與第 3 層需要評估的子集合（排除 cross product）。

  5. 為什麼 既無法使用 上的索引、估計又不準？寫出等價且可 sargable 的條件。

  6. （動手）建立兩個高度相關的欄位並載入資料，比較 前後 的估計列數與選用的 join 演算法。