??向量化執(zhí)行和編譯執(zhí)行是目前主流的兩種數據庫執(zhí)行引擎優(yōu)化手段，本文從以下幾個方面對向量化執(zhí)行和編譯執(zhí)行進行淺析。
一、以當代CPU主要特性為背景，引出數據庫執(zhí)行引擎的主要優(yōu)化方向。
二、分別解析向量化執(zhí)行和編譯執(zhí)行的原理，并進行對比(結論主要來自2018VLDB論文[1])。
三、介紹了以ROF[2]為代表的向量化與編譯執(zhí)行融合的技術。

當代CPU特性

??了解CPU特性可以讓我們真正理解各種數據庫執(zhí)行引擎優(yōu)化技術的動機。影響數據庫執(zhí)行引擎執(zhí)行效率的CPU特性主要有以下幾點：超標量流水線與亂序執(zhí)行、分支預測、多級存儲與數據預取、SIMD。

超標量流水線與亂序執(zhí)行

??CPU指令執(zhí)行可以分為多個階段(如取址、譯碼、取數、運算等)，流水線的意思是指一套控制單元可以同時執(zhí)行多個指令，只是每個指令處在不同的階段，例如上一條指令處理到了取數階段，下一條指令處理到了譯碼階段。超標量的意思是指一個CPU核同時有多套控制單元，因此可以同時有多個流水線并發(fā)執(zhí)行。CPU維護了一個亂序執(zhí)行的指令窗口，窗口中的無數據依賴的指令就會被取來并發(fā)執(zhí)行。
??程序做好以下兩個方面，可以提高超標量流水線的吞吐(IPC，每時鐘周期執(zhí)行指令數)。一，流水線不要斷，不需要等到上一條指令執(zhí)行完，就可以開始執(zhí)行下一條指令。這意味著程序分支越少越好(知道下一條指令在哪)。二，并發(fā)指令越多越好。指令之間沒有依賴，意味著更流暢的流水線執(zhí)行，以及在多個流水線并發(fā)執(zhí)行。

分支預測

??程序分支越少，流水線效率越高。但是程序分支是不可避免的。程序分支可以分為兩種，條件跳轉和無條件跳轉。條件跳轉來自if或switch之類的語句。無條件跳轉又可根據指令的操作數為跳轉地址還是跳轉地址指針，分為直接跳轉和間接跳轉。直接跳轉一般為靜態(tài)綁定的函數調用，間接跳轉來自函數返回或虛函數之類動態(tài)綁定的函數調用。
??當執(zhí)行一個跳轉指令時，在得到跳轉的目的地址之前，不知道該從哪取下一條指令，流水線就只能空缺等待。為了提高這種情況下的流水線效率，CPU引入了一組寄存器，用來專門記錄最近幾次某個地址的跳轉指令的目的地址。這樣，當再一次執(zhí)行到這個跳轉指令時，就直接從上次保存的目的地址出取指令，放入流水線。等到真正獲取到目的地址的時候，再看如果取錯了，則推翻當前流水線中的指令，取真正的指令執(zhí)行。

多級存儲與數據預取

??多級存儲就不用解釋了，當數據在寄存器、cache或內存中，CPU取數速度不在一個數量級。尤其cache和內存訪問，相差兩個數量級。CPU在內存取數的時候會首先從cache中查找數據是否存在。若不存在，則訪問內存，在訪問內存的同時將訪問的數據所在的一個內存塊一起載入cache。
??如果程序訪問數據存在線性訪問的模式，CPU會主動將后續(xù)的內存塊預先載入cache，這就是CPU的數據預取。有時候程序訪問數據并不是線性的，例如Hash表查找等。CPU也提供了數據預取指令，程序可以事先主動將會用到的數據載入cache，這就是Software Prefetch。
??如何利用好寄存器和cache是數據庫查詢執(zhí)行非常重要的優(yōu)化方向。

SIMD

??單指令多數據流，對于計算密集型程序來說，可能經常會需要對大量不同的數據進行同樣的運算。SIMD引入之前，執(zhí)行流程為同樣的指令重復執(zhí)行，每次取一條數據進行運算。例如有8個32位整形數據都需要進行移位運行，則由一條對32位整形數據進行移位的指令重復執(zhí)行8次完成。SIMD引入了一組大容量的寄存器，一個寄存器包含832位，可以將這8個數據按次序同時放到一個寄存器。同時，CPU新增了處理這種832位寄存器的指令，可以在一個指令周期內完成8個數據的位移運算。
??如何利用好SIMD也是不少數據庫的優(yōu)化方向，尤其是向量化執(zhí)行的策略下。

