TDSQL-A自研列存儲(chǔ)及優(yōu)化原理大揭秘

在“國(guó)產(chǎn)數(shù)據(jù)庫(kù)硬核技術(shù)沙龍-TDSQL-A技術(shù)揭秘”系列分享中，5位騰訊云技術(shù)大咖分別從整體技術(shù)架構(gòu)、列式存儲(chǔ)及相關(guān)執(zhí)行優(yōu)化、集群數(shù)據(jù)交互總線、Fragment執(zhí)行框架/查詢分片策略/子查詢框架以及向量化執(zhí)行引擎等多個(gè)方面對(duì)TDSQL-A進(jìn)行了深入解讀。錯(cuò)過直播的小伙伴有福啦，今天帶來(lái)本次系列分享中騰訊云數(shù)據(jù)庫(kù)高級(jí)工程師伍鑫老師主題為“TDSQL-A列存儲(chǔ)設(shè)計(jì)原理及執(zhí)行優(yōu)化詳解”的文字版。

TDSQL-A是騰訊首款分布式分析型數(shù)據(jù)庫(kù)，采用全并行無(wú)共享架構(gòu)，適應(yīng)于海量OLAP關(guān)聯(lián)分析查詢場(chǎng)景，能夠支持2000臺(tái)物理服務(wù)器以上的集群規(guī)模，存儲(chǔ)容量能達(dá)到單數(shù)據(jù)庫(kù)實(shí)例百P級(jí)。其中，TDSQL-A還具有自研列式存儲(chǔ)引擎，能支持行列混合存儲(chǔ)，對(duì)分析模型下的查詢語(yǔ)句性能做到了極致優(yōu)化。

1

TDSQL-A整體架構(gòu)

在開始之前，我們先來(lái)了解下TDSQL-A的整體架構(gòu)，它分為這幾個(gè)模塊：

第一是上層的GTM事務(wù)管理器，它主要是負(fù)責(zé)全局事務(wù)的管理，協(xié)調(diào)機(jī)群的事務(wù)，同時(shí)管理集群的全體對(duì)象。右上角是協(xié)調(diào)節(jié)點(diǎn)，它是業(yè)務(wù)訪問入口。協(xié)調(diào)節(jié)點(diǎn)模塊是水平對(duì)等的，也就是說業(yè)務(wù)連接到任何一個(gè)協(xié)調(diào)節(jié)點(diǎn)上，都能夠獲得到一致的數(shù)據(jù)庫(kù)視圖。

第二是下方的數(shù)據(jù)節(jié)點(diǎn)。數(shù)據(jù)節(jié)點(diǎn)也是實(shí)際存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)，每個(gè)數(shù)據(jù)節(jié)點(diǎn)只會(huì)存儲(chǔ)數(shù)據(jù)的分片，而數(shù)據(jù)節(jié)點(diǎn)之間加在一起會(huì)形成一個(gè)完整的數(shù)據(jù)視圖。

而數(shù)據(jù)節(jié)點(diǎn)和協(xié)調(diào)節(jié)點(diǎn)之間是集群的數(shù)據(jù)交互總線。集群交互總線的目的是把集群內(nèi)部節(jié)點(diǎn)連接在一起，從而完成整個(gè)查詢交互。

最后，左側(cè)描述的是數(shù)據(jù)庫(kù)內(nèi)核的運(yùn)維管控系統(tǒng)。通過運(yùn)維管理、實(shí)時(shí)監(jiān)控、實(shí)時(shí)告警、安全審計(jì)和數(shù)據(jù)治理等功能，可以進(jìn)行自動(dòng)化的運(yùn)維，減少運(yùn)維人員和用戶使用的成本。

2

自研列存儲(chǔ)帶來(lái)極致優(yōu)化性能

我們今天主要分享兩個(gè)方面，一個(gè)是TDSQL-A自研列存儲(chǔ)，另外一個(gè)是基于自研列存儲(chǔ)的優(yōu)化器相關(guān)優(yōu)化。現(xiàn)在先來(lái)看看TDSQL-A的自研列存儲(chǔ)。

