一個查詢計劃由若干個操作組成。
一個任務(wù)task是一系列的（一個或多個）操作的執(zhí)行（如在用pipeline技術(shù)時，一個pipeline的一系列操作叫做task）。

對于一個查詢計劃，DBMS需要決定在哪、何時、如何執(zhí)行：

• 要用多少個tasks
• 要用多少CPU cores
• tasks執(zhí)行在哪個CPU cores上
• task的輸出存哪

進(jìn)程模型

DBMS的Process Model定義了系統(tǒng)的結(jié)構(gòu)如何支持來自多個用戶應(yīng)用的并發(fā)請求。
worker是DBMS組件，代表客戶端執(zhí)行任務(wù)并返回結(jié)果。

• Process per DBMS worker：每個worker就是一個獨立的OS進(jìn)程，依賴系統(tǒng)調(diào)度，對于全局?jǐn)?shù)據(jù)結(jié)構(gòu)用共享內(nèi)存，一個進(jìn)程的崩潰不會導(dǎo)致整個系統(tǒng)的崩潰
• Process Pool：每個worker用pool中空閑的進(jìn)程，仍依賴系統(tǒng)調(diào)度和共享內(nèi)存，不利于CPU cache本地化。因為對于Cache而言，有可能worker的多個線程讀寫同一個數(shù)據(jù)。所有的連接不再和worker連接，而是通過調(diào)度線程進(jìn)行交互和數(shù)據(jù)傳輸
• Thread per worker：一個進(jìn)程包含多個worker線程，DBMS控制調(diào)度，可用可不用dispatcher線程， 線程崩潰可能導(dǎo)致整個系統(tǒng)崩潰

多線程結(jié)構(gòu)的優(yōu)點：上下文切換開銷低，不需要管理共享內(nèi)存

無論用什么進(jìn)程模型，worker操作本地數(shù)據(jù)至關(guān)重要

Processing Model / 處理模型

processing Model定義了系統(tǒng)如何執(zhí)行一個查詢計劃

1. 迭代器模型
   每個查詢計劃執(zhí)行operator都實現(xiàn)了一個next函數(shù)
   每次調(diào)用，operator都會返回一個元組或者沒有元組返回一個空標(biāo)志；operator實現(xiàn)了一個循環(huán)，在它的孩子上繼續(xù)調(diào)用next函數(shù)檢索元組然后進(jìn)行處理。

   
   
   迭代器模型.png
   
   

   每次調(diào)用next函數(shù)都會獲得一個元組，下面的節(jié)點emit提交一個元組。
   迭代器模型在所有的DBMS中都用，允許元組流水線（一次執(zhí)行多條指令？一直執(zhí)行多條元組？），一些操作會阻塞知道孩子提交了所有的元組（如連接，子查詢，排序）
   輸出控制簡單

2. Materialization Model
   每個operator一次處理所有的輸入，然后一次提交輸出
   DBMS把投影進(jìn)行早做防止掃描太多元組；可以發(fā)送行或列。
   輸出可以使整個元組（NSM）或列的集合(DSM).

   
   
   Materialization Model.png

   如圖，每次都是return
   這個更適用于OLTP因為查詢一次只會訪問少量的元組，更低的執(zhí)行開銷，較少的函數(shù)調(diào)用。不適用于OLAP

3. 矢量模型
   像迭代器模型，每個operator都實現(xiàn)了一個next函數(shù)，但是每個operator都提交批量的元組而不是一個元組。
   

   operator的內(nèi)部循環(huán)會同時處理多個元組；批量的大小基于硬件和查詢屬性
   Vectorization Model.png
   適用于OLAP查詢，因為可以極大地每個operator的調(diào)用

plan處理方向

1. 自頂向下：從根開始執(zhí)行，從孩子pull數(shù)據(jù)；元組隨著函數(shù)調(diào)用傳遞
2. 自底向上：從葉子節(jié)點開始把數(shù)據(jù)push給父節(jié)點；可以對pipeline的緩存和寄存器進(jìn)行更嚴(yán)格的控制

內(nèi)存訪問

無論用什么進(jìn)程模型，worker操作本地數(shù)據(jù)至關(guān)重要
如何讓worker操作本地數(shù)據(jù)

硬件內(nèi)存分布

• 一致內(nèi)存訪問：若干個CPU-Cache與系統(tǒng)總線相連，若干塊內(nèi)存與總線相連，CPU通過總線訪問內(nèi)存。 優(yōu)點是每個CPU的核訪問存儲數(shù)據(jù)的時間比較穩(wěn)定，缺點是每次只能有一個CPU核去訪問存儲的數(shù)據(jù)，因為總線總是會占用，擴(kuò)展能力較差
• 非一致內(nèi)存訪問：CPU之間內(nèi)部相連，每個CPU連有若干塊內(nèi)存。訪問自己的內(nèi)存很快，訪問別人的內(nèi)存很慢。

數(shù)據(jù)的存儲位置

對于NVMA而言，DBMS可以把數(shù)據(jù)庫分塊使得每一部分塊對應(yīng)一個CPU，放入對應(yīng)CPU的內(nèi)存中。通過控制和track分區(qū)的位置，DBMS就可以調(diào)度操作在離它最近的CPU core上執(zhí)行

