DBMS將SQL語句轉(zhuǎn)換為查詢計劃。 Operator被安排在Tree上。 數(shù)據(jù)從葉子流向根。 樹中根節(jié)點的輸出是查詢的結(jié)果。通常運算符是二元的（1-2個孩子）。 可以以多種方式執(zhí)行相同的查詢計劃。 大多數(shù)DBMS都希望盡可能多地使用索引掃描。
處理模型
處理模型分為3類，迭代模型，主要是自頂向下的。物化模型，是自底向上的。矢量模型，像迭代模型一樣通過next來交互，但是是批量發(fā)送數(shù)據(jù)，也是自頂向下的。
在大多數(shù)dbms的系統(tǒng)都支持迭代模型，物化模型更加適合oltp而非olap。而矢量模型是olap的理想選擇。
我們來看下幾個模型。
迭代模型
所有的代數(shù)運算符(operator)都被看成是一個迭代器，它們都提供一組簡單的接口：open()—next()—close()，查詢計劃樹由一個個這樣的關(guān)系運算符組成，每一次的next()調(diào)用，運算符就返回一行(Row)，每一個運算符的next()都有自己的流控邏輯，數(shù)據(jù)通過運算符自上而下的next()嵌套調(diào)用而被動的進行拉取。
每一個運算符都將下層的輸入看成是一張表，next()接口的一次調(diào)用就獲取表中的一行數(shù)據(jù)，這樣設(shè)計的優(yōu)點是：
- 每個運算符之間的代數(shù)計算是相互獨立的，并且運算符可以伴隨查詢關(guān)系的變化出現(xiàn)在查詢計劃樹的任意位置，這使得運算符的算法實現(xiàn)變得簡單并且富有拓展性。
- 數(shù)據(jù)以row的形式在運算符之間流動，只要沒有sort之類破壞流水性的運算出現(xiàn)，每個運算符僅需要很少的buffer資源就可以很好的運行起來，非常的節(jié)省內(nèi)存資源。
但是這種運算符的嵌套模型也有它的缺點：
迭代模型的流控是一種被動拉取數(shù)據(jù)的過程，每行數(shù)據(jù)流向每一個運算符都需要額外的流控操作，所以數(shù)據(jù)在操作符之間的流動帶來了很多冗余的流控指令。
運算符之間的next()調(diào)用帶來了很深的虛函數(shù)嵌套，編譯器無法對虛函數(shù)進行inline優(yōu)化，每一次虛函數(shù)的調(diào)用都需要查找虛函數(shù)表，同時也帶來了更多的分支指令，復(fù)雜的虛函數(shù)嵌套對CPU的分支預(yù)測非常不友好，很容易因為預(yù)測失敗而導(dǎo)致CPU流水線變得混亂。這些因素都會導(dǎo)致CPU執(zhí)行效率低下。
物化模型
這個模型主要就是底層開始驅(qū)動，把需要的數(shù)據(jù)一次性準備好喂給上層。缺點就是直接大批量的數(shù)據(jù)傳輸，所以不太適合olap這種在大數(shù)據(jù)集里分析的操作。
矢量模型
是迭代模型的升級版，從單個拉數(shù)據(jù)到批量?？梢杂行p少每一個operator invoke的次數(shù)。
數(shù)據(jù)獲取方式
當數(shù)據(jù)庫管理系統(tǒng)想要獲取數(shù)據(jù)。需要去找。有3種查找方式。
分別是順序掃描，索引掃描，和多索引掃描。
順序掃描
顧名思義就是一個一個page查，每個page一個一個查條目。
為了提速，有如下優(yōu)化方式。
?預(yù)?。禾崆矮@取下幾頁，以便DBMS在訪問每個頁面時不必阻塞。
?并行化：并行使用多個線程/進程執(zhí)行掃描。
?緩沖池旁路：掃描線程將從磁盤獲取的頁面存儲在其本地內(nèi)存而不是緩沖池中。這避免了順序泛濫問題。
?Zone map：預(yù)先計算頁面中每個元組屬性的聚合。然后，DBMS可以通過首先檢查其區(qū)域映射來檢查是否需要訪問頁面。每個頁面的區(qū)域地圖是存儲在單獨的頁面中，每個區(qū)域映射頁面中通常有多個條目。因此，可以減少順序掃描中檢查的總頁數(shù)。
?延遲實現(xiàn)：每個Operator傳遞下一個Operator所需的最少量信息（例如，記錄ID）。這僅適用于列存儲系統(tǒng)（即DSM）。
?堆群集：使用群集索引指定的順序?qū)⒃M存儲在堆頁面中。
索引掃描
DBMS選擇一個索引（或多個索引）來查找查詢所需的元組。
使用多個索引時，DBMS會對每個索引執(zhí)行搜索并生成一組匹配的記錄ID。 可以使用位圖，哈希表或布隆過濾器來實現(xiàn)此記錄ID。 DBMS基于查詢的謂詞（并集與交叉）組合這些集合。 然后它檢索記錄并應(yīng)用任何剩余的條款。 這在Postgres中稱為位圖掃描。
按照它們在非聚簇索引中出現(xiàn)的順序檢索元組是低效的。 DBMS可以首先找出它需要的所有元組，然后根據(jù)它們的頁面ID對它們進行排序。
在非聚集索引上掃描的問題
