讀後感：Volcano-An Extensible and Parallel Query Evaluation System

能寫、能存、能讀是資料庫三大基本功能，而查詢引擎就是完成資料庫讀的重要模塊，顯然應該位列資料庫核心組件列表。查詢引擎沒有精確的形式化定義，但是Volcano模型[1]卻影響了非常多的關係資料庫查詢引擎的設計，學習一下。

Volcano模型的提出者是Goetz Graefe，其1994年發表此文，並於2017年獲得Edgar F. Codd（關係模型奠基人）創新獎[2]，也算是此生貢獻給資料庫了。

從文章標題看得出來，Volcano重點關注的是擴展性和並行性。擴展性的意思是，查詢引擎可以比較容易的應用在不同的資料庫系統裡面，通過簡單的修改就可以適配新數據類型，新演算法，新運算元。並行性的意思是不同的運算元可以很方便的並行運行，不同的數據分片可以很方便的被並行處理。據作者論文中寫，Volcano是第一個融合擴展性和並行性的查詢引擎。如果我們想一下10年前出現的Map-Reduce編程模型，以及近幾年很火的各種SQL-On-Hadoop方案的競爭和演化，會發現Volcano的思想仍然閃耀光芒。

Volcano將系統設計分為兩個部分，見圖1，下面的模塊是文件系統，上面模塊是查詢處理系統。筆者個人理解文件系統模塊的存在更多的是為了說明整個系統的完整性，不是文章重點，因此會簡單介紹，重點介紹其查詢處理系統部分。

Volcano的文件系統部分包括緩存管理，文件記錄，B樹索引等。以緩存管理為例，作者認為緩存模塊應該提供若干種不同的替換策略，但是具體使用哪一種需要上層應用決定（不是業務應用，是說查詢處理系統），並指出當前資料庫系統中緩存模塊自己決定替換策略是不太合理的。上面這種思想貫穿在整個論文中，即底層模塊提供機制，上層調用指定策略決定如何組合底層的機制來解決問題，這也是擴展性的一個方面。

Fig 2. Linux文件系統簡略結構

下面重點介紹其查詢處理系統。作者首先提到了文件系統裡面有很靈活的機制來增強文件系統的擴展性，這句話作者一筆帶過未加詳細說明。個人理解可能類似Linux內核中虛擬文件層對各個具體的文件系統提出的介面要求，只要符合這個要求的文件系統都可以被內核有效識別。虛擬文件系統規定文件系統必須提供一系列的文件操作指針，比如open/seek/read/format等，有了這個約定我們自己要寫一個實驗性質的文件系統對接到Linux內核中並非難事，這樣一些新的文件系統就可以出現，從而推動整個體系的演進[3]。從面向對象語言的角度，VFS有點像介面聲明，而各個具體的文件系統就是不同的實現類，介面指針可以被任何模塊使用，只要符合這個介面約束的實現都可以填充進去。作者提出的查詢處理系統基本思想與此類似，其認為每個運算元都應該實現成一個iterator，有三個介面，分別是open/next/close，其中open可以做一些資源初始化，比如打開文件，next將游標向前推進返回Next-Record（由ID和指向buffer的數據指針組成；為了性能，可以返回一批記錄），close負責銷毀資源。

Fig 3. iterator 示例

圖3展示了iterator體系的基本思想，很容易看到每個iterator都實現了相同的介面，即open/next/close，每個運算元並不關心其他運算元是幹什麼或者怎麼乾的，只要實現這三個介面大家就可以配合工作，這真是一個非常巧妙的組合。這樣做至少從以下幾個優點：

1. 很容易更新演算法：比如已有的group by運算元在資源佔用上不夠高效，那麼只要按照這三個介面重新實現一個就可以方便的換掉已有的實現，而這個更換過程中對其他模塊無感知（準確的說，是用新運算元填充iterator，不是重新實現iterator）
2. 很容易添加新的iterator：整個運算元體系就是一堆實現了open/next/close迭代器的組合，那麼想實現了一個新的運算元放入這個體系也變得非常容易，並且對系統其它部分無感知
3. 很容易異構化，並行化：本質上上游的iterator只關心下游iterator送來的數據，至於該下游iterator是如何得到這些數據的則完全不關心，所以這就使得我們很容易將iterator放到不同的CPU（分散式系統裡面就是不同計算節點）運行，簡化了並行化的複雜度，並可以將並行化做成標準流程，為所有運算元共享
4. 很容易重新組合運算元：查詢優化中可以基於一些重寫規則或者統計信息來重新定義各個運算元執行的順序，從而達到優化查詢的目的，而Volcano體系結構中，允許各個運算元自由組合，那麼這就使得查詢優化變得更加容易實現

說道這裡，我們還要插播一下iterator和operator的關係。作者在文章中說，In summary, demand-driven dataflow is implemented by encoding operators as iterators, i.e., with open, next, and close procedures, since ...，可以認為，iterator是一個更廣泛的框架，規定了操作流程是open、next、close，然後可以提供了一些非常通用的實現，比如內存的控制，而從處理邏輯看，其基本可以認為是一個空殼，真正幹活的是operator。

