Query Execution
Processing model
DBMS 的 processing model 定義了系統如何執行 query plan ，主要包含了三種模型 :
- Iterator Model
- Materialization Model
- Vectorized / Batch Model
Iterator Model
Iterator 模型，也被稱為 Volcano model 或 Pipeline model，是最常見的 processing model，幾乎每個 row-based 的 DBMS 都有使用這種模型。
這個模型的核心是讓每個資料庫 operator 都實現一個 Next 函數，使查詢計畫中的每個節點在需要資料時，能夠向其子節點請求下一個 tuple (如果資料已經回傳完畢則返回 null)，直到查詢計畫的葉節點發出資料為止。
Iterator 模型支持 pipelining ，這代表 DBMS 會盡量對 tuple 進行處理，然後在處理下一個 tuple。有些 operator (如 join、subquery 和 ORDER BY 等) 在處理時會阻塞直到它們的所有子節點都發出資料為止，這類操作符被稱為 Pipeline Breakers。
Materialization Model
每個 operator 都有一個 output 函數，會一次性處理完所有 input 並將結果一次性返回，輸出可以是 DSM 或 NSM 的形式。
這種方法更適合 OLTP 系統，因為 OLTP 通常只須回傳少量資料，可以減少調用 Next 函數的次數。
Vectorized / Batch Model
Vectorized / Batch Model 是一種 iterator 和 materialization 的混合模型，在調用 Next 函數時，會一次性回傳一批 tuple，可以根據硬體條件來調整 batch 的大小。
這種方式適合於 OLAP 系統，可以減少調用 Next 函數的次數，並且可以使用 SIMD 指令集來批量處理 tuple。
Access Methods
access method 是指 DBMS 從 table 中獲得資料的方式，主要有以下幾種 :
- Sequential Scan
- Index Scan
- Multi-Index Scan
Sequential Scan
sequential scan 指的是 DBMS 逐行讀取 table 中的所有資料，通常效能會較差，DBMS 會維護一個 cursor 來記錄當前讀取的位置。
有許多的優化方法可以提升 sequential scan 的效能，如 :
- Prefetching
- Buffer Pool Bypass
- Parallelization (本節)
- Late Materialization
- Heap Clustering
- Data Skipping (本節)
Data Skipping
有兩種方法可以實現 data skipping :
- Approximate Queries (有損的) : 在表中選取一個子集，並生成近似的結果
- Zone Maps (無損的) : 在每個 page 上維護一個 metadata (如平均值、最大最小值)，可以快速判斷是否包含需要的資料或是是否需要訪問這個 page
Index Scan
DBMS 會選擇一個索引來幫助查詢，選擇的依據如下 :
- index 包含了那些屬性
- query 中包含了那些屬性
- 屬性的範圍
- 謂詞組合 (AND、OR)
- 索引鍵是否唯一
Multi-Index Scan
有些資料庫支援多索引的查詢，可以透過多個索引來將找出每個對應的 record id ，並且將他們集合起來。
如 PostgreSQL 的 Bitmap Index Scan，MySQL 的 Index Merge 等。
Modification Queries
DBMS 中的 modification 主要包含 INSERT、UPDATE 和 DELETE 三種操作，這些操作會影響到 table 中的資料。
在 UPDATE 跟 DELETE 操作中，child operator 會跟蹤已經處理過的 tuple 並返回 record id，而在 INSERT 中有兩種實現方式，一種是自己 materialize tuple，另一種是接收 child operator 的輸出。
如上面的圖，我們有可能會遇到 Halloween Problem，這個問題是指在更新過程中，由於更新後的 tuple 位置可能會改變，所以可能會更新到已經更新過的 tuple。
Expression Evaluation
DBMS 會將 WHERE 條件中的表達式轉換成一個 expression tree，遍歷之後產生結果，可以使用 JIT 編譯技術來加速表達式的計算。
Scheduler
scheduler 的功用是將 data flow 跟 control flow 進行清晰的分離，適合在 batch mode (一次性處理一組資料) 中使用，尤其是在 vectorization model 中。
scheduler 會生成 work order，並將其放入 scheduling queue 中，然後 worker 會從 work queue 中取出 work order 並執行。
Parallel vs Distributed Databases
在前面的討論中，我們都只專注在 single worker 的環境下，但是在現實中，我們會需要多個 worker 來平行處理 query。
在平行或分散式的系統中，資料庫會分布在多個資源中來提高 parallelism，這些資源可以是多個 CPU、多個硬碟、多個機器等，但在使用者的角度，這應該跟一個單一的資料庫是一樣的。
- Parallel Database
- 物理連結較近，且 溝通快
- 通訊成本較小
- Distributed Database
- 節點之間相距較遠
- 通訊成本較大
Process Model
process model 定義了 DBMS 的多用戶平行處理的架構，我們會用 worker 這個詞來代表執行的單位，它可以是一個 process 或 thread。
Process per Worker
client 端的請求經過 dispatcher 後會由 dispatcher 分配一個 worker 來處理，每個 worker 都是一個獨立的 process。
- 依賴於作業系統的 scheduler
- 使用 shared memory 來儲存全局的資料結構
- 單一的 process crash 並不會造成整個系統的 crash
這種 process model 主要出現在 pthread 還沒有穩定的時候，主要是為了解決移植性問題，如舊版的 Oracle 和 DB2 以及現在的 PostgreSQL。
Thread per Worker
DBMS 由一個 process 和多個 worker thread 組成。
- DBMS 通常會自己管理 scheduler
- 可能沒有 dispatcher
- thread crash 可能導致系統崩潰
- 由於使用 thread，context switch 的成本較低，且不需要維護 shared model
這種 process model 是近年來最流行的，如 MySQL、SQL Server、MySQL 以及新版的 Oracle 都支持這種模型。
對於每個 query plan 來說，scheduler 可以決定
- 要被拆成多少個 tasks
- 使用多少個 cpu core
- 將 tasks 分配給哪些 core
- 輸出要被放在哪裡
Embedded DBMS
Embedded DBMS 是一種與傳統 client-server 架構的 DBMS 不同的架構，在這種架構中，DBMS 會直接在跟應用程式相同的 address space 中運行，並由應用程式負責 task 和 scheduler 的管理。
常見的有 SQLite、DuckDB、RocksDB 等。
Inter-Query Parallelism
Inter-Query Parallelism 是指同時執行多個查詢的能力，如果都是 read only 的查詢，那麼不需要多餘的協調，如果有 write 操作，則需要更多的機制來確保一致性。
Intra-Query parallelism
Intra-Query Parallelism 是指通過平行化 來將單個 query 分解成多個 operators 來提升性能。
在這個過程中，每個 operator 都是資料的 producer，也同時是其他 operator 的 consumer，這種設計使得平行算法可以應用於每個 relational operator。
Intra-Operator Parallelism (Horizontal)
將資料拆解成多個子集，並透過 exchange operator 來合併子集處理的結果。
Inter-Operator Parallelism (Vertical)
將 operator 串聯成 pipeline，並由前一個階段不斷地產生 tuple 來供給下一個階段而不用等待整個階段處理完畢，也叫做 pipelined parallelism。
通常會在一些 streaming 的系統中使用，如 Spark、Flink 等。
Bushy Parallelism
Bushy Parallelism 是 Intra-Operator 和 Inter-Operator Parallelism 的混合形式。
Observation
使用額外的 process / thread 來平行執行 query 可以提高 CPU 的利用率，但如果瓶頸出現在 disk I/O 上，那麼這種平行處理就沒有太大的意義，甚至有可能因為 cache miss 而導致效能下降。
I/O Parallelism
I/O Parallelism 是指在 DBMS 中使用額外的進程或執行緒來平行執行查詢，以提高資料存取的效能。這種技術旨在克服硬碟是主要瓶頸的情況，透過將資料庫分散在多個存儲設備上來提高效能。
Multi-Disk I/O Parallelism
在 multi-disk I/O parallelism 中，DBMS 會將資料庫檔案分散在多個硬碟上，這可以使用 RAID 來實現，
Database Partitioning
可以將一個 logical table 分割成多個 physical segments 分開儲存，以提高 I/O 效能。