LSM-Tree
Doris的存儲結(jié)構(gòu)是類似LSM-Tree設(shè)計的，因此很多方面都是通用的，先閱讀了解LSM相關(guān)的知識，再看Doris的底層存儲與讀取流程會清晰透徹很多，LSM基本知識如下:
原理：把各種數(shù)據(jù)先用log等形式組織在內(nèi)存中(該數(shù)據(jù)結(jié)構(gòu)稱為MemTable，且有序)；到達一定數(shù)據(jù)量后再批量merge寫入磁盤(該數(shù)據(jù)結(jié)構(gòu)稱為SSTable)；為壓縮存儲，會通過歸并排序合并壓縮SSTable。LSM主要是利用順序?qū)懸入S機寫更快速高效的原理，加上歸并排序，合并壓縮文件，提供更高效的數(shù)據(jù)存儲與查詢支持。
MemTable: 內(nèi)存里的表，有序且存儲在內(nèi)存Buffer中；用有序數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)，一般是用跳表(SkipList)，也可以是有序數(shù)組或紅黑樹等二叉搜索樹。
SSTable: Sorted Strings Table; 由MemTable按SSTable文件格式刷入磁盤持久化存儲，一般由一組數(shù)據(jù)block和一組元數(shù)據(jù)block組成，數(shù)據(jù)是已序的。元數(shù)據(jù)block會存儲數(shù)據(jù)block的描述信息，如索引、BloomFilter、壓縮、統(tǒng)計等信息；數(shù)據(jù)block存儲數(shù)據(jù)?？梢钥醋魇且粋€有序的數(shù)組或有序鏈表。
Compaction: 通過歸并排序算法，合并壓縮SSTable。
LSM（Log-Structured Merge-Tree）是一種在分布式系統(tǒng)中常用的數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和檢索大量數(shù)據(jù)。它結(jié)合了日志結(jié)構(gòu)化（Log-Structured）和歸并排序（Merge-Sort）的思想，通過將數(shù)據(jù)按照鍵的順序合并存儲，實現(xiàn)了高效的寫入和讀取操作。
其核心思想在于充分發(fā)揮磁盤連續(xù)讀寫的性能優(yōu)勢、以短時間的內(nèi)存與 IO 的開銷換取最大的寫入性能，數(shù)據(jù)以 Append-only 的方式寫入 Memtable、達到閾值后凍結(jié) Memtable 并 Flush 為磁盤文件、再結(jié)合 Compaction 機制將多個小文件進行多路歸并排序形成新的文件，最終實現(xiàn)數(shù)據(jù)的高效寫入。
SSTable文件格式是一個很重要的信息;其包含存儲與檢索數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計，比如索引值，壓縮算法，布隆過濾器等高效的設(shè)計。
參考:
LSM 樹設(shè)計原理
LSM Tree索引：高性能寫引擎
索引
官網(wǎng)文檔: 索引概述.
Doris內(nèi)建的索引: 前綴索引(Short key Index)、ZoneMap索引，默認是根據(jù)建表時的key列生成的。
Doris 的數(shù)據(jù)存儲在類似 SSTable（Sorted String Table）的數(shù)據(jù)結(jié)構(gòu)中。該結(jié)構(gòu)是一種有序的數(shù)據(jù)結(jié)構(gòu)，可以按照指定的列進行排序存儲。在這種數(shù)據(jù)結(jié)構(gòu)上，以排序列作為條件進行查找，會非常的高效。
在 Aggregate、Unique 和 Duplicate 三種數(shù)據(jù)模型中。底層的數(shù)據(jù)存儲，是按照各自建表語句中，AGGREGATE KEY、UNIQUE KEY 和 DUPLICATE KEY 中指定的列進行排序存儲的。因此在此排序列的基礎(chǔ)上根據(jù)不同的場景構(gòu)建內(nèi)置的索引，提高查詢的性能與效率。
Duplicate、Aggregate、Unique 模型，都會在建表指定 key 列，然而實際上是有所區(qū)別的：對于 Duplicate 模型，表的key列， 可以認為只是 “排序列”，并非起到唯一標識的作用。而 Aggregate、Unique 模型這種聚合類型的表，key 列是兼顧 “排序列” 和 “唯一標識列”，是真正意義上的“ key 列”。
參考:
Apache Doris 索引機制解析
Doris-BE-存儲結(jié)構(gòu)設(shè)計解析
Join
官網(wǎng)文檔: Doris Join 優(yōu)化原理
概覽
Doris 支持兩種物理算子，一類是 Hash Join，另一類是 Nest Loop Join。
Doris 支持 4 種數(shù)據(jù) Shuffle 方式：
-
BroadCast Join: 要求把右表全量的數(shù)據(jù)都發(fā)送到左表上，即每一個參與 Join 的節(jié)點，它都擁有右表全量的數(shù)據(jù)
-
Shuffle Join: 只支持hash join場景(即等值匹配). 當進行 Hash Join 時候，可以通過 Join 列計算對應(yīng)的 Hash 值，并進行 Hash 分桶，并將分桶后的數(shù)據(jù)分散到節(jié)點中進行計算
-
Bucket Shuffle Join: 右表數(shù)據(jù)掃描出來之后進行數(shù)據(jù)分區(qū)的 Hash 計算，根據(jù)左表本身的數(shù)據(jù)分布發(fā)送到右表對應(yīng)的 Join 計算節(jié)點上。
-
Colocation: 導(dǎo)入數(shù)據(jù)時，提前將join表的數(shù)據(jù)分散到一個節(jié)點
Runtime Filter
Doris 在進行 Hash Join 計算時會在右表構(gòu)建一個哈希表，左表流式的通過右表的哈希表從而得出 Join 結(jié)果。而 RuntimeFilter 就是充分利用了右表的 Hash 表，在右表生成哈希表的時候，同時生成一個基于哈希表數(shù)據(jù)的一個過濾條件(Filter)，然后下推到左表的數(shù)據(jù)掃描節(jié)點，通過這樣的方式，左表在運行時(Runtime)提前進行數(shù)據(jù)過濾，提高查詢效率。
Runtime Filter是分布式SQL查詢引擎框架通用的一種優(yōu)化手段，具體可參考: Join優(yōu)化技術(shù)之Runtime Filter.
Runtime Filter涉及到的下推技術(shù)同樣也是查詢引擎框架常用的優(yōu)化手段; 常見的下推優(yōu)化技術(shù)有:謂詞下推, 存儲層下推等。
Doris支持的三種類型RuntimeFilter:
- IN 的優(yōu)點是過濾效果明顯，且快速。它的缺點首先第一個它只適用于 BroadCast，第二，它右表超過一定數(shù)據(jù)量的時候就失效了，當前 Doris 目前配置的是1024，即右表如果大于 1024，IN 的 Runtime Filter 就直接失效了，其余的RuntimeFileter則沒有限制。
- MinMax 的優(yōu)點是開銷比較小。它的缺點就是對數(shù)值列還有比較好的效果，但對于非數(shù)值列，基本上就沒什么效果。
- Bloom Filter 的特點就是通用，適用于各種類型、效果也比較好。缺點就是它的配置比較復(fù)雜并且計算較高。
使用場景的要求:
- 第一個要求就是左表大右表小，因為構(gòu)建 Runtime Filter是需要承擔計算成本的，包括一些內(nèi)存的開銷。
- 第二個要求就是左右表 Join 出來的結(jié)果很少，說明這個 Join 可以過濾掉左表的絕大部分數(shù)據(jù)。
Join Reorder
Join Reorder 是指在執(zhí)行SQL查詢時，決定多個表進行 join 的順序。它是數(shù)據(jù)庫查詢優(yōu)化的一個重要方面，對查詢性能和效率有著重要的影響， 不同的 join order 對性能可能有數(shù)量級的影響。
從定義來看，其實就是尋找最短路徑(最優(yōu)解)的過程，因此可以從算法的角度考慮，比如動態(tài)規(guī)劃算法與貪心算法；同時也可以基于規(guī)則來做。
Doris中Join Reorder的實現(xiàn)是基于規(guī)則策略的，其規(guī)則定義如下：文章來源：http://www.zghlxwxcb.cn/news/detail-747359.html
- 讓大表、跟小表盡量做 Join，它生成的中間結(jié)果是盡可能小的。
- 把有條件的 Join 表往前放，也就是說盡量讓有條件的 Join 表進行過濾
- Hash Join 的優(yōu)先級高于 Nest Loop Join，因為 Hash join 本身是比 Nest Loop Join 快很多的。
Join Reorder 也是SQL查詢引擎框架通用的一種優(yōu)化手段, 在PolarDB、TiDB、StarRocks等數(shù)據(jù)庫框架中都有涉及與應(yīng)用。其實現(xiàn)與說明如下:文章來源地址http://www.zghlxwxcb.cn/news/detail-747359.html
- TiDB Join Reorder 算法簡介
- StarRocks Join Reorder 源碼解析
- PolarDB-X 優(yōu)化器核心技術(shù) ~ Join Reorder
到了這里，關(guān)于聊聊分布式 SQL 數(shù)據(jù)庫Doris(七)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
