From Relational Algebra to Physical Operators: Where Query Cost Comes From

SQL states a result. Relational algebra gives that result a logical operator tree. Physical operators decide how to produce it with pages, memory, indexes, sorting, and hashing.

One logical expression, many executions

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

Projection π, selection σ, and join ⋈ describe meaning. They do not require a particular join algorithm or order.

In plain terms: relational algebra says what intermediate results mean; a physical plan says which loops, hash tables, and page reads create them.

Scans establish the input

A sequential scan reads every page of a relation: approximately B(R) I/Os when it is not cached. An index scan first traverses the index, then may visit table pages. It wins only when avoided work exceeds random access and lookup overhead.

Projection can be pipelined if it only drops columns. Duplicate-removing projection requires hashing or sorting and therefore additional memory and I/O.

Join algorithms have different conditions

For relations R and S:

Tuple nested loop: simple, but disastrous when it rescans S for every row of R.
Block nested loop: uses memory pages to process chunks of the outer relation.
Index nested loop: effective when the inner side has a selective index and the outer side is small.
Hash join: strong for equality joins; build a hash table on the smaller input.
Sort-merge join: useful when inputs are already sorted or ordered output is valuable.

A simplified block nested-loop cost with M memory pages is:

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

Making the smaller relation the outer input reduces the number of rescans.

One-pass and two-pass thinking

An operator is one-pass when its working state fits in available memory—for example, hashing a small relation before probing it. When it does not fit, a two-pass algorithm partitions or sorts data to disk, then processes partitions.

The memory threshold creates a cliff: a small cardinality-estimation error can turn an in-memory hash into a spill.

Pipeline or materialize

Pipelining sends rows directly to the next operator and reduces temporary storage. Materialization writes an intermediate result, which costs I/O but may be required for sorting, reuse, blocking aggregation, or plan boundaries.

Read a plan bottom-up

The bottom nodes produce rows. Their parents consume them. For every node ask:

How many rows enter and leave?
Is the operator blocking or streaming?
Does it build memory state or spill?
How many times does loops repeat it?

Review card

Logical operators define meaning; physical operators define work.
Count pages, not only rows.
Index access is useful only when it avoids enough table work.
Join algorithm choice depends on size, memory, predicates, and indexes.
Spilling changes an in-memory operator into extra I/O passes.
Read execution plans from leaves upward.

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 往上讀。