clickhouse索引原理介绍

clickhouse本身支持很多表引擎，这里只介绍其中最常用的MergeTree引擎。

建表语句

CREATE TABLE [IF NOT EXISTS] [db.]table_name (
    name1 [type1] [DEFAULT|MATERIALIZED|ALIAS expr1] [TTL expr1],
    name2 [type2] [DEFAULT|MATERIALIZED|ALIAS expr2] [TTL expr2],
    ...
    INDEX index_name1 expr1 TYPE type1(...) GRANULARITY value1, # 创建普通索引（跳数索引）
    INDEX index_name2 expr2 TYPE type2(...) GRANULARITY value2
) ENGINE = MergeTree()
ORDER BY expr
[PARTITION BY expr] # 创建分区键索引
[PRIMARY KEY expr] # 创建主键索引
[SAMPLE BY expr]
[TTL expr [DELETE|TO DISK 'xxx'|TO VOLUME 'xxx'], ...]
[SETTINGS name=value, ...]

介绍其中几个关键选项的含义：

PARTITION BY ：分区键。指定表数据以何种标准进行分区。分区键既可以是单个列字段，也可以通过元组的形式使用多个列字段，同时它也支持使用列表达式。
ORDER BY ：排序键，用于指定在一个数据片段内，数据以何种标准排序。默认情况下主键（PRIMARY KEY）与排序键相同。
PRIMARY KEY：主键。声明后会依照主键字段生成一级索引。默认情况下，主键与排序键(ORDER BY)相同，所以通常直接使用ORDER BY代为指定主键。
SETTINGS:：index_granularity选项表示索引的粒度，默认值为8192。MergeTree索引在默认情况下，每间隔8192行数据才生成一条索引。

数据存储文件

下面是clickhouse在存储数据时所产生的文件，现分别对其用途做简要说明：

checksums.txt 校验文件，用于记录其他的各类文件（如idx, mrk等）的size和其哈希值，用于快速校验文件的完整性和正确性。
columnx.txt 列信息文件，明文存储，记录该表的所有列信息。
count.txt 计数文件，明文存储，记录当前分区下数据的总行数。
primary.idx 主键索引文件
列名.bin 列数据文件，使用压缩格式存储。每一列都对应一个该文件，如列age为age.bin
列名.mrk 列标记文件，使用二进制存储。
partition.dat 保存当前分区下分区表达式最终生成的值
minmax_.idx 记录当前分区下分区字段对应原始数据的最小和最大值。
skp_idx_列名.idx 跳数索引数据文件。
skp_idx_列名.mrk 跳数索引标记文件。

索引类型

首先说明两个重要概念

granule 索引粒度，由index_granularity指定，默认8192
block 列存储文件的压缩单元。每个列存文件的Block包含若干个Granule，具体多少个Granule是由参数min_compress_block_size控制，每次列的Block中写完一个Granule的数据时，它会检查当前Block Size有没有达到设定值，如果达到则会把当前Block进行压缩然后写磁盘。

主键索引

对应文件：primary.idx

与传统数据库不同，主键索引是可以相同的。主键索引存储的是主键值和block，且数据是按照主键进行排序的。若查询条件中含有主键值，则会先根据主键索引得到可能的granule范围，再根据mk标记文件中的偏移量确定数据。

分区键索引

数据文件：minmax_分区键名.idx

记录当前分区下分区字段对应原始数据的最小和最大值。用于查询时迅速排除不需要的分区。

跳数索引

数据文件： skp_idx_列名.idx

语法：INDEX index_name1 expr1 TYPE type1(...) GRANULARITY value1

索引的可用类型包括minmax, set, bloom_filter。

和主键索引类似，也是一种稀疏索引。因为数据是按主键排序的，主键索引统计的其实就是每个Granule粒度的主键序列最大和最小值，而Skipping索引提供的聚合函数种类更加丰富，是主键索引的一种补充能力。

数据插入

MergeTree在写入一批数据时，数据总会以数据片段的形式写入磁盘，且数据片段不可修改。为了避免片段过多，ClickHouse会通过后台线程，定期合并这些数据片段，属于相同分区的数据片段会被合成一个新的片段。

MergeTree表的写入链路是一个极端的batch load过程，Data Part不支持单条的append insert。每次batch insert都会生成一个新的MergeTree Data Part。如果用户单次insert一条记录，那就会为那一条记录生成一个独立的Data Part，这必然是无法接受的。一般我们使用MergeTree表引擎的时候，需要在客户端做聚合进行batch写入或者在MergeTree表的基础上创建Distributed表来代理MergeTree表的写入和查询，Distributed表默认会缓存用户的写入数据，超过一定时间或者数据量再异步转发给MergeTree表。MergeTree存储引擎对数据实时可见要求非常高的场景是不太友好的。

数据查询

例如有如下数据，主键为x和y。

x	y	z
A	a	1
A	a	2
A	c	1
B	c	1
B	c	2
C	a	3
C	a	1

假设index_granularity为2，先将数据分为多个block

x	y	block-id
A	a	1
A	a	1
A	c	2
B	c	2
B	b	3
C	a	3
C	a	4

primary.idx内容展示的是主键和block的关系

主键	block
(A,a)	1
(A,c)	2
(B,b)	3
(C,a)	4

x.bin 和 y.bin存储对应的各个列的数据，x.mrk存储如下

block-id	offset
1	1-3
2	4-9
3	10-30

查询过程如下：

1、查询条件
2、通过查询条件的主键，可以根据primary.idx得出数据落在哪些block
3、根据block id 到各自的 mrk上寻找对应的offset
4、根据offset去bin中获取对应的数据，加载到内存中向量化操作，过滤

从以上可以看出：

查询条件含有主键会减少很多不必要的磁盘IO
查询返回的值中列越少，读取的列标记文件和列数据文件就越少，磁盘IO也会降低很多

参考文章