這就是TDSQL的向量化執(zhí)行引擎？有效降低函數(shù)調(diào)用開銷，提升CPU利用率

在“國產(chǎn)數(shù)據(jù)庫硬核技術(shù)沙龍-TDSQL-A技術(shù)揭秘”系列分享中，5位騰訊云技術(shù)大咖分別從整體技術(shù)架構(gòu)、列式存儲及相關(guān)執(zhí)行優(yōu)化、集群數(shù)據(jù)交互總線、Fragment執(zhí)行框架/查詢分片策略/子查詢框架以及向量化執(zhí)行引擎等多方面對TDSQL-A進行了深入解讀。沒有觀看直播的小伙伴，可要認(rèn)真做筆記啦！今天帶來本系列分享中最后一篇騰訊云數(shù)據(jù)庫高級工程師胡翔老師主題為“TDSQL-A向量化執(zhí)行引擎技術(shù)揭秘”的分享的文字版。

作為領(lǐng)先的分析型數(shù)據(jù)庫，TDSQL-A是騰訊首款分布式分析型數(shù)據(jù)庫，采用全并行無共享架構(gòu)，具有自研列式存儲引擎，支持行列混合存儲，適應(yīng)于海量OLAP關(guān)聯(lián)分析查詢場景。它能夠支持2000臺物理服務(wù)器以上的集群規(guī)模，存儲容量能達到單數(shù)據(jù)庫實例百P級。

一、TDSQL-A向量化執(zhí)行引擎

1.1 背景

要優(yōu)化數(shù)據(jù)庫的查詢執(zhí)行效率，就要充分地利用CPU、緩存等資源。但在現(xiàn)實中，硬件發(fā)展帶來的能力提升并沒有在實際應(yīng)用中得到體現(xiàn)。右圖統(tǒng)計了不同的數(shù)據(jù)庫操作的CPU利用率，可以看到像seq scan、index scan這些基本的數(shù)據(jù)庫操作，實際上并沒有有效地利用好CPU，利用率還是很低。根本原因在于沒有按照最高效使用CPU的方式來設(shè)計和實現(xiàn)實際的應(yīng)用系統(tǒng)。所以我們必須了解當(dāng)代CPU的主要特征。

當(dāng)前CPU主要具有以下五個特征：

·流水線?？梢栽试S一個指令周期內(nèi)執(zhí)行多個命令，具有多個核心的CPU還支持超標(biāo)量流水線，允許并發(fā)執(zhí)行多個流水線，進一步提高CPU的計算能力。

·亂序執(zhí)行?？梢栽试S不具有依賴關(guān)系的指令并發(fā)執(zhí)行，避免因為等待某個指令而阻塞運行。

·分支預(yù)測。CPU會對分支進行預(yù)測并根據(jù)預(yù)測選取下一步執(zhí)行的路徑，提前加載指令和數(shù)據(jù)，但如果分支預(yù)測失敗，也會導(dǎo)致流水線中斷。

·分層存儲。CPU周圍設(shè)置了寄存器、L1/L2/L3緩存、內(nèi)存和磁盤等多級存儲，數(shù)據(jù)越靠近CPU，計算速度越快，反之，如果頻繁地從內(nèi)存或者磁盤讀取數(shù)據(jù)，會導(dǎo)致CPU把較多的時間浪費到IO上，計算效率減低。

·SIMD等新硬件能力。SIMD即單指令多數(shù)據(jù)流，一次操作完成多組操作數(shù)的計算，可以進一步提高計算效率。像SIMD等新硬件提供了更強的執(zhí)行能力。

我們針對CPU的這些特征，提出了幾個數(shù)據(jù)庫查詢性能的優(yōu)化方向：

首先，可以通過向量化批量計算提高CPU流水線和亂序執(zhí)行的執(zhí)行效率；其次，編寫CPU計算友好的程序，比如通過減少上下依賴、減少分支、預(yù)取數(shù)據(jù)到緩存等方式，讓CPU集中于計算任務(wù)；最后，還可以通過SIMD來對計算密集型的簡單程序進行改造，加速計算效率。

1.2 向量化計算

顧名思義，向量化計算就是按照向量的方式計算，也就是一次計算多對操作數(shù)。

按照實現(xiàn)方式的不同，向量化主要分為以下三種類型：