繼續上面的主題，難道如此複雜的問題就這麼簡單的解決了？思路確實如此，但是還有很多細節。我們看到了圖3中的arguments、input和state。input容易理解，就是來自下游iterator的輸出，這個輸出理論上是一片位元組數據，如何解釋這些數據靠的是支持函數（support function）。支持函數需要細緻的了解一下，這個概念也是該文的核心信息。支持函數在作用上可以理解為虛擬文件系統的file_operations結構，裡面以函數指針的形式規定了眾多文件操作聲明，比如要open一個文件，就要提供文件名，打開模式，許可權信息。支持函數可以是預編譯好的，也可以是動態生成的代碼並在運行時進行解析。支持函數可能長下面這樣，

int32_t comp(void* left, void* right) // 比較兩條記錄

int64_t hash-1(void* left) // hash

void pack(void* input, void* output); // 壓縮

void unpack(void* input, void* output) // 解壓

void add(void* input, const char* col) // 系統函數

void udf-1(void* input, void* output) // 用戶定義函數

...

支持函數被當做arguments的一部分傳入進來，每個state record記錄其所屬iterator需要的所有支持函數。需要注意的是，支持函數的參數也可以是一個函數指針，這又增加了系統的擴展能力。如果鑽一點牛角尖的話，arguments裡面不僅包含支持函數，也可以包含整個iterator體系需要的參數，比如用戶傳入的一些常量等，這一類參數文中稱為bindings。解釋了input和argument，還剩下state，這個也算比較容易理解，在iterator運行的過程中總有一些中間結果需要記錄，比如count operator就需要記錄中間結果，group by也需要記錄中間結果，然後經過整理再吐給上游。

關於支持函數，operator，iterator的關係，按照文章的意思，應該是iterator在最外層，每個iterator都可以包裝幾個operators，然後支持函數被operator使用。而實際的系統中，我想他們的界線應該是模糊的，比如sum的operator是不是跟sum的支持函數可以並列？一個幾乎是空殼的iterator是不是乾脆換成operator好了？論文要求的是準確描述概念，概念越多越好，職責分明；工程要求代碼精簡，有些概念是可以權衡合併的。

說道這裡，本文的核心邏輯就結束了，但是因為這篇文章的目標是實際的工程領域的可擴展性和並行性，因此還有一些細節是需要再次思考的。

首先，文中特別提到了scan和filter，並指出filter operator包括三個功能，分別是predicate，transform和apply。predicate可以過濾一些行，比如利用bit vector技術（如bloomfilter）減少上層operator處理的數據量；transform是按照上層operator要求進行必要的變換，比如去掉一些不必要的列，解壓或者將讀出來的數據變成指針繼續向上傳遞；apply一般用來更新狀態，比如讀了多少行，打日誌等。從理論角度看，filter這麼多的功能應該拆開變成operator樹上面的三層operator，但是實際上，這三個操作的組合關係是固定且有限的，因此拍平是更合理的選擇。另外，文中還提到將索引讀和數據讀分開實現，並使用類似Join的技術在必要的時候連接起來，對於非主鍵索引，是一種合理的抽象；對於主鍵索引，我不太認同，因為資料庫記錄一般比較小，這種操作增加了系統複雜度甚至會增加查詢的IO。

Fig 3. 二元輸入，一對一記錄匹配關係

其次，文中通過一個一對一操作符實現了眾多的join類型，因為本質上這些join都是在笛卡爾積上面進行選擇。不過我有點懷疑這樣可能導致性能的損失，intersection和union應該有各自更高效的實現。

最後，文章提到了兩個meta operator。一個是chose plan operator，這個概念就是在執行過程中允許動態的選擇一些執行路徑。動態執行今天是一個很流行的概念，但是卻不是通過iterator加一層實現的，而是在查詢優化階段就確定了，而查詢優化階段跟執行階段是並列的，並不從屬。主要原因我覺得可能是優化太複雜，不是放在iterator裡面通過支持函數選擇一個策略這麼簡單。跳出來看，查詢過程中動態優化當然很牛，不過更務實的做法也許是通過查詢統計優化查詢計劃，然後在下一次查詢時候體現出優化結果。第二個是exchange operator，這是用於自動並行化的標準運算元，有了這個，其他運算元就不用考慮並行化的問題。並行有兩類，一類是將數據分成很多分區，每個分區執行一樣的operator樹，這些執行是並行的，最後結果合併起來；一類是數據只有一份，要執行的各個運算元之間可以並行。這兩種並行並不互斥，可以一起使用來優化系統。在Volcano的設計中，並行化operator交互使用的就是exchange operator，不管是單機或者多機。exchange 可以理解成一個非同步信號，當這個信號發出後，接收方就開始幹活，發送方不會停下來等待結果，而是繼續前進，當接收方幹完活返回結果的時候，發送方按照預定邏輯處理就可以了。在分散式系統裡面，exchange operator大概可以理解為rpc operator（想想Map-Reduce），MPP SQL引擎Impala裡面實現了此類運算元。

至此，學習了這篇文章的核心理念，具備統一介面的運算元，有向無環圖的運算元組合，通過添加交換節點而自動增加並行能力。似懂非懂，以後繼續找這個領域的專家學習。

[1]. Volcano-An Extensible and Parallel Query Evaluation System

[2]. https://sigmod.org/sigmod-awards/people/goetz-graefe-2017-sigmod-edgar-f-codd-innovations-award/

[3]. https://researcher.watson.ibm.com/researcher/files/il-AVISHAY/01-block_io-v1.3.pdf