01存儲引擎

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

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

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

▲圖1 Doris文件格式

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

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

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

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

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

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

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

02查詢引擎

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

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

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

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

▲圖4 聚合算子

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

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

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

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

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

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

03查詢優(yōu)化器

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

1）常量折疊。常量折疊可以預先對常量表達式進行計算，計算后的結果有助于規(guī)劃器進行分區(qū)分桶裁剪，以及執(zhí)行層利用索引進行數(shù)據(jù)過濾等。例如將where event_dt>=cast（add_months（now（）,-1） as date）折算成where event_dt >=’2022-02-20’[14] [15] （編寫本節(jié)時是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）提取公共表達式。提取公共表達式可以將SQL中的一些析取范式轉換成和取范式，而和取范式通常對執(zhí)行引擎是比較友好，可以將查詢條件重組或者下推，減少數(shù)據(jù)掃描和讀取的行數(shù)。例如將條件where （a>1 and b=2） or （a>1 and b=3） or （a>1 and b=4）轉化成 where a>1 and b in （2,3,4），明顯后者的判斷速度比前者的快很多。

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

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

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

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

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

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

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

▲圖8 Doris Colocation Join示意圖

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

▲圖9 Doris Bucket Join示意圖

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

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

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

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

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

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