查詢執(zhí)行模型

火山模型

??數據庫查詢執(zhí)行最著名的是火山模型，也是在各種數據庫系統中應用最廣泛的模型。SQL查詢在數據庫中經過解析，會生成一棵查詢樹，查詢數的每個節(jié)點為代數運算符(Operator)?；鹕侥Ｐ桶袿perator看成迭代器，每個迭代器都會提供一個next() 接口。一般Operator的next() 接口實現分為三步， 1.調用子節(jié)點Operator的next() 接口獲取一行數據(tuple)，2.對tuple進行Operator特定的處理(如filter 或project 等)，3.返回處理后的tuple。因此，查詢執(zhí)行時會由查詢樹自頂向下的調用next() 接口，數據則自底向上的被拉取處理。火山模型的這種處理方式也稱為拉取執(zhí)行模型(Pull Based)。
??火山模型的優(yōu)點是，處理邏輯清晰，每個Operator 只要關心自己的處理邏輯即可，耦合性低。但是缺點也非常明顯：數據以行為單位進行處理，不利于CPU cache 發(fā)揮作用。且每處理一行需要調用多次next() 函數，而next()為虛函數，開銷大。VectorWise[4]對TPC-H中Q1執(zhí)行過程進行了性能分析，結果發(fā)現所有Operator的運算邏輯(也就是真正的查詢執(zhí)行過程)所花費的時間只占總時間的10%。向量化執(zhí)行和編譯執(zhí)行分別從兩個方向入手進行優(yōu)化。

編譯執(zhí)行

??考慮到火山模型大量虛函數調用導致的性能損失，推送執(zhí)行模型(Push Based)很好的解決了這個問題。與拉取模型相反，推送模型自低向上的執(zhí)行，執(zhí)行邏輯由底層Operator開始，其處理完一個tuple之后，將tuple傳給上層Operator處理。
??Hyper[3]作為代表性的編譯執(zhí)行的數據庫，就采用了這種推送模型。我們直接來看Hyper論文中的例子，有如下SQL查詢，

select *
from R1,R3,
    (select R2.z,count(*)
    from R2
    where R2.y=3
    group by R2.z) R2
where R1.x=7 and R1.a=R3.b and R2.z=R3.c

??對于上面的SQL查詢，其對應的Operator查詢樹如下圖左側所示。其中的符號對應著SQL應該也能看得出來，分別為Filter、Aggregation和Join。

??前面CPU的多級存儲介紹提到，數據訪問速度最快的是寄存器。所以在執(zhí)行查詢樹時最理想的情況就是數據一直留在寄存器中(假設寄存器的容量足以放下一個tuple)，每個Operator直接處理寄存器中的數據。Operator之間從拉取模型的虛函數調用，變成了以數據為中心(data-centric)的順序執(zhí)行。當然，并不是所有的Operator的運算邏輯都可以處理完寄存器中的tuple之后，把tuple留在寄存器中，由下一個Operator 接著處理。例如Join的時候，需要構建hash表，tuple就必須寫入內存了(整個hash表當然不可能放到寄存器)。
??Hyper把Join這種不得不把數據從寄存器取出來，寫入內存(論文中稱這個事件為Materialization)的Operator稱為Pipeline Breaker。然后以Pipeline Breaker為分割，將查詢樹劃分為多個pipeline。在一個pipeline內，數據可以一直留在寄存器中。因此上圖左側的查詢樹，分割為Pipeline之后，對應的查詢樹就如圖右側所示。說到這里還是會覺得有點抽象，看一下上面的查詢樹對應的編譯執(zhí)行的偽代碼，如下圖?？梢娒總€Pipeline對應一個For循環(huán)，一次循環(huán)處理一個tuple，tuple在一次循環(huán)內是不離開寄存器的。

??編譯執(zhí)行的難點在于如何把查詢樹編譯成這樣的代碼執(zhí)行。不像拉取模型，一個next()調用把數據傳遞和數據處理邏輯分的明明白白。復雜的Operator邏輯直接影響到編譯執(zhí)行的代碼生成。Hyper觀察Operator處理數據的模式，從中抽象出了兩種函數接口Produce() 和 Consume()。Produce()函數負責產生結果tuple，然后通過調用下一個Operator的Consume()函數，將tuple向上傳遞。Consume()函數負責具體的tuple處理邏輯。Produce() 和 Consume()只是為了代碼生成引入的邏輯概念，實際上是每個Operator會根據規(guī)則拆分為兩個代碼塊，一塊對應Produce() ，一塊對應consume()。代碼生成的時候就可以根據這個規(guī)則生成代碼。從下圖可以看出Join、Filter和Scan Operator與代碼塊的簡單對應。當然，實際上會更加復雜。Hyper會利用LLVM直接生成其中間語言。詳細的生成規(guī)則可見論文[3]附錄。

