ClickHouse优化（译） -- 跳数索引

原文

理解 ClickHouse 跳数索引

跳数索引简介

许多因素都会影响 ClickHouse 的查询性能。大多数场景下的关键因素是判断 ClickHouse 在查询时在WHERE 子句条件中是否可以使用主键。因此，选择适用于最常见查询模式的主键对于高效的表设计至关重要。

尽管如此，无论主键如何精心调优，都难免会出现无法使用主键的查询用例。用户通常依赖 ClickHouse 获取时间序列类型的数据，但他们通常希望根据其他业务维度分析相同的数据，例如客户 ID、网站 URL 或产品编号。在这种情况下，查询性能可能会相当差，因为可能需要对每个列值进行完整的扫描才能应用 WHERE 子句条件。虽然 ClickHouse 在这些情况下仍然相对较快，但评估数百万或数十亿个单独的值将导致“无索引”查询的执行速度比基于主键的查询慢得多。

在传统关系型数据库中，解决此问题的一种方法是将一个或多个“辅助”索引添加到表中。这是一种 b-tree数据结构，它允许数据库以 O(log(n)) 而不是 O(n)（全表扫描） 时间复杂度中找到磁盘上的所有匹配行，其中 n 是行数。但是这种类型的辅助索引不适用于 ClickHouse（或其他列式数据库），因为磁盘上没有单独的行可以添加到索引中。

相反，ClickHouse 提供了一种在特定情况下可以显著提高查询速度的与众不同的索引。这种结构被命名为“跳数”索引，因为它们使 ClickHouse 能够跳过读取确定没有匹配值的重要数据块。

基本操作

用户只能在 MergeTree 表系列上使用跳数索引。每个索引数据都有四个主要参数：

• 索引名称。索引名称用于在每个分区中创建索引文件。此外，在删除或应用索引时需要它作为参数。
• 索引表达式。索引表达式用于计算存储在索引中的集合值。它可以是列、简单运算符和且/或组成的由索引类型确定的函数的子集。
• 类型。索引的类型控制确定是否可以跳过读取和评估每个索引块的计算量。
• 粒度。每个索引块由 GRANULARITY 粒度组成。例如，如果表主键的粒度为 8192 行，并且索引粒度为 4，则每个索引的“块”将为 32768 行。

当用户创建跳数索引时，表的每个分区目录中都会创建两个附加文件。

• skpidx{index_name}.idx，其中包含有序的表达式值）
• skpidx{index_name}.mrk2，其中包含相关数据列文件的相应偏移量。

如果 WHERE 子句的部分过滤条件在执行查询和读取相关列文件时与跳数索引表达式匹配时，ClickHouse 将使用索引文件数据来确定每个相关数据块是否必须处理或可以绕过（假设该块尚未被主键排除）。使用下表加载可测试的数据， 测试一个简单的示例。

CREATE TABLE skip_table
(
  my_key UInt64,
  my_value UInt64
)
ENGINE MergeTree primary key my_key
SETTINGS index_granularity=8192;

INSERT INTO skip_table SELECT number, intDiv(number,4096) FROM numbers(100000000);