·自動向量化。編譯器可以識別出循環(huán)內(nèi)哪些操作可以寫成向量化執(zhí)行的方式，但要求必須是簡單的循環(huán)，不能包含條件、跳轉(zhuǎn)等語句，不能包含前后依賴關(guān)系，硬件也必須要支持SIMD指令。

·添加編譯器提示。通過使用一些關(guān)鍵字或者預(yù)編譯指令，強制進行向量化。

·顯式向量化。通過CPU提供的SIMD指令集來手工編寫向量化執(zhí)行的代碼。

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

1.3 列存儲

這里再次介紹一下列存儲，因為列存儲跟向量化密切相關(guān)，向量化計算就是基于列存儲來構(gòu)建。

我們先來了解下數(shù)據(jù)庫存儲。數(shù)據(jù)庫存儲主要分為兩類：行存儲和列存儲。

行存儲中，每一行的元組的每一列實際上是連續(xù)存儲的，這樣的優(yōu)點是易于添加或者修改一個元組，但在讀取數(shù)據(jù)時可能會額外讀到不需要的列，比較適合于包含大量高并發(fā)增刪改查事務(wù)的OLTP場景。

列存儲中，每一列是單獨存儲的，這樣就可以只讀取需要的列，但缺點是元組的寫入需要操作多個文件，比較適合于包含大數(shù)據(jù)量讀取和復(fù)雜計算的OLAP場景。

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

1.4 向量化查詢執(zhí)行引擎

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

傳統(tǒng)查詢執(zhí)行引擎采用火山模型，按照一次處理一個元組的方式，邏輯非常簡單，便于開發(fā)實現(xiàn)，但是效率比較低，主要原因有以下三點：

首先，CPU把大部分時間都花在遍歷查詢操作樹上，而不是在真正處理數(shù)據(jù)。一次處理一個Tuple的處理速度可能非?？?，但是處理完之后就需要調(diào)用下層算子獲取下一個tuple，這就導(dǎo)致函數(shù)調(diào)用的次數(shù)比較多，這樣就進而會浪費掉CPU的很多時間。其次，數(shù)據(jù)和指令的緩存命中率低。頻繁的函數(shù)調(diào)用導(dǎo)致寄存器需要保存更多的信息，而且實現(xiàn)時可能會為了通用性的考慮，對接口進行封裝，這就會導(dǎo)致復(fù)雜度的提升，執(zhí)行越復(fù)雜就會導(dǎo)致緩存利用率越低。最后，這種傳統(tǒng)的方式無法利用新硬件提供的SIMD能力進行進一步優(yōu)化。

與之相比，向量化查詢執(zhí)行引擎仍然采用火山模型，但是按照一次處理一組元組的方式，實現(xiàn)批量讀取和批量處理，大大減少了函數(shù)調(diào)用開銷，CPU可以把更多的時間集中到實際的計算上，效率會更高。

按照向量化計算的方式，對一組數(shù)據(jù)做簡單的循環(huán)計算，同時數(shù)據(jù)按照列組織形式表示成列向量，每個列向量對應(yīng)的一整塊連續(xù)數(shù)據(jù)，進而可以批量讀入緩存以及進行批量處理，這就可以大大提高指令、數(shù)據(jù)的緩存命中率，進而提高CPU的執(zhí)行效率。

以上圖中的例子為例。這是一個帶where子句的聚合運算語句，左邊是行存儲非向量化查詢執(zhí)行過程，右邊是列存儲向量化查詢執(zhí)行過程?；诹写鎯?，我們只需要獲取id和agg列的數(shù)據(jù)?；谙蛄炕樵儓?zhí)行引擎，每層算子獲取的都是表示成列向量的一組元組，并對每個列向量進行批量計算。

1.5 向量化執(zhí)行實例

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

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

向量化改造之后，一些具體步驟可以通過簡單的循環(huán)來進行批量處理。

首先，根據(jù)輸入的向量在分組列上批量計算Hash值；其次，根據(jù)上一步計算的Hash值批量獲取Hash bucket值；然后，批量處理輸入向量內(nèi)的每個元組，在Hash table內(nèi)查找匹配的Hash entry或者創(chuàng)建新的Hash entry，如果發(fā)生哈希沖突，按照Open addressing的處理方式，繼續(xù)對下一個位置進行匹配處理；接著根據(jù)上一步獲取的對應(yīng)每個輸入向量的Hash entry，批量計算Agg結(jié)果并更新到對應(yīng)的Hash entry上（count++）；最后，掃描Hash table的每一個Hash entry，計算最終的Agg結(jié)果（count計算不需要此步驟），將結(jié)果組織成向量形式返回給上層算子。