??編譯執(zhí)行以數據為中心，消滅了火山模型中的大量虛函數調用開銷。甚至使大部分指令執(zhí)行，可以直接從寄存器取數，極大的提高了執(zhí)行效率。

向量化執(zhí)行

??向量化執(zhí)行依然采用類似火山模型的拉取式模型，唯一的區(qū)別是其Operator的next()函數每次返回的是一批數據(如1000行)(一般向量化特指列式存儲系統中，按列聚合的一組數據；在行式系統中稱為RowSet迭代，本文不嚴格區(qū)分這兩種情況)。向量化執(zhí)行相對編譯執(zhí)行好理解一點，直接看一個例子(來自[1])，下圖是一個JoinOperator的編譯生成的偽代碼和向量化執(zhí)行的偽代碼的對比。JoinOperator 的執(zhí)行邏輯為，以左表的數據構建Hash表，然后以右表中的每行記錄，分別去Hash表查找。這里的Hash表的沖突處理采用的是鏈地址法，偽代碼中最后一個循環(huán)就是遍歷鏈表，找到真正的匹配項。

??圖中(a)部分為編譯執(zhí)行模型生成的偽代碼，結合上一小節(jié)的介紹，比較容易理解。看一下圖中(b)部分向量化執(zhí)行的偽代碼。剛剛提到，向量化執(zhí)行的模式為拉取模型，每個Operator實現一個next()接口。與火山模型不同的，它一次處理一組數據。因此，可以看到這里面的變量都是Vector。由于變量為Vector，就需要事先定義一些專門處理Vector的元語(Primitives)。例如為Vector中的每一個元素計算Hash值的proheHash_，以及圖中的compareKeys_、buildGather_。了解了這個，上面的偽代碼也就不難看懂了。
??向量化執(zhí)行模型有一下幾個好處：1.大大減少火山模型中的虛函數調用數量；2.以塊為處理單位數據，提供了cache命中率；3.多行并發(fā)處理，契合了CPU亂序執(zhí)行與并發(fā)執(zhí)行的特性。4.同時處理多行數據，使SIMD有了用武之地(雖然目前SIMD對大多數數據庫查詢起到的作用比較有限[1]，本質上數據庫查詢都屬于數據訪問密集型應用，而不是SIMD最擅長的計算密集型應用)。

向量化VS編譯執(zhí)行

??相比火山模型，向量化與編譯執(zhí)行都使數據庫查詢執(zhí)行性能得到了極大的提升，這兩者之間相比又如何呢。首先這兩個模型是不相容的，二者只能取其一。因為編譯執(zhí)行強調的是以數據為中心，在一個Pipeline內是不會有Materialization的，但是向量化執(zhí)行是拉取模型，每次經過next()調用，Vector的傳遞必須Materialize。
??Pavlo[1]的團隊在同一個系統(Peloton)里實現了這兩種模型，以進行各方面對比。這里直接說結論，那就是各有千秋，沒有誰比誰更優(yōu)秀，只有誰比誰更合適。[1]選取了TPC-H中非常有代表性的5個SQL查詢，Q1和Q18主要運算為定點數運算(Fixed-point arithmetic)和Aggregation，Q6主要運算為Filter，Q3和Q9主要運算為Join。測試結果如下圖。

??從圖中可以看出向量化執(zhí)行對于Q3和Q9查詢更高效，而編譯執(zhí)行對于Q1和Q18語句更高效。為了理解這種性能差異的原因，我們還需要下面這張圖來進行解釋。

??圖中的Typer是編譯執(zhí)行引擎，Tectorwise是向量化執(zhí)行引擎。Memory Stall指的是CPU執(zhí)行指令時，內存取數的等待時間?？梢钥闯鯭3和Q9，Typer主要就是慢在了Memory Stall。因為Hash表數據分布比較隨機，Hash查找時cache命中率不高，經常需要訪問內存。向量化執(zhí)行模型的循環(huán)較短，并發(fā)度高，可以同時有更多的指令等待取數，總的等待時間就短了。而編譯執(zhí)行循環(huán)內部會包含多個Operator的運算，這些有依賴關系的指令占據了大部分的亂序執(zhí)行窗口，并發(fā)度低，總的等待取數時間就長了。另外，更復雜的循環(huán)也導致分支預測失敗的代價更高。而對于Q1和Q18，由于運算過程中cache命中率比較高，沒有Memory Stall的拖累，編譯執(zhí)行模型Pipeline執(zhí)行無Materialization的優(yōu)勢就體現出來了。

