01存儲(chǔ)引擎

對(duì)于一個(gè)分析型數(shù)據(jù)庫，最核心的三個(gè)組成部分就是存儲(chǔ)引擎、查詢引擎和查詢優(yōu)化器，這也是Doris極致性能的決定因素。在此之外，向量化執(zhí)行引擎的加入，讓CPU的能力得到了更充分的發(fā)揮，更進(jìn)一步提升了Doris查詢性能。

和大多數(shù)分析型數(shù)據(jù)庫一樣，Doris也是以列存格式存儲(chǔ)數(shù)據(jù)的。數(shù)據(jù)按照列進(jìn)行連續(xù)存儲(chǔ)，因?yàn)轭愋拖嗤?，因此可以獲得極高的壓縮率，節(jié)省磁盤空間。Doris對(duì)不同列的數(shù)據(jù)類型還提供了不同的編碼方式，如INT類型會(huì)使用BitShuffle的編碼方式，而字符串類型會(huì)使用字典編碼。更進(jìn)一步，Doris還會(huì)自動(dòng)根據(jù)列的值分布情況來切換編碼類型。比如對(duì)于字符串類型，如果列的去重值比較多，則不再使用字典編碼，而直接切換到Plain Text編碼，以避免不必要的空間浪費(fèi)。

從文件組織形式上，Doris的文件格式和Parquet比較類似。一個(gè)數(shù)據(jù)版本會(huì)被分割成最大空間為256MB一個(gè)的Segment，每個(gè)Segment對(duì)應(yīng)一個(gè)物理文件。Segment通常分為Header、Data Region、Index Region、Footer幾個(gè)部分。Data Region 用于按列存儲(chǔ)數(shù)據(jù)，每一列又被分為多個(gè)Page，而Page是Doris的最小數(shù)據(jù)存取單元，如圖1所示。

▲圖1 Doris文件格式

Index Region負(fù)責(zé)存儲(chǔ)數(shù)據(jù)的索引。Doris提供了豐富的索引結(jié)構(gòu)來幫助加速數(shù)據(jù)的讀取和過濾。索引的類型大體可以分為智能索引和二級(jí)索引兩種。其中智能索引是在Doris數(shù)據(jù)寫入時(shí)自動(dòng)生成的，無須用戶干預(yù)，包括前綴稀疏索引、Min Max索引等。而二級(jí)索引是用戶可以選擇性地在某些列上添加的輔助索引，需要用戶自主選擇是否創(chuàng)建，比如像Bloom Filter、Bitmap倒排索引等。

前綴稀疏索引是建立在排序結(jié)構(gòu)上的一種索引。存儲(chǔ)在文件中的數(shù)據(jù)是按照排序列有序存儲(chǔ)的。Doris會(huì)在排序列數(shù)據(jù)上，每1024行創(chuàng)建一個(gè)稀疏索引項(xiàng)，如圖2所示。索引的Key即當(dāng)前這1024行中第一行的前綴排序列的值。當(dāng)用戶的查詢條件包含這些排序列是，我們可以通過前綴稀疏索引快速的定位到起始行。

▲圖2 Doris前綴稀疏索引和Min Max索引示例

Min Max索引是建立在Segment和Page級(jí)別的索引。對(duì)于Page中的每一列，Min Max索引都會(huì)記錄這個(gè)Page中的最大值和最小值，同樣，在Segment級(jí)別也會(huì)對(duì)每一列的最大值和最小值進(jìn)行記錄。這樣當(dāng)進(jìn)行等值或范圍查詢時(shí)，可以通過Min Max索引快速過濾掉不需要讀取的行。

Bloom Filter（布隆過濾器）是一種需要用戶自主選擇是否創(chuàng)建的索引。當(dāng)對(duì)某一列創(chuàng)建Bloom Filter索引后，Doris會(huì)在page級(jí)別創(chuàng)建該列的Bloom Filter結(jié)構(gòu)。Bloom Filter是一種使用固定空間的位圖來快速判斷一個(gè)值是否存在的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)非常適合用于高基數(shù)列上的等值查詢，比如UUID。

Bitmap也是一種需要用戶自主選擇是否創(chuàng)建的索引。Bitmap索引是一種基于位圖的數(shù)據(jù)結(jié)構(gòu)，其Key值是實(shí)際的列值，而Value值是key在數(shù)據(jù)文件中的offset 。通過Bitmap索引，Doris可以很快定位到列值對(duì)應(yīng)的行號(hào)，進(jìn)行快速取數(shù)。這種索引比較合適在基數(shù)較低的列上進(jìn)行等值查詢的場景，比如城市等。

