這就是TDSQL的向量化執行引擎？有效降低函式呼叫開銷，提升CPU利用率

在“國產資料庫硬核技術沙龍-TDSQL-A技術揭祕”系列分享中，5位騰訊雲技術大咖分別從整體技術架構、列式儲存及相關執行優化、叢集資料互動匯流排、Fragment執行框架/查詢分片策略/子查詢框架以及向量化執行引擎等多方面對TDSQL-A進行了深入解讀。沒有觀看直播的小夥伴，可要認真做筆記啦！今天帶來本系列分享中最後一篇騰訊雲資料庫高階工程師胡翔老師主題為“TDSQL-A向量化執行引擎技術揭祕”的分享的文字版。

作為領先的分析型資料庫，TDSQL-A是騰訊首款分散式分析型資料庫，採用全並行無共享架構，具有自研列式儲存引擎，支援行列混合儲存，適應於海量OLAP關聯分析查詢場景。它能夠支援2000臺物理伺服器以上的叢集規模，儲存容量能達到單資料庫例項百P級。

一、TDSQL-A向量化執行引擎

1.1 背景

要優化資料庫的查詢執行效率，就要充分地利用CPU、快取等資源。但在現實中，硬體發展帶來的能力提升並沒有在實際應用中得到體現。右圖統計了不同的資料庫操作的CPU利用率，可以看到像seq scan、index scan這些基本的資料庫操作，實際上並沒有有效地利用好CPU，利用率還是很低。根本原因在於沒有按照最高效使用CPU的方式來設計和實現實際的應用系統。所以我們必須瞭解當代CPU的主要特徵。

當前CPU主要具有以下五個特徵： ●流水線。可以允許一個指令週期內執行多個命令，具有多個核心的CPU還支援超標量流水線，允許併發執行多個流水線，進一步提高CPU的計算能力。 ●亂序執行。可以允許不具有依賴關係的指令併發執行，避免因為等待某個指令而阻塞執行。 ●分支預測。CPU會對分支進行預測並根據預測選取下一步執行的路徑，提前載入指令和資料，但如果分支預測失敗，也會導致流水線中斷。 ●分層儲存。CPU周圍設定了暫存器、L1/L2/L3快取、記憶體和磁碟等多級儲存，資料越靠近CPU，計算速度越快，反之，如果頻繁地從記憶體或者磁碟讀取資料，會導致CPU把較多的時間浪費到IO上，計算效率減低。 ●SIMD等新硬體能力。SIMD即單指令多資料流，一次操作完成多組運算元的計算，可以進一步提高計算效率。像SIMD等新硬體提供了更強的執行能力。

我們針對CPU的這些特徵，提出了幾個資料庫查詢效能的優化方向： 首先，可以通過向量化批量計算提高CPU流水線和亂序執行的執行效率；其次，編寫CPU計算友好的程式，比如通過減少上下依賴、減少分支、預取資料到快取等方式，讓CPU集中於計算任務；最後，還可以通過SIMD來對計算密集型的簡單程式進行改造，加速計算效率。

1.2 向量化計算 顧名思義，向量化計算就是按照向量的方式計算，也就是一次計算多對運算元。

按照實現方式的不同，向量化主要分為以下三種類型： ●自動向量化。編譯器可以識別出迴圈內哪些操作可以寫成向量化執行的方式，但要求必須是簡單的迴圈，不能包含條件、跳轉等語句，不能包含前後依賴關係，硬體也必須要支援SIMD指令。 ●新增編譯器提示。通過使用一些關鍵字或者預編譯指令，強制進行向量化。 ●顯式向量化。通過CPU提供的SIMD指令集來手工編寫向量化執行的程式碼。

三種方式中，第一種是最為簡單也是應用最廣泛的方式，只需要遵循一定的程式碼編寫規則即可，不會影響原來程式碼的邏輯性和可讀性，效能加速效果也不錯。而另外兩種方式對程式設計人員的要求很高，需要結合編譯器和硬體能力來做深度優化。

1.3 列儲存

這裡再次介紹一下列儲存，因為列儲存跟向量化密切相關，向量化計算就是基於列儲存來構建。

我們先來了解下資料庫儲存。資料庫儲存主要分為兩類：行儲存和列儲存。

行儲存中，每一行的元組的每一列實際上是連續儲存的，這樣的優點是易於新增或者修改一個元組，但在讀取資料時可能會額外讀到不需要的列，比較適合於包含大量高併發增刪改查事務的OLTP場景。

列儲存中，每一列是單獨儲存的，這樣就可以只讀取需要的列，但缺點是元組的寫入需要操作多個檔案，比較適合於包含大資料量讀取和複雜計算的OLAP場景。

採用列儲存的好處有很多。除了上面提到的資料裁剪能力之外，列儲存還可以通過壓縮演算法帶來更高的壓縮比，也可以通過字典裡列排序或者稀疏索引加速資料的查詢效率。另外，這種列式的儲存組織形式還為上層計算的效能優化提供了很大的便利，特別是在向量化查詢和延遲物化等方面。

1.4 向量化查詢執行引擎

這部分主要介紹的是，如何結合前面提到的向量化和列儲存技術，來對查詢執行引擎進行向量化加速計算。

傳統查詢執行引擎採用火山模型，按照一次處理一個元組的方式，邏輯非常簡單，便於開發實現，但是效率比較低，主要原因有以下三點：

首先，CPU把大部分時間都花在遍歷查詢操作樹上，而不是在真正處理資料。一次處理一個Tuple的處理速度可能非常快，但是處理完之後就需要呼叫下層運算元獲取下一個tuple，這就導致函式呼叫的次數比較多，這樣就進而會浪費掉CPU的很多時間。其次，資料和指令的快取命中率低。頻繁的函式呼叫導致暫存器需要儲存更多的資訊，而且實現時可能會為了通用性的考慮，對介面進行封裝，這就會導致複雜度的提升，執行越複雜就會導致快取利用率越低。最後，這種傳統的方式無法利用新硬體提供的SIMD能力進行進一步優化。

