01存儲引擎

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

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

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

▲圖1 Doris文件格式

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

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

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

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

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

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

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

02查詢引擎

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

▲圖3 MPP框架執行流程示意圖

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

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

▲圖4 聚合算子

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

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

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

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

▲圖5 Runtime Filter實現邏輯示意圖

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

03查詢優化器

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

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

2）子查詢改寫。將子查詢改寫為Join操作，從而利用Doris在Join上做的一系列優化來提升查詢效率。例如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中的一些析取范式轉換成和取范式，而和取范式通常對執行引擎是比較友好，可以將查詢條件重組或者下推，減少數據掃描和讀取的行數。例如將條件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中的析取范式轉換成和取范式并提煉出公共條件部分。這些公共條件可以預先過濾部分數據，從而減少數據處理量。

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

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

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

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

▲圖7 Doris Join Reorder優化示意圖

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

▲圖8 Doris Colocation Join示意圖

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

▲圖9 Doris Bucket Join示意圖

04向量化執行引擎

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

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

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

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

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