除了存儲(chǔ)方式和索引結(jié)構(gòu)，Doris在讀取邏輯上也有很多優(yōu)化。比如延遲物化功能會(huì)先根據(jù)有索引的列，定位到一個(gè)數(shù)據(jù)范圍，然后再根據(jù)有過濾條件的列進(jìn)行進(jìn)一步過濾來縮小數(shù)據(jù)范圍，最后再讀取其他需要讀取的列。這種方式可以很大程度上減少不必要的數(shù)據(jù)讀取，降低查詢請(qǐng)求對(duì)I/O的資源消耗。

02查詢引擎

Doris的查詢引擎是基于MPP的火山模型，是從早期版本的Apache Impala演化而來的。在Doris中，一個(gè)SQL語句會(huì)先生成一個(gè)邏輯執(zhí)行計(jì)劃，然后根據(jù)數(shù)據(jù)的分布，形成一個(gè)物理執(zhí)行計(jì)劃。物理執(zhí)行計(jì)劃會(huì)有多個(gè)Fragment，而Fragment之間的數(shù)據(jù)傳輸則是由Exchange模塊完成的。通過Exchange模塊，Doris在執(zhí)行整個(gè)查詢的時(shí)候就有了數(shù)據(jù)重分布（Reshuffle）的能力，查詢不再局限于數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)，從而能夠更好地利用多節(jié)點(diǎn)資源進(jìn)行并行數(shù)據(jù)處理。執(zhí)行框架如圖3所示。

▲圖3 MPP框架執(zhí)行流程示意圖

邏輯執(zhí)行計(jì)劃的Agg階段變成了物理執(zhí)行計(jì)劃中的先重分布然后匯總的兩個(gè)步驟，這個(gè)過程和Hadoop是類似的，都是按照相同的Key進(jìn)行數(shù)據(jù)重分布。

除了整體的執(zhí)行框架通過并行設(shè)計(jì)來提高查詢效率外，Doris 還對(duì)很多具體的查詢算子進(jìn)行了優(yōu)化。比如圖4種的聚合算子。

▲圖4 聚合算子

在Doris中，聚合算子會(huì)被拆分成兩級(jí)聚合。第一級(jí)聚合會(huì)在數(shù)據(jù)所在節(jié)點(diǎn)先進(jìn)行一次本地聚合，以減少發(fā)送到第二層聚合時(shí)需要傳輸?shù)臄?shù)據(jù)量，而第二級(jí)聚合會(huì)將Key相同的數(shù)據(jù)匯聚到同一個(gè)節(jié)點(diǎn)，進(jìn)行最終的聚合計(jì)算。

在此基礎(chǔ)上，Doris還實(shí)現(xiàn)了自適應(yīng)的聚合算法。首先我們要知道，聚合算子是一種阻塞型算子，需要等到全部數(shù)據(jù)處理完成后，才會(huì)將數(shù)據(jù)發(fā)送給上層節(jié)點(diǎn)。而自適應(yīng)聚合算法的意思是，在第一級(jí)聚合算子中，如果發(fā)現(xiàn)數(shù)據(jù)的聚合效果很低，即使聚合后也無法有效降低需要傳輸?shù)臄?shù)據(jù)量，則會(huì)自動(dòng)停止第一級(jí)聚合，而將算子轉(zhuǎn)換為一個(gè)非阻塞的流式算子，直接將讀取到的數(shù)據(jù)發(fā)送到上層節(jié)點(diǎn)，從而避免不必要的阻塞等待時(shí)間。

針對(duì)Join算子，Doris也進(jìn)行了大量優(yōu)化，其中Runtime Filter是很重要的一種優(yōu)化方式。在兩個(gè)表的Join操作中，我們通常將右表稱為BuildTable，而將左表稱為ProbeTable。在實(shí)現(xiàn)上，通常首先讀取右表的數(shù)據(jù)，在內(nèi)存中構(gòu)建一個(gè)HashTable，然后開始讀取左表的每一行數(shù)據(jù)，并在HashTable中進(jìn)行連接匹配，返回符合連接條件的數(shù)據(jù)。通常來說，左表的數(shù)據(jù)量會(huì)大于右表的數(shù)據(jù)量。

