网站排名和什么有关,wordpress文章头图,上海优秀网站设计,深圳制作网站制作公司哪家好本文主要讲述ClickHouse中的数据存储结构#xff0c;包括文件组织结构和索引结构#xff0c;以及建立在其基础上的数据过滤机制#xff0c;从Part裁剪到Mark裁剪#xff0c;最后到基于SIMD的行过滤机制。
数据过滤机制实质上是构建在数据存储格式之上的算法#xff0c;所…本文主要讲述ClickHouse中的数据存储结构包括文件组织结构和索引结构以及建立在其基础上的数据过滤机制从Part裁剪到Mark裁剪最后到基于SIMD的行过滤机制。
数据过滤机制实质上是构建在数据存储格式之上的算法所以在介绍过滤机制前先介绍下ClickHouse中数据存储格式。
PS本文基于ClickHouse v24.1
一、数据存储的目录结构
ClickHouse数据存储在目录结构上采用大数据系统常见的分区然后分区内在进行细分文件的方式。
表中的数据首先按照分区键被划分为多个分区分区键常采用日期的方式比如下图中按照月份分区。每次数据批量插入形成一个最小的存储单元ClickHouse中称为PartPart归属于某一个分区。 ClickHouse中一个表的所有分区的所有Part放在同一个目录中Part所属的分区可以根据Part名进行区分Part的命名方式如下
partition-id _ min-id _ max-id _ level
Part目录内部文件组织形式如下
primary.idx - 是主键索引文件记录了每个Mark对应的主键索引值整个数据集一个.idx文件
[Column].mrk - 记录Mark(Mark在索引结构中介绍)对应的数据在数据文件.bin文件中的offset用于根据Mark定为到数据位置每个列一个.mrk文件。
[Column].bin - 真实数据文件每个列一个.bin文件
checksums.txt - part checksum文件用于校验数据完整性
columns.txt - 元数据记录列名以及数据类型
count.txt - 元数据记录该Part总行数可以用于加速count(*)查询
partition.dat - 分区表达式
minmax_[Column].idx - 某一个列的最大最小值可以用于加速查询分区键固定有一个最大最小索引用于分区裁剪
statistics_(column_name).stat - 列的统计信息用于查询加速
二、索引结构
每个part形成一个完整的索引结构整体上Clickhouse的存储是列式的每个列单独存储compact模式将多个文件合并成了一个但本质上是一样的。Clickhouse索引的大致思路是首先根据索引列将整个数据集进行排序这点类似MySQL的联合索引其次将排序后的数据每隔8192行选取出一行记录其索引值和序号并形成稀疏索引这个序号在Clickhouse中序号被称作Mark也就是说Mark表示一组数据。
下图是一个二维表date, city, action的索引结构其中date,city是索引列整个part文件的宏观结构如下 那么查询如何使用索引呢以下查询为例
select count(distinct action) where datetoDate(2020-01-01) and city’bj’
1.查找primary.idx并找到对应的Mark集合即数据block集合
2. 对于要读取的每个列根据.mrk文件定位到Mark对应在数据文件.bin中的数据offset
3.读取到对应的数据供后续计算
以上为宏观步骤下面会介绍其具体原理。
三、何时使用索引
在SQL编译阶段初始化执行Pipeline的时候ClickHouse会分析待查询的数据目标是解析出需要读取哪些Part的哪些Mark列表。解析结果如下所示的AnalysisResult。在真正执行的时候Scan算子直接读取这些Mark列表对应的数据。 struct AnalysisResult{RangesInDataParts parts_with_ranges; // 最终要扫描的Part列表以及每个Part的扫描范围rangeNames column_names_to_read; // 需要读取那些列// 以下是一些统计信息 UInt64 total_parts 0; // Parts总数UInt64 selected_parts 0; // 命中的Part数量UInt64 selected_ranges 0; // 命中的range数量UInt64 selected_marks 0; // 命中的marks总数UInt64 selected_rows 0; // 命中的marks包含的总数据行数};
关键堆栈
ReadFromMergeTree::selectRangesToRead
ReadFromMergeTree::getAnalysisResult()
ReadFromMergeTree::initializePipeline
QueryPlan::buildQueryPipeline
InterpreterSelectWithUnionQuery::execute()
executeQuery
四、KeyCondition原理
在介绍如何使用索引前先介绍下其核心算法。KeyCondition对外提供的语义是检查一个范围矩阵是否可以满足过滤条件。首先在构建KeyCondition的时候有两个必要参数一个是过滤条件语法树这是过滤的主体另一个是keys表示在判断是否满足的时候只关心这些列。然后当使用KeyCondition的时候用户需要传入一个keys范围矩阵来判断该范围矩阵是否满足过滤条件分。
范围矩阵是keys的范围数组比如c1,c2,c3三个主键列构成的一个范围矩阵可以是[[a, b], [1, 1], [x, x]]当用户进行Mark裁剪的时候会生成范围矩阵然后判断该范围矩阵是否满足条件。又比如常用的时间分区构成的一个范围矩阵可以是[[2023-11-22, 2023-11-22]]当用户进行分区裁剪的时候遍历每个分区构建范围矩阵然后判断该分区是否满足条件。
满足过滤条件分三种情况1范围矩阵中的数据全部满足过滤条件2部分满足3全部不满足。为表示以上三个语义ClickHouse设置了一个数据结构 {can_be_true, can_be_false}它的{true, false}、{true, true}、{false, true}三个值对应以上三种语义。
KeyCondition的核心是一个RPN表达式主要流程分成两个阶段1构建RPN即将过滤条件转换成RPN表达式2匹配匹配一个范围矩阵是否满足条件。RPN的优势是表达一个表达式的时候不需要括号在进行计算的时候使用栈在碰到操作符的时候从栈顶弹出操作数就可以完成整个表达式的计算。 通过类比能够更好的理解在过滤场景中如何使用RPN上图展示了RPN在四则运算法则和过滤两个场景中的使用情况另种场景中唯一的区别是结果类型不一样一个是number一个是BoolMask {can_be_true, can_be_false}。更多关于RPN请参考wiki。
四、如何使用索引
1. Part裁剪
Part裁剪的目的是一次性过滤整个Part文件只保留可能包含目标数据的Part。ClickHouse中的Part裁剪过程中会构建两个KeyCondition。其中一个被称为主要用于根据分区列的最大值和最小值进行Part过滤。minmax_idx_condition的keys为构成分区键对应的原始列比如分区键为toDate(date_time)那么它的key为date_time列后续进行过滤的时候传入的也是date_time对应的值组成的范围矩阵。下图展示了minmax_idx_condition的工作原理。 另一个被称为主要用于过滤分区。partition_pruner的key为分区表达式组成的列比如分区键为toDate(date_time)那么它的key为toDate(date_time)后续进行过滤的时候传入的是分区对应的值组成的范围矩阵。下图展示了partition_pruner的工作原理。 Part裁剪的主要逻辑位于MergeTreeDataSelectExecutor::selectPartsToRead大家可以自行参阅
for (size_t i 0; i prev_parts.size(); i)
{if (!minmax_idx_condition-checkInHyperrectangle( // 基于分区键的列的最大最小值索引进行Part裁剪part-minmax_idx-hyperrectangle, minmax_columns_types).can_be_true)continue;if (partition_pruner-canBePruned(*part)) // 基于分区表达式进行Part裁剪continue;parts.push_back(prev_parts[i]);
}
2. Mark裁剪
过滤完Part后会进一步进行Mark过滤首先回顾下什么是Mark在一个Part内部数据按照主键进行排序然后每隔8192行数据将数据进行分组这个分组id就被称为MarkMark表示一组按照主键有序的数据。
ClickHouse索引过滤的最小粒度就是Mark。下图展示了c1,c2,c3三个列组成主键的一个Part的数据结构以及Mark过滤的流程。 在Mark裁剪过程中输入的是一个MarkRange比如[2, 5]输出的是一系列的MarkRange那么如何使用KeyCondition呢
因为KeyCondition进行判断的时候输入的是主键列的范围矩阵所以需要先将MarkRange转换成范围矩阵。将MarkRange转换成范围矩阵相当于将多维空间的范围转换为一维空间的范围所以转换出来的范围矩阵有很多个这里不做过多讨论有兴趣可以参考方法。MarkRange [2, 5]转换成的一个范围矩阵为[[a, a], [1, 1], [z, inf]]下图展示了Mark裁剪的工作原理 至此我们过滤出来了一系列的mark同时数据存储结构和索引在过滤过程中的使命也完成了。接下来需要过滤每个mark中的Row。
六、Row过滤
Row过滤发生在查询执行阶段。ClickHouse中Row过滤也是按照batch的方式进行该batch在ClickHouse内部被称为Chunk它大小可能与Mark不同。ColumnVector::filter记录了数值类型的列过滤的主要逻辑其它列过滤思路大同小异。
1. 生成Filter Mask
首先对根据过滤条件给一个Chunk的数据生成一个Filter MaskFilter Mask是一个行数等于Chunk大小的UInt8数组数组中只有2个值其中0表示该行的数据不符合过滤条件1表示符合。 2. Filter column by Filter Mask
根据Filter Mask进行数据过滤过滤的过程中使用到了SIMD技术进行优化具体流程如下
首先将数据按照64个的粒度为一组按照组的粒度进行处理然后将byte mask转换成bit mask参考函数转换后的bit mask可以直接用一个UInt64表示。 对于每个分组按照数据分布的不同情况分别进行过滤
1如果bit_mask等于0也就是该分组的bit mask全0直接忽略该分组
2如果bit mask 全1将整个分组复制到结果集中
3[0][1]或者[1][0]将byte maskt中连续1的区间复制到结果集 3. Filter column by Filter Mask version 2
过滤部分ClickHouse提供了一个SIMD的版本使用AVX512指令集。依然将数据按照64个的粒度为一组按照组的粒度进行处理然后将byte mask转换成bit mask对于每个分组按照数据分布的不同情况分别处理
1如果bit mask 全0直接忽略该分组
2bit mask 全1将整个分组复制到结果集中使用向量化方法批量进行复制
_mm512_storeu_si512(reinterpret_cast(res_data[current_offset i]), _mm512_loadu_si512(reinterpret_cast(data_pos i)));
3其它情况使用向量化函数根据mask将数据拷贝到结果集中
4. 过滤结尾部分 5. Row过滤优化总结
1 为什么使用Filter Mask
1过滤多个列的时候可以复用Filter Mask2便于使用SIMD指令
2 为什么分组处理
因为ClickHouse数据按照主键排序很多情况下数据按照某些列局部有序过滤的时候可将整个分组过滤掉或者命中的概率比较大这样相比单个行的处理方式在处理过程中没有判断消除了分支预测失败的场景避免CPU执行流水线被破坏同时增大指令与数据缓存的命中率这也是过滤高性能的核心设计点。
3 是不是使用位宽越大的SIMD指令集越好比如AVX512一定快于SSE2
大多数场景下是的但是在过滤场景中不是的。因为增大位宽那么分组大小也会相应增大分组越大全零或者全一的概率越小那么过滤整个分组的概率越小所以需要看数据分布情况。