1.6 向量化執(zhí)行效果

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

藍色是行存，橙色是原列存，灰色是列存向量化。測試了1G/10G/100G的結(jié)果，可以看出列存向量化的執(zhí)行時間最短。數(shù)據(jù)量越大，原列存和列存向量化效果越明顯。最好的情況下，列存向量化運行時間是原列存的1/2，列存向量化運行時間是行存的1/8。

1.7 下一步計劃

最后介紹關(guān)于向量化的下一步計劃，主要有以下四方面：

·Just-in-Time編譯優(yōu)化。對函數(shù)調(diào)用進行展開，減少函數(shù)調(diào)用，比較適合于復(fù)雜的表達式或者算子計算。

·SIMD指令加速。適合于簡單的線性計算，可以利用現(xiàn)代CPU的SSE、AVX指令讓一條指令實現(xiàn)512bit數(shù)據(jù)計算。

·Hash Agg/Hash Join等算法進一步向量化優(yōu)化。

·列存掃描等存儲相關(guān)部分進一步優(yōu)化。

二、TDSQL-A與CK的對比

2.1 CK介紹

CK是目前社區(qū)里面比較熱門的，應(yīng)用場景也比較廣泛。

首先，在架構(gòu)上，集群內(nèi)劃分為多個分片，通過分片的線性擴展能力，支持海量數(shù)據(jù)的分布式存儲計算，每個分片內(nèi)包含一定數(shù)量的節(jié)點Node，即進程，Node之間互為副本，通過ZooKeeper進行數(shù)據(jù)同步。

其次，CK的數(shù)據(jù)模型主要使用MergeTree表引擎——一種LSM Tree的實現(xiàn)，同時支持分布式表，寫入時進行數(shù)據(jù)轉(zhuǎn)發(fā)，讀取時進行數(shù)據(jù)收集。

再者，在存儲上，CK采用了列存、分區(qū)、數(shù)據(jù)排序和分塊、主鍵索引等方式。最后，在計算上，CK采用向量化執(zhí)行方式，利用SIMD指令加速。

2.2 存儲引擎

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

TDSQL-A采用的是典型的列存設(shè)計，功能完備，包括完整的事務(wù)能力，同時還設(shè)計一些特殊的優(yōu)化來加速數(shù)據(jù)讀寫操作。

2.3 SQL引擎

在SQL引擎上，TDSQL-A繼承了PG原生的SQL能力，SQL完備且兼容性好，支持多表關(guān)聯(lián)、存儲過程等復(fù)雜查詢，另外TDSQL-A在分布式架構(gòu)上對優(yōu)化器和執(zhí)行器具有很多優(yōu)化。我們也在分布式架構(gòu)上做了一些并發(fā)器和執(zhí)行器的優(yōu)化，左圖實際上就是分布式的一個重要例子。

CK也具有出色的向量化執(zhí)行引擎，特別是在AGG計算中，針對不同數(shù)據(jù)類型設(shè)計不同的數(shù)據(jù)結(jié)構(gòu)和算法，將CPU和內(nèi)存能力發(fā)揮到極致。右圖中列了一下針對于Hash AGG計算設(shè)計的不同數(shù)據(jù)結(jié)構(gòu)。

2.4 對比

整體來看，TDSQL-A相比于CK，在SQL能力、事務(wù)能力、優(yōu)化器能力、分布式管控能力以及高可用能力上具有優(yōu)勢，而CK則在計算引擎執(zhí)行效率上表現(xiàn)突出。

TDSQL-A受惠于PG社區(qū)的長期積累，同時經(jīng)過我們團隊長時間的功能增強、性能優(yōu)化以及在多個應(yīng)用領(lǐng)域的實踐，已經(jīng)具備了全面和強大的能力，可以提供企業(yè)級一站式解決方案，可以把事務(wù)、高可用以及部分業(yè)務(wù)邏輯放到數(shù)據(jù)庫中來處理，大大降低業(yè)務(wù)的復(fù)雜程度。我們也將繼續(xù)與PG社區(qū)、CK社區(qū)等優(yōu)秀開源社區(qū)保持緊密聯(lián)系，吸收改進新的發(fā)展技術(shù)和研究成果，不斷地提高TDSQL-A的能力并開放給我們的用戶。