資料庫架構
從整體資料庫架構來看，我們可以知道分為網絡協定層、優化器層、執行器、存儲，詳見下圖：
SQL從用戶端發送到資料庫服務端，經過解析器、文法語義分析、邏輯優化和實體優化，從一個字元串轉換為解析樹、文法樹到最終的執行計劃，那麼最終是如何變成機器可以執行的操作呢，本文重點就是來講執行器的一些重要元件和原理。
執行器
我們先來了解下重要的一個查詢的執行過程：
一個查詢SQL變成執行計劃後，既然叫執行計劃，那麼它一定可以序列化成一系列的操作。執行計劃就是由一堆操作符組成的，每個操作符對應的執行個體對象就是一次操作符作用在一組資料上的調用。一次任務就是一系列這樣的一個或多個操作符執行個體的執行。
執行層的優化
我們現在将要讨論的是那些資料集合能夠整個加載到記憶體中的SQL執行過程中可以進行性能優化的方法。當我們不考慮磁盤問題時候，我們還有其他的一些瓶頸。
優化的目标
1: 減少指令數：用很少的指令去做更多的事情
2: 減少每個指令的周期：在較短周期内執行更多的CPU指令，這意味着需要減少由于cache misses和stalls的緩存加載和存儲
3: 并行執行:使用多線程同時并行執行每一條SQL
主要介紹的内容包括：
MonetDB/X100的分析
執行模型
并行執行
MonetDB/X100
MonetDB/X100是從很低角度分析執行瓶頸的一個基于記憶體的OLAP資料庫，它能夠證明現在的資料庫并沒有針對目前CPU的架構體系來進行設計。2010年，被Actian收購後改名叫Vectorwise，後來改稱為Actian Vector和Actian Avalanche。
CPU簡介
CPUs會把很多指令變為流水線的各個階段，目的是通過屏蔽那些在一個周期無法完成的指令，進而讓所有處理器在一個周期内都能夠處于忙碌狀态。Super-scalar CPUs可以支援多流水線，即：
→ 如果指令互相獨立，在一個周期内可以并行執行多個指令。
→ 費林分類: 單處理指令單資料(SISD)
那麼目前資料庫中對于CPU設計的問題有哪些呢？
1: 依賴性：如果一個指令依賴于另一個指令，那麼它們就不能被立即推到同一個流水線裡。
2: 分支預測：CPU嘗試着預測程式中某一個代碼分支，并将其指令填充到一個流水線裡。如果預測失敗，那它需要把所有的推測的工作全部扔掉并重新重新整理流水線。
分支預測失敗
對于長流水線，CPUs通常都會推測執行的代碼分支，這裡潛在的隐藏了那些互相依賴的執行之間的等待。在資料庫領域，在一個順序掃描中，最多執行的代碼分支是filter操作，但是這個幾乎不可能預測準确。
選擇查詢掃描
SELECT * FROM table
WHERE key >= $(low)
AND key <= $(high) 下圖可以看到，這條SQL如何通過分支的和無分支的方式進行掃描
那麼看看效果，無分支較為穩定，而有分支的情況下随着SQL選擇率不同表現出不同CPU指令數量的不同
過度指令
資料庫需要支援不同的資料類型，是以它在對值進行執行任何操作的時候必須去檢查值的類型，這樣導緻了巨大的選擇語句，而且CPU都無法預測每一個代碼分支。比如Postgres的NUMERIC類型.
資料庫的執行模型說明了資料庫如何執行SQL的執行計劃，不同工作的負載有不同的權衡：
1: 疊代模型（Iterator Model）
2: 物化模型（Materialization Model）
3: 向量化/批處理模型（Vectorized / Batch Model）
疊代模型
執行計劃中的每個操作符都需要實作next函數，每一次調用，操作符都傳回一個tuple或者EOF。實作loop的操作符，可以去調用子操作符的next來擷取tuples并行進行處理。這個模型也叫火山模型或者流水線模型。
幾乎所有的資料庫都可以支援tuple的流水化處理，一些操作符可能需要等待它的子操作符傳回所有的元組才能繼續執行，比如Joins, Subqueries, Order By。這種模型對外輸出是非常容易的。
下面是支援這種模型的資料庫：
物化模型
每一個操作符需要一次性處理很多，然後一次一并對外輸出。操作符物化把自己的輸出當成一個單獨的結果。資料庫系統也可以把一些建議下推減少太多的tuples。它可以支援發送一個物化的行或者一個列資料。輸出可以是多行(NSM)或者多列(DSM)。
這種模型更适合OLTP負載，因為那些查詢隻一次通路小規模的資料，更小的執行和協調的消耗，更少的函數調用。如果對于那些中間結果集很大的OLAP負載是不适合的。
: 向量化和批處理模型
像疊代模型一樣，每個操作符都實作了next函數，但是每個指令在内部都一次循環處理多個tuples，每次批處理的大小都取決于迎接或者查詢的屬性。
這種模型是OLAP查詢的理想模型，因為它們極大的減少了操作符數量，可以允許操作符使用向量化指令去批量處理tuples，也可以認為是SIMD方式。
執行計劃的處理方式
1: 自頂向下（Top-to-Bottom）：開始從頂端從子操作符拉資料，元組通常要通過所有的函數調用。
2: 自底向上（Bottom-to-Top）：開始從葉子推送資料到它們的父操作符，允許更嚴格的控制流水線中的緩存和寄存器。
INTER-QUERY并行
通過允許同時執行多個查詢來改進整個的性能，通過并發控制方案去提供一個隔離的錯覺，很難提供一個并發的方案不去極大的影響資料庫的處理模型。
INTRA-QUERY并行
通過并行執行操作符來改進單查詢的性能。
1: Intra-Operator (Horizontal)
2: Inter-Operator (Vertical)
這些技術并不是互相排斥的，每個關系操作符都有相應的并行算法。
Intra-Operator (Horizontal)
操作符并分解成互相獨立的執行個體，用同一函數處理資料的不同子集。資料庫用exchange操作符來合并自操作符的結果。
Inter-Operator (Vertical)
→ 操作是重疊的，目的是讓資料從一個階段流到下一個階段，而不進行物化，也叫流水線并行。這種在傳統資料庫并不常見。不是所有操作符都能夠把結果集輸出，直到它們能夠接收到子操作符的所有tuples，這種方式更多出現在流式處理系統中。
比如下列資料庫：
這是它們的處理方式：
查詢計劃采用正确數量的workers取決于CPU cores、資料量及對應操作符的功能實作。
Worker的配置設定方式
1: 每Core一個Worker：每個core可以綁定到一個線程上，參考sched_setaffinity
2: 每Core多個Workers：每個core或者socket可以用在worker池中，允許CPU cores充分被利用。
TASK配置設定方式
1: Push：一個中心的配置設定器，配置設定任務到各個workers，并監控它們的執行過程。當有worker完成任務後，通知配置設定器配置設定下一個任務。
1: Pull：workers從隊列中取下一個任務并處理，完畢後再處理隊列中下一個任務。
最後的思考
最簡單的方式是實作對現代CPUs的架構不會總是産生最有效的政策。我們可以看到向量化/自底向上的執行是執行OLAP查詢最好的方式。
參考連結和文獻：
- 課程原文CMU 15-721 15-查詢執行和處理過程 Query Execution & Processing[- P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005
](
https://15721.courses.cs.cmu.edu/spring2019/papers/15-execution/boncz-cidr2005.pdf) - L. Shrinivas, et al., Materialization Strategies in the Vertica Analytic Database: Lessons Learned, in ICDE, 2013 (Optional)