本文作者：呂政、長別、知數等
目的
隨著數字經濟時代的到來，越來越多的應用依賴數據分析來挖掘數據的價值。作為大數據存儲、在線分析的重要基礎系統，分析型資料庫（OLAP）為數據價值的在線化提供重要的技術平台。
阿里巴巴OLAP團隊經過調研發現，現有的OLAP資料庫執行引擎往往是在已有的OLTP執行引擎的基礎之上，進行二次開發而來，存在性能損耗大、歷史包袱重、未充分利用最新優化技術、未充分發揮新硬體優勢等問題。
隨著數據量的快速增長和數據分析需求的日趨強勁，OLAP系統所需要承擔的計算量也呈指數級增長，現有系統的性能難以滿足未來的在線數據分析的需求。經過分析，阿里巴巴OLAP團隊認為，真正面向全面上雲時代、面向數字經濟時代的OLAP執行引擎，應當具備如下技術特點：
• 支持多種硬體平台。滿足企業上雲需求，支持多種硬體平台。除了支持傳統X86平台，也應當兼容ARM平台，同時支持利用GPU、FPGA等新興硬體進行加速。
• 極致性價比。充分利用硬體性能，精選最佳算法和算子實現，提升硬體執行效率。對於密集、複雜的計算，使用特殊算法特殊硬體來提升效率。
• SQL 兼容性高。高度兼容現有的SQL標準、優化器標準、存儲標準，減少用戶的遷移難度和學習難度。用戶無需改寫SQL，無需重新學習優化技術，無需遷移數據，僅需要進行小版本軟體升級，即可享受到最新的性能優化技術。
為了解決如上需求，阿里巴巴OLAP AnalyticDB Postgres(簡稱ADB PG版)研發團隊歷時1年多，研發了新型的計算引擎Odyssey。Odyssey計算引擎具備如下主要技術特點:
• 支持多種軟硬體平台。除傳統X86平台外，也支持ARM晶片伺服器；支持採用GPU、FPGA加速部分核心算法。
• 性能強勁。拋棄傳統資料庫執行引擎的實現方式，充分利用硬體執行效率。通過算法設計，消除了火山模型、碎片化內存分配、冗餘邏輯等帶來的性能問題，將寶貴的CPU資源用於核心計算；採用LLVM進行動態代碼生成（CodeGen），提升表達式計算性能、精簡計算邏輯，實現邏輯計算完美「瘦身」；採用「超算」優化技術、對算子性能進行建模，全面分析代碼熱點，嚴格考察每一行代碼的實現性能；充分利用新硬體特性，利用CPU的SIMD技術、GPU的超高帶寬技術、FPGA的深度流水線，進一步提升性能。
• 兼容性強。Odyssey計算引擎內生於ADB PG版，與PostgreSQL的SQL標準、優化器、存儲層多個層面實現完美兼容，用戶無需任何操作，即可從原生引擎遷移到Odyssey計算引擎。
本文的如下部分，我們將從架構設計、核心技術點、性能評測三個維度，介紹新型計算引擎Odyssey的特點。
Odyssey計算引擎介紹
基本框架
下圖是ADB PG版的系統框架，以及Odyssey計算引擎與ADB PG版的關係。
ADB PG是一個MPP架構、高可用、可伸縮的分布式分析型資料庫系統。一個ADB PG集群由Master節點和Segment節點組成，通過網絡進行互聯。Master節點負責接收用戶請求、對SQL進行解析/優化、下發計算任務。Segment節點負責存儲數據、執行計算任務，Segment節點之間可能會有多次數據交換(shuffle)操作。網絡互聯速度、存儲性能、Segment節點的執行性能，均對ADB PG的性能有重要影響。本次發布的Odyssey計算引擎，主要提升了Segment的執行性能。
Odyssey計算引擎的研發目標，是為ADB PG新增一個更高效的計算引擎，而保持原有各模塊不變。ADB PG的Master節點在接收到用戶的SQL請求之後，對SQL進行解析、優化，生成執行計劃然後下發到Segment，Odyssey計算引擎對這一環節沒有影響，因此用戶無需修改SQL、無需重新優化SQL。
Segment接受到Master節點下發的執行計劃後，若Odyssey打開，將不再調用原生執行引擎，而是調用Odyssey計算引擎。在存儲層面，Odyssey計算引擎與ADB PG原生的Heap表、AOCS表、AORO表均完全兼容，復用原生存儲結構和存儲訪問接口，Odyssey專注於執行層。理論上說，Odyssey原生引擎與ADB PG的優化器優化、存儲優化等不同層次的優化是正交的，可以無縫銜接。
Odyssey計算引擎執行流程如上圖所示。Odyssey通過hook接入ADB PG，成為對用戶透明的新引擎。ADB PG在SQL執行開始時，通過選擇不同的Hook函數，來選擇不同的執行引擎。對於用戶來說，既可以選擇原生執行引擎，也可以通過設置GUC參數選擇Odyssey執行引擎。下一個版本將通過代價模型和規則來自動的選擇計算引擎，更能發揮各自的優勢。
為了保證系統的穩定性和功能的完整性，Odyssey計算引擎支持執行引擎的回退，當功能不支持或者執行失敗，可以自動回退到原生的執行引擎。由於執行引擎本身是無狀態的，用戶可以根據需求，以任意粒度（庫級別、session級別、SQL級別）進行執行引擎切換。
設計思想
基於上述架構，Odyssey計算引擎充分利用ADB PG自身的優勢，復用其存儲、優化器和事務控制，Odyssey專注於計算性能的提升，與原生ADB PG強大、豐富的功能形成互補。為了提升計算性能，通過對原生執行引擎進行分析、橫向對比多種執行引擎，我們設計了新的計算引擎。Odyssey計算引擎重新設計了plan node、codegen和executor，三者之間一一對應，如下圖所示，每個plan的node對應一個codegen單元和一個Executor，codegen單元根據plan node生成code(IR)，Executor根據硬體平台選擇不同的後端，將IR生成對應的執行文件，並申請資源執行，最終的結果通過master返回給客戶端。
執行模型優化。Odyssey計算引擎放棄了傳統的火山模型，改用批量化(batch)的火山模型，批量化執行減少函數調用的開銷，也方便使用向量化計算提升數據處理效率，同時也使得開發更為靈活、優化空間更大。
即時編譯技術。Odyssey計算引擎採用了Just-in-Time(JIT)技術，採用LLVM動態生成代碼。在一些核心操作上採用JIT技術，解決了高級語言抽象程度過高帶來的性能開銷，可以對表達式計算、複雜邏輯操作進行彙編級優化，最大化壓縮指令的規模。
內存管理優化。ADB GP原生執行引擎存在碎片化內存分配、碎片化內存拷貝等性能問題。Odyssey計算引擎在算法層進行了重新設計，採用模塊化內存分配、最大化重複利用已分配內存，大大減少了內存分配的次數。
超算軟體優化。Odyssey計算引擎的開發，大量採用了「超級計算機」軟體開發中的優化技術。在超算軟體優化中，建立理論性能模型、進行詳細性能剖析（Profiling）、嚴格審核代碼性能，能夠有效幫助軟體性能的提升。Odyssey計算引擎全面採用了相關技術，做到每個算子、每段代碼，都進行了深度優化。
多平台兼容。除傳統X86平台，Odyssey計算引擎兼容其他X86平台和ARM平台，同時支持不同版本的Linux作業系統，為用戶提供了更多的選擇和優化空間。
硬體加速優化。Odyssey計算引擎能夠利用GPU的超大吞吐能力和FPGA的高密度計算能力。對於部分計算量大、吞吐要求高的算子，採用GPU進行加速；對於部分計算邏輯相對固定、邏輯複雜的算子，採用FPGA進行加速。
核心技術點
執行模型優化
上圖展示了TPCH-Q3的執行計劃。在ADB PG中，一條SQL會被轉化成一個樹形執行計劃。資料庫傳統的傳統火山模型，是父節點驅動子節點執行，子節點按行返回數據給父節點，然後父節點再繼續執行。火山模型有三個核心性能問題：
(1) 函數調用過多，每行數據的傳遞需要至少一次函數調用，CPU開銷大；
(2) 優化困難，一些邏輯運算橫跨多個函數，無法進行優化；
(3) CPU利用率低，CPU完成某個算子的一個操作後，馬上返回到上層節點去做另一個操作，邏輯跳轉多，不利於提升CPU執行效率。
Odyssey計算引擎對火山模型進行了完全重寫，在復用原有的樹形架構基礎上，採用批量化(batch)執行提升執行性能。
火山模型中，節點之間傳遞數據的單位為一行，每個節點生成一行數據之後會被上層節點層層拉取，然後進行下一階段的計算。 而Odyssey計算引擎以batch為單位進行數據傳遞。一個Batch包含多行數據（通常是數千行數據），採用列優先格式進行數據存儲。一個節點在生成多行數據、填滿一個batch之後，才會將數據返回給上層節點，消除了火山模型的性能問題。一方面，該方案將火山模型的函數調用的次數降低了三個數量級，消除了過多函數調用帶來的性能影響；另一方面，減少了跨函數的操作，有利於在算法層進行優化、為各個算子選取最佳算法；最後，減少了邏輯跳轉操作，能夠有效利用現代CPU的執行資源。
內存管理
Odyssey計算引擎繼續沿用了ADB PG的內存管理模塊。ADBPG原生的內存管理模塊除了性能上有所提升，而且能夠自動追蹤內存的分配，從而實現自動的內存釋放，提升性能的同時避免了內存泄露的問題。該模塊已經經過大規模雲上實踐的檢驗，因此在工程上。Odyssey計算引擎沿用了這一模塊，但是在內存的使用上進行了優化，減少了不必要的內存分配和碎片化的內存分配。
一方面，Odyssey會盡力復用已分配的內存，避免不必要的多次內存分配。在火山模型中，部分節點生成一行數據後會為這行數據分配新的內存空間，因此每行數據都可能需要一次內存分配。Odyssey拋棄了火山模型、使用batch進行數據中轉。每個batch的數據被上層節點消費完一行，Odyssey會復用此batch的內存空間，無須重新進行分配。
// 原生引擎：碎片化分配，按行分配內存
for (...) {
void* hash_entry = palloc(32);
... // copy data
}
// Odyssey引擎：整塊內存分配。
void* hash_table = palloc(32*1000,000);
for () {
... // copy data
}
另一方面，在一些大快內存分配時，Odyssey選取了效率更高的分配方式(如上述偽代碼所示)。例如在Hash Join建哈希表時，一次插入一行數據，ADB PG的原生執行引擎，會在每行數據的插入之前為這一行分配內存。因此，每一行數據都需要重新進行一次內存分配，這種方案會帶來大量的碎片化內存分配。例如Hash表有1M行，每行32字節，會導致1M個32字節的碎片化內存分配。對於現代化的系統來說，碎片化的內存分配對於性能的影響是非常大的，不僅分配過程非常耗時，後續的管理、追蹤、釋放過程也會非常耗時。
Odyssey對ADB PG原生執行引擎的碎片化內存分配問題進行了診斷和原因分析，排查出幾個導致碎片化內存分配的關鍵算法問題。通過算法設計，Odyssey避免了碎片化內存分配問題，從而在不降低內存使用效率的同時，提高了內存管理的性能。
Codegen
Odyssey計算引擎採用基於LLVM的Codegen(代碼生成)技術，減少了虛函數的調用，提升了複雜邏輯表達式和邏輯判斷的性能。有別於PostgreSQL 11中表達式的codegen，Odyssey計算引擎是對整個算子進行codegen。目前Codegen主要用於三個層面的優化，算子優化、邏輯表達式優化和Code Specialization(代碼專業化)。
算子優化。採用codegen，可以將整個算子生成一個函數，減少虛函數調用和冗餘代碼，也可以將多個算子生成一個函數，不光有上述優勢，還能減少內存的使用和內存的拷貝。例如join + group by的場景，可以融合成一個函數，將join和AGG在一個函數裡實現。特別是如果hash key和group key相同時，只需要建一個hash表。
邏輯表達式優化。如下代碼實例解釋了是如何實現這一優化的。對於a > 10 and b < 5這樣一個過濾條件, ADBPG是通過三個函數調用來實現的，第一個函數調用Int32GT(a, 10)實現 a > 10, 第二個函數調用Int32LT(b, 5)實現b < 5, 第三個函數實現And操作。該方案需要三次函數調用，對性能有明顯的影響。而Odyssey計算引擎採用的方案，使用LLVM生成LLVM IR，在編譯成底層的機器碼，只需要三條指令即可完成這一操作。通過該方案，Odyssey計算引擎避免了大量的冗餘操作，能夠針對不同的表達式、不同的邏輯判斷，生成最小化的底層代碼。
// 實例SQL
select count(*) from table where a > 10 and b < 5;
// ADBPG表達式方案：多次函數調用
result = Int8AndOp(Int32GT(a, 10), Int32LT(b, 5));
// Odyssey方案：生成最小化底層代碼
%res1 = icmp ugt i32 %a, 10;
%res2 = icmp ult i32 %b, 5;
%res = and i8 %res1, %res2;
Code Specialization。 對於一些在執行全已知的邏輯判斷，可以通過LLVM進行code specialization, 從而消除邏輯判斷。例如，某些數據結構的類型SQL解析完成後、在執行引擎開始執行前是確定的，比如每個節點的輸出數據類型、數據長度。如果是使用高級語言（比如C語言）進行執行，由於寫代碼是開發者並不知道數據的類型，需要對每個元素的類型、長度進行判斷。但是LLVM是在代碼生成時就確定了數據的類型，因此生成的最終代碼無需進行判斷、直接進行操作即可。由於執行引擎經常需要進行數據類型、長度判斷，儘管每次節省的時間非常少，但是累計下來性能的提升非常明顯。
向量化執行
將按行拉取數據的火山模型改為按batch拉取數據的火山模型後，結合按列存放的優勢，可以更進一步挖掘處理器的性能。例如，批量化處理的模型可以利用CPU的向量指令，或者GPU的眾核優勢，進一步提升性能。
// 偽代碼樣例：利用SIMD指令加速聚合
for (int i = 0; i < round_row; i += 8) {
__m256 m_tmp = _mm256_load_ps(&(aligned_input_data[i]));
__m256 ymm2 = _mm256_permute2f128_ps(m_tmp , m_tmp , 1);
m_tmp = _mm256_add_ps(m_tmp, ymm2);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
result += m_tmp[0];
}
例如OLAP 中常用的Aggregation操作，採用SIMD指令，計算性能能提升4倍左右，偽代碼如上所示。一些更為複雜的算法可以利用GPU眾核計算能力，例如並行過濾、聚合、規約等算法，計算性能最高可以提升一個數量級。
跨平台支持
雲計算時代，雲平台支持多種不同的硬體資源，除傳統x86平台外，國產x86平台、國產ARM平台、GPU、FPGA資源均可支持，用戶只需要購買相應的資源規格即可，滿足了用戶不同的場景需求。Odyssey計算引擎在ADB PG的基礎之上，進一步擴展了支持的範圍，目前Odyssey計算引擎已經完美運行在x86平台和ARM平台上。
除此之外，Odyssey計算引擎支持使用GPU和FPGA對關鍵算子進行加速。GPU作為一種眾核架構，計算資源和帶寬資源充足，適合數據密集型、高吞吐的場景。FPGA作為一種可定製化處理器，非常適合一些邏輯複雜的操作，有效提升硬體的資源利用率。目前Odyssey計算引擎支持使用GPU加速部分高密度算子，可實現超過5倍的性能提升。支持使用FPGA加速存儲層的壓縮和解壓縮，最高性能提升超過10倍。
性能結果
測試採用的是標準的TPCH測試集，使用TPCH官方的工具生成數據和22條SQL，數據量為1TB，scale factor = 1000，集群規模都為32個segment。22條SQL從Q1到Q22單並發順序、連續執行，每一條SQL發送出去記為開始時間，返回結果為結束時間，執行時間為兩者的差值。
X86平台測試結果
x86平台測試在阿里雲上進行，實例的具體規格如下：
單節點核數：4
單節點內存：32G
單節點磁碟：320G SSD
實例節點數：32
測試結果如下：
從圖中可以看出，Odyssey計算引擎比原生引擎有比較明顯的優勢，Q1、Q4、Q9、Q11、Q17、Q20、Q21、Q22這些SQL有1倍以上的提升，其中Q17有2倍以上的性能提升。提升的比例與SQL類型有關，對於計算密集型的SQL優勢更加明顯。對於IO密集型的SQL，我們在IO接口上做了適配和優化，計算性能提升的同事，IO性能也有提升。
ARM平台測試結果
ARM平台的測試採用三台伺服器，一台作為master，另外兩台作為計算節點。計算節點上各部署16個segment，共32個segment。每台伺服器的配置如下：
CPU：128 cores
內存：378G
磁碟：3.84Tx4 AliFlash
從圖中可以看出，在ARM平台，Odyssey計算引擎也有比較大的優勢，而且相對x86平台，Odyssey在ARM平台上優勢更明顯。
總結
以上是ADB PG新的計算引擎Odyssey的一些技術細節，總的來說，Odyssey使用了新的技術：JIT，新的模型：批量（batch）化的火山模型，新的硬體特性：CPU的AVX指令、GPU的眾核計算、FPGA的專用計算。在公有雲上1TB的TPCH實測，22條語句的總時間是原引擎的50%，單條SQL性能最高提升2倍多；ARM伺服器上搭載Odyssey計算引擎的ADB PG也有一倍的性能提升，並且相對X86平台，Odyssey引擎提升更明顯。
接下來的Odyssey計算引擎還會在存儲層適配優化，更極致的性能優化上下功夫，敬請各位關注!