與之相比，向量化查詢執行引擎仍然採用火山模型，但是按照一次處理一組元組的方式，實現批量讀取和批量處理，大大減少了函式呼叫開銷，CPU可以把更多的時間集中到實際的計算上，效率會更高。

按照向量化計算的方式，對一組資料做簡單的迴圈計算，同時資料按照列組織形式表示成列向量，每個列向量對應的一整塊連續資料，進而可以批量讀入快取以及進行批量處理，這就可以大大提高指令、資料的快取命中率，進而提高CPU的執行效率。

以上圖中的例子為例。這是一個帶where子句的聚合運算語句，左邊是行儲存非向量化查詢執行過程，右邊是列儲存向量化查詢執行過程。基於列儲存，我們只需要獲取id和agg列的資料。基於向量化查詢執行引擎，每層運算元獲取的都是表示成列向量的一組元組，並對每個列向量進行批量計算。

1.5 向量化執行例項

下面通過一個聚合計算的例子來進一步介紹向量化執行的具體步驟。

這個例子使用兩個列進行分組，並對每個組內進行count(*)計算。整個流程包含兩個步驟：一是構建hash table並在每個hash entry上計算聚合結果；二是遍歷hash table，計算最終的聚合結果。

向量化改造之後，一些具體步驟可以通過簡單的迴圈來進行批量處理。

首先，根據輸入的向量在分組列上批量計算Hash值；其次，根據上一步計算的Hash值批量獲取Hash bucket值；然後，批量處理輸入向量內的每個元組，在Hash table內查詢匹配的Hash entry或者建立新的Hash entry，如果發生雜湊衝突，按照Open addressing的處理方式，繼續對下一個位置進行匹配處理；接著根據上一步獲取的對應每個輸入向量的Hash entry，批量計算Agg結果並更新到對應的Hash entry上（count++）；最後，掃描Hash table的每一個Hash entry，計算最終的Agg結果（count計算不需要此步驟），將結果組織成向量形式返回給上層運算元。

1.6 向量化執行效果

接下來看一下向量化執行的效果。下面給出了一些測試用例，主要包含多種不同型別的Agg和Join場景，涵蓋了定長和變長列。

藍色是行存，橙色是原列存，灰色是列存向量化。測試了1G/10G/100G的結果，可以看出列存向量化的執行時間最短。資料量越大，原列存和列存向量化效果越明顯。最好的情況下，列存向量化執行時間是原列存的1/2，列存向量化執行時間是行存的1/8。

1.7 下一步計劃

最後介紹關於向量化的下一步計劃，主要有以下四方面： ●Just-in-Time編譯優化。對函式呼叫進行展開，減少函式呼叫，比較適合於複雜的表示式或者運算元計算。 ●SIMD指令加速。適合於簡單的線性計算，可以利用現代CPU的SSE、AVX指令讓一條指令實現512bit資料計算。 ●Hash Agg/Hash Join等演算法進一步向量化優化。 ●列存掃描等儲存相關部分進一步優化。

二、TDSQL-A與CK的對比

2.1 CK介紹

CK是目前社群裡面比較熱門的，應用場景也比較廣泛。

首先，在架構上，叢集內劃分為多個分片，通過分片的線性擴充套件能力，支援海量資料的分散式儲存計算，每個分片內包含一定數量的節點Node，即程序，Node之間互為副本，通過ZooKeeper進行資料同步。

其次，CK的資料模型主要使用MergeTree表引擎——一種LSM Tree的實現，同時支援分散式表，寫入時進行資料轉發，讀取時進行資料收集。

再者，在儲存上，CK採用了列存、分割槽、資料排序和分塊、主鍵索引等方式。最後，在計算上，CK採用向量化執行方式，利用SIMD指令加速。

2.2 儲存引擎

在儲存引擎上來看，TDSQL-A和CK各有自己鮮明的特點。

TDSQL-A採用的是典型的列存設計，功能完備，包括完整的事務能力，同時還設計一些特殊的優化來加速資料讀寫操作。

2.3 SQL引擎

在SQL引擎上，TDSQL-A繼承了PG原生的SQL能力，SQL完備且相容性好，支援多表關聯、儲存過程等複雜查詢，另外TDSQL-A在分散式架構上對優化器和執行器具有很多優化。我們也在分散式架構上做了一些併發器和執行器的優化，左圖實際上就是分散式的一個重要例子。

CK也具有出色的向量化執行引擎，特別是在AGG計算中，針對不同資料型別設計不同的資料結構和演算法，將CPU和記憶體能力發揮到極致。右圖中列了一下針對於Hash AGG計算設計的不同資料結構。

2.4 對比

整體來看，TDSQL-A相比於CK，在SQL能力、事務能力、優化器能力、分散式管控能力以及高可用能力上具有優勢，而CK則在計算引擎執行效率上表現突出。

TDSQL-A受惠於PG社群的長期積累，同時經過我們團隊長時間的功能增強、效能優化以及在多個應用領域的實踐，已經具備了全面和強大的能力，可以提供企業級一站式解決方案，可以把事務、高可用以及部分業務邏輯放到資料庫中來處理，大大降低業務的複雜程度。我們也將繼續與PG社群、CK社群等優秀開源社群保持緊密聯絡，吸收改進新的發展技術和研究成果，不斷地提高TDSQL-A的能力並開放給我們的使用者。

本文由部落格一文多發平臺 OpenWrite 釋出！