在执行不使用主键的简单查询时，my_value 会扫描列中的所有 1 亿条数据：

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.079 sec. Processed 100.00 million rows, 800.10 MB (1.26 billion rows/s., 10.10 GB/s.

现在添加一个非常基本的跳数索引：

ALTER TABLE skip_table ADD INDEX vix my_value TYPE set(100) GRANULARITY 2;

通常跳数索引只应用于新插入的数据，所以只添加索引不会影响上面的查询。

要使索引应用到现有数据，请使用以下语句：

ALTER TABLE skip_table MATERIALIZE INDEX vix;

使用新创建的索引重新运行查询：

SELECT * FROM skip_table WHERE my_value IN (125, 700)

┌─my_key─┬─my_value─┐
│ 512000 │      125 │
│ 512001 │      125 │
│    ... |      ... |
└────────┴──────────┘

8192 rows in set. Elapsed: 0.051 sec. Processed 32.77 thousand rows, 360.45 KB (643.75 thousand rows/s., 7.08 MB/s.)

ClickHouse 没有处理800 M的1亿行数据，而是只读取分析了360 KB 的 32768 行数据——四个粒度，每个粒度 8192 行。

在更直观的表现中，这是my_value如何读取和选择 a 为 125 的 4096 行的方式，以及在不从磁盘读取的情况下如何跳过以下行：

用户可以通过在执行查询时启用跟踪，来记录有关跳数索引使用情况的详细信息。在 clickhouse-client 中，设置 send_logs_level：

SET send_logs_level='trace';

这将在尝试优化查询SQL 和表索引时提供有用的调试信息。在上面的示例中，调试日志显示了跳数索引跳过了除两个粒度数据之外的所有粒度数据：

 default.skip_table (933d4b2c-8cea-4bf9-8c93-c56e900eefd1) (SelectExecutor): Index `vix` has dropped 6102/6104 granules.

跳数索引类型

minmax

这种轻量级索引类型不需要参数。它存储每个块的索引表达式的最小值和最大值（如果表达式是元组，它单独存储元组元素的每个成员的值）。这种类型非常适合按值松散排序的列。这种索引类型通常在查询处理期间处理成本最低。

这种类型的索引仅适用于标量或元组表达式——索引永远不会应用于返回数组或map数据类型的表达式。

set

这种轻量级索引类型接受每个块设置的值的 max_size 的单个参数（0 允许无限数量的离散值）。此集合包含块中的所有值（如果值的数量超过 max_size，则为空）。这种索引类型适用于每组粒度中基数较低的列（本质上是“聚集在一起”），但总体上基数较高。

该索引的成本、性能和有效性取决于块内的基数。如果每个块都包含大量的唯一值，要么针对大型索引集查询条件成本非常大，要么由于超过 max_size 导致索引为空而不会应用索引。

布隆过滤器

布隆过滤器是一种数据结构，它允许以少量误差为代价对集合成员进行节省空间。在跳数索引的情况下，误差不是一个重要的考虑因素，因为唯一的缺点是读取了一些不必要的块。但是，可能存在的误差确实意味着索引表达式应该是正确的，否则可能会跳过有效数据。

由于布隆过滤器可以更有效地处理大量离散值的数据，所以它们适用于产生大量值的条件表达式。尤其是通过使用 mapKeys 或 mapValues 函数将键或值转换为数组，可以将布隆过滤器索引应用于数组（其中测试数组的每个值）和maps。

基于布隆过滤器的数据跳数索引类型共有三种：

• 基本的bloom_filter，它使用0到1之间允许的“误差”率的单个可选参数（如果未指定，则使用0.025）。

• 专门的tokenbf_v1。它需要三个参数，所有参数都与调整使用的布隆过滤器有关：（1）过滤器的大小（以字节为单位）（较大的过滤器要具有较小的误差，需要在存储方面有一定的消耗），（2）应用的哈希函数的数量（同样，更多的哈希函数能减少误差），以及（3）布隆过滤器哈希函数的seed。有关这些参数如何影响布隆过滤器功能的更多详细信息，请参阅此处的计算公式。此索引仅适用于 String、FixedString 和 Map 数据类型。输入表达式被拆分为由非字母数字字符分隔的字符序列。例如，列值This is a candidate for a "full text" search将包含序列This is a candidate for full text search. 它旨在用于 LIKE、EQUALS、IN、hasToken() 和类似搜索中较长字符串中的单词和其他值。例如，一种可能的用途可能是在一列自由格式的应用程序日志行中搜索少量的类名或行号。

• 专门的ngrambf_v1。该索引的功能与tokenbf_v1索引相同。它在布隆过滤器设置之前需要一个额外参数，即索引的 ngram 的大小。ngram 是长度为n的字符串的任意子串，因此大小为4的ngram的字符串A short string将被索引为：

  'A sh', ' sho', 'shor', 'hort', 'ort ', 'rt s', 't st', ' str', 'stri', 'trin', 'ring'

  此索引还可用于文本搜索，尤其是没有分词的语言，例如中文。

跳数索引函数

跳数索引的核心目的是限制常用查询分析的数据量。鉴于 ClickHouse 数据的分析性质，在大多数情况下，这些查询的模式包括函数表达式。因此，跳数索引必须与常用函数正确交互才能有效。这可能在以下情况下发生：

• 插入数据并将索引定义为函数表达式（表达式的结果存储在索引文件中），或者

• 处理查询并将表达式应用于存储的索引值以确定是否排除该块。

每种类型的跳数索引都适用于此处列出的索引实现的可用 ClickHouse 函数的子集 。通常，集合索引和基于布隆过滤器的索引（另一种集合索引）都是无序的，因此不适用于范围。相反，由于确定范围是否相交非常快，因此 minmax 索引在确定范围上应用得特别好。部分匹配函数 LIKE、startsWith、endsWith 和 hasToken 的功能取决于使用的索引类型、索引表达式和数据特征。

跳数索引设置

两个适用于跳数索引的可用设置。

• use_skip_indexes （0 或 1，默认为 1）。并非所有查询都可以有效地使用跳数索引。如果一个特定的过滤条件可能包括大多数粒度，则不必要应用跳数索引，有时甚至是巨大的成本。对于不太可能从任何跳数索引中受益的查询，请将该值设置为 0。
• force_data_skipping_indexes（以逗号分隔的索引名称列表）。此设置可用于防止某些类型的低效查询。在查询表除非使用跳数索引， 否则过于笨重的情况下，将此设置一个或多个索引名称，将在不使用列出的索引的任何查询情况下返回异常。这将防止编写不佳的查询消耗服务器资源。

跳数索引最佳实践

跳过索引并不直观，特别是对于习惯于使用 RDMS 领域中的基于行的二级索引或文档存储中的反向索引的用户而言。为了获得任何优化，应用 ClickHouse跳数索引必须避免足够的粒度读取来抵消计算索引的成本。至关重要的是，如果一个值在索引块中出现一次，则意味着必须将整个块读入内存进行计算，并且不必要地产生了索引成本。

考虑以下数据分布：

假设主键/排序键是timestamp，并且在visitor_id上有一个索引。考虑以下查询：

SELECT timestamp, url FROM table WHERE visitor_id = 1001

对于这种数据分布，传统的二级索引将非常有利。二级索引不会读取所有 32678 行来查找满足请求的 visitor_id 的 5 行，而是仅包含五个行位置，并且只会从磁盘读取这五行。对于 ClickHouse 跳数索引，情况正好相反。visitor_id无论跳过索引的类型如何，都将扫描列中的所有 32678 个值。

因此，通过简单地向关键列添加索引来尝试优化ClickHouse 查询的想法通常是不正确的。此高级功能仅应在调查其他替代方案后使用，例如修改主键（参考如何选择主键）、使用投影或使用物化视图。即使跳数索引是合适的，通常也需要仔细调整索引和表。

在大多数情况下，有用的跳数索引需要主键和目标非主键列/表达式之间的强相关性。如果没有相关性（如上图），则几千个值的块中至少有一行满足过滤条件的几率很高，导致跳过少数块。相反，如果主键的值范围（如一天中的时间）与潜在索引列中的值（如电视观众年龄）密切相关，那么 minmax 类型的索引可能是有益的。请注意，在插入数据时可能会增加这种相关性，方法是在排序/ORDER BY 键中包含其他列，或者以与主键关联的值在插入时分组的方式批量插入。例如，即使主键是包含来自大量站点的事件的时间戳，也可以将特定 site_id 的所有事件分组并写入到一起。这将导致许多粒度仅包含几个站点 ID，因此在按特定 site_id 值搜索时可能会跳过许多块。

跳数索引的另一个很好的应用场景是高基数表达式，其中任何一个值在数据中都相对稀疏。一个示例是跟踪 API 请求中的错误代码的可观察性平台。某些错误代码虽然在数据中很少见，但对于搜索可能特别重要。在 error_code 列上设置跳数索引将允许绕过绝大多数不包含错误的块，从而显着改善以错误为中心的查询。

最后，关键的最佳实践是测试、测试和再次测试。同样，与用于搜索文档的 b-tree 二级索引或反向索引不同，跳数索引行为不易预测。将它们添加到表中会在数据摄取和由于多种原因而无法从索引中受益的查询上产生巨大的成本。它们应该始终在线上环境的数据上进行测试，并且测试应该包括类型、粒度大小和其他参数的变化。测试通常会揭示仅从猜想实验中看不到的不明显模式和陷阱。