本節課深入探討了數據庫系統如何執行查詢計劃，特別是涉及到的查詢處理模型、數據訪問方法以及表達式評估機制。理解這些概念對于優化數據庫性能和理解查詢執行的底層原理至關重要。

查詢計劃處理模型

數據庫管理系統（DBMS）的查詢計劃處理模型定義了它如何執行查詢計劃。這些模型各有優缺點，適用于不同的工作負載和運行環境。

迭代模型（Iterator Model）

也叫火山模型（Volcano Model）/ 流水線模型（Pipeline Model）。

• 這是最常見的處理模型，幾乎所有數據庫系統都采用此模型，特別是基于行的系統。
• 其核心思想是，查詢計劃中的每個操作符（如連接、排序等）都實現了一個 Next() 函數。當一個父節點調用其子節點的 Next() 函數時，子節點會返回 一個元組 （tuple），或者在沒有更多元組時返回一個空標記。這種機制使得數據能夠像 流水線一樣 在操作符之間流動，單個元組可以盡可能遠地在查詢計劃中向上處理，從而最大化內存中元組的工作量，這在基于磁盤的系統中尤為重要，因為磁盤I/O非常昂貴。
• 盡管該模型支持高效的流水線處理，但某些操作符無法在接收到所有子元組之前繼續處理，它們被稱為 管道阻塞點（Pipeline Breakers） 。常見的管道阻塞點包括： 連接（Joins） 、 子查詢（Subqueries） 和  ORDER BY 操作 。例如，一個哈希連接在探測階段之前必須先構建完整的哈希表。
• 迭代模型易于理解和推理，并且與 LIMIT 子句等輸出控制機制配合得很好。

物化模型（Materialization Model）

• 該模型是迭代模型的一個 專用版本 ，主要用于內存數據庫系統。
• 與迭代模型每次返回一個元組不同，物化模型中的每個操作符會 一次性處理所有輸入數據，然后一次性地發出所有輸出數據 。這意味著操作符會“物化”其全部結果作為一個單一的輸出。一旦操作符完成執行并返回其結果緩沖區，DBMS就無需再返回它來獲取更多數據。
• 這種方法對于 OLTP（在線事務處理）工作負載非常適用 ，因為OLTP查詢通常只訪問少量元組。這樣可以減少函數調用的開銷。
• 然而，它 不適合處理具有大量中間結果的OLAP（在線分析處理）查詢 ，因為這可能導致DBMS不得不將這些中間結果溢出到磁盤，從而降低性能。

向量化模型（Vectorized / Batch Model）

• 向量化模型 基于迭代模型 ，但進行了優化。
• 在每次調用 Next() 函數時，操作符不是返回一個元組，而是返回 一個批次（batch）或向量（vector）的元組 。
• 系統被設計成操作符的內部循環可以直接處理一整批元組，而不是逐個元組處理。批次的大小可以根據硬件和查詢特性進行調整。
• 這種方法 非常適合OLAP查詢 ，因為它們通常需要掃描大量元組，減少了 Next() 函數的調用次數。此外，它還允許操作符利用 向量化（SIMD）指令 來高效處理元組批次，極大地提升了性能。現代大型數據倉庫系統廣泛采用此模型.

除了上述模型，查詢計劃的執行方向通常是 從頂向下（Top-to-Bottom） ，即從根節點開始，并從其子節點“拉取”數據。但也存在 從底向上（Bottom-to-Top） 的方法，它允許更精細地控制CPU緩存和寄存器中的數據流，盡管這種方法對人類程序員來說更難理解和實現。

數據訪問方法（Access Methods）

數據訪問方法定義了DBMS如何從表中檢索數據。它們是查詢計劃中的葉子操作符，負責將數據“喂給”上層的操作符。

順序掃描（Sequential Scan）

• 這是最基本的訪問方法，DBMS會遍歷表中的 每一個數據頁 ，將其從緩沖區池中取出。然后，它會遍歷該頁中的每一個元組，并評估謂詞（WHERE子句）以決定是否包含該元組。DBMS會維護一個內部游標來跟蹤已檢查的最后一個頁面和槽位。
• 優化措施 ：盡管順序掃描在沒有索引時是唯一的選擇，但它在基于磁盤的系統中通常性能很慢。因此，有多種優化方法來提升其效率：

預取（Prefetching） ：提前獲取后續的幾個數據頁，避免在需要時阻塞等待I/O。

緩沖區池旁路（Buffer Pool Bypass） ：掃描操作符將從磁盤獲取的頁面存儲在其本地內存中，而不是污染共享的緩沖區池緩存，從而避免“順序泛洪”問題。

