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

在“國產(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進行了深入解讀。錯過直播的小伙伴有福啦，今天帶來本次系列分享中騰訊云數(shù)據(jù)庫高級工程師伍鑫老師主題為“TDSQL-A列存儲設(shè)計原理及執(zhí)行優(yōu)化詳解”的文字版。

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

1

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

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

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

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

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

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

2

自研列存儲帶來極致優(yōu)化性能

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

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

每列單獨存儲，多個列邏輯組成一行，一次磁盤IO只包含一列數(shù)據(jù)，這一列的數(shù)據(jù)可能是一行中的一列，或者是執(zhí)行中的一個數(shù)據(jù)，同時在這種編排格式下，更方便去做數(shù)據(jù)壓縮，因為相同列的數(shù)據(jù)類型有更高的一致性和匹配度，所以可能會面向很多極致的壓縮的場景，也更適合OLAP的計算場景。

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

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

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

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

2.2 TDSQL-A列存儲模型介紹

TDSQL-A中列存儲首先會分為多個Slice文件，不同的文件可以分配不同的并發(fā)訪問的數(shù)據(jù)變更請求，每一個Slice文件標號為SID，SID里面會包含多個Row的信息，每一個列會有一個單獨的自己的文件存儲，我們可以通過RID來去尋找對應不同行的列的數(shù)據(jù)。我們可以簡單理解為SID和RID是一個標識，通過它們可以去支持索引查詢或者后面講到的延遲物化里面通過ID掃描到相應的數(shù)據(jù)來進行一個補缺。

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

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

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

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

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

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

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

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

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

3

提前物化or延遲物化？優(yōu)化器選擇有方法

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

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

3.1提前物化VS延遲物化

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

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

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

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

3.2不同場景應用不同物化策略

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

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

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

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

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

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

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

3.3延遲物化推動通信效率提升

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