ClickHouse存储引擎之MergeTree引擎——索引

2020-07-05 20:16:36

一、一级索引

​ MergeTree的主键使用PRIMARY KEY来定义，MergeTree会根据index_granularity间隔(默认8192行)，为数据表生成一级索引并保存到primary.idx文件里，索引数据会按照PRIMARY KEY排序，所以，ClickHouse中经常通过ORDER BY来代替主键。此时，索引(primary.idx)和数据文件(column.bin)会按照相同的规则排序

​ ClickHouse的一级索引使用了稀疏索引实现，即每一行索引表计对应的是一段数据，而不是一行数据。它使用少量的索引标记就可以记录大量数据的区间位置信息。

1、索引粒度

​ ClickHouse通过index_granularity参数来控制索引粒度，默认为8192，最新版本可以使用自适应索引粒度大小，则标记文件会被命名为(column.mrk2)。数据会以该参数的大小被标记为多个小区间，每个区间默认最多8192行数据，MergeTree使用MarkRange来表示一个具体区间，并通过start和end表示具体范围。

​ 在ClickHouse中，索引粒度不仅影响一级索引(primary.idx)，同时也影响数据标记文件(column.mrk)和数据文件(column.bin)。这是由于MergeTree无法只通过索引来完成查询工作，通过标记文件建立以稀疏索引(primary.idx)和对应数据文件(column.bin)的映射关系，MergeTree会先通过稀疏索引(primary.idx)找到对应数据的偏移量信息(column.mrk)，再通过偏移量直接从数据文件(column.bin)读取数据。所以一级索引和数据标记的间隔粒度相同，均有index_granularity参数决定，数据文件也会依据该参数生成压缩数据块。

MergeTree按照索引粒度划分数据

2、索引数据的生成规则

​ MergeTree需要间隔index_granularity行数据才会生成一条索引记录，索引值会依据声明的主键字段来获取。例如官方提供的测试数据表hits_v1使用了年月分区(PARTITION BY toYYYYMM(EventDate))，如果使用CounterID作为主键，则每间隔8192行数据就会取一次CounterID的值作为索引值，索引数据最终写入parimary.idx文件中保存。

​ 以上是使用单个字段作为主键的情况，若使用多个主键，例ORDER BY(CounterID, EventDate)，则每间隔8192行同时取CounterID和EventDate两列值作为索引，上述例子，索引值将为572014-03-1716352014-03-1832662014-03-19

二、索引的查询过程

​ MarkRange在ClickHouse中用来定义标记区间，MergeTree按照index_granularity设置的索引粒度，将一段完整的数据划分成了多个小的间隔数据段，一个数据段则是一个MarkRange，它与索引编号对应，使用start和end两个属性表示区间范围，通过start和end对应的索引编号的取值，可以得到它所对应的数值区间，数值区间则表示了该MarkRange的数据范围。

​ 假如一份测试数据，共有192条记录。其中主键ID为String类型，ID取值从A000开始，后面依次为A001、A002…A191。MergeTree的索引粒度为index_granularity=3，根据索引的生成规则，primary.idx文件内的索引数据会为A000A003A006A009A012...A186A189

​ 根据索引数据，MergeTree会将此数据片段分为192/3 = 64个小的MarkRange，两个相邻MarkRange相距步长为1，所有MarkRange(整个数据片段)的最大数值区间为[A000, +inf)。MarkRange和数值区间范围示意图如下：

​ 索引的查询其实为基于主键的查询条件转换的条件区间和MarkRange对应的数值区间这两个区间的交集判断。整个查询过程可分为以下三个步骤：

  1. 生成查询条件区间。

    例如：

    条件为 WHERE ID = 'A003',条件区间会转换为['A003', 'A003'];

    条件为WHEER ID > 'A000',条件区间会转换为['A000', +inf];

  2. 递归交集判断：以递归的形式，依次对MarkRange的数值区间与条件区间做交集判断。从最大的MarkRange区间[A000,+inf]开始

    1. 如果不存在交集，则直接去掉整段MarkRange数据
    2. 存在交集，且MarkRange步长大于8(end - start)，则将此区间进一步拆分成8个字区间(由merge_tree_coarse_index_granularity指定，默认为8)，不断重复，做交集判断
    3. 存在交集，并且MarkRange不可被再分解(步长小于8)，则记录MarkRange并返回

  3. 合并MarkRange区间：将最终匹配的MarkRange聚合

