資料庫查詢引擎的進化之路

8 人贊了文章

摘要：在關係資料庫中，除了查詢優化器之外，查詢調度器和計劃執行器是兩個同等重要的模塊，並且隨著計算機硬體的發展，他們的重要性越發彰顯。本文將由OceanBase團隊的90後技術專家聿明 帶你一起回顧執行器在發展過程中的重大演變。

本文作者：聿明

現任螞蟻金服OceanBase團隊技術專家，自2013年加入OceanBase一直從事SQL方向的解析，執行以及優化的相關工作。

正文：

在關係資料庫中，當大家提到SQL查詢，自然而然的想到查詢優化器，毋庸置疑，這是關係數據計算中非常重要並且複雜的一個模塊，它決定了查詢關係以哪種方式執行能夠得到一個最優的結果。但是在關係計算的過程中，還有兩個同等重要的模塊，那就是查詢調度器和計劃執行器。

在關係資料庫發展的早期，受制於計算機IO能力的約束，計算在查詢整體的耗時佔比並不明顯，這個時候調度器和執行器的作用被弱化，一個查詢的好壞更主要取決於優化器對執行計劃的選擇好壞。但是在今天，隨著計算機硬體的發展，調度器和執行器也逐漸彰顯了它們的重要地位，這裡我們重點介紹下執行器發展過程中的一些演變。

繞不開的火山

Volcano Model是一種經典的基於行的流式迭代模型(Row-BasedStreaming Iterator Model)，在我們熟知的主流關係資料庫中都採用了這種模型，例如Oracle，SQL Server, MySQL等。

在Volcano模型中，所有的代數運算符(operator)都被看成是一個迭代器，它們都提供一組簡單的介面：open()—next()—close()，查詢計劃樹由一個個這樣的關係運算符組成，每一次的next()調用，運算符就返回一行(Row)，每一個運算符的next()都有自己的流控邏輯，數據通過運算符自上而下的next()嵌套調用而被動的進行拉取。

上圖展示了Spark1.0的查詢迭代器模型(OceanBase0.5中採用了相同的結構)，這是一個最簡單的火山模型例子，拉取數據的控制命令從最上層的Aggregate運算符依次傳遞到執行樹的最下層，而數據流動的方向正好相反。

火山模型中每一個運算符都將下層的輸入看成是一張表，next()介面的一次調用就獲取表中的一行數據，這樣設計的優點是：

1. 每個運算符之間的代數計算是相互獨立的，並且運算符可以伴隨查詢關係的變化出現在查詢計劃樹的任意位置，這使得運算符的演算法實現變得簡單並且富有拓展性。
2. 數據以row的形式在運算符之間流動，只要沒有sort之類破壞流水性的運算出現，每個運算符僅需要很少的buffer資源就可以很好的運行起來，非常的節省內存資源。

但是這種運算符的嵌套模型也有它的缺點：

1. 火山模型的流控是一種被動拉取數據的過程，每行數據流向每一個運算符都需要額外的流控操作，所以數據在操作符之間的流動帶來了很多冗餘的流控指令。
2. 運算符之間的next()調用帶來了很深的虛函數嵌套，編譯器無法對虛函數進行inline優化，每一次虛函數的調用都需要查找虛函數表，同時也帶來了更多的分支指令，複雜的虛函數嵌套對CPU的分支預測非常不友好，很容易因為預測失敗而導致CPU流水線變得混亂。這些因素都會導致CPU執行效率低下。

通常，一個查詢的直接開銷主要取決於兩個因素：第一個因素就是跨存儲和計算操作符之間的數據傳輸開銷，另一個因素就是數據運算所花費的時間。

火山模型最早於1990年Goetz Graefe在Volcano, an Extensible and Parallel Query Evaluation System這篇論文中提出，在90年代早期，計算機的內存資源十分昂貴，相對於CPU的執行效率，IO效率要差得多，因此運算符和存儲之間的IO交換是影響查詢效率的主要因素（IO牆效應），火山模型將更多的內存資源用於IO的緩存設計而沒有優化CPU的執行效率是在當時的硬體基礎上很自然的權衡。

隨著硬體的發展，計算機的內存容量變得越來越大，更多的數據可以直接存儲在內存中，而單核CPU的運算能力並沒有顯著提升，這個時候CPU對執行效率的影響就變得更加重要，因此越來越多對CPU執行效率的優化被提出。

操作符融合

優化操作符的執行效率最簡單有效的方法就是減少執行過程中操作符的函數調用。由於ProjectOp和FilterOp在計劃樹中最為常見的兩個操作符，因此在OceanBase1.0中，我們將這兩種操作符融合在其它特定的代數操作符中，這大大減少了計劃樹中的運算符的個數以及運算符之間的next()嵌套調用，同時，PorjectOp和FilterOp變成每個操作符內部的一種能力，這也增強了代碼局部性能力，優化了CPU的分支預測能力。