說到列存儲(chǔ)，相信大家都比較熟悉。列存儲(chǔ)對(duì)具體的查詢模型或者訪問模型本身是有特殊優(yōu)化的。傳統(tǒng)情況下，數(shù)據(jù)庫(kù)更多的是偏向事務(wù)型的場(chǎng)景，在每次數(shù)據(jù)寫入的時(shí)候，都會(huì)把整行寫到存儲(chǔ)上面，一次磁盤IO可以訪問所有列。這種場(chǎng)景在面對(duì)互聯(lián)網(wǎng)這種大數(shù)據(jù)量分析的情況下，可能有些列在計(jì)算的時(shí)候并不需要訪問，這會(huì)帶來(lái)IO訪問上的瓶頸，同時(shí)在后續(xù)優(yōu)化上，也不方便針對(duì)特定的計(jì)算場(chǎng)景去進(jìn)行優(yōu)化。因此列存儲(chǔ)也就應(yīng)運(yùn)而生了。

每列單獨(dú)存儲(chǔ)，多個(gè)列邏輯組成一行，一次磁盤IO只包含一列數(shù)據(jù)，這一列的數(shù)據(jù)可能是一行中的一列，或者是執(zhí)行中的一個(gè)數(shù)據(jù)，同時(shí)在這種編排格式下，更方便去做數(shù)據(jù)壓縮，因?yàn)橄嗤械臄?shù)據(jù)類型有更高的一致性和匹配度，所以可能會(huì)面向很多極致的壓縮的場(chǎng)景，也更適合OLAP的計(jì)算場(chǎng)景。

TDSQL-A同時(shí)支持行存儲(chǔ)和列存儲(chǔ)建表，行表和列表之間可以進(jìn)行互相操作，行列表之間支持混合查詢，根據(jù)用戶的場(chǎng)景去設(shè)定不同的行表和列表的定義方式，同時(shí)在混合查詢的時(shí)候也嚴(yán)格保證事務(wù)一致性，從而讓客戶可以比較放心地去定義自己的行表和列表。

2.1 TDSQL-A自研列存儲(chǔ)整體設(shè)計(jì)

這部分主要是介紹我們針對(duì)列存儲(chǔ)所做的優(yōu)化。TDSQL-A在設(shè)計(jì)列存儲(chǔ)之前就已經(jīng)去充分調(diào)研過客戶相關(guān)的需求，下面這張圖就把我們的整個(gè)能力完整地呈現(xiàn)了出來(lái)。

通過比較好的列存儲(chǔ)格式的文件編排，可以達(dá)到更好的插入或者讀取的性能。上層通過Buffer進(jìn)行高速的加速，以及延遲物化以及向量化執(zhí)行，對(duì)整個(gè)引擎做到了針對(duì)性的極致優(yōu)化；通過完整的設(shè)計(jì)，可以比較好的去優(yōu)化查詢計(jì)劃以及執(zhí)行引擎，從而達(dá)到一個(gè)比較好的執(zhí)行效果。

2.2 TDSQL-A列存儲(chǔ)模型介紹

TDSQL-A中列存儲(chǔ)首先會(huì)分為多個(gè)Slice文件，不同的文件可以分配不同的并發(fā)訪問的數(shù)據(jù)變更請(qǐng)求，每一個(gè)Slice文件標(biāo)號(hào)為SID，SID里面會(huì)包含多個(gè)Row的信息，每一個(gè)列會(huì)有一個(gè)單獨(dú)的自己的文件存儲(chǔ)，我們可以通過RID來(lái)去尋找對(duì)應(yīng)不同行的列的數(shù)據(jù)。我們可以簡(jiǎn)單理解為SID和RID是一個(gè)標(biāo)識(shí)，通過它們可以去支持索引查詢或者后面講到的延遲物化里面通過ID掃描到相應(yīng)的數(shù)據(jù)來(lái)進(jìn)行一個(gè)補(bǔ)缺。

