当前位置:   article > 正文

【ClickHouse内核】MergeTree索引相关基础知识点_index_granularity

index_granularity

目录

概述

主键索引

稀疏索引的含义

稀疏索引的优势

索引粒度

MergeTree表引擎和索引粒度相关的属性

索引粒度的优势

索引数据的生成规则

索引的工作机制


概述

索引是clickhouse查询速度比较快的一个重要原因,正是因为有索引可以避免不必要的数据的扫描和处理。传统基于hdfs的olap引擎都是不支持索引的,基本的数据过滤只能支持分区进行过滤,这样会扫描处理很多不必要的数据。

那么我们下面就揭开ClikHouse关于索引的神秘面纱。

 

主键索引

MergeTree的主键使用PRIMARY KEY定义,待主键定义之后,MergeTree会依据index_granularity间隔(默认8192行),为数据表生成主键索引并保存至primary.idx文件内,索引数据按照PRIMARY KEY排序。相比使用PRIMARY KEY定义,更为常见的简化形式是通过ORDER BY指代主键。在此种情形下,PRIMARY KEY与ORDER BY定义相同,所以索引(primary.idx)和数据(.bin)会按照完全相同的规则排序。

ClickHouse的主键索引和别的数据库是不一样的,他不是唯一的,可以使用相同的主键插入多行。

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

 

稀疏索引的含义

稀疏索引中,每一行索引标记对应的是一段数据,而不是一行。用一个形象的例子来说明:如果把MergeTree比作一本书,那么稀疏索引就好比是这本书的一级章节目录。一级章节目录不会具体对应到每个字的位置,只会记录每个章节的起始页码。

 

稀疏索引的优势

稀疏索引的优势是显而易见的,它仅需使用少量的索引标记就能够记录大量数据的区间位置信息,且数据量越大优势越为明显。以默认的索引粒度(8192)为例,MergeTree只需要12208行索引标记就能为1亿行数据记录提供索引。由于稀疏索引占用空间小,所以primary.idx内的索引数据常驻内存,取用速度自然极快。

 

索引粒度

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表引擎和索引粒度相关的属性

  • index_granularity — 索引粒度。索引中相邻的『标记』间的数据行数。默认值,8192 。
  • index_granularity_bytes — 索引粒度,以字节为单位,默认值: 10Mb。
  • enable_mixed_granularity_parts — 是否启用通过 index_granularity_bytes 控制索引粒度的大小。在19.11版本之前, 只有 index_granularity 配置能够用于限制索引粒度的大小。当从具有很大的行(几十上百兆字节)的表中查询数据时候,index_granularity_bytes 配置能够提升ClickHouse的性能。如果你的表里有很大的行,可以开启这项配置来提升SELECT 查询的性能。

 

索引粒度的优势

在ClickHouse中数据是列式存储的方式。每一列都单独存储在一个.bin文件中。举个例子如下所示

这样会有一个比较严重的问题:

如果 列.bin 文件较大,即使读取一行数据,也要加载整个 bin 文件,浪费了大量的 IO,非常影响性能。

那么有没有办法优化呢?ClickHouse MergeTree 把 bin 文件根据颗粒度(GRANULARITY)划分为多个颗粒(granule),每个 granule 单独压缩存储。

SETTINGS index_granularity=3 表示每 3 行数据为一个 granule,分区目前只有 9 条数据,所以被划分成 3 个granule:

为方便读取某个 granule,使用 *.mrk 文件记录每个 granule 的 offset,每个 granule 的 header 里会记录一些元信息,用于读取解析:

这样,我们就可以根据 mrk 文件,直接定位到想要的 granule,然后对这个单独的 granule 进行读取。

 

 

索引数据的生成规则

由于是稀疏索引,所以MergeTree需要间隔index_granularity行数据才会生成一条索引记录,其索引值会依据声明的主键字段获取。举个例子如下所示

--创建表语句CREATE TABLE primary_idx_test(    `value` String)ENGINE = MergeTree()ORDER BY valueSETTINGS index_granularity = 3, index_granularity_bytes = 0--插入数据insert into primary_idx_test values('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');

 

