1、概念
- block：一次寫入生成的一個(gè)數(shù)據(jù)塊。
- primary.idx文件：存儲(chǔ)了稀疏索引,一個(gè)part對(duì)應(yīng)一個(gè)稀疏索引。
- bin文件：真正存儲(chǔ)數(shù)據(jù)的文件，由1到多個(gè)壓縮數(shù)據(jù)組成。壓縮數(shù)據(jù)是最小存儲(chǔ)單位，由『頭文件』和『壓縮數(shù)據(jù)塊』組成。頭文件由壓縮算法、壓縮前的字節(jié)大小、壓縮后的字節(jié)大小三部分組成；壓縮數(shù)據(jù)塊嚴(yán)格限定在壓縮前64K~1M byte大小。（這個(gè)大小是ClickHouse認(rèn)為的壓縮與解壓性能消耗最小的大?。?。即，一個(gè)壓縮數(shù)據(jù)塊由N個(gè)block組成，一個(gè)bin文件又由N個(gè)壓縮數(shù)據(jù)塊組成。
- mrk文件：存儲(chǔ)了block在bin文件中哪個(gè)壓縮數(shù)據(jù)以及這個(gè)壓縮數(shù)據(jù)的數(shù)據(jù)塊中的起始偏移量。
| 索引中的mark index | 壓縮數(shù)據(jù)index | 在壓縮數(shù)據(jù)塊中起始的字節(jié)數(shù)（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 12001 |
| 2 | 1 | 0 |
2、數(shù)據(jù)存儲(chǔ)
數(shù)據(jù)以壓縮數(shù)據(jù)為單位，存儲(chǔ)在bin文件中。
壓縮數(shù)據(jù)對(duì)應(yīng)的壓縮數(shù)據(jù)塊，嚴(yán)格限定按照64K~1M byte的大小來(lái)進(jìn)行存儲(chǔ)。
（1）如果一個(gè)block對(duì)應(yīng)的大小小于64K，則需要找下一個(gè)block來(lái)拼湊，直到拼湊出來(lái)的大小大于等于64K。
（2）如果一個(gè)block的大小在64K到1M的范圍內(nèi)，則直接生成1個(gè)壓縮數(shù)據(jù)塊。
（3）如果一個(gè)block的大小大于了1M，則切割生成多個(gè)壓縮數(shù)據(jù)塊。一個(gè)part下不同的列分別存儲(chǔ)，不同的列存儲(chǔ)的行數(shù)是一樣的。
3、檢索過(guò)程
以 where partition = '2019-10-23' and ID >= 10 and ID < 100 （ID是索引字段）的query描述大體檢索流程:
- 每個(gè)索引都有對(duì)應(yīng)的min/max的partition值，存儲(chǔ)在內(nèi)存中。當(dāng)contition帶上partition時(shí)就可以從這些block列表中找到需要檢索的索引，找到對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)文件夾，命中對(duì)應(yīng)的索引（primary.idx）
- 根據(jù)ID字段，把條件轉(zhuǎn)化為[10,100)的條件區(qū)間,再把條件區(qū)間與這個(gè)partition對(duì)應(yīng)的稀疏索引做交集判斷。如果沒有交集則不進(jìn)行具體數(shù)據(jù)的檢索；如果有交集，則把稀疏索引等分8份，再把條件區(qū)間與稀疏索引分片做交集判斷，直到不能再拆分或者沒有交集，則最后剩下的所有條件區(qū)間就是我們要檢索的block值。
- 通過(guò)步驟2我們得到了我們要檢索的block值。通過(guò)上面我們知道存在多個(gè)block壓縮在同一個(gè)壓縮數(shù)據(jù)塊的情況并且一個(gè)bin文件里面又存在N個(gè)壓縮數(shù)據(jù)的情況，所以不能直接通過(guò)block的值直接到bin文件中搜尋數(shù)據(jù)。我們通過(guò)映射block值到mrk中，通過(guò)mrk知道這個(gè)block對(duì)應(yīng)到的壓縮數(shù)據(jù)以及在壓縮數(shù)據(jù)塊里面的字節(jié)偏移量，就得到了我們最后需要讀取的數(shù)據(jù)地址。
- 把bin文件中的數(shù)據(jù)讀取到內(nèi)存中，找到對(duì)應(yīng)的壓縮數(shù)據(jù)，直接從對(duì)應(yīng)的起始偏移量開始讀取數(shù)據(jù)。
4、example
(1)寫入
假設(shè)表的index字段為Column A，一個(gè)Column A的字符長(zhǎng)度為30KB；還有個(gè)非index字段Column B，一個(gè)Column B的字符長(zhǎng)度為100KB；index_granularity=2。
依7次寫入7行數(shù)據(jù)，數(shù)據(jù)如下
| A | B |
|---|---|
| a | 1 |
| a | 3 |
| b | 2 |
| b | 2 |
| c | 1 |
| a | 4 |
| a | 0 |
寫入以后假設(shè)已經(jīng)完全merge，則排序后為：
| A | B |
|---|---|
| a | 0 |
| a | 1 |
| a | 3 |
| a | 4 |
| b | 2 |
| b | 2 |
| c | 1 |
則生成的索引為：
| mark number | value |
|---|---|
| 0 | a |
| 1 | a |
| 2 | b |
| 3 | c |
(2)存儲(chǔ)
根據(jù)壓縮數(shù)據(jù)的64KB~1MB的理論，則在
Column A.bin文件中，對(duì)應(yīng)的存儲(chǔ)為：
（3個(gè)block才大于64KB，生成一個(gè)壓縮數(shù)據(jù)塊）
Column A.mrk文件中，對(duì)應(yīng)的存儲(chǔ)為：
| 索引中的mark number | 壓縮數(shù)據(jù)index | 在壓縮數(shù)據(jù)塊中起始的字節(jié)數(shù)（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 61440(30 * 1024 * 2) |
| 2 | 1 | 30720 |
| 3 | 2 | 0 |
同理有Column B.mrk文件為：
Column B.bin文件為：
| 索引中的mark number | 壓縮數(shù)據(jù)index | 在壓縮數(shù)據(jù)塊中起始的字節(jié)數(shù)（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 0 |
| 4 | 4 | 0 |
| 5 | 5 | 0 |
| 6 | 6 | 0 |
(3)搜索
以A='a'為例，則命中的索引mark number為0跟1。
再返回回來(lái)mrk文件中，以(0,0)代表壓縮數(shù)據(jù)塊0，偏移量0。例如對(duì)于Column A而言，mark number 0則命中[(0,0),(0,61440))對(duì)應(yīng)的block，mark number 1命中了[(0,61441),(1,30720))對(duì)應(yīng)的block。將這些block加載進(jìn)內(nèi)存，再通過(guò)偏移量計(jì)算，得到最終需要掃描的行。
5、other
- 為什么加了partition查詢會(huì)變快？因?yàn)橹恍枰獟呙杵ヅ鋚artition對(duì)應(yīng)的索引就可以，不加partition就需要掃描所有partition上的索引。
- 為什么用范圍查詢也能命中索引？理由如3。
6、reference
朱凱老師的分享，in ClickHouse Meetup
