深入了解clickhouse的索引查询过程

关于Clickhouse的索引的查询过程，我们先手来了解几个概念，MarkRange：在ClickHouse中是用于定义标记区间的对象。index_granularity：标记多个小的区间数据组成的粒度。MergeTree按照index_granularity的间隔粒度，将一段完整的数据划分成了多个小的间隔数据段，一个具体的数据段即是一个MarkRange。MarkRange与索引编号对应，使用start和end两个属性表示其区间范围。通过与start及end对应的索引编号的取值，即能够得到它所对应的数值区间。而数值区间表示了此MarkRange包含的数据范围。

举个例子：

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

根据索引数据，MergeTree会将此数据片段划分成192/3=64个小的MarkRange，两个相邻MarkRange相距的步长为1。其中，所有MarkRange（整个数据片段）的最大数值区间为[A000,+inf)，其如下图：

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

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

1：生成查询条件区间：首先，将查询条件转换为条件区间。即便是单个值的查询条件，也会被转换成区间的形式。

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

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

3：合并MarkRange区间：将最终匹配的MarkRange聚在一起，合并它们的范围。

最后我们看一下完整的逻辑示意图：