我們?cè)诖鎯?chǔ)格式上還設(shè)計(jì)了版本列，即通過xmin、xmax的相關(guān)記錄來(lái)去支持事務(wù)的判斷。針對(duì)不同類型的數(shù)據(jù)，我們又有一些相應(yīng)的優(yōu)化機(jī)制，定長(zhǎng)類型緊湊排列，變長(zhǎng)類型構(gòu)建字典列，來(lái)加速數(shù)據(jù)查找。

同時(shí)針對(duì)一些排序相關(guān)的查詢，我們?cè)诖鎯?chǔ)上面也進(jìn)行了優(yōu)化。比如說由索引列來(lái)進(jìn)行高效的排序，或者是xmin、xmax相關(guān)的計(jì)算加速或優(yōu)化，從而在存儲(chǔ)層面提供支持。

2.3 TDSQL-A基于自研列存儲(chǔ)的三大優(yōu)勢(shì)

針對(duì)一些有特定特征的場(chǎng)景，TDSQL-A可以用輕量級(jí)壓縮算法來(lái)做一個(gè)更高效的壓縮，對(duì)于通用的一些場(chǎng)景，通過透明壓縮算法也可以達(dá)到一個(gè)比較好的整體壓縮效果。在例圖里可以看到，根據(jù)等值數(shù)據(jù)、遞增數(shù)據(jù)可能會(huì)達(dá)到上百倍的壓縮效果。

高效計(jì)算能力也是TDSQL-A的一大特性。實(shí)際上我們?cè)O(shè)計(jì)了比較豐富的功能來(lái)支持TDSQL-A的計(jì)算優(yōu)化，主要分為這幾個(gè)方向：

第一點(diǎn)是SeqScan的向量化支持。在底層掃描數(shù)據(jù)的時(shí)候，實(shí)際數(shù)據(jù)量越大，向量化帶來(lái)的效果和優(yōu)化的空間也是越大，向量化對(duì)上層的復(fù)雜計(jì)算提供了支持；

第二點(diǎn)是Shared CTE。簡(jiǎn)單來(lái)說，之前的版本可能需要把數(shù)據(jù)拉到CN做，在TDSQL-A中，我們也做了相應(yīng)的支持，可以分布式的在DN上去計(jì)算CTE。Shared CTE算子會(huì)在計(jì)算時(shí)把數(shù)據(jù)進(jìn)行物化。我們?cè)赟hared CTE物化時(shí)針對(duì)性地去借鑒了列存的數(shù)據(jù)格式編排，包括上面的提到的向量化的計(jì)算，以及其他的一些優(yōu)化，可以更好地借助列存版本在設(shè)計(jì)上的優(yōu)勢(shì)，或者計(jì)算上的優(yōu)勢(shì)來(lái)去提高整個(gè)場(chǎng)景的計(jì)算性能；

第三點(diǎn)是延遲物化進(jìn)一步減少計(jì)算和網(wǎng)絡(luò)消耗。我們會(huì)針對(duì)列存做更多的極致優(yōu)化來(lái)提升查詢性能，提供更大規(guī)模數(shù)據(jù)上的實(shí)時(shí)查詢效果。

TDSQL-A的并行能力，實(shí)際上分為節(jié)點(diǎn)級(jí)并行、進(jìn)程級(jí)并行以及指令級(jí)并行，進(jìn)程級(jí)并行后面我會(huì)介紹一下具體優(yōu)化性里面怎么去進(jìn)行一個(gè)優(yōu)化，針對(duì)并行、延遲物化去進(jìn)行一個(gè)統(tǒng)一的規(guī)劃。

3

提前物化or延遲物化？?jī)?yōu)化器選擇有方法

上一部分介紹了很多列存儲(chǔ)以及相關(guān)的查詢優(yōu)化方法，這部分我們主要去詳細(xì)展開延遲物化相關(guān)的介紹。