page fault：訪問內(nèi)存未命中

內(nèi)存的分配

DBMS調(diào)用malloc時發(fā)生什么假設(shè)沒有allocator可以釋放的內(nèi)存塊？
allocator擴(kuò)展進(jìn)程的數(shù)據(jù)段，但只會給一個地址；新的虛擬內(nèi)存不會立即得到物理內(nèi)存的支持；只有當(dāng)CPU訪問這塊地址發(fā)生了page fault之后才會配分物理內(nèi)存。

但是發(fā)生page fault之后物理內(nèi)存分配到NUMA系統(tǒng)的哪里呢？

1. 交錯：跨CPU均勻的分配內(nèi)存
2. 分配在 線程訪問內(nèi)存導(dǎo)致page fault所在的CPU上

partitioning是基于一些策略把數(shù)據(jù)庫劃分，placement是告訴DBMS把劃分出的每一部分放在哪里

Worker的分配模型

根據(jù)CPU內(nèi)核數(shù)量，數(shù)據(jù)的大小以及worker的功能進(jìn)行，提供合適數(shù)量的worker完成查詢計劃

1. one worker per Core：每個core分配一個固定在內(nèi)核中一個線程
2. Multiple Worker per Core：每個core有一個worker池；當(dāng)一個worker阻塞時保證CPU充分利用；

Task分配模型

1. Push：一個中心分配器線程分配task給workers，并監(jiān)視他們的進(jìn)程；當(dāng)worker通知分配器完成了，再分配新的任務(wù)
2. Pull：worker從一個task隊列中pull一個task，處理，返回結(jié)果，get下一個task

把邏輯查詢轉(zhuǎn)化為Tasks

如何從一個邏輯查詢計劃創(chuàng)建一個任務(wù)集合？

靜態(tài)調(diào)度

DBMS產(chǎn)生查詢計劃時決定要用多少個線程執(zhí)行，查詢時不變。
最簡單的方式就是有多少個CPU核心就用多少個任務(wù)；也可以基于數(shù)據(jù)的定位來分配任務(wù)到相應(yīng)的線程來實現(xiàn)最大的本地數(shù)據(jù)處理。

Morsel驅(qū)動的調(diào)度

執(zhí)行在跨核心分布的水平劃分運行的一種task的動態(tài)調(diào)度：one woker per core，pull-based task assginment, Round-robin data placement
優(yōu)化數(shù)據(jù)集完全適合內(nèi)存的DBMS查詢優(yōu)化
解決沒有硬盤后的其他瓶頸

混合結(jié)構(gòu)

沒有單獨的調(diào)度線程，線程為每個查詢計劃協(xié)作調(diào)度。
……

優(yōu)化的目標(biāo)：減少指令數(shù)，用更少的執(zhí)行執(zhí)行相同的操作；減少每個指令的周期，用更少的周期執(zhí)行更多的CPU指令；并行執(zhí)行，用多個線程并行執(zhí)行一個查詢

訪問路徑的選擇
是進(jìn)行連續(xù)的掃描還是用索引掃描來檢索表中的數(shù)據(jù)。這取決于謂詞的選擇性、硬件性能和并發(fā)性。

MONETDB/X100

CPU流水線——目標(biāo)是通過隱藏來自無法在此周期完成的指令的delay，保持處理器所有部分在每個周期都busy。
流水線與超標(biāo)量CPU
超標(biāo)量CPU支持多流水線，如果指令間是獨立的，那么可以在一個周期內(nèi)并行執(zhí)行多條指令。

DBMS/CPU 問題：

1. 依賴：如果一條指令依賴另一條指令，它就不能直接被pushed到同一個流水線。
2. 分支謂詞：CPU會對跳轉(zhuǎn)指令進(jìn)行預(yù)測，把預(yù)測的部分加入流水線，預(yù)測錯誤需要把這些預(yù)測錯誤的東西丟掉flush流水線。
   DBMS中最常執(zhí)行的分支操作是在連續(xù)掃描中的過濾操作，這幾乎是不可能正確預(yù)測的。

DBMS需要支持不同的數(shù)據(jù)類型，所以在對值進(jìn)行任何操作前都需要檢查數(shù)據(jù)的類型，通常用大量的switch語句實現(xiàn)，這也創(chuàng)造了更多的分支，對于CPU預(yù)測太難了

branching通過if判斷是否進(jìn)入一個分支，如果不進(jìn)入需要刷新管道，對CPU不友好；Branchless對于所有的數(shù)據(jù)都進(jìn)行傳輸，因為都在內(nèi)存中又用了管道技術(shù)，所以耗時較短，CPU可以直接順序執(zhí)行。

查詢的并行性

Inter_Query 并行

并行執(zhí)行多個查詢，用并發(fā)控制協(xié)議提供隔離
并發(fā)控制協(xié)議并不受DBMS進(jìn)程模型的大的影響

Intra_Query并行

把一個查詢的多個操作并發(fā)執(zhí)行
實現(xiàn)上有水平的和垂直的兩種，并不沖突，而且每個操作都有自己的并行算法

Intra-Operator Horizontal.png

Intra-Operator并行.png