查詢執行

從 SQL 到結果的管線

Parser 與 AST

Parser 分兩層：詞法分析（lexer）把字串切成 token（關鍵字、識別字、常數、運算子）， 語法分析依文法規則組成抽象語法樹（AST）。以 為例：

AST 只反映語法，還不知道 是哪張表、 是什麼型別——那是 analyzer 的工作， 它查系統目錄把每個名稱綁定到 OID，並為運算子選出正確的實作（）。 Prepared statement 的價值就在這裡：解析與分析（甚至規劃）只做一次，之後以參數重複執行。

邏輯計畫與實體計畫

• 邏輯計畫是第 1 章的關聯代數樹：\(\pi_{name}(\sigma_{age>30}(\mathit{users}))\)。它只說「做什麼」。

• 實體計畫為每個邏輯運算子選定演算法與存取路徑：\(\sigma\) 用 Seq Scan 加 Filter 還是 Index Scan？ \(\bowtie\) 用 Hash Join、Nested Loop 還是 Merge Join？輸出要不要排序？要不要平行？

一個邏輯運算子可能對應多個實體運算子，反之亦然（Index Scan 同時完成 \(\sigma\) 與資料存取）。 最佳化器（第 6 章）就是在實體計畫空間中搜尋。

處理模型

執行器如何在運算子之間傳遞資料，是效能的決定性因素之一：

Volcano / 迭代器模型

Graefe 的 Volcano（1994）定義每個運算子都實作 、、： 根節點呼叫子節點的 拉取一筆 tuple，子節點再向它的子節點拉，直到葉節點的掃描。拉式（pull-based）、一次一筆。

class Executor {
 public:
  virtual void Init() = 0;                       // open
  virtual bool Next(Tuple *out, RID *rid) = 0;   // 回傳 false 表示結束
  virtual ~Executor() = default;                 // close
};

class FilterExecutor : public Executor {
 public:
  void Init() override { child_->Init(); }
  bool Next(Tuple *out, RID *rid) override {
    while (child_->Next(out, rid)) {
      if (predicate_->Evaluate(*out).GetAs<bool>()) return true;   // 只讓符合者通過
    }
    return false;
  }
 private:
  std::unique_ptr<Executor> child_;
  const Expression *predicate_;
};

優點：簡單、組合性極佳（任何運算子都能接任何運算子）、管線化（不需物化中間結果）、 可以提早停止。缺點：每筆 tuple 都要經過多層虛擬函數呼叫，CPU 分支預測差、快取局部性低——在資料都在記憶體的時代成為瓶頸。 PostgreSQL、MySQL、SQLite（以 bytecode VM 形式）、早期多數系統都是 Volcano。

物化模型（Materialization）

每個運算子一次處理全部輸入、產生完整輸出再交給父節點。函數呼叫少，適合 OLTP 的小結果集與記憶體資料庫（VoltDB、早期 MonetDB）； 但中間結果可能極大，不適合 OLAP。

向量化模型（Vectorized / Batch）

MonetDB/X100（Boncz et al. 2005）的洞見：仍用 Volcano 的 ，但每次回傳一批（如 1024–2048 筆）同一欄位的值（向量）， 運算子內部以緊湊迴圈處理整批資料。函數呼叫開銷攤到上千筆、迴圈可被編譯器自動 SIMD 化、資料留在 CPU 快取。 DuckDB（）、ClickHouse、Velox、Snowflake、Databricks Photon 都是向量化引擎（第 13 章）。

推送式與程式碼生成

Neumann 的 HyPer（2011）反其道而行：推式（push-based）——葉節點把 tuple 推給父節點； 並把整條管線（pipeline）編譯成機器碼（LLVM），使資料盡量留在暫存器中直到遇到 pipeline breaker（排序、雜湊建表、聚合）。 產生的程式碼接近手寫 C++。代價是編譯延遲（毫秒級，對短查詢不划算）與實作複雜度。 PostgreSQL 11 起以 LLVM JIT 編譯表達式求值與 tuple 解構（，由成本門檻 控制），但運算子仍是 Volcano。

存取方法

葉節點負責把資料從儲存引擎拉出來：

• Seq Scan：依序讀 heap 的每一頁，對每筆 tuple 套用 Filter。成本 \(\approx\) 頁數 \(\times\) 循序 I/O。永遠可用，對小表或低選擇性查詢反而最快。

• Index Scan：以索引找到 TID，逐筆回 heap 取 tuple。高選擇性時極快，但 heap 存取是隨機 I/O。

• Index Only Scan：全部欄位都在索引中、且 VM 顯示頁面 all-visible 時，完全不碰 heap（第 3 章）。

• Bitmap Index Scan + Bitmap Heap Scan：先用一或多個索引收集 TID 建成點陣圖（可對多個索引做 AND/OR）， 依頁號排序後循序讀 heap；中等選擇性的最佳解。點陣圖太大時退化為「每頁一個 bit」的 lossy 模式，需重新檢查條件。

• TID Scan：，直接定址。

Join 演算法

設 \(R\) 有 \(M\) 頁、\(m\) 筆 tuple，\(S\) 有 \(N\) 頁、\(n\) 筆 tuple，緩衝池可用 \(B\) 頁。以下成本以 I/O 頁數計。

Nested Loop Join

for each tuple r in R:            -- 外層（outer）
  for each tuple s in S:          -- 內層（inner）
    if r.key == s.key: emit (r, s)

• 簡單 NLJ：成本 \(M + m \cdot N\)。每筆外層 tuple 都把內層掃一遍，幾乎不可接受。