我們講延遲物化，但實(shí)際上并不是所有的延遲物化都快，我們需要去尋找最優(yōu)的策略和方案，為客戶自動(dòng)調(diào)整到去用延遲物化還是提前物化。下面先介紹兩種物化策略的區(qū)別。

3.1提前物化VS延遲物化

簡(jiǎn)單的場(chǎng)景的時(shí)候，采用提前物化，提前把C1、C2或者D1、D2列全部都掃描出來(lái)，去組裝成tuple進(jìn)行內(nèi)部計(jì)算，這個(gè)時(shí)候它的好處是數(shù)據(jù)只訪問一次。但如果join的選擇率比較低的話，我們就會(huì)浪費(fèi)掉很多早期的網(wǎng)絡(luò)交互。如果采用延遲物化，且join的選擇率非常低，C2列我可以進(jìn)行一個(gè)延遲物化，在join結(jié)束之后我才去把它的數(shù)據(jù)進(jìn)行一個(gè)補(bǔ)全，這種情況下我可能減少了很多不必要的掃描和網(wǎng)絡(luò)交互。

但是對(duì)于這兩種場(chǎng)景，join的選擇率以及整個(gè)不同列的寬度或者數(shù)據(jù)列在重新掃描時(shí)遇到亂序等場(chǎng)景，都會(huì)影響到我們選擇不同策略的規(guī)劃，并非簡(jiǎn)單的一定會(huì)選擇延遲物化或者選擇提前物化。

這里面延遲物化會(huì)減少物化的tuple數(shù)量，降低IO、網(wǎng)絡(luò)、計(jì)算壓力；同時(shí)在基于列存儲(chǔ)的訪問上，可以借助計(jì)算上面的增強(qiáng)技術(shù)來(lái)去降低CPU的消耗；延遲物化還有一個(gè)好處就是在掃描數(shù)據(jù)相對(duì)較少的情況下，需要cache的數(shù)據(jù)量是更少的，像這時(shí)候也會(huì)變相地提高整個(gè)計(jì)算的cache命中率，減少cpu的消耗。

提前物化的好處是減少LM中不必要的數(shù)據(jù)reaccess（需要頻繁的多次訪問相同的數(shù)據(jù)塊從而導(dǎo)致更高的訪問）。所以提前物化在選擇率比較高的時(shí)候，或者本身join中間會(huì)有數(shù)據(jù)亂序的情況下，可能提前物化的效果會(huì)更好。提前物化里面還有更細(xì)致的結(jié)構(gòu)化。有兩種方式，一種是先對(duì)A列進(jìn)行prediate計(jì)算，這時(shí)候它可能已經(jīng)過濾了很多數(shù)據(jù)，再去進(jìn)行第二列的prediate計(jì)算。但這種情況下，只能對(duì)列存儲(chǔ)來(lái)去做相應(yīng)的優(yōu)化；相應(yīng)地就是右邊這種在早期掃的時(shí)候不管Predicate，先去把A、B兩列掃描出來(lái)，然后再去進(jìn)行Predicate，這樣掃描的數(shù)據(jù)量還是會(huì)比較多，這個(gè)也是一個(gè)細(xì)致的優(yōu)化，可以通過這樣的方式去減少更多的列存儲(chǔ)的數(shù)據(jù)掃描量。

3.2不同場(chǎng)景應(yīng)用不同物化策略

這里我們介紹下TDSQL-A優(yōu)化器是如何針對(duì)不同場(chǎng)景對(duì)物化策略進(jìn)行選擇。