本案例中使用value作为主键(ORDER BY value),则每间隔3行数据就会取一次value的值作为索引值,索引数据最终会被写入primary.idx文件进行保存。这里需要特殊注意下,我们需要配置下index_granularity_bytes为0,关闭了他自适应算法,仅按数据行数限制索引粒度来降低复杂程度。

例如第0(3*0)行value取值1,第3(3*1)行value取值4,而第6(3*2)行value取值7,最终索引数据将会是147。

 

MergeTree对于稀疏索引的存储是非常紧凑的,索引值前后相连,按照主键字段顺序紧密地排列在一起。不仅此处,ClickHouse中很多数据结构都被设计得非常紧凑,比如其使用位读取替代专门的标志位或状态码,可以不浪费哪怕一个字节的空间。以小见大,这也是ClickHouse为何性能如此出众的深层原因之一。

 

索引的工作机制

在前面我们说到MarkRange在ClickHouse中是用于定义标记区间的对象。MergeTree按照index_granularity的间隔粒度,将一段完整的数据划分成了多个小的间隔数据段,一个具体的数据段即是一个MarkRange。MarkRange与索引编号对应,使用begin和end两个属性表示其区间范围。通过与begin及end对应的索引编号的取值,即能够得到它所对应的数值区间。而数值区间表示了此MarkRange包含的数据范围。

还用我们之前举的例子来描述过程。MergeTree的索引粒度index_granularity=3,根据索引的生成规则,primary.idx文件内的索引数据如下所示。

--创建表语句CREATE TABLE primary_idx_test(    `value` String)ENGINE = MergeTree()ORDER BY valueSETTINGS index_granularity = 3, index_granularity_bytes = 0--插入数据insert into primary_idx_test values('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');

 

根据索引数据,MergeTree会将此数据片段划分成9/3=3个小的MarkRange。如下所示。

 

在引出了数值区间的概念之后,对于索引的查询过程就很好解释了。索引查询其实就是两个数值区间的交集判断。其中,一个区间是由基于主键的查询条件转换而来的条件区间;而另一个区间是刚才所讲述的与MarkRange对应的数值区间。

 

整个索引查询过程可以大致分为3个步骤。

(1)生成查询条件区间:首先,将查询条件转换为条件区间。即便是单个值的查询条件,也会被转换成区间的形式,例如下面的例子。

WHERE value = '1'['1', '1'] WHERE value > '0' ('0', +inf) WHERE value < '9'(-inf, '9') WHERE ID LIKE '6%'['6', '7')

 

(2)递归交集判断:以递归的形式,依次对MarkRange的数值区间与条件区间做交集判断。从最大的区间[0,+inf)开始:

  • 如果不存在交集,则直接通过剪枝算法优化此整段MarkRange。
  • 如果存在交集,且MarkRange步长(end-begin)大于index_granularity属性(默认值为8),则将此区间进一步拆分成8个子区间(由merge_tree_coarse_index_granularity指定,默认值为8),并重复此规则,继续做递归交集判断。
  • 如果存在交集,且MarkRange不可再分解(步长小于index_granularity属性(默认值为8)),则记录MarkRange并返回。

(3)合并MarkRange区间:将最终匹配的MarkRange聚在一起,合并它们的范围。

 

完整逻辑的如下图所示。

MergeTree通过递归的形式持续向下拆分区间,最终将MarkRange定位到最细的粒度,以帮助在后续读取数据的时候,能够最小化扫描数据的范围。当查询条件WHERE value='1'的时候,最终只需要读取[1, 4)区间的数据,它们对应MarkRange(begin:0, end:1)范围,而其他无用的区间都被裁剪掉了。

 

参考资料

  • https://bohutang.me/2020/06/26/clickhouse-and-friends-merge-tree-disk-layout/
  • <<ClickHouse原理解析与应用实践>>
    分享大数据行业的一些前沿技术和手撕一些开源库的源代码
    微信公众号名称:技术茶馆
    微信公众号ID    :    Night_ZW

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/273256
推荐阅读
相关标签
  

闽ICP备14008679号