一、ADB PG 和Laser 計算引擎的介紹
（一）ADB PG 架構
ADB PG 是一款雲原生資料倉庫，在保證事務ACID 能力的前提下，主要解決雲上海
量資料的實時分析問題。它的架構與傳統的MPP 資料倉庫非常類似，主要分成兩層，第一層是master 節點；第二層是work 節點。
master 節點主要承擔實時寫入和事務的處理，執行計劃的生成。與其他的傳統的
MPP 資料倉庫不同的是ADB PG 的master 節點支援線性擴充，可以通過多個master
提升整體的事務能力、實時寫入吞吐能力。
work 節點主要承擔兩個功能，第一個功能是執行，第二個功能是存儲。執行引擎采用
的是向量化執行引擎，通過向量列式Batch 處理，codegen 技術，以及Fusion Scan 加速列式計算效率，在一些分析場景性能相對于普通的火山模型有了3~5 倍的提升。
同時它的存儲節點不僅支援傳統的行表和清單，也可以通過外表方式支援一些開源的表
結構，例如Parquet、ORC 等開源資料結構。ADB PG 可以直接分析儲存在類似于像
OSS/HDFS 等分布式存儲上的資料，減少資料的導入，可以大幅的降低使用者的使用門檻和存儲成本。
（二）為什麼做Laser 計算引擎
為什麼不采用PG 原生的計算引擎？
第一，PG 是一個傳統的事務型資料庫，它主要的優化大多來自于TP 的事務優化，并沒有針對海量資料的分析計算做定制化的優化。
第二，PG 計算引擎采用解釋執行的邏輯，複雜表達式采用函數執行樹的遞歸的調用解
釋執行。如圖中的例子所示，每個表達式都被翻譯成一個函數并組成一個執行樹。每一條的資料都通過以上的函數遞歸調用去完成最終的計算。它帶來的問題就是在海量千萬以上的資料計算場景，虛函數調用大幅影響計算的性能。
第三， PG 預設隻支援行存存儲引擎，并不支援列存，是以它的整個計算執行過程是逐行處理資料，并沒有對列存做定制化的優化。
第四， PG 代碼具有非常好的擴充性、相容性，但是在性能上考慮不多。例如說在計算過程中會涉及到記憶體的多次拷貝，序列化的開銷比較高。
最後，PG 采用的是單分區單程序執行模式，無法充分發揮現代多核CPU 的優勢。
（三）主流OLAP 業界方案
在開始ADB PG 計算引擎的選型過程，我們重點調研了目前主流的OLAP 業界主流
方案。
主要分成兩大類，第一類：向量化執行；第二類：編譯執行。
第一：向量化執行的基本做法，非常類似于火山模型，主要差别來自于它采用的是批量計算，每一批裡優先列式計算。
這種模式優勢在于可以充分發揮CPU 的流水線執行和記憶體的順序通路，減少cache
的miss。缺點是第一實作邏輯比較複雜。第二，它需要批量的資料，并不适合每次計算數量較小的OLTP 場景。第三,它需要緩存批量資料，緩存本身帶來一定的記憶體開銷。
第二：編譯執行基本做法是使用Codegen 技術，将所有的算子編譯成函數，通過PUSH 的模型自下而上通過資料上推完成計算。
優點一：由于每次計算的都是一行資料，執行過程可以将這一行資料儲存在寄存器裡面，寄存器計算代替記憶體計算。優點二，它通過Codegen 技術把複雜的算子編譯成一個函數，是以它非常适合計算複雜性非常高的計算加速。
缺點在于，PUSH 模型控制邏輯比較複雜，同時由于采用單條計算，無法做到記憶體的順序通路，是以它整體的Cache miss 率比較高。典型的代表産品有Spark 和 Peloton。
ADB PG 綜合考慮這兩類方案的優缺點，最終使用了向量化的方案，主要考慮到ADB PG 原生PG 火山模型與向量化模型架構上較為接近，改造成向量計算引擎的邏輯順暢，改造成本較編譯執行小。
（四）業界主流計算引擎對比
我們對業界主流開源計算引擎做了對比，包括ClickHouse、PG11、Spark、ADBPG。在執行模型上，ClickHouse 和ADB PG、PG11 都采用的向量執行，Spark 采用
的是編譯執行。
在記憶體模型上，ClickHouse 采用的是列存、PG11 采用行存、Spark 采用行存、ADB PG 采用行列混存。行列混存主要應用在類似于join、AGG 的場景，我們可以将多列group by、hashtable 資料拼成一列資料，可以充分發揮順序通路的效率。
在即時編譯上，ClickHouse 采用表達式級LLVM、PG11 采用表達式級LLVM，Spark 采用Stage Java 技術,ADB PG 采用算子級LLVM 技術。算子級LLVM 技術可以提升算子的計算性能。
在硬體加速上，ClickHouse 和PG11 都不支援硬體加速，Spark 支援FPGA 加速，ADB PG 采用IR 技術，可以通過将IR 翻譯成對應的機器執行代碼,進而支援GPU 加速。
二、laser 計算引擎的核心技術
Laser 計算引擎的核心技術主要包括5 大塊:
1. 向量計算引擎
2. 行列式記憶體模型
3. JIT 加速
4. SIMD 指令加速
5. FUSION SCAN
第一,向量計算引擎，傳統火山模型中算子之間資料逐條互動，向量化計算引擎之間的互動的是BATCH 資料，然後在每個算子内部，采用的列式多條資料并行計算，這種邏輯可以充分的發揮CPU 流水線的作用。
在記憶體模型上，我們采用的是行列混存記憶體模型。在算子之間資料傳遞的是一個mini batch，mini batch 内部采用的行列混存的結構。由于每列資料在記憶體裡都是連續擺放的，是以每次計算一列都是記憶體的順序通路的過程。
第三，針對複雜計算，采用JIT 技術加速。可以利用LLVM CodeGen 技術将複雜計算過程轉換成IR 代碼，然後再通過IR 代碼翻譯成機器碼。它的好處是可以避免類型判斷，減少虛函數的調用，進而提升計算性能。
第四，針對一些簡單場景（如：聚合場景、固定場景），利用現代CPU 的SIMD 指令，實作單條指令多條資料的并行執行，大幅提升這些簡單場景的效率。
第五，針對列存場景，可以通過FUSION SCAN 去減少無用列讀取，避免無用記憶體的中間拷貝，進而提升清單的計算性能。
（一）向量計算引擎
下圖是一個典型的火山模型下SUM 算子的計算過程。對于火山模型，如果總共有n條資料，就會調用n 次的函數調用。右邊是向量化執行過程，sum 函數接收輸入參數是一個數組，而不是兩個變量。整個執行過程，資料按2048 條分批處理，每2048 條資料調用一次sum 函數。
從這個例子中明顯可以看出：
第一，Sum 函數調用從原來的n 次變成n÷2048，減少了多次。
第二，在函數内部進行中，由于計算的資料是一個batch，就可以充分發揮SIMD 指令加速效果，實作單條指令多條語句的并行計算。
第三，可以針對一些算子，如AGG 和JOIN，可以将AGG 和JOIN 算子函數合并一個函數，可以進一步的減少虛函數調用，提升系統性能。
由于計算過程中全部采用數組計算，可以将計算過程中的數組使用記憶體池化技術管理。通過MemoryPool 可以實作定長資料的記憶體的複用，避免頻繁記憶體配置設定和釋放，減少整個記憶體的碎片。在實際的TPC-H 的測試中，使用向量化引擎後，Q1 提升了120%，Q18提升了190%。
（二）SIMD指令加速
針對簡單的加速，可以利用現代CPU 的SSE、AVX 指令，一條指令可以實作512bit 資料計算。
我們對TPCH 測試中的Lineitem 表做性能的對比測試，在使用SIMD 以後，整體的性能從原來的1 秒多降低到了200 多毫秒，有了4 倍左右的提升。
（三）Just-in-Time 編譯優化
ADB PG 不僅支援表達式級的CodeGen，也支援算子級的CodeGen。每個plan的node 對應一個CodeGen 單元和一個Executor，CodeGen 單元根據plan node 生成code(IR)，Executor 根據硬體平台選擇不同的後端，将IR 生成對應的執行檔案，并申請資源執行，最終的結果通過master 傳回給用戶端。
如圖所示，對于這樣一個簡單的表達式，where a>10 and b<5，如果采用解釋執行，總共包括三次函數調用，1、a>10；2、b<5；3、and 函數。
如果使用LLVM GIT 編譯優化，上面的三個函數就編譯成三條LLVM 指令，避免了三次函數調用的開銷。
在TPCH 測試場景中，使用JIT 加速後整體的性能提升了20%~30%，并且在測試中發現,表達式越複雜，性能提升越明顯。
（四）Fusion Scan 優化
Fusion Scan 主要優化是減少無用列的讀取，并且盡量的減少無用資料的讀取和記憶體的拷貝。
舉個例子，如果要查詢滿足a 大于3 和b 小于6 的a，c*d 的值，傳統做法是對資料庫中的每條資料資料，做a 大于3 和b 小于6 的條件過濾并且計算對應列的值。
Fusion Scan 的做法分成兩階段：
第一階段是對過濾列做計算。把a 列和b 列的所有資料讀出來，對每條資料進行判斷。如圖所示，滿足條件的隻有第一行第三行，我們把第一行第三行号儲存在一個bitset中，同時把第一行和第三行的a 列值也儲存在mini batch 中；
第二階段是計算project 列，由于滿足這個條件隻有第一行和第三行，我們隻需要把c 列和d 列的第一行和第三行的值讀取出來。同時為了避免中間結果的資料拷貝，我們直接去将c 列和d 列的值結果相乘，把結果儲存在mini batch 的第二列中。
在計算過程中，我們提前将表達式編譯成IR 代碼，可以避免了多次表達式函數的遞歸調用。
以上過程的主要優化點在于：
第一、避免無用清單D、E、F、G 列讀取；
第二、實作了按需讀取，隻有滿足條件的c 列和d 列的裡面内容才進行計算和IO，不需要讀那些不滿足條件的資料。同時在c 和d 計算過程中，直接進行c 和d 的讀取，無需記憶體中間結果的拷貝。
在實際執行過程中，Fusion Scan 結合列存塊block 索引做進一步的優化。block
索引中包含了資料塊的min 和max，我們可以将min 和max 值和where 條件做交集，
隻有這個交集非空的話，才會去真正讀取block 的值，否則可以直接跳過這個block。
通過Fusion Scan 的技術，在列存的場景Scan 算子整體的性能有3 倍以上的提升。
（五）算子實作-HashJoin
HashJoin 的向量化執行引擎，算法采用Hybrid Hash Join，HashTable 采用開放連結清單資料結構。
HashJoin 的實作過程，主要包括：
1. 把左表probe 列的值取出來計算它的Hash 值。
2. Hashcode 的值去模entry 個數，擷取對應的行号。
3. 對應行号裡的所有的entry 對象，比較它的哈希值，如果哈希值相同，再去比較join key。
4. 如果join key 相同，則代表probe 成功，拼接左右表的對應列并生成最終的結果。
如何将這樣的執行過程用向量化實作?
1. 從左表裡面讀取批量資料。
2. 使用CodeGen 技術批量計算hash code 值。
3. 根據hashcode 值，批量查找hash table，得到可能的結果集。
4. 批量比較左右表的join 列值，如果比對的話，則拼接左右表的對應列并生成最終的結果。
與原來行式的火山模型比起來，向量化執行主要差一點在于：
1. 按列計算；
2. 批量計算。
（六）插件內建
計算引擎如何與ADB PG 代碼融合？
ADB PG 同時支援PG 計算引擎和Laser 向量化計算引擎。優化器會自動根據SQL 的pattern 和掃描的資料量來決定是否使用Laser。如果掃描資料量太少，則使用原生的計算引擎。如果資料量足夠多，并且這些SQL pattern 比較适合使用向量化執行引擎的，就使用laser 計算引擎。
Laser 引擎的所有代碼采用插件模式，代碼獨立。好處在于代碼可以和原生代碼之間完全是松耦合關系，不會影響PG 的原生代碼，同時可以複用裡面的一些函數和資料結構。插件模式還帶來一個好處，就是可以實作熱更新。因為采用動态庫方式，能夠在不重新開機PGdameon 程序的情況下，替換插件，完成更新LASER 引擎。
唯一需要修改的是三個stub 函數—ExecutorStart、ExecutorRun、ExecutorEnd。
（七）TPC-H 結果
2020 年5 月20 号，我們完成了TPC-H 30TB 場景測試，拿到了世界第一的成績。相比于第二名微軟SQL Server 2019，整體性能提升了290%，且成本隻有SQL
Server 的1/4。
通過性能名額統計，Laser 計算引擎對性能提升起了至關重要的價值，相對于PG 計算引擎，性能提升了兩倍之多。細分計算引擎的各種優化，其中大半的性能提升都是來自于向量化提升。其次是是JIT 加速，主要來源于表達式的計算。第三來自于是Fusion Scan，針對列存場景下，我們通過Fusion Scan，減少了記憶體的拷貝，減少了無用的讀取。最後還有小部分來自于SIMD 指令的提升。
三、計算引擎的未來展望
整體的未來轉化（以未來一年為計劃）：
第一：2020 年12 月，支援視窗函數，完成全算子的向量化改造。
第二：2020 年3 月，完成網絡motion 重構。
第三：2020 年6 月，完成算子并行執行優化，可以充分利用多核能力。
第四：2020 年9 月，完成優化器适配。優化器不僅适配計劃資料書，同時能夠根據計算引擎來做動态識别，能夠感覺到資料的動态變化，再去動态去調整執行計劃。