ClickHouse和他的朋友們（6）MergeTree儲存結構

 上篇的 儲存引擎技術進化與MergeTree 介紹了儲存演算法的演進。

儲存引擎是一個數據庫的底盤，一定要穩和動力澎湃。

接下來我們將一起來探索下 ClickHouse MergeTree 列式儲存引擎，解構下這臺“跑車”最重要的部件。

所有的儲存引擎，無論精良與粗製濫造，最終都是要把資料回寫到磁碟，來滿足儲存和索引目的。

磁碟檔案的構造可以說是演算法的物理體現，我們甚至可以通過這些儲存結構反推出其演算法實現。

所以，要想深入瞭解一個儲存引擎，最好的入手點是它的磁碟儲存結構，然後再反觀它的讀、寫機制就會有一種水到渠成的感覺。

如果這個分析順序搞反了，會有一種生硬的感覺，網上大部分教程都是這種“生硬”式教學，本文將直擊靈魂從最底層談起，徹底搞明白４個問題：

1. MergeTree 有哪些檔案？

2. MergeTree 資料如何分佈？

3. MergeTree 索引如何組織？

4. MergeTree 如何利用索引加速？

話不多說，上表：

CREATE TABLE default.mt
(
    `a` Int32,
    `b` Int32,
    `c` Int32,
    INDEX `idx_c` (c) TYPE minmax GRANULARITY 1
)
ENGINE = MergeTree
PARTITION BY a 
ORDER BY b
SETTINGS index_granularity=3

造點資料：

insert into default.mt(a,b,c) values(1,1,1);
insert into default.mt(a,b,c) values(5,2,2),(5,3,3);
insert into default.mt(a,b,c) values(3,10,4),(3,9,5),(3,8,6),(3,7,7),(3,6,8),(3,5,9),(3,4,10);

磁碟檔案

ls ckdatas/data/default/mt/
1_4_4_0  3_6_6_0  5_5_5_0  detached  format_version.txt

可以看到，生成了 3 個數據目錄，每個目錄在 ClickHouse 裡稱作一個分割槽(part)，目錄名的字首正是我們寫入時欄位 a 的值: 1,3,5，因為表分割槽是這樣定位的：PARTITION BY a。

現在我們看看 a=3 分割槽：

ls ckdatas/data/default/mt/3_6_6_0/
a.bin  a.mrk2  b.bin  b.mrk2  c.bin  checksums.txt  c.mrk2  columns.txt  count.txt  minmax_a.idx  partition.dat  primary.idx  skp_idx_idx_c.idx  skp_idx_idx_c.mrk2

• *.bin 是列資料檔案，按主鍵排序(ORDER BY)，這裡是按照欄位 b 進行排序
• *.mrk2 mark 檔案，目的是快速定位 bin 檔案資料位置
• minmax_a.idx 分割槽鍵 min-max 索引檔案，目的是加速分割槽鍵 a 查詢
• primay.idx 主鍵索引檔案，目的是加速主鍵 b 查詢
• skp_idx_idx_c.* 欄位 c 索引檔案，目的是加速 c 的查詢

在磁碟上，MergeTree 只有一種物理排序，就是 ORDER BY 的主鍵序，其他檔案(比如 .mrk/.idx)是一種邏輯加速，圍繞僅有的一份物理排序，要解決的問題是：

在以欄位 b 物理排序上，如何實現欄位 a、欄位 c 的快速查詢？

MergeTree 引擎概括起來很簡單：整個資料集通過分割槽欄位被劃分為多個物理分割槽，每個分割槽內又通過邏輯檔案圍繞僅有的一種物理排序進行加速查詢。

儲存結構

資料檔案

對於單個物理分割槽內的儲存結構，首先要明確一點，MergeTree 的資料只有一份：*.bin。

a.bin 是欄位 a 的資料，b.bin 是欄位 b 的資料，c.bin 是欄位 c 的資料，也就是大家熟悉的列儲存。

各個 bin 檔案以 b.bin排序對齊（b 是排序鍵），如圖：

這樣會有一個比較嚴重的問題：如果 *.bin 檔案較大，即使讀取一行資料，也要載入整個 bin 檔案，浪費了大量的 IO，沒法忍。

granule

高、黑科技來了，ClickHouse MergeTree 把 bin 檔案根據顆粒度(GRANULARITY)劃分為多個顆粒(granule)，每個 granule 單獨壓縮儲存。

SETTINGS index_granularity=3 表示每 ３ 行資料為一個 granule，分割槽目前只有 ７ 條資料，所以被劃分成 3 個 granule(三個色塊)：

為方便讀取某個 granule，使用 *.mrk 檔案記錄每個 granule 的 offset，每個 granule 的 header 裡會記錄一些元資訊，用於讀取解析:

這樣，我們就可以根據 ｍark 檔案，直接定位到想要的 granule，然後對這個單獨的 granule 進行讀取、校驗。