比較早期的數(shù)據(jù)庫(kù)或者是九十年代以前更多的是選擇一個(gè)Rule-based Optimizer（RBO）。簡(jiǎn)單講就是通過靜態(tài)的規(guī)則去對(duì)邏輯查詢計(jì)劃進(jìn)行優(yōu)化，像提前下推，都是通過強(qiáng)制的規(guī)則去進(jìn)行計(jì)算的。這里的好處就是我可以比較簡(jiǎn)單地實(shí)現(xiàn)，或在早期理論比較簡(jiǎn)單的情況下，通過這樣的方式來(lái)達(dá)到比較好的呈現(xiàn)效果。但是它在面對(duì)更復(fù)雜的查詢、算子、優(yōu)化等這些場(chǎng)景時(shí)，可能中間會(huì)有互斥，或者很難去進(jìn)行最終的優(yōu)化。這種情況下Cost Based Optimizer就應(yīng)運(yùn)而生，后面會(huì)整體介紹通過整個(gè)不同paths的代價(jià)評(píng)估來(lái)進(jìn)行整體的估算，實(shí)際上像比較新的或者現(xiàn)在的數(shù)據(jù)庫(kù)整合都會(huì)互相去達(dá)到比較好的優(yōu)勢(shì)的借鑒。

我們?cè)趈oin Reordering的時(shí)候，到底是怎么基于cost來(lái)進(jìn)行推算的呢？舉個(gè)例子，比如說我們有三張表，在join優(yōu)化器里面它會(huì)選擇動(dòng)態(tài)規(guī)劃的一個(gè)算法，最開始會(huì)把同一個(gè)jointree所有join參與的表打散成base relation，這個(gè)時(shí)候基于base relation去進(jìn)行不同層級(jí)的計(jì)算。第一層我們就會(huì)選擇這三張表其中兩張表來(lái)做一個(gè)計(jì)算，生成相應(yīng)的一個(gè)path，這條紅線就是生成某一個(gè)level的查詢方法的一個(gè)路徑，對(duì)于每個(gè)path會(huì)有相應(yīng)的代價(jià)叫cost。第二層基于剛才第一層生成表的選擇情況，再去補(bǔ)全第三張表，這種情況下相對(duì)于是一個(gè)動(dòng)態(tài)規(guī)劃，中間的一個(gè)轉(zhuǎn)移函數(shù)主要是通過不同path中間去選擇一個(gè)Cheapest cost，通過這種方式來(lái)完成整個(gè)查詢計(jì)劃的便利，選擇出代價(jià)最低的計(jì)劃，這里面是一個(gè)簡(jiǎn)單鋪墊。

考慮到并行的情況下，這個(gè)問題就會(huì)變的更復(fù)雜一些，同時(shí)需要規(guī)劃一個(gè)并行的path，或者是一個(gè)非并行的path，在每一個(gè)轉(zhuǎn)移函數(shù)的時(shí)候需要去考慮，在有并行paths的情況下，是否需要在當(dāng)前這一層把這個(gè)并行path加一個(gè)gather節(jié)點(diǎn)，來(lái)變成一個(gè)串行的path。實(shí)際上串行只能跟串行比，并行的數(shù)據(jù)還沒有整理完畢，這種情況下每一層都會(huì)去考慮所有的串行的path里面再去加上gather的并行path，這樣整體的cost一對(duì)比，然后統(tǒng)一來(lái)選擇并行還是串行，這也是并行優(yōu)化里面比較重要的一部分。

如果再考慮到延遲物化的話，這個(gè)問題就會(huì)變的更加復(fù)雜，就是說我們?cè)诓鸱殖蒪ase relation的時(shí)候，通過query tree可以知道join的時(shí)候哪些列是不需要的。比如這個(gè)表有100列，中間的join可能只用了10列，可以只生成這10列的缺失狀態(tài)的path，實(shí)際上生成對(duì)應(yīng)的path還是可以滿足當(dāng)前第一層場(chǎng)景的。如果我發(fā)現(xiàn)join需要第三、第四列需要補(bǔ)全的時(shí)候，會(huì)在join之前把這兩列通過延遲物化算子把它補(bǔ)全進(jìn)來(lái)，這樣保證每一層在計(jì)算的時(shí)候需要的數(shù)據(jù)是補(bǔ)全進(jìn)來(lái)的。另外在轉(zhuǎn)移函數(shù)的時(shí)候，也需要去考慮正常的path怎么去跟延遲物化的path進(jìn)行一個(gè)對(duì)比，需要去把延遲物化的path補(bǔ)全，將相應(yīng)的列補(bǔ)全的情況下才能去跟正常的paths進(jìn)行一個(gè)對(duì)比。這種情況下是完整的轉(zhuǎn)移函數(shù)，這個(gè)時(shí)候就會(huì)比較好的體現(xiàn)出選擇一個(gè)什么樣的paths，最后生成物理的相應(yīng)計(jì)劃。

