【列存引擎内核】索引与跳数索引

ClickHouse 的 PRIMARY KEY 不是唯一约束——它是 稀疏排序索引，每 granule 一条，配合物理排序做 granule 剪枝。二级 Data Skipping Index 进一步跳过 granule，与 PG B-Tree 指针索引本质不同。

一、稀疏主键

primary.idx：granule \(i\) 存该行 ORDER BY 前缀键值。

查询 WHERE date >= '2024-01-01' AND date <= '2024-01-31' → 二分 primary.idx → Mark Range。

不能保证 WHERE id = 1 只读一行——可能读整个 granule（最多 index_granularity 行）。

flowchart TB
  PK[primary.idx 每 granule 1 键]
  PK --> R[Mark Range]
  R --> READ[读 granule 内所有行再 filter]

二、ORDER BY 与 PRIMARY KEY

PRIMARY KEY 必须是 ORDER BY 前缀；可 ORDER BY (a,b,c) PRIMARY KEY (a,b) 减少索引体积。

排序键选择决定 merge 归并顺序与剪枝效果——DDL 核心设计。

三、Data Skipping Index

ALTER TABLE t ADD INDEX idx_url url TYPE bloom_filter GRANULARITY 4;

GRANULARITY n：每 \(n\) 个 granule 一条索引项。文件 skp_idx_* .idx + .mrk2。

flowchart TB
  Q[WHERE url = ?] --> PK[primary.idx 剪枝]
  PK --> SK[bloom_filter 跳数索引]
  SK --> G1[Granule 跳过]
  SK --> G2[Granule 保留 → 读列]
  G2 --> MRK[Mark → .bin]

四、与 PG B-Tree 对照

五、设计建议

• PK 前缀放 高频范围过滤 列（日期、租户 id）
• 高基数等值辅助 bloom；低基数 set/minmax
• 错误索引几乎无剪枝还占空间

六、EXPLAIN indexes=1

与 第 5 篇 联用，查看 Skip 索引排除 granule 数。本环境无实例，不贴输出。

七、学术谱系：稀疏主键 · Zone Map · Skip Index

争论：多建 skip index 换剪枝 vs 索引维护与空间。错误索引「几乎无剪枝还占空间」（第五节）——与 Abadi「系统栈要完整」一致：索引必须服务真实谓词。

7.1 工程间隙

7.2 开放问题

1. Projection 与 skip index 职责如何划分？ 可检验：同查询只加 projection vs 只加 bloom 的 EXPLAIN indexes 与 parts 体积。
2. 自适应跳数索引（按查询历史推荐）——研究与产品都在演进，无统一标准。

八、小结

索引 = 减少 granule，不是 定位行。理解这一点可避免把 ClickHouse 当 OLTP 主库。

上一篇：Merge 与 Mutation

下一篇：ReplicatedMergeTree

参考资料

核心论文

1. Stonebraker et al., C-Store, VLDB 2005（排序投影；A 级）。
2. Abadi et al., FnT DB 2013 综述中的 zone-map / 段摘要坐标（A 级）。

规范 / 源码 / 文档

3. ClickHouse Documentation, Primary Keys、Data Skipping Indexes（A 级）。
4. PostgreSQL 系列, B-Tree（对照）。

稀疏主键 vs B-Tree

PG B-Tree 叶项指向 heap tuple（14-btree）；CH primary.idx 每 granule 一条，不指向行，只用于 granule 范围剪枝。

跳数索引类型

定义在 INDEX idx_name expr TYPE ... GRANULARITY g；GRANULARITY 表示每多少个 granule 写一条索引项。

Mark Range 算法（概念）

对每个 Part：

1. 用 primary.idx 二分/扫描，找与 PK 谓词相交的 granule 下标区间 \([g_{lo}, g_{hi}]\)。
2. 跳数索引进一步缩小区间（第 7 篇）。
3. 对每列 Mark 文件取 \([g_{lo}, g_{hi}]\) 对应压缩块并解压。
4. PREWHERE 列优先读，结果位图过滤后再读其余列（若优化器下推）。

PREWHERE 语义

PREWHERE 不是语法糖：优化器将选择性高的条件移到存储层，减少列 IO。官方建议高选择性条件放 PREWHERE；WHERE 其余 predicate 在内存 Block 上执行。

并行

• Part 级：MergeTreeReadPool 分配 Part 给线程。
• Granule 级：Mark Range 切分。
• max_threads 与 max_streams_to_max_threads_ratio 共同约束。