稀疏主键 — 键的顺序决定能跳过什么

一句话总结

MergeTree 的主索引记录的不是每一行，而是每个颗粒（默认 8192 行）第一行的一个键值。所以索引能做的事，只是筛掉“这个颗粒里不可能有要找的值”，而能筛掉多少，取决于排序键的列顺序和前面列的基数（取值的种类数）。

为什么需要它

行式数据库的 B 树指向每一行。几十亿行时，索引放不进内存，而分析查询反正要扫描几百万行，精确定位某一行的能力用处不大。ClickHouse 走了相反的路。它把磁盘上的行按排序键顺序排开，每 8192 行一组，只记录第一个键值。一张 200 万行的表，索引只有 245 个键值——压缩后的文件只有几百字节——所以始终可以放在内存里。

代价是精度。索引挑选的单位是颗粒，所以即使要找的行只有一行，也要读 8192 行。而且索引就是排序顺序本身，所以一张表只有一种排序顺序。有的查询会变快，有的查询则完全得不到帮助。本模块讲的就是如何用数字区分这个“有的”。在上一个模块所讲的“只有按排序键过滤才会跳过”的基础上再深入一步，看看用第二个键列过滤时会发生什么。

工作原理

把同样的 200 万行放进 ORDER BY (site, user_id) 和 ORDER BY (user_id, site) 两张表，并为 245 个颗粒中被选中的颗粒涂色的图。在第一张表中，按 site 过滤时，用二分查找选出 docs 那一段的 50 个颗粒；按 user_id 过滤时，每个站点段各选出一两个，共 9 个，用的是 generic exclusion search。在第二张表中，按 user_id 过滤选出 1 个，按 site 过滤则要读全部 245 个

ORDER BY (site, user_id) 的表先按 site 排序，在同一个 site 内再按 user_id 排序。如果有五个站点，磁盘上就会依次摆着五个站点段。给它加上 EXPLAIN indexes = 1，PrimaryKey 阶段就会告诉你它选了多少个颗粒。

PrimaryKey
  Keys: site
  Condition: (site in ['docs.example', 'docs.example'])
  Parts: 1/1
  Granules: 50/245
  Search Algorithm: binary search

用第一个键列过滤时是二分查找。索引是按第一列排序的，所以可以立刻找到 docs 开始的标记和结束的标记。如果只用第二列 user_id 过滤，情况就不同了。user_id 在每个站点段都从 0 重新开始，所以整体上并不是有序的。这时 ClickHouse 使用的是 generic exclusion search。查看相邻两个标记的键值，如果它们之间前面的列的值没有变化，后面列的范围就确定了，因此可以判定“这个区间里没有 4242”。前面的列发生变化的区间无法判定，就保留下来。官方指南的结论就是这个——该算法在前面键列的基数较低时才有效。在实验 Pod 中，user_id = 4242 在 245 个颗粒中选出了 9 个。

在把键顺序颠倒的 ORDER BY (user_id, site) 表中，结果也随之颠倒。user_id 现在是第一列，所以 1 个颗粒就够了。但按 site 过滤则是 245/245——全部读取。5 万个用户分布在 245 个颗粒上，每个颗粒里约有 200 个用户，相邻标记之间前面的列 user_id 几乎总是在变化，所以任何区间都无法排除。前面列的基数高时，后面的列作为索引就没有用处。

颗粒大小也是一个旋钮。用表设置 index_granularity = 1024 创建，标记会从 246 个增加到 1955 个，查找 user_id = 4242 时读取的行数从 73,728 减少到 9,216。代价是索引文件（system.parts 的 primary_key_size）变大。因为设计是把索引放在内存里，所以颗粒切得越细，占用的内存越多。

最后，PRIMARY KEY 与 ORDER BY 可以不同。可以按 (site, user_id, ts) 排序，而只让索引记录 (site, user_id)。MergeTree 文档的规则只有一条——主键必须是排序键的前缀。写成不是前缀的内容，表就创建不出来（“Primary key must be a prefix of the sorting key”）。在实验 Pod 中比较排序相同的两张表，主键文件从 1,620 字节减少到 647 字节。过滤时不用的靠后的列，只参与排序，不必进入索引。

还有一个陷阱。26.8 默认开启了查询条件缓存，所以同一个 WHERE 第二次运行时，会跳过“上次没有匹配行的颗粒”。user_id = 4242 的查询第一次读了 73,728 行，第二次读了 40,960 行。要衡量索引的能力，需要加上 --use_query_condition_cache 0 再测量。

在现场相遇的样子

经常听到这样的问题：“按 id 排了序，为什么按站点的报表还是慢？”答案通常是键顺序。把几乎总会出现在查询 WHERE 里的列放在前面，其中取值种类少的列放在前面，经常用来切范围的时间列放在它后面。如果是一天的站点报表，(site, ts) 比 (site, user_id) 能把读取的行数减少到几分之一——本模块实验的最后一步就是这个。

第二种常见情况，是为了“让所有查询都快”，把取值种类多的列先摆进键里。越靠后的列，要求前面的列在相邻标记之间保持相同的值才有用——上面 generic exclusion search 的规则会逐列叠加。过滤时不用的靠后的列，应该从索引中去掉，把 PRIMARY KEY 缩短为前缀；确实需要另一种排序的查询，则用后面模块的投影或物化视图来解决。

官方文档（Choosing a primary key）指出，排序键必须在创建表时确定，以后不能追加。要改变排序，就得新建一张表再迁移过去，所以创建之初先看几个代表性查询的 EXPLAIN，是最便宜的做法。

下一项实验要做什么

用 (site, user_id) 创建 sparse.hits 并写入 200 万行，把数据片段合并成一个。保存按 site 过滤和只按 user_id 过滤时的 EXPLAIN，记下选中的颗粒和查找方式，再在颠倒键顺序的表上测量两个查询的 rows_read。比较把颗粒缩小到 1024 行的表的标记数，以及单独设置 PRIMARY KEY 的表的索引大小，然后为一天的站点报表查询选出合适的排序键，把读取的行数减少到四分之一以下。