實(shí)際上的應(yīng)用場(chǎng)景會(huì)更加復(fù)雜，像具體的SeqScan Cost的計(jì)算，怎么考慮到延遲物化來(lái)做一個(gè)調(diào)整呢？實(shí)際上，寬度是有動(dòng)態(tài)的調(diào)整，根據(jù)不同的情況去進(jìn)行一個(gè)計(jì)算。像RidScan Cost在去進(jìn)行一個(gè)列的補(bǔ)全的時(shí)候，需要根據(jù)這個(gè)列之前傳給我的RID，基于具體計(jì)劃的情況去進(jìn)行考慮。這種情況下其實(shí)就需要考慮Rid是不是sort的，去掃描的時(shí)候，會(huì)不會(huì)有很多的re-access，這種情況下會(huì)導(dǎo)致RidScan Cost比較復(fù)雜。第三點(diǎn)拼裝的時(shí)候LM Fetch需要考慮當(dāng)前是不是通過Remote Scan，或者本節(jié)點(diǎn)的local scan。不同的cost的計(jì)算也是不一樣的，包括第四點(diǎn)Remote Subpath Cost計(jì)算會(huì)大量的降低網(wǎng)絡(luò)帶寬的情況，這個(gè)要考慮到少掃了80%的列的寬度，實(shí)際上對(duì)網(wǎng)絡(luò)層也是有很大影響的，這都是要統(tǒng)一地去計(jì)算。

這些都會(huì)對(duì)整個(gè)優(yōu)化器的決策去進(jìn)行一個(gè)調(diào)整，最開始生成base paths的時(shí)候，實(shí)際上我是不知道我到底需不需要去remote或者需不需要去sort，這個(gè)時(shí)候都會(huì)標(biāo)成local或者skip sort，另外一點(diǎn)就是在幾種情況下可能會(huì)導(dǎo)致產(chǎn)生變化，比如說remoteSubpath，因?yàn)槲沂盏捻樞蚩赡苁莵y序的，RD已經(jīng)亂了，后面再去進(jìn)行RD Stand的時(shí)候，通過代價(jià)來(lái)去評(píng)估它是不是可以這樣走，或者如果要這樣走，我是不是要在物理算子上進(jìn)行一個(gè)排序，以及Hashjoin的時(shí)候都會(huì)有相應(yīng)的一些影響。比如說最簡(jiǎn)單的ARTIST外表應(yīng)該是順序，但是它有join的時(shí)候，讀上來(lái)順序也是亂的。像Inner Path更是如此，Hash table實(shí)際上會(huì)對(duì)整個(gè)順序進(jìn)行改變，這些都會(huì)對(duì)延遲物化有很深層的影響，導(dǎo)致優(yōu)化器里面會(huì)有不同的決策、選擇。

3.3延遲物化推動(dòng)通信效率提升

通過這些比較嚴(yán)謹(jǐn)?shù)乃伎己蛢?yōu)化器的調(diào)整，我們更多的參數(shù)回歸和調(diào)整，我們也達(dá)到了比較好的效果。比如說，1TB的數(shù)據(jù)如果了選擇率相對(duì)比較低，10%的情況下P60%，2表JOIN可能會(huì)有一個(gè)時(shí)間上81.1%的提升，消耗時(shí)間的下降以及網(wǎng)絡(luò)占用帶寬的下降；如果是多表的話，會(huì)有更好的一個(gè)效果。