而Runtime Filter的設(shè)計(jì)思路，是在右表構(gòu)建HashTable的同時(shí)，為連接列生成一個(gè)過濾結(jié)構(gòu)。之后把這個(gè)過濾結(jié)構(gòu)推給左表。這樣，左表就可以利用過濾結(jié)構(gòu)，對(duì)數(shù)據(jù)進(jìn)行過濾，從而減少Probe節(jié)點(diǎn)需要傳輸和比對(duì)的數(shù)據(jù)量。這種過濾結(jié)構(gòu)被稱為Runtime Filter。針對(duì)不同的數(shù)據(jù)，Doris也實(shí)現(xiàn)了不同類型的過濾器，例如In Predicate，Bloom Filter和Min Max。用戶可以根據(jù)不同場景選擇不同的過濾器。Runtime Filter實(shí)現(xiàn)邏輯示意圖如圖5所示。

▲圖5 Runtime Filter實(shí)現(xiàn)邏輯示意圖

Runtime Filter可以適用于大部分Join場景，包括節(jié)點(diǎn)的自動(dòng)穿透，將Filter穿透下推到最底層的掃描節(jié)點(diǎn)，例如分布式Shuffle Join中，將多個(gè)節(jié)點(diǎn)產(chǎn)生的Filter進(jìn)行合并后再下推數(shù)據(jù)讀取節(jié)點(diǎn)等。

03查詢優(yōu)化器

除了查詢執(zhí)行層方面的優(yōu)化，Doris 在查詢優(yōu)化器方面也做了大量工作。Doris中的查詢優(yōu)化器能夠同時(shí)進(jìn)行基于規(guī)則和基于代價(jià)的查詢優(yōu)化。在基于規(guī)則的查詢優(yōu)化方面，Doris包括但不限于以下優(yōu)化規(guī)則。

1）常量折疊。常量折疊可以預(yù)先對(duì)常量表達(dá)式進(jìn)行計(jì)算，計(jì)算后的結(jié)果有助于規(guī)劃器進(jìn)行分區(qū)分桶裁剪，以及執(zhí)行層利用索引進(jìn)行數(shù)據(jù)過濾等。例如將where event_dt>=cast（add_months（now（）,-1） as date）折算成where event_dt >=’2022-02-20’[14] [15] （編寫本節(jié)時(shí)是2022年3月20日晚上）。

2）子查詢改寫。將子查詢改寫為Join操作，從而利用Doris在Join上做的一系列優(yōu)化來提升查詢效率。例如select * from tb1 where col1 in （select col2 from tb2） a改寫成select tb1.* from tb1 inner join tb2 on tb1.col1=tb2.col2。

3）提取公共表達(dá)式。提取公共表達(dá)式可以將SQL中的一些析取范式轉(zhuǎn)換成和取范式，而和取范式通常對(duì)執(zhí)行引擎是比較友好，可以將查詢條件重組或者下推，減少數(shù)據(jù)掃描和讀取的行數(shù)。例如將條件where （a>1 and b=2） or （a>1 and b=3） or （a>1 and b=4）轉(zhuǎn)化成 where a>1 and b in （2,3,4），明顯后者的判斷速度比前者的快很多。

4）智能預(yù)過濾。智能預(yù)過濾可以將SQL中的析取范式轉(zhuǎn)換成和取范式并提煉出公共條件部分。這些公共條件可以預(yù)先過濾部分?jǐn)?shù)據(jù)，從而減少數(shù)據(jù)處理量。

5）謂詞下推也是查詢優(yōu)化器常見的優(yōu)化手段。Doris中的謂詞下推不僅可以穿透算子，更能進(jìn)一步地下推到存儲(chǔ)引擎，利用數(shù)據(jù)索引進(jìn)行數(shù)據(jù)的過濾，如圖6所示。

▲圖6 Doris中的謂詞下推示意圖

而在基于代價(jià)的查詢優(yōu)化方面，Doris主要針對(duì)Join算子進(jìn)行了大量優(yōu)化。

Join Reorder功能可以通過一些表的統(tǒng)計(jì)信息，自動(dòng)的調(diào)整Join的順序。而Join順序的調(diào)整，會(huì)顯著降低Join操作中生成的中間數(shù)據(jù)集的大小，從而加速查詢的執(zhí)行，如圖7所示。

▲圖7 Doris Join Reorder優(yōu)化示意圖

Colocation Join可以利用數(shù)據(jù)的分布情況，將原本需要Shuffle后才能進(jìn)行Join的數(shù)據(jù)，在本地即可完成Join操作，從而避免了Shuffle時(shí)大量的網(wǎng)絡(luò)數(shù)據(jù)傳輸。如圖8所示。

▲圖8 Doris Colocation Join示意圖

