ClickHouse内幕（1）数据存储与过滤机制
内容提要
本文介绍了ClickHouse中的数据存储结构和索引结构，以及基于这些结构的数据过滤机制。
延伸解读
存储结构如何支撑高效过滤
ClickHouse的列式存储和稀疏索引设计，使得数据过滤可以逐层裁剪。每个Part内部，数据按主键排序并每8192行生成一个Mark，主键索引文件记录每个Mark的索引值。查询时，先通过分区键的最大最小值索引和分区表达式裁剪掉不相关的Part，再根据主键范围矩阵裁剪Mark，最终只读取必要的列数据。这种分层过滤机制大幅减少了I/O和计算量，是ClickHouse查询性能的关键。
KeyCondition与RPN：过滤条件的核心引擎
KeyCondition是ClickHouse过滤机制的核心组件，它通过逆波兰表达式（RPN）将过滤条件转换为可高效计算的表达式。RPN无需括号，利用栈结构即可完成计算，适合在过滤场景中快速判断范围矩阵是否满足条件。KeyCondition返回的BoolMask包含can_be_true和can_be_false两个布尔值，分别表示范围矩阵可能满足或可能不满足条件，从而支持Part裁剪和Mark裁剪。这种设计使得过滤条件能够灵活地应用于不同粒度的数据裁剪。
行过滤优化：Filter Mask与SIMD的权衡
在查询执行阶段，ClickHouse使用Filter Mask标记符合过滤条件的行，并利用SIMD指令集加速过滤。Filter Mask是一个UInt8数组，0表示不符合，1表示符合。过滤时按64个数据为一组，将byte mask转换为bit mask，根据全0、全1或混合情况分别处理。分组处理能利用数据局部有序性，减少分支预测失败，提高缓存命中率。但并非SIMD位宽越大越好，因为分组增大会降低全0或全1的概率，反而可能减少批量过滤的机会，需根据数据分布权衡。
Q&A
ClickHouse的数据存储结构是怎样的？
ClickHouse的数据存储采用分区和文件细分的方式，数据按分区键划分为多个分区，每个分区包含多个Part，Part是最小的存储单元。
ClickHouse如何实现数据过滤？
ClickHouse通过Part裁剪、Mark裁剪和Row过滤机制实现数据过滤，利用索引文件和SIMD技术优化查询性能。
什么是Part和Mark在ClickHouse中的作用？
Part是ClickHouse中最小的存储单元，Mark表示一组有序数据，二者在数据存储和索引结构中起到关键作用。
ClickHouse的Row过滤是如何优化的？
Row过滤使用Filter Mask和SIMD技术进行优化，通过分组处理提高过滤效率，减少CPU流水线的破坏。
ClickHouse的索引结构是如何构建的？
ClickHouse的索引结构通过对数据进行排序和形成稀疏索引来构建，使用Mark来表示数据的有序性。
在ClickHouse中，如何进行Part裁剪？
Part裁剪通过最大最小值索引和分区表达式进行，过滤掉不相关的Part，以提高查询效率。