上圖展示了select count(*) from store_sales where ss_item_sk=1000;這條查詢在OceanBase1.0的執行計劃，操作符從原來的4個變成了2個，而FilterOp和SelectOp成為了操作符中的一個局部運算。

RowSet迭代

在火山模型的基礎上另一種簡單有效的優化方式就是RowSet機制，簡而言之就是每一次數據流的傳遞不再是單行的形式，而是若干的row組成的集合，這使得運算更多的停留在next()內部，而不是在函數調用間頻繁的切換，從而保證代碼局部性和減少函數間調用次數。

RowSet機制將數據在各個環節的流向變成了一個局部範圍的循環操作，這迎合了現代編譯器技術和CPU動態指令預測技術對簡單循環指令的極致優化，同時RowSet的構造可以通過CPU的SIMD指令進行加速，這也比單行數據在內存中的拷貝更加高效，這使得一些結果集比較大的查詢執行效率能夠明顯提升。

推送模型

推送模型最早在一些流媒體計算中被使用，隨著大數據時代的來臨，在一些基於內存設計的OLAP資料庫也被大量使用起來，例如HyPer、LegoBase等。

上圖展示了拉取模型和推送模型兩種不同的控制流和數據流方向，從圖中我們可以看出拉取模型的控制流程更符合查詢執行的直觀印象，上層運算符按需的向下層運算符獲取數據並執行，這本質是一層層的函數嵌套調用。而推送引擎剛好相反，通過將上層的計算下推到數據產生的操作符中，由數據的最終生產者驅動上層運算符對數據進行消費。

為了更直觀的比較拉取模型和推送模型對代碼結構的影響，我們將圖1中提到的簡單查詢各個運算符中next()介面的實現展開成偽代碼，如下圖所示：

通過上圖的對比很容易可以看出，相比於拉取模型，推送模型改變了數據迭代過程中的嵌套調用關係，大大簡化了查詢過程中的指令跳轉流程，從而使得推送模型有更好的代碼局部性，優化了CPU執行效率。但是推送模型實現也更為複雜，?Hyper系統通過設計模式中的Visitor模式來實現了計算推送引擎，基本思想是每個operator提供了兩個介面：produce()用來生產數據，consume()介面用來消費數據，和拉取模型不同的是，consume()並不像next()那樣需要關心流控邏輯，而只用關心operator本身的關係代數邏輯，流控邏輯被produce()接管。

這裡有個問題是對於一些本身和流控相關的operator很難用這種模型實現，或者說反而執行效率不如拉取模型的高，例如limit、merge join、nested loop join等操作，其關係代數運算本身就和流控相關，查閱了Hyper相關論文，作者並沒有詳細解釋怎麼去解決這個問題，我的猜測是Hyper處理的場景是OLAP為主，在該場景下，流控operator出現概率是較少的，不用特別去關注它們的執行效率，並且在一些極端場景中可以將這些運算在其它運算元中做特殊處理。

拉取&推送模型融合

對於一個通用的關係資料庫可能不得不考慮推送模型中這些缺點，因為在OLTP場景下，merge join、nested loop join這類操作出現的頻率可能遠遠高於hash join操作，所以在通用資料庫的執行引擎中融合使用拉取模型和推送模型是一個較好的選擇：在一些比較耗時的物化操作中(例如Hash Join中的hash table構建，Aggregate操作等)，通過next()介面調用向下層傳遞一個callback函數，將耗時的阻塞運算通過callback下壓到下一個阻塞操作符中，當下層運算符生產好數據後，再依次調用callback list中的回調函數。

而對於limit、merge join、nested loop join這類運算則不會通過callback下壓，這種實現方式還有一個好處就是，原有的火山模型並不需要大改，同時也能發揮出推送模型的一些優勢，這也是一個比較自然的權衡選擇。

編譯執行

拉取模型和推送模型影響的是執行流程的代碼布局，但只要是解釋執行，就無法避免運算符之間的虛函數調用。隨著計算機硬體的發展，內存變得越來越大，這意味著越來越多的數據可以直接cache在內存中，而訪問磁碟的頻率被大幅度的降低，這個時候「IO牆」的效應被削弱，而由於解釋執行無法感知CPU寄存器，高頻的內存訪問，使CPU和內存之間形成了「內存牆」效應，為了解決這個問題，越來越多的內存資料庫開始使用編譯執行來優化自己的查詢效率，例如HyPer、MemSQL、Hekaton、Impala、Spark Tungsten等。

相比於解釋執行，編譯執行具有以下優點：

1. inline虛函數調用：在火山模型中，處理一行數據最少需要調用一次next()。這些函數的調用是由編譯器通過虛函數調度實現(vtable)，而編譯執行的過程中沒有函數調用，並且大量裁剪了解釋執行中的流控指令，這使得CPU執行會更加高效。

