聊聊分散式 SQL 資料庫Doris(七)

LSM-Tree

Doris的儲存結構是類似LSM-Tree設計的，因此很多方面都是通用的，先閱讀了解LSM相關的知識，再看Doris的底層儲存與讀取流程會清晰透徹很多，如下是幾個關鍵的設計:

SSTable: Sorted Strings Table; 一般由一組資料block和一組後設資料block組成，資料是已序的。後設資料會儲存資料block的描述資訊，如索引、BloomFilter、壓縮、統計等資訊。

MemTable: 記憶體裡的表，有序且儲存在Buffer中；可以用多種資料結構來組織，一般是用跳錶(SkipList)，也可以是有序陣列或紅黑樹等二元搜尋樹；最後會被轉化成SSTable格式刷入磁碟持久化儲存。

Compaction: 合併壓縮SSTable。

參考:

LSM 樹設計原理

LSM Tree索引：高效能寫引擎

索引

官網檔案: 索引概述.

Doris內建的索引: 字首索引(Short key Index)、ZoneMap索引，預設是根據建表時的key列生成的。

Doris 的資料儲存在類似 SSTable（Sorted String Table）的資料結構中。該結構是一種有序的資料結構，可以按照指定的列進行排序儲存。在這種資料結構上，以排序列作為條件進行查詢，會非常的高效。

在 Aggregate、Unique 和 Duplicate 三種資料模型中。底層的資料儲存，是按照各自建表語句中，AGGREGATE KEY、UNIQUE KEY 和 DUPLICATE KEY 中指定的列進行排序儲存的。因此在此排序列的基礎上根據不同的場景構建內建的索引，提高查詢的效能與效率。

Duplicate、Aggregate、Unique 模型，都會在建表指定 key 列，然而實際上是有所區別的：對於 Duplicate 模型，表的key列， 可以認為只是 「排序列」，並非起到唯一標識的作用。而 Aggregate、Unique 模型這種聚合型別的表，key 列是兼顧 「排序列」 和 「唯一標識列」，是真正意義上的「 key 列」。

參考: Apache Doris 索引機制解析

Join

官網檔案: Doris Join 優化原理

概覽

Doris 支援兩種物理運算元，一類是 Hash Join，另一類是 Nest Loop Join。

Doris 支援 4 種資料 Shuffle 方式：

1. BroadCast Join: 要求把右表全量的資料都傳送到左表上，即每一個參與 Join 的節點，它都擁有右表全量的資料

2. Shuffle Join: 只支援hash join場景(即等值匹配). 當進行 Hash Join 時候，可以通過 Join 列計算對應的 Hash 值，並進行 Hash 分桶，並將分桶後的資料分散到節點中進行計算

3. Bucket Shuffle Join: 右表資料掃描出來之後進行資料分割區的 Hash 計算，根據左表本身的資料分佈傳送到右表對應的 Join 計算節點上。

4. Colocation: 匯入資料時，提前將join表的資料分散到一個節點

Runtime Filter

Doris 在進行 Hash Join 計算時會在右表構建一個雜湊表，左表流式的通過右表的雜湊表從而得出 Join 結果。而 RuntimeFilter 就是充分利用了右表的 Hash 表，在右表生成雜湊表的時候，同時生成一個基於雜湊表資料的一個過濾條件(Filter)，然後下推到左表的資料掃描節點，通過這樣的方式，左表在執行時(Runtime)提前進行資料過濾，提高查詢效率。

Runtime Filter是分散式SQL查詢引擎框架通用的一種優化手段，具體可參考: Join優化技術之Runtime Filter.

Runtime Filter涉及到的下推技術同樣也是查詢引擎框架常用的優化手段; 常見的下推優化技術有:謂詞下推, 儲存層下推等。

Doris支援的三種型別RuntimeFilter:

1. IN 的優點是過濾效果明顯，且快速。它的缺點首先第一個它只適用於 BroadCast，第二，它右表超過一定資料量的時候就失效了，當前 Doris 目前設定的是1024，即右表如果大於 1024，IN 的 Runtime Filter 就直接失效了，其餘的RuntimeFileter則沒有限制。
2. MinMax 的優點是開銷比較小。它的缺點就是對數值列還有比較好的效果，但對於非數值列，基本上就沒什麼效果。
3. Bloom Filter 的特點就是通用，適用於各種型別、效果也比較好。缺點就是它的設定比較複雜並且計算較高。

使用場景的要求:

1. 第一個要求就是左表大右表小，因為構建 Runtime Filter是需要承擔計算成本的，包括一些記憶體的開銷。
2. 第二個要求就是左右表 Join 出來的結果很少，說明這個 Join 可以過濾掉左表的絕大部分資料。

Join Reorder

Join Reorder 是指在執行SQL查詢時，決定多個表進行 join 的順序。它是資料庫查詢優化的一個重要方面，對查詢效能和效率有著重要的影響， 不同的 join order 對效能可能有數量級的影響。

從定義來看，其實就是尋找最短路徑(最優解)的過程，因此可以從演演算法的角度考慮，比如動態規劃演演算法與貪婪演演算法；同時也可以基於規則來做。

Doris中Join Reorder的實現是基於規則策略的，其規則定義如下：

1. 讓大表、跟小表儘量做 Join，它生成的中間結果是儘可能小的。
2. 把有條件的 Join 表往前放，也就是說盡量讓有條件的 Join 表進行過濾
3. Hash Join 的優先順序高於 Nest Loop Join，因為 Hash join 本身是比 Nest Loop Join 快很多的。

Join Reorder 也是SQL查詢引擎框架通用的一種優化手段, 在PolarDB、TiDB、StarRocks等資料庫框架中都有涉及與應用。其實現與說明如下:

1. TiDB Join Reorder 演演算法簡介
2. StarRocks Join Reorder 原始碼解析
3. PolarDB-X 優化器核心技術 ~ Join Reorder