編譯執(zhí)行融合向量化

??什么？融合？不是才說這兩種執(zhí)行模型不相容么？說簡單也簡單，把查詢樹分解一下，部分用向量化方式，部分用編譯執(zhí)行方式即可?；舅枷胧呛唵?，可真的做起來，還是有不少問題需要解決的。目前這樣的系統并不多，這里就介紹一個最近的工作。Pavlo的團隊在Peloton中實現的一個原型系統 Relaxed Operator Fusion (ROF)[2]。
??編譯執(zhí)行的主要目標是減少Materialization，ROF則是在編譯執(zhí)行的基礎上，主動在其中的Pipeline中插入Materialization，將Pipeline分割為Stage，在Stage內依然是tuple-at-a-time data-centric的推送模型，保留了編譯執(zhí)行數據停留在寄存器中的優(yōu)點。而跨Stage或Pipeline時，則以Block(一組tuple)為單位傳遞數據，這個時候就可以利用上SIMD。另外，ROF還使用了Software Prefetch來優(yōu)化編譯執(zhí)行當Hash表查找時cache命中率低Memory Stall過多的問題。
??我們可以通過下面這個例子了解ROF的主要思想。

SELECT SUM(...) AS revenue
FROM LineItem JOIN Part ON l_partkey = p_partkey
WHERE (CLAUSE1) OR (CLAUSE2) OR (CLAUSE3)

??上面的SQL是TPC-H Q19的簡化版本。其中CLAUSE1~3分別是LineItem和Part兩個表上的查詢條件。這段SQL對應的編譯執(zhí)行的查詢數和ROF的查詢樹如下圖。

??可以看到ROF 相比原來的查詢樹，在P2這個Pipeline的第一個Filter后面插入了一個Operator(圖中標紅)。這個Operator表示Vector Output，把P2分成了兩個Stage(我們稱這種分割Stage的Operator為Stage boundary)，在Stage內部為tuple-at-a-time，跨Stage則以Vector為單位傳遞數據。P2對應ROF的偽代碼如下圖。Stage1進行TableScan和Filter，將VECTOR_SIZE數量的Tuple插入Vector。Stage2對Vector中的數據進行HashProbe、Filter以及Aggregate。

??上面的例子展示了ROF是怎么把Pipeline分割成Stage的，但是到目前為止，我們并沒有看到這么做有什么好處。這里最關鍵的問題是，應該在Pipeline的哪個位置插入Stage boundary，才能達到最優(yōu)的效果。ROF按照兩個規(guī)則分割Stage：R1. 可以使用SIMD的Operator的輸入和輸出點；R2. 需要對無規(guī)律地址數據(且數據量大于Cache)進行訪問的Operator的輸入點。R1是為了利用SIMD進行并發(fā)計算，R2是為了使用Software prefetch提高cache命中率。這是基本策略，在實現時還有一些技術點需要考慮。為了快速獲取SIMD寄存器中Filter過后的數據，ROF利用一個Mask索引，將SIMD寄存器中的有效數據Shuffle到一起。當數據量不大時，數據預取反而會帶來額外開銷。ROF在編譯時會生成兩套執(zhí)行路徑，在運行時根據數據量決定是否需要預取。具體細節(jié)這里就不展開了，感興趣的同學可以看一下論文[2]。
??對于TPC-H中的查詢，實現了ROF的Peloton與VectorWise[4]和Hyper[3]的性能對比，性能提升在1~8倍之間[2]。

總結

??本文介紹了向量化執(zhí)行與編譯執(zhí)行的優(yōu)化動機、原理、效果，以及這一塊最近學術研究的進展。由于各種查詢不同運算的差異性和多樣性，以及隨著硬件機制的發(fā)展，這一塊后續(xù)還有不少工作可以擴展。

[1] Kersten, Timo, et al. "Everything you always wanted to know about compiled and vectorized queries but were afraid to ask." Proceedings of the VLDB Endowment 11.13 (2018): 2209-2222.
[2] Menon, Prashanth, Todd C. Mowry, and Andrew Pavlo. "Relaxed operator fusion for in-memory databases: Making compilation, vectorization, and prefetching work together at last." Proceedings of the VLDB Endowment 11.1 (2017): 1-13.
[3] Neumann, Thomas. "Efficiently compiling efficient query plans for modern hardware." Proceedings of the VLDB Endowment4.9 (2011): 539-550.
[4] Boncz, Peter A., Marcin Zukowski, and Niels Nes. "MonetDB/X100: Hyper-Pipelining Query Execution." Cidr. Vol. 5. 2005.