并行化（Parallelization） ：使用多個線程或進程并行執行掃描操作。

區域圖（Zone Maps） ：對每個數據頁中的屬性值預先計算聚合信息（如最小值、最大值、平均值等）。在訪問頁面之前，DBMS首先檢查區域圖，如果區域圖指示該頁面不可能包含滿足條件的元組，就可以 跳過整個頁面 的讀取，從而大大減少磁盤I/O。然而，區域圖的 維護成本較高 ，不適用于高更新頻率的OLTP系統，但對于“一次寫入，多次讀取”的OLAP工作負載非常有用。

延遲物化（Late Materialization） ：在列式存儲系統（DSM）中，可以延遲拼接完整元組的時機。操作符只傳遞最少必要的信息（例如記錄ID）給下一個操作符，只有當上層查詢計劃需要實際數據時，才回表獲取完整元組數據。這避免了不必要的數據移動，尤其是在僅需要部分列的情況下。

堆聚簇（Heap Clustering） ：如果元組在堆頁中按照聚簇索引的順序存儲，DBMS可以直接跳轉到需要的頁面，從而實現順序訪問。

索引掃描（Index Scan）

• DBMS選擇一個或多個索引來快速定位查詢所需的元組，從而 減少不必要的工作量 。
• 選擇最佳索引是復雜的，取決于索引中包含的屬性、查詢中引用的屬性、屬性值的分布、謂詞的類型（如小于、大于、等于）以及索引是否唯一等因素。
• 多索引/位圖掃描（Multi-Index / Bitmap Scan） ：當查詢條件可以利用多個索引時，DBMS會分別在每個匹配的索引上執行查找，生成匹配的記錄ID集合。然后，根據查詢的謂詞（AND子句使用 交集 ，OR子句使用 并集 ）將這些集合進行組合。最后，DBMS根據組合后的記錄ID去檢索實際的元組并應用任何剩余的謂詞。Postgres稱之為“位圖掃描”，它通常使用位圖、哈希表或Bloom過濾器來實現集合操作。
• 二級索引回表隨機I/O優化（Index Scan Page Sorting） ：對于 非聚簇索引（unclustered index） ，通過索引掃描獲取記錄ID后，由于元組在磁盤上的存儲順序可能與索引的邏輯順序不同，直接回表可能會導致大量 隨機I/O ，效率低下。為了解決這個問題，DBMS可以 先通過索引掃描，收集所有滿足條件的記錄ID 。然后， 不立即回表，而是根據這些記錄ID所在的頁面ID進行排序 。這樣，當實際去讀取數據頁時，相關的元組將集中在少數幾個頁面中，從而將大量的隨機I/O轉換為更高效的 順序I/O ，每個頁面只需讀取一次。

表達式評估（Expression Evaluation）

DBMS將SQL查詢中的 WHERE 子句等謂詞表示為 表達式樹（Expression Tree） 。樹中的節點代表不同類型的表達式，如比較運算符、邏輯運算符（AND/OR）、算術運算符、常量值和元組屬性引用等。

• 評估過程 ：在運行時評估表達式樹時，DBMS會維護一個上下文句柄，其中包含當前正在處理的元組、查詢參數和表模式等元數據。然后，DBMS會 遍歷表達式樹 （通常是深度優先），從葉子節點開始，計算出中間值并向上層節點傳遞，直到根節點產生最終的布爾結果（真或假），以判斷元組是否匹配謂詞。
• 性能瓶頸與JIT編譯 ：雖然表達式樹在概念上易于理解和實現，但對于 大量數據（例如數十億行） ，每次評估一個元組時都重復遍歷表達式樹會變得 非常慢 。因為每次遍歷都需要進行函數調用、分支跳轉、類型檢查和運算符調度等開銷。
• 為了解決這個問題，高端數據庫系統采用了 即時編譯（Just-In-Time Compilation, JIT） 技術。JIT編譯可以將表達式樹 直接編譯成機器碼指令 ，這些指令可以非常高效地在CPU上執行，從而避免了重復的樹遍歷開銷。一些先進的系統甚至可以將整個查詢計劃編譯成一條指令流水線，進一步減少間接跳轉，使得查詢執行如同手動編寫并編譯的代碼一樣高效。

總結 ：本節課強調，數據庫查詢計劃的執行方式有多種，具體取決于數據庫系統所處的環境和所處理的工作負載。在大多數情況下，DBMS會盡可能優先使用索引掃描。而表達式樹雖然靈活易懂，但在處理大量數據時會因其解釋執行的特性而變得緩慢，因此通過 JIT編譯 將其優化為原生機器碼是提升性能的關鍵。