大致流程图如下：

二、二级索引

MergeTree还支持二级索引，但目前还处于测试阶段，官方不建议大量使用。

1、定义方式

MergeTree二级索引又叫跳数索引，是由数据按索引粒度分割后的每部分在指定表达式上的汇总信息组成，这些汇总信息有助于用where条件过滤时跳过不满足的数据，从而减少select查询从磁盘读取的数据量以及数据扫描的范围。

跳数索引默认是关闭的，需要执行SET allow_experimental_data_skipping_indices = 1开启，在创建表时指定，定义语法为：

INDEX index_name expr TYPE index_type(...) GRANULARITY granularity_value

当建表语句中声明了跳数索引，则会额外生成相对应的索引和标记文件(skp_idx_[column].idx和skp_idx_[column].mrk)

2、granularity与index_granularity的关系

不同的二级索引中，除了各个索引不同类型的参数以外，都共同拥有granularity参数。对于跳数索引，index_granularity定义了数据粒度，二granularity定义了聚合信息汇总的力度。即granularity定义了一行跳数索引能够跳过多少个index_granularity区间的数据。

跳数索引的生成规则可以大概解释为：

  1. 按照index_granularity粒度间隔将数据划分为n段，总共有[0, n-1]个区间(n = total_rows / index_granularity，向上取整)
  2. 根据索引定义声明，从0区间开始，一次按照index_granularity粒度从数据中获取聚合信息，每次向前移动1步(n + 1)，聚合信息逐步累加
  3. 当移动到granularity次区间时，则进行数据汇总并生成一行跳数索引数据

示例：

以minmax索引为例，它聚合了一个index_granularity区间内的最大和最小数据，假设index_granulariyt=8192且granulariyt=3，则数据按照index_granularity划分为n等份，MergeTree从第0段分区开始，依次获取聚合信息，当获取到第三个分区(granularity=3)，则汇总并生成第一行minmax索引(前3段minmax汇总后取值为[1, 9])，如下图所示：

3、跳数索引的类型

​ 目前，MergeTree支持4中跳数座因，分别是minmax、set、ngrambf_v1和tokenbf_v1，一张数据表支持同时声明多个跳数索引。

  • minmax：minmax索引记录了一段数据内的最小值和最大值，用于快速跳过无用的数据区间

    • INDEX a ID TYPE minmax GRANULARITY 5 表示minmax索引会记录每5个index_granularity区间数据中的最大值和最小值

  • set：存储指定字段或表达式的唯一值，完整形式为set(max_rows)，max_rows表示在一个index_granularity内，索引最多纪录的数据行数，如果max_rows=0，则表示无限制

    • INDEX b(length(ID) * 8) TYPE set(100) GRANULARITY 5 表示该索引会记录数据中ID长度*8之后的取值，并且每个index_granularity最多纪录100条

  • ngrambf_v1：记录了数据块中n元短语的布隆表过滤器(简单来讲，布隆表过滤器本质是由仅包含0和1位值的列表组成，默认均为0，利用哈希函数对数据值进行处理，并将结果位置上对应位的值改为1，由于存在哈希冲突，所以只能判断不在列表中和可能在列表中)，只支持String和FixedString数据类型，可用于优化like、in、equals、notIn、notEquals的查询性能，完整形式为ngrambf_v1(n, size_of_bloom_filter_in_bytes, number_of_hash_functions, random_seed)，各参数含义为：

    • n: token长度，依据n长度将数据切割为token短语
    • size_of_bloom_filter_in_bytes: 布隆过滤器的大小
    • number_of_hash_functions: 布隆过滤器中使用Hash函数的个数
    • random_seed: Hash函数的随机种子

    例如：INDEX c(ID, Code) TYPE ngrambf_v1(3, 256, 2, 0) GRANULARITY 5 表示依照3的粒度将数据切割成短语token，token经过两个Hash函数映射后再被写入，布隆过滤器大小伟256字节

  • tokenbf_v1：和ngrambf_v1类似，但它会自动按照非字符、数字的字符串切割token

  1. 一、一级索引
    1. 1、索引粒度
    2. 2、索引数据的生成规则
  2. 二、索引的查询过程
  3. 二、二级索引
    1. 1、定义方式
    2. 2、granularity与index_granularity的关系
    3. 3、跳数索引的类型