目前，我們還有缺少一種對映：每個 mark 與欄位值之間的對應，哪些值區間落在 mark0，哪些落在 mark1 ...？

有了這個對映，就可以實現最小化讀取 granule 來加速查詢：

1. 根據查詢條件確定需要哪些 mark
2. 根據 mark 讀取相應的 granule

儲存排序

在瞭解 MergeTree 索引機制之前，需要明白以下兩點：

1. 只有一份全量資料，儲存在 *.bin 檔案

2. *.bin 按照 ORDER BY 欄位降序儲存

3. 
   

稀疏索引

因為資料只有一份且只有一種物理排序，MergeTree在索引設計上選擇了簡單、高效的稀疏索引模式。

什麼是稀疏索引呢？就是從已經排序的全量資料裡，間隔性的選取一些點，並記錄這些點屬於哪個 mark。

1. primary index

主鍵索引，可通過[PRIMARY KEY expr]指定，預設是 ORDER BY 欄位值。

注意 ClickHouse primary index 跟 MySQL primary key 不是一個概念。

在稀疏點的選擇上，取每個 granule 最小值：

2. skipping index

普通索引。

INDEXidx_c(c) TYPE minmax GRANULARITY 1 針對欄位 c 建立一個 minmax 模式索引。

GRANULARITY 是稀疏點選擇上的 granule 顆粒度，GRANULARITY 1 表示每 1 個 granule 選取一個：

如果定義為GRANULARITY 2 ，則 2 個 granule 選取一個：

3. partition minmax index

針對分割槽鍵，MergeTree 還會建立一個 min/max 索引，來加速分割槽選擇。

4. 全景圖

查詢優化

現在熟悉了 MergeTree 的儲存結構，我們通過幾個查詢來體驗下。

1. 分割槽鍵查詢

語句：

select * from default.mt where a=3

查詢會直接根據 a=3 定位到單個分割槽:

<Debug> InterpreterSelectQuery: MergeTreeWhereOptimizer: condition "a = 3" moved to PREWHERE
<Debug> default.mt (SelectExecutor): Key condition: unknown
<Debug> default.mt (SelectExecutor): MinMax index condition: (column 0 in [3, 3])
<Debug> default.mt (SelectExecutor): Selected 1 parts by a, 1 parts by key, 3 marks by primary key, 3 marks to read from 1 ranges
┌─a─┬──b─┬──c─┐
│ 3 │  4 │ 10 │
│ 3 │  5 │  9 │
│ 3 │  6 │  8 │
│ 3 │  7 │  7 │
│ 3 │  8 │  6 │
│ 3 │  9 │  5 │
│ 3 │ 10 │  4 │
└───┴────┴────┘

2. 主鍵索引查詢

語句：

select * from default.mt where b=5

查詢會先從 3 個分割槽讀取 prmary.idx，然後定位到只有一個分割槽符合條件，找到要讀取的 mark:

<Debug> default.mt (SelectExecutor): Key condition: (column 0 in [5, 5])
<Debug> default.mt (SelectExecutor): MinMax index condition: unknown
<Debug> default.mt (SelectExecutor): Selected 3 parts by a, 1 parts by key, 1 marks by primary key, 1 marks to read from 1 ranges
┌─a─┬─b─┬─c─┐
│ 3 │ 5 │ 9 │
└───┴───┴───┘

3. 索引查詢

語句：

select * from default.mt where b=5

查詢會先從 3 個分割槽讀取 prmary.idx 和 skp_idx_idx_c.idx 進行 granule 過濾（沒用的 drop 掉），然後定位到只有 3_x_x_x 分割槽的一個 granule 符合條件:

<Debug> InterpreterSelectQuery: MergeTreeWhereOptimizer: condition "c = 5" moved to PREWHERE
<Debug> default.mt (SelectExecutor): Key condition: unknown
<Debug> default.mt (SelectExecutor): MinMax index condition: unknown
<Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 1 / 1 granules.
<Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 1 / 1 granules.
<Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 2 / 3 granules.
<Debug> default.mt (SelectExecutor): Selected 3 parts by a, 1 parts by key, 5 marks by primary key, 1 marks to read from 1 ranges
┌─a─┬─b─┬─c─┐
│ 3 │ 9 │ 5 │
└───┴───┴───┘

總結

本文從磁碟儲存結構入手，分析 ClickHouse MergeTree 的儲存、索引設計。

只有瞭解了這些底層機制，我們才好對自己的 SQL 和表結構進行優化，使其執行更加高效。

ClickHouse MergeTree 設計簡單、高效，它首要解決的問題是：在一種物理排序上，如何實現快速查詢。

針對這個問題，ClickHouse使用稀疏索引來解決。

在官方 roadmap 上，列舉了一個有意思的索引方向：Z-Order Indexing，目的是把多個維度編碼到一維儲存，當我們給出多維度條件的時候，可以快速定位到這個條件點集的空間位置，目前 ClickHouse 針對這個索引設計暫無進展。

from: https://www.gushiciku.cn/pl/pS3b/zh-tw