Bucket Join是Colocation Join的通用版本。在Colocation Join中，用戶需要在建表時(shí)就指定表的分布，以保證需要關(guān)聯(lián)查詢的若干個(gè)表有相同的數(shù)據(jù)分布。而Bucket Join會(huì)更智能地自動(dòng)判斷SQL中的關(guān)聯(lián)條件和數(shù)據(jù)分布之間的關(guān)系，將原本需要同時(shí)Shuffle的左右兩張表的數(shù)據(jù)的操作，變成僅將右表數(shù)據(jù)重分布到左表所在的節(jié)點(diǎn)，從而減少數(shù)據(jù)的移動(dòng)量。如圖9所示。

▲圖9 Doris Bucket Join示意圖

04向量化執(zhí)行引擎

傳統(tǒng)的數(shù)據(jù)庫都是典型的迭代模型，執(zhí)行計(jì)劃里面的每個(gè)算子通過調(diào)用下一個(gè)算子的next（）方法來獲取數(shù)據(jù)，數(shù)據(jù)從最底層的數(shù)據(jù)塊中一條一條的讀取處理最終返回給客戶，它的問題在于每個(gè)tuple（也叫元組，是一種常見的編程數(shù)據(jù)類型，和數(shù)組類似，但是元組的元素可以是不同的類型）都要調(diào)用一次函數(shù)，調(diào)用開銷太大，而且因?yàn)镃PU每次只處理一條數(shù)據(jù)，無法利用[18] [19] CPU技術(shù)升級(jí)帶來的新特性，比如SIMD。向量化模型每次處理的是一批數(shù)據(jù)，這些數(shù)據(jù)會(huì)被保存在一種叫作向量的數(shù)據(jù)結(jié)構(gòu)里面，然后因?yàn)槊看翁幚淼氖且慌鷶?shù)據(jù)，因此可以在每個(gè)Batch內(nèi)部可以做各種優(yōu)化。簡單的說，向量化執(zhí)行引擎 = 高效的向量數(shù)據(jù)結(jié)構(gòu)（Vector）+ 批量化處理模型（nextBatch） + Batch內(nèi)性能優(yōu)化（例如SIMD等）。

原本向量化執(zhí)行引擎只是一個(gè)概念，是ClickHouse將其變成了現(xiàn)實(shí)，率先在數(shù)據(jù)庫產(chǎn)品中實(shí)現(xiàn)了向量化執(zhí)行引擎并展示出強(qiáng)悍性能。通過向量化執(zhí)行引擎原理的介紹，我們可以看出，向量化執(zhí)行引擎非常適合基于列存儲(chǔ)的OLAP數(shù)據(jù)庫，可以極大的提高并行查詢效率。在ClickHouse之后，OLAP數(shù)據(jù)庫實(shí)現(xiàn)向量化執(zhí)行引擎幾乎已經(jīng)成為標(biāo)配。目前，除了Doris以外，polar-x、TDSQL都聲稱部分或者全部實(shí)現(xiàn)了向量化執(zhí)行引擎功能。

Doris是在0.15版本引入向量化執(zhí)行引擎功能的，并在1.0版本中逐漸成熟。根據(jù)Doris的演進(jìn)計(jì)劃，向量化執(zhí)行引擎會(huì)逐步替換當(dāng)前Doris的行式SQL執(zhí)行引擎，以充分釋放現(xiàn)代CPU的計(jì)算能力，實(shí)現(xiàn)更強(qiáng)悍的查詢性能。

在絕大多數(shù)場景之中，用戶只需要將session變量enable_vectorized_engine設(shè)置為true，則FE在進(jìn)行查詢規(guī)劃時(shí)就會(huì)默認(rèn)將SQL算子與SQL表達(dá)式轉(zhuǎn)換為向量化的執(zhí)行計(jì)劃，從而提升SQL執(zhí)行性能。

關(guān)于作者：王春波，資深大數(shù)據(jù)架構(gòu)師，現(xiàn)就職于一家互聯(lián)網(wǎng)公司，任高級(jí)數(shù)倉工程師，負(fù)責(zé)電商數(shù)倉項(xiàng)目；在銀行業(yè)、零售行業(yè)深耕多年，參與和負(fù)責(zé)過多家銀行、零售數(shù)據(jù)分析實(shí)施項(xiàng)目；“數(shù)據(jù)中臺(tái)研習(xí)社”號(hào)主，《Doris實(shí)時(shí)數(shù)倉實(shí)戰(zhàn)》《高效使用Greenplum：入門、進(jìn)階與數(shù)據(jù)中臺(tái)》作者。