• Block NLJ：一次讀一塊外層（\(B-2\) 頁），內層每塊只掃一次：\(M + \lceil M/(B-2) \rceil \cdot N\)。外層選小表。

• Index NLJ：內層有索引時，每筆外層 tuple 做一次索引查找：\(M + m \cdot C\)（\(C\) 為一次查找成本，通常 1–3 頁）。 這是 OLTP 中最常見的 join：外層幾筆、內層有主鍵索引。

NLJ 的優點：不需要等值條件（可做任意 \(\theta\)-join）、可管線化、外層很小時無人能敵。

Sort-Merge Join

1. 分別對 \(R\)、\(S\) 依 join 鍵排序（若已有序或有索引可省略）。

2. 兩個游標同步前進：鍵相等就輸出配對（注意重複鍵需要回溯），較小的一方前進。

成本 \(= \text{sort}(R) + \text{sort}(S) + (M + N)\)；排序以外部合併排序計（下一節）。 當輸入已排序、或輸出需要依 join 鍵排序（、後續 merge）時特別划算；也是不等值條件（）之外的範圍 join 友善演算法。

Hash Join

• In-memory hash join：成本 \(M + N\)，是等值 join 的首選。

• Grace / partitioned hash join（雜湊表放不下時）：先用 \(h_1\) 把 \(R\)、\(S\) 各自分割成 \(B-1\) 個桶寫回磁碟， 再逐桶配對（桶內用 \(h_2\) 建表）。成本 \(3(M+N)\)：讀寫各一次分割、再讀一次配對。

• Hybrid hash join：記憶體夠時把第一個分區直接留在記憶體，省掉它的寫回。

• Bloom filter：建表時順便建 bloom filter，probe 端先用它過濾掉大多數不會配對的 tuple，減少雜湊表查找與下推至掃描端。

• 雜湊 join 只支援等值條件、且必須等 build 端全部讀完才能輸出第一筆（pipeline breaker）。

三種 join 的選擇

排序與聚合

外部合併排序

資料放不進記憶體時：第一趟每次讀 \(B\) 頁排序後寫出一個 run（共 \(\lceil M/B \rceil\) 個）； 之後每趟以 \(B-1\) 路合併。總趟數 \(1 + \lceil \log_{B-1} \lceil M/B \rceil \rceil\)，每趟讀寫 \(2M\) 頁。 以 \(B = 1000\) 頁（8 MB）為例，兩趟就能排序 \(B(B-1) \approx 10^6\) 頁（8 GB）。 Top-N heapsort（）只需維護大小 \(N\) 的堆，一趟掃描即可，PostgreSQL 會自動選用。

聚合

• 排序聚合（GroupAggregate）：先依 鍵排序，相同鍵相鄰，一趟掃過即可；輸出天然有序。

• 雜湊聚合（HashAggregate）：以分組鍵為雜湊表鍵，維護每組的累計狀態；不需排序、通常較快， 但群組數太多時雜湊表會超過 ——PostgreSQL 13 起會分區溢出到磁碟（之前會直接超用記憶體）。

• 本質上是沒有聚合函數的分組； 需要額外的去重步驟。

其他運算子與平行執行

• Materialize：把子節點結果暫存，供 nested loop 內層重複掃描。

• Append / MergeAppend：、分割表的子表掃描。

• Limit、Unique、WindowAgg、SetOp、SubPlan（相關子查詢，每筆外層執行一次——常是效能殺手）。

• Gather / Gather Merge：Volcano 論文中的 exchange 運算子——它把平行處理封裝成一個普通的迭代器， 子樹由多個 worker 各跑一份（Parallel Seq Scan 以頁為單位分工、Parallel Hash Join 共享雜湊表）， 結果由 leader 收集。 控制 worker 數。

讀懂 EXPLAIN ANALYZE

EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, count(*)
FROM   customers c JOIN orders o ON o.customer_id = c.id
WHERE  c.country = 'TW'
GROUP  BY c.name;

HashAggregate  (cost=4512.30..4515.30 rows=300 width=40) (actual time=38.1..38.2 rows=287 loops=1)
  Group Key: c.name
  Batches: 1  Memory Usage: 61kB
  Buffers: shared hit=1730
  ->  Hash Join  (cost=27.80..4388.60 rows=24740 width=32) (actual time=0.4..31.9 rows=24611 loops=1)
        Hash Cond: (o.customer_id = c.id)
        Buffers: shared hit=1730
        ->  Seq Scan on orders o  (cost=0.00..3670.00 rows=200000 width=8) (actual time=0.01..12.5 rows=200000 loops=1)
              Buffers: shared hit=1670
        ->  Hash  (cost=24.00..24.00 rows=304 width=32) (actual time=0.3..0.3 rows=287 loops=1)
              Buckets: 1024  Batches: 1  Memory Usage: 27kB
              ->  Seq Scan on customers c  (cost=0.00..24.00 rows=304 width=32) (actual time=0.01..0.2 rows=287 loops=1)
                    Filter: (country = 'TW'::text)
                    Rows Removed by Filter: 2213
                    Buffers: shared hit=60
Planning Time: 0.35 ms
Execution Time: 38.4 ms

閱讀方法：由內而外、由下而上。(1) 掃描 並過濾國家，287 筆進入 Hash 建表（build 端是小表，正確）； (2) 掃描 20 萬筆 probe；(3) 雜湊聚合 287 組，全部在記憶體完成； (4) 是估計、 是毫秒實測、 估計 vs 實際接近表示統計良好； 大於 1 時 actual time 與 rows 是每次的平均，要乘上 loops。 全部命中，沒有磁碟 I/O。