2.內存和CPU寄存器中的臨時數據：在火山模型中，運算符在傳遞行數據的時候，都需要將行數據存儲在一個內存buffer中，每一次執行至少需要訪問一次內存，而編譯執行沒有數據的迭代過程，臨時數據被直接存放在CPU寄存器中(當然前提是寄存器的數量足夠多)，而直接訪問寄存器的效率要比訪問內存高一個數量級。

3. 循環展開(Loop unrolling)和SIMD：當運行簡單的循環時，現代編譯器和CPU是令人難以置信的高效。編譯器會自動展開簡單的循環，甚至在每個CPU指令中產生SIMD指令來處理多個元組。CPU的特性，比如管道(pipelining)、預取(prefetching)以及指令重排序(instruction reordering)使得運行簡單的循環非常地高效。然而編譯器和CPU對複雜函數調用的優化極少，而火山模型具有非常複雜的流控調用。

在OceanBase2.0中，我們利用LLVM對執行引擎中的表達式運算和PL也進行了編譯執行的優化。這裡主要介紹下OceanBase的表達式編譯執行：

在編譯階段，主要有三個步驟：

1. IR代碼生成，對於表達式(c1+c2)*c1+(c1+c2)*3，我們假設所有的類型都為bigint，通過分析表達式語義樹，使用LLVM codegen的API生成IR代碼如圖(a)。

2. 代碼優化，我們可以看到，c1+c2表達式做了兩次計算，而這個表達式是可以作為公共表達式進行抽取的，經過LLVM 優化後，IR代碼如圖(b), 只進行了一次c1+c2的計算，總的執行命令也得到減少。另外，使用表達式解釋執行時，所有的中間結果都需要在內存中物化；而編譯後的代碼可以將中間結果保存在CPU的寄存器中，直接用於下一步的計算，大大的提升了執行效率。LLVM還提供了很多類似的優化，我們都可以直接使用，從而大大提升表達式的計算速度。

結果對比

我們使用TPC-H lineitem表1G數據(約600w行)，對不同資料庫在同樣的測試環境進行了性能測試對比，執行SQL:

SELECT SUM(CASE WHEN l_partkey IN(1,2,3,7)

THEN l_linenumber + l_partkey +10

ELSE l_linenumber + l_partkey +5

END) AS result

FROM lineitem;

從上圖的結果可以看出，在大數據量的情況下，編譯執行相比於解釋執行有明顯的優勢，當數據量變得更大的時候，這種優勢會更加明顯。但編譯執行也有它本身的缺點：

• 單純的將Volcano模型編譯成代碼塊可能會帶來函數inline後代碼成倍增長，反而使得執行效率很難提升。因此單純的拉取模型並不適合編譯執行，拉取和推送結合是一個很好的選擇。對於編譯執行感興趣的同學強烈推薦閱讀Hyper作者Thomas Neumann的一篇論文Efficiently CompilingEfficient Query Plans for Modern Hardware，在這篇論文中作者詳述了一些複雜operator的優化技巧，以及如何寫編譯執行代碼能夠使執行效率最大化。
• 編譯執行的binary code生成非常耗時，往往是10+ms級別的時間開銷，對於OLAP型資料庫而言，編譯消耗的時間並不算太壞，因為查詢主要時間消耗來自於數據的計算，而對於OLTP型資料庫，在一些高頻的小數據查詢中，這樣的編譯耗時是無法容忍的，OceanBase的解決方案是通過Plan Cache機制將編譯的結果緩存並復用，消除同一個查詢的編譯次數。

寫在最後

軟體技術的發展總是和硬體技術的發展緊密結合在一起的，迎合硬體技術的發展而改變軟體技術棧的相應策略能夠使得設計的系統獲得更大的受益。雖然OceanBase不是一個單純的內存資料庫，但是通過合理的分區方式，我們可以將用戶訪問較熱的數據cache在內存中，使其近似於一個分散式的純內存資料庫，因此針對於內存資料庫設計的這些優化思想也同樣適合OceanBase的架構模型。

現在，OceanBase正在基於這些學術上的新思想做更多工程化的實踐，比如更加普及的編譯執行，計算下推，分散式並行執行等技術.同時我們也在關注列式存儲格式對資料庫執行引擎技術的影響，探索將列存計算引擎的一些優勢融入到OceanBase的方法，強化OceanBase在分析型計算場景的執行能力，突出其HTAP資料庫的定位。

OceanBase技術交流群

想跟本文作者OB第一小鮮肉聿明 深入交流嗎？

想認識螞蟻金服OceanBase團隊的一線技術專家嗎？

掃描下方二維碼聯繫螞蟻金服加群小助手，快速加入OceanBase技術交流群！