從 Relational Algebra 到 Physical Operators：查詢成本從哪裡來

SQL 描述要得到的結果；relational algebra 把結果表示成 logical operator tree；physical operator 再決定如何用 page、memory、index、sort 與 hash 產生結果。

同一個 logical expression，有很多執行方法

π name (
  σ topic = 'databases' (
    Researcher ⋈ PaperAuthor ⋈ Paper
  )
)

Projection π、selection σ 與 join ⋈ 描述 meaning，不規定 join algorithm 或執行順序。

白話來說： Relational algebra 說 intermediate result 代表什麼；physical plan 說要用哪些 loop、hash table 和 page read 把它做出來。

Scan 決定輸入成本

Sequential scan 讀取 relation 的每個 page，未 cache 時約是 B(R) 次 I/O。Index scan 先走 index，再視情況讀 table page。只有省下的工作大於 random access 與 lookup overhead 時，index 才會贏。

只移除 column 的 projection 可以 pipeline；需要去重的 projection 必須 hash 或 sort，因此需要額外 memory 與 I/O。

Join algorithm 各有前提

對 relations R 和 S：

Tuple nested loop： 簡單，但每個 R row 都重掃 S 時非常昂貴。
Block nested loop： 用 memory page 分批處理 outer relation。
Index nested loop： Outer 很小且 inner 有 selective index 時有效。
Hash join： 適合 equality join，通常對較小 input 建 hash table。
Sort-merge join： Input 已排序，或 ordered output 有價值時適合。

使用 M 個 memory page 的簡化 block nested-loop cost：

B(R) + ceil(B(R) / (M - 2)) × B(S)

讓較小 relation 當 outer，可以減少重掃次數。

One-pass 與 two-pass

Working state 放得進 memory 時，operator 可以 one-pass，例如先把小 relation hash 後再 probe。放不下時，two-pass algorithm 必須先 partition 或 sort 到 disk，再逐區處理。

Memory threshold 會形成 cliff：小幅 cardinality estimation error，就可能讓 in-memory hash 變成 disk spill。

Pipeline 或 materialize

Pipelining 直接把 row 傳給下一個 operator，減少 temporary storage。Materialization 會寫 intermediate result，增加 I/O，但 sort、重複使用、blocking aggregation 或 plan boundary 有時需要它。

從下往上讀 plan

最下面 node 產生 rows，parent 再消費。每個 node 都問：

進出多少 rows？
Operator 是 blocking 還是 streaming？
是否建立 memory state 或 spill？
loops 讓它重複幾次？

複習卡

Logical operator 定義 meaning；physical operator 定義工作量。
計算 page，不只計 rows。
Index 只有在省下足夠 table work 時才有用。
Join algorithm 取決於 size、memory、predicate 與 index。
Spill 會把 memory operator 變成額外 I/O passes。
Execution plan 從 leaf 往上讀。