跳到主要内容
跳到主要内容

ClickHouse 主索引的实用介绍

引言

在本指南中,我们将深入探讨 ClickHouse 的索引。我们将详细说明和讨论:

您可以选择在自己的计算机上执行本指南中给出的所有 ClickHouse SQL 语句和查询。 有关安装 ClickHouse 和入门的说明,请参见 快速入门

备注

本指南重点介绍 ClickHouse 的稀疏主索引。

有关 ClickHouse 二级数据跳过索引,请参阅 教程

数据集

在本指南中,我们将使用一组匿名的网络流量数据集作为示例。

  • 我们将使用示例数据集中的 8.87 百万行(事件)的子集。
  • 解压缩后的数据大小为 8.87 百万事件,约 700 MB。在 ClickHouse 中存储时压缩为 200 MB。
  • 在我们的子集中,每行包含三个列,分别表示在特定时间点击了 URL 的互联网用户(UserID 列)、URL 列和 EventTime 列。

有了这三列,我们可以制定一些典型的网络分析查询,比如:

  • “特定用户的前 10 个点击量最高的 URL 是哪些?”
  • “点击特定 URL 最频繁的前 10 个用户是谁?”
  • “用户点击特定 URL 的最受欢迎的时间(例如,星期几)是什么时候?”

测试机器

本文档中给出的所有运行时数据都基于在配备 Apple M1 Pro 芯片和 16GB RAM 的 MacBook Pro 上本地运行 ClickHouse 22.2.1。

完整表扫描

为了查看在没有主键的情况下查询如何在我们的数据集上执行,我们通过执行以下 SQL DDL 语句创建一个表(使用 MergeTree 表引擎):

接下来,通过以下 SQL 插入语句将部分点击数据插入到表中。 这使用了 URL 表函数 来加载存储在 clickhouse.com 上的完整数据集的一个子集:

响应为:

ClickHouse 客户端的结果输出显示,上述语句将 8.87 百万行插入了该表。

最后,为了简化本指南后续讨论,并使图表和结果可重复,我们使用 FINAL 关键字对表进行 优化

备注

通常在将数据加载到表中后,不需要也不推荐立即优化表。 本示例为何需要这样做将变得明显。

现在我们执行第一个网络分析查询。以下查询计算了互联网用户 UserID 为 749927693 的点击量前 10 的 URL:

响应是:

ClickHouse 客户端的结果输出表明 ClickHouse 执行了完整的表扫描!我们表中的 8.87 百万行的每一行都被流入了 ClickHouse。这无法扩展。

为了使这一过程(更)高效且(大幅)加快速度,我们需要使用一个具有适当主键的表。这将使 ClickHouse 自动(基于主键的列)创建一个稀疏主索引,从而显著加快我们示例查询的执行速度。

ClickHouse 索引设计

为大规模数据设计索引

在传统的关系数据库管理系统中,主索引会为每个表行包含一个条目。这将导致我们的数据集的主索引包含 8.87 百万条目。这种索引允许快速定位特定行,从而在查找查询和点更新中实现高效率。在 B(+)-Tree 数据结构中查找一个条目的平均时间复杂度为 O(log n);更精确地说,log_b n = log_2 n / log_2 b,其中 bB(+)-Tree 的分支因子,n 是被索引行的数量。由于 b 通常在几百到几千之间,因此 B(+)-Trees 是非常浅的结构,定位记录所需的磁盘寻址较少。在 8.87 百万行和分支因子为 1000 的情况下,平均需要 2.3 次磁盘寻址。这个能力是有代价的:额外的磁盘和内存开销,在向表中添加新行和将条目添加到索引时更高的插入成本,有时还需要对 B-Tree 进行重新平衡。

考虑到 B-Tree 索引相关的挑战,ClickHouse 中的表引擎采用了不同的方法。ClickHouse MergeTree 引擎系列 被设计并优化以处理大规模的数据量。这些表被设计为每秒接收数百万行插入,并存储非常大的数据量(数百 PB)。数据快速写入表中 逐部分,在后台应用合并部分的规则。在 ClickHouse 中,每个部分都有自己的主索引。当部分被合并时,合并部分的主索引也会被合并。在 ClickHouse 所针对的巨大规模下,盘存和内存效率非常重要。因此,主索引为每个部分在一组行(称为“granule”)中只有一个索引条目(称为“mark”)——这种技术称为 稀疏索引

稀疏索引之所以可行,是因为 ClickHouse 将每个部分的行在磁盘上按主键列的顺序存储。稀疏主索引允许它快速(通过对索引条目进行二分查找)识别可能匹配查询的行组,而不是直接定位单行。找到的可能匹配的行(granules)随后被并行流入 ClickHouse 引擎,以便查找匹配项。这种索引设计使主索引小(可以完全适应主内存),同时显著加快查询执行时间:尤其是对于数据分析用例中典型的范围查询。

以下详细说明了 ClickHouse 如何构建和使用其稀疏主索引。稍后在本文中,我们将讨论一些选择、删除和排序用于构建索引(主键列)的表列的最佳实践。

带主键的表

创建一个具有复合主键的表,关键列为 UserID 和 URL:

DDL 语句详情

为了简化本指南后面的讨论,并使图表和结果可重现,DDL 语句:

  • 通过 ORDER BY 子句指定表的复合排序键。

  • 通过设置显式控制主索引将包含多少索引条目:

    • index_granularity: 显式设置为其默认值 8192。这意味着,对于每组 8192 行,主索引将有一个索引条目。例如,如果表包含 16384 行,则该索引将有两个索引条目。

    • index_granularity_bytes: 设置为 0,以禁用 自适应索引粒度。自适应索引粒度意味着 ClickHouse 会自动为一组 n 行创建一个索引条目,如果以下任一条件为真:

      • 如果 n 小于 8192,且该 n 行的组合行数据大小大于或等于 10 MB(index_granularity_bytes 的默认值)。

      • 如果 n 行的组合行数据大小小于 10 MB,但 n 为 8192。

    • compress_primary_key: 设置为 0 以禁用 主索引的压缩。这将使我们在以后可以选择查看其内容。

DDL 语句中的主键会根据指定的两个关键列创建主索引。


接下来插入数据:

响应如下:


并优化表:


我们可以使用以下查询来获取有关我们表的元数据:

响应为:

ClickHouse 客户端的输出显示:

  • 表的数据以 宽格式 存储在磁盘的特定目录中,这意味着该目录内每个表列都有一个数据文件(和一个标记文件)。
  • 表包含 8.87 百万行。
  • 所有行的未压缩数据大小为 733.28 MB。
  • 所有行在磁盘上的压缩大小为 206.94 MB。
  • 表有一个主索引,包含 1083 个条目(称为“marks”),索引大小为 96.93 KB。
  • 总之,表的数据文件、标记文件和主索引文件在磁盘上共占用 207.07 MB。

数据在磁盘上按主键列(和附加列)排序存储

我们上面创建的表具有

  • 复合 主键 (UserID, URL)
  • 复合 排序键 (UserID, URL, EventTime)
备注
  • 如果我们仅指定了排序键,则主键将被隐式地定义为等于排序键。

  • 为了节省内存,我们显式指定了仅包含我们查询过滤的列的主键。基于主键的主索引被完全加载到主内存中。

  • 为了在本指南的图表中保持一致性,并最大化压缩比,我们定义了一个单独的排序键,并包含了我们表的所有列(如果在相似数据的列中将数据放置得相对紧密,例如通过排序,那么该数据将得到更好的压缩)。

  • 如果同时指定了主键,则主键必须是排序键的前缀。

插入的行按主键列(和排序键的附加 EventTime 列)的字典顺序(升序)存储在磁盘上。

备注

ClickHouse 允许插入具有相同主键列值的多行。在这种情况下(参见下方图表中的第 1 行和第 2 行),最终顺序由指定的排序键确定,因此取决于 EventTime 列的值。

ClickHouse 是一个 列式数据库管理系统。如下图所示

  • 在磁盘上的表示中,每个表列都有一个单独的数据文件 (*.bin),其中存储该列的所有值,并采用 压缩 格式,并且
  • 8.87 百万行在磁盘上按主键列(和附加排序键列)的字典升序存储,即在这种情况下
    • 首先按 UserID,
    • 然后按 URL,
    • 最后按 EventTime:

UserID.bin, URL.bin, 和 EventTime.bin 是磁盘上的数据文件,存储 UserIDURLEventTime 列的值。

备注
  • 由于主键定义了行在磁盘上的字典顺序,因此一个表只能有一个主键。

  • 我们从 0 开始编号行,以便与 ClickHouse 内部行编号方案对齐,该方案也用于记录消息。

将数据组织到 granules 中以进行并行数据处理

出于数据处理的目的,表的列值在逻辑上分成 granules。 granule 是流入 ClickHouse 进行数据处理的最小不可分割数据集。 这意味着 ClickHouse 始终以流式方式(并行)读取一整组行(granule),而不是单独读取个别行。

备注

列值不是物理存储在 granules 中:granules 只是用于查询处理的列值的逻辑组织形式。

下图显示了我们表的 8.87 百万行(列值)如何被组织为 1083 个 granule,作为表的 DDL 语句中包含设置 index_granularity(默认值为 8192)的结果。

基于在磁盘上的物理顺序,前 8192 行(它们的列值)逻辑上归属于 granule 0,然后下 8192 行(它们的列值)归属于 granule 1,依此类推。

备注
  • 最后一个 granule(granule 1082)“包含”少于 8192 行。

  • 我们在本指南开头的“DDL 语句详情”中提到,我们禁用了 自适应索引粒度(为了简化本指南中的讨论,并使图表和结果可重复)。

    因此,我们示例表的所有 granule(最后一个除外)的大小都是相同的。

  • 对于具有自适应索引粒度的表(索引粒度是 默认自适应的),某些 granule 的大小可能小于 8192 行,具体取决于行数据的大小。

  • 我们用橙色标记了一些来自主键列的列值 (UserID, URL)。 这些橙色标记的列值是在每个 granule 的每第一行的主键列值。 正如我们将在下面看到的,这些橙色标记的列值将是表的主索引中的条目。

  • 我们从 0 开始编号 granules,以便与 ClickHouse 内部的编号方案对齐,该方案也用于记录消息。

主索引每个 granule 有一个条目

主索引是根据上面图表中显示的 granules 创建的。该索引是一个未压缩的平面数组文件(primary.idx),包含所谓的从 0 开始的数值索引标记。

下图显示索引存储了每个 granule 的第一行的主键列值(在上面的图中用橙色标记的值)。 换句话说:主索引存储来自表中每第 8192 行的主键列的值(基于主键列定义的物理行顺序)。 例如:

  • 第一个索引条目(下图中的“mark 0”)存储来自上面图表中 granule 0 第一行的关键列值,
  • 第二个索引条目(下图中的“mark 1”)存储来自上面图表中 granule 1 第一行的关键列值,依此类推。

总的来说,该索引对于我们的表具有 8.87 百万行和 1083 个 granules,有 1083 个条目:

备注
  • 对于具有 自适应索引粒度 的表,主索引中还会存储一个“最终”的附加标记,用于记录最后一行的主键列值,但由于我们禁用了自适应索引粒度(为了简化本指南中的讨论,并使图表和结果可重复),因此我们示例表的索引不包括此最终标记。

  • 主索引文件完全加载到主内存中。如果文件大于可用的空闲内存,则 ClickHouse 会引发错误。

检查主索引的内容

在自管理的 ClickHouse 集群上,我们可以使用 file 表函数 检查我们示例表的主索引内容。

为此,我们首先需要将主索引文件复制到正在运行的集群中的节点的 user_files_path

  • 步骤 1:获取包含主索引文件的部分路径
  • SELECT path FROM system.parts WHERE table = 'hits_UserID_URL' AND active = 1

    返回 /Users/tomschreiber/Clickhouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4 在测试机器上。

  • 步骤 2:获取 user_files_path
  • 在 Linux 上 默认 user_files_path/var/lib/clickhouse/user_files/

    您可以在 Linux 上检查是否有所更改:$ grep user_files_path /etc/clickhouse-server/config.xml

    在测试机器上,路径是 /Users/tomschreiber/Clickhouse/user_files/

  • 步骤 3:将主索引文件复制到 user_files_path
  • cp /Users/tomschreiber/Clickhouse/store/85f/85f4ee68-6e28-4f08-98b1-7d8affa1d88c/all_1_9_4/primary.idx /Users/tomschreiber/Clickhouse/user_files/primary-hits_UserID_URL.idx


现在我们可以通过 SQL 检查主索引的内容:

  • 获取条目数量
  • SELECT count( )<br/>FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String'); 返回 1083

  • 获取前两个索引标记
  • SELECT UserID, URL<br/>FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')<br/>LIMIT 0, 2;

    返回

    240923, http://showtopics.html%3...<br/> 4073710, http://mk.ru&pos=3_0

  • 获取最后一个索引标记
  • SELECT UserID, URL FROM file('primary-hits_UserID_URL.idx', 'RowBinary', 'UserID UInt32, URL String')<br/>LIMIT 1082, 1; 返回 4292714039 │ http://sosyal-mansetleri...


这与我们示例表的主索引内容的图表完全匹配:

主键条目称为索引标记,因为每个索引条目标记着特定数据范围的开始。针对示例表:

  • UserID 索引标记:

    存储在主索引中的 UserID 值按升序排序。
    因此,上述图表中的“mark 1”表示在 granule 1 及所有后续 granule 中,所有表行的 UserID 值均保证大于或等于 4,073,710。

稍后我们将看到,这种全局顺序使 ClickHouse 能够 在查询过滤主键的第一列时对索引标记执行二分查找算法

  • URL 索引标记:

    主键列 UserIDURL 的基数相似,通常意味着所有键列的索引标记仅在前驱键列值保持一致时,才表示数据范围。 例如,由于上面图表中标记 0 和标记 1 的 UserID 值不同,ClickHouse 无法假设在 granule 0 中所有表行的 URL 值都大于或等于 'http://showtopics.html%3...'。但是,如果上面图表中标记 0 和标记 1 的 UserID 值相同(这意味着 UserID 值在 granule 0 中的所有表行保持不变),ClickHouse 可假设在 granule 0 中所有表行的 URL 值都大于或等于 'http://showtopics.html%3...'

    我们稍后将详细讨论这一点对查询执行性能的影响。

主索引用于选择 granules

现在我们可以在主索引的支持下执行我们的查询。

以下查询计算了 UserID 为 749927693 的点击量前 10 的 URL。

响应是:

ClickHouse 客户端的输出现在显示,取而代之的是进行完整表扫描,仅流入 ClickHouse 的行数为 8,190。

如果 启用了跟踪日志,则 ClickHouse 服务器日志文件显示 ClickHouse 正在对 1083 个 UserID 索引标记执行 二分查找,以识别可能包含 UserID 列值为 749927693 的行的 granules。这需要 19 步,平均时间复杂度为 O(log2 n)

我们可以在上面的跟踪日志中看到,现存的 1083 个标记中有一个标记满足查询条件。

跟踪日志详情

标记 176 被识别(“找到的左边界标记”是含有的,“找到的右边界标记”是不含有的),因此 granule 176 的所有 8192 行(开始于行 1,441,792 - 我们将在本指南后面看到)被流入 ClickHouse,以找到 UserID 列值为 749927693 的实际行。

我们还可以通过在示例查询中使用 EXPLAIN 子句 来重现此过程:

响应如下:

客户端输出显示,选择了 1083 个 granules 中的一个,可能包含 UserID 列值为 749927693 的行。

结论

当查询过滤的列是复合键的一部分并且是第一个键列时,ClickHouse 将在关键列的索引标记上运行二分查找算法。


如上所述,ClickHouse 使用其稀疏主索引快速(通过二分查找)选择可能包含与查询匹配的行的 granules。

这是 ClickHouse 查询执行的 第一阶段(granule 选择)

第二阶段(数据读取) 中,ClickHouse 定位所选的 granules,以便将其所有行流入 ClickHouse 引擎,以找到与查询实际匹配的行。

我们将在以下部分中更详细地讨论第二阶段。

标记文件用于定位分片

下图展示了我们表的主索引文件的一部分。

如上所述,通过对索引中1083个UserID标记进行二叉搜索,标记176被识别。因此,其对应的分片176可能包含UserID列值为749.927.693的行。

分片选择详细信息

上面的图示表明,标记176是第一个索引条目,其中与分片176相关的最小UserID值小于749.927.693,而标记177的下一个分片(分片177)的最小UserID值大于该值。因此,只有与标记176对应的分片176可能包含UserID列值为749.927.693的行。

为了确认(或否认)分片176中的某些行是否包含UserID列值为749.927.693,必须将属于该分片的所有8192行传输到ClickHouse中。

为此,ClickHouse需要知道分片176的物理位置。

在ClickHouse中,我们表的所有分片的物理位置存储在标记文件中。与数据文件类似,每个表列都有一个标记文件。

以下图示展示了存储表的UserID、URL和EventTime列的分片物理位置的三个标记文件UserID.mrkURL.mrkEventTime.mrk

我们讨论了主索引是一个平坦的未压缩数组文件(primary.idx),包含从0开始编号的索引标记。

类似地,标记文件也是一个平坦的未压缩数组文件(*.mrk),包含从0开始编号的标记。

一旦ClickHouse识别并选择了可能包含查询匹配行的分片的索引标记,就可以在标记文件中执行位置数组查找,以获取该分片的物理位置。

特定列的每个标记文件条目存储两个位置,形式为偏移量:

  • 第一个偏移量(上图中的“block_offset”)定位于包含所选分片压缩版本的,该压缩列数据文件潜在地包含几个压缩的分片。定位的压缩文件块在读取时解压到主内存中。

  • 第二个偏移量(上图中的“granule_offset”)来自标记文件,提供了分片在未压缩块数据中的位置。

然后,将属于定位的未压缩分片的所有8192行传输到ClickHouse进行进一步处理。

备注
  • 对于具有宽格式且没有自适应索引粒度的表,ClickHouse使用如上所示的.mrk标记文件,包含每个条目的两个8字节长地址。这些条目是物理位置,所有位置的分片都具有相同的大小。

索引粒度是默认自适应的,但为了简化本指南中的讨论,并使图例和结果可重现,我们对示例表禁用了自适应索引粒度。我们的表使用宽格式,因为数据的大小大于min_bytes_for_wide_part(默认情况下自管理集群为10 MB)。

  • 对于具有宽格式且具有自适应索引粒度的表,ClickHouse使用.mrk2标记文件,它包含与.mrk标记文件相似的条目,但每个条目有一个额外的第三个值:与当前条目相关的分片的行数。

  • 对于紧凑格式的表,ClickHouse使用.mrk3标记文件。

为什么使用标记文件

为什么主索引不直接包含与索引标记相对应的分片的物理位置?

因为在ClickHouse设计的非常大规模下,重要的是要非常高效地使用磁盘和内存。

主索引文件需要适合主内存。

对于我们的示例查询,ClickHouse使用主索引并选择一个可能包含与我们的查询匹配的行的单个分片。仅对于那个分片,ClickHouse才需要物理位置来传输相应的行以进行进一步处理。

此外,仅UserID和URL列需要这些偏移信息。

对于在查询中未使用的列,例如EventTime,不需要偏移信息。

对于我们的示例查询,ClickHouse仅需要UserID数据文件(UserID.bin)中分片176的两个物理位置偏移量和URL数据文件(URL.bin)中分片176的两个物理位置偏移量。

标记文件提供的间接性避免了在主索引中直接存储所有三个列的1083个分片的物理位置条目,从而避免在主内存中存放不必要(可能未使用)数据。

下图及以下文本说明了对于我们的示例查询,ClickHouse如何定位UserID.bin数据文件中的分片176。

我们在本指南中早前讨论过,ClickHouse选择了主索引标记176,因此分片176被视为可能包含匹配查询的行。

ClickHouse现在使用来自索引的选定标记号(176)在UserID.mrk标记文件中进行位置数组查找,以获取定位分片176的两个偏移量。

如图所示,第一个偏移量定位于UserID.bin数据文件中的压缩文件块,该文件块反过来包含分片176的压缩版本。

一旦定位的文件块解压到主内存中,便可以使用标记文件中的第二个偏移量定位未经压缩的数据中的分片176。

ClickHouse需要定位(并从中流式传输所有值)UserID.bin数据文件和URL.bin数据文件中的分片176,以执行我们的示例查询(用户ID 749.927.693的互联网用户点击次数最多的前10个URL)。

上面的图示显示了ClickHouse如何定位UserID.bin数据文件的分片。

与此同时,ClickHouse正在对URL.bin数据文件的分片176执行相同的操作。两个相应的分片被对齐,并流式传输到ClickHouse引擎以进行进一步处理,即对所有UserID为749.927.693的行按组聚合和计数URL值,最后按降序输出计数最多的10个URL组。

使用多个主索引

次要关键列可能(不)效率低下

当一个查询在包含复合主键的一列上进行过滤并且是第一个关键列时,ClickHouse 会对该关键列的索引标记执行二叉搜索算法

但是当查询在复合主键的一列上进行过滤,但该列不是第一个关键列时,会发生什么?

备注

我们讨论一个场景,当查询明确不在第一个关键列上进行过滤,而是在次要关键列上进行过滤。

当查询在第一个关键列以及其后的任何关键列上都进行过滤时,ClickHouse对第一个关键列的索引标记执行二叉搜索。



我们使用一个查询,计算在URL "http://public_search" 上点击最频繁的前10个用户:

响应是:

客户端输出显示,尽管URL列是复合主键的一部分,ClickHouse几乎执行了完整的表扫描!ClickHouse从表的887万行中读取了881万行。

如果启用了trace_logging,ClickHouse服务器日志文件表明,ClickHouse在1083个URL索引标记中使用了通用排除搜索来识别可能包含URL列值为"http://public_search"的行的分片:

我们在上面的示例追踪日志中可以看到,从1083个分片中选择了1076个(通过标记),这些分片被认为可能包含与匹配的URL值。

这导致有881万行流式传输到ClickHouse引擎(通过使用10个流并行进行),以识别实际包含URL值"http://public_search"的行。

然而,正如我们稍后所见,从所选的1076个分片中,只有39个分片实际包含匹配的行。

虽然基于复合主键(UserID,URL)的主索引对加速过滤特定UserID值的查询非常有用,但该索引在加速过滤特定URL值的查询方面并未提供显著帮助。

其原因是URL列不是第一个关键列,因此ClickHouse正在对URL列的索引标记使用通用排除搜索算法(而不是二叉搜索),该算法的有效性依赖于 URL列与其前驱关键列UserID之间的基数差异。

为了说明这一点,我们提供了一些有关通用排除搜索如何工作的细节。

通用排除搜索算法

以下是说明ClickHouse通用排除搜索算法如何在通过次要列选择分片时工作的示例,前驱关键列具有较低或较高的基数。

我们将假设以下示例:

  • 一个查询正在搜索URL值= "W3"的行。
  • 我们的点击表的抽象版本,UserID和URL的简化值。
  • 具有相同复合主键(UserID,URL)。这意味着行首先按UserID值排序。具有相同UserID值的行随后按URL排序。
  • 每个分片的大小为两个,即每个分片包含两行。

我们在下面的图示中将每个分片的前两行的关键列值用橙色标记。

前驱关键列具有较低的基数

假设UserID具有较低的基数。在这种情况下,同一UserID值很可能分布在多个表行和分片中,因此索引标记相同的UserID。对于具有相同UserID的索引标记,URL值按升序排序(因为表行首先按UserID排序,然后按URL)。这允许高效过滤,如下所述:

对于我们抽象示例数据的分片选择过程,有三种不同的场景,图中所示:

  1. 标记0,其中URL值小于W3,并且直接后续的索引标记的URL值也小于W3可以被排除,因为标记0和1具有相同的UserID值。注意,这个排除预条件确保分片0完全由U1 UserID值组成,因此ClickHouse可以假设分片0中的最大URL值也小于W3并排除该分片。

  2. 标记1,其中URL值小于(或等于)W3,并且直接后续的索引标记的URL值大于(或等于)W3被选中,因为这意味着分片1可能包含URL W3的行。

  3. 标记2和3,其中URL值大于W3可以被排除,因为主索引的索引标记存储每个分片的第一行的关键列值,因此在磁盘上按关键列值对表行排序,分片2和3不可能包含URL值W3。

前驱关键列具有较高的基数

当UserID具有较高的基数时,同一UserID值分布在多个表行和分片中的可能性很小。这意味着索引标记的URL值不是单调增加的:

如上图所示,所有显示的标记和URL值小于W3的标记都被选择以流式传输与其相关的分片行到ClickHouse引擎。

这是因为,尽管图中的所有索引标记都符合上述场景1的描述,但它们不满足提到的排除预条件,即直接后继的索引标记具有与当前标记相同的UserID值,因此不能被排除。

例如,考虑标记0,其中URL值小于W3,并且直接后续的索引标记的URL值也小于W3。这不能被排除,因为直接后续的标记1与当前标记0的UserID值不同。

这最终阻止ClickHouse对分片0中的最大URL值进行假设。相反,它必须假设分片0可能包含URL值W3,并被迫选择标记0。

标记1、2和3的情况也是如此。

结论

ClickHouse使用的通用排除搜索算法取代了在查询过滤的列是复合关键的一部分,但不是第一个关键列的情况下使用的二叉搜索算法,在前驱关键列基数较低时最有效。

在我们的示例数据集中,两个关键列(UserID,URL)具有类似的高基数,并且正如所解释的,当前驱关键列为URL列时,通用排除搜索算法并不那么有效。

关于数据跳过索引的说明

由于UserID和URL的基数相似较高,我们对URL的查询过滤在创建表的复合主键(UserID,URL)上也不会受益于创建次级数据跳过索引

例如,这两个语句在我们表的URL列上创建和填充一个minmax数据跳过索引:

ClickHouse现在创建了一个额外的索引,每组4个连续的分片存储最小和最大URL值(注意上面的GRANULARITY 4子句):

第一个索引条目(上图中的“标记0”)存储属于我们表的前4个分片的的最小和最大URL值。

第二个索引条目(“标记1”)存储属于我们表接下来的4个分片的行的最小和最大URL值,依此类推。

(ClickHouse还为定位与索引标记关联的分片组创建了一个特殊的标记文件)。

由于UserID和URL的基数相似较高,这个次级数据跳过索引无法帮助在执行我们的查询过滤URL时排除分片的选择。

查询所查找的特定URL值(即'http://public_search')非常可能在索引为每组分片存储的最小值和最大值之间,从而导致ClickHouse被迫选择这组分片(因为它们可能包含匹配查询的行)。

需要使用多个主索引

因此,如果我们想显著加速过滤特定URL的查询示例,则需要使用优化该查询的主索引。

如果我们还希望保持对过滤特定UserID的示例查询的良好性能,则需要使用多个主索引。

以下展示了实现这一点的方法。

创建附加主索引的选项

如果我们想显著加速我们的两个示例查询——一个过滤具有特定UserID的行,另一个过滤具有特定URL的行——则需要使用多个主索引,使用以下三种选项之一:

  • 创建一个第二个表,使用不同的主键。
  • 在我们的现有表上创建一个物化视图
  • 向我们的现有表添加一个投影

所有这些选项都将有效地将我们的示例数据复制到一个附加表中,以重新组织表的主索引和行排序顺序。

然而,这三种选项在如何透明地将附加表路由到用户查询和插入语句方面有所不同。

创建一个第二个表,使用不同的主键时,查询必须明确发送到最适合该查询的表版本,并且新数据必须显式地插入到两个表中,以保持表同步:

使用物化视图时,附加表是隐式创建的,并且数据在两个表之间自动保持同步:

投影是最透明的选择,因为除了在数据变化时自动保持隐式创建(并隐藏的)附加表同步外,ClickHouse也将自动选择最有效的表版本来处理查询:

在下面,我们将更详细地讨论这三种创建和使用多个主索引的选项,并提供实际示例。

选项1:次要表

我们创建一个新的附加表,在主键中交换关键列的顺序(与我们的原始表相比):

将我们原始表中的887万行全部插入附加表:

响应如下:

最后优化表:

由于我们交换了主键中列的顺序,插入的行如今在磁盘中的字典序存储方式与我们的原始表相比是不同的,因此该表的1083个分片包含与之前不同的值:

这是生成的主键:

现在可用于显著加速我们的示例查询,该查询过滤URL列,以计算在URL "http://public_search"上点击最频繁的前10个用户:

响应是:

现在,ClickHouse比几乎执行完整表扫描要有效得多地执行该查询。

原始表中,UserID是第一个,URL是第二个关键列,ClickHouse在执行此查询时使用了通用排除搜索算法,这在UserID和URL的基数相似较高时并不非常有效。

使用URL作为主索引中的第一列,ClickHouse现在在索引标记上运行二叉搜索。 ClickHouse服务器日志中的对应追踪日志确认了这一点:

ClickHouse仅选择了39个索引标记,而不是1176个当时使用通用排除搜索时选择的标记。

请注意,附加表是为加速对UserIDs的查询执行而优化的,但对于原始表的查询结果不佳.

类似于原始表的查询对我们[示例查询]背后的UserIDs的性能并不会很有效,因为UserID现在是该表主索引中的第二个关键列,因此ClickHouse将使用通用排除搜索进行分片选择,而对于UserID和URL的基数相似较高,这并不有效。 打开详细框以获取具体信息。

对UserIDs的查询筛选现在具有不佳的性能

响应是:

服务器日志:

我们现在有两个表。分别优化为加速对UserIDs的查询和对URLs的查询。

选项2:物化视图

在我们现有表上创建一个物化视图

响应如下:

备注
  • 我们在视图的主键中交换了与我们的原始表中关键列的顺序。
  • 物化视图由一个隐式创建的表支持,该表的行顺序和主索引基于给定的主键定义。
  • 隐式创建的表由SHOW TABLES查询列出,且其名称以.inner开头。
  • 也可以首先显式创建物化视图的后备表,然后该视图可以通过TO [db].[table]子句指向该表。
  • 我们使用POPULATE关键字以立即用从源表Hits_UserID_URL的所有887万行填充隐式创建的表。
  • 如果新行插入到源表Hits_UserID_URL中,则这些行也会自动插入到隐式创建的表中。
  • 实际上,隐式创建的表具有与我们显式创建的次级表相同的行顺序和主索引:

ClickHouse将隐式创建的表及其主索引(primary.idx)存储在ClickHouse服务器数据目录中的特殊文件夹中:

隐式创建的表(及其主索引)支持的物化视图现在可以显著加速执行我们的示例查询,过滤URL列:

响应是:

因为隐式创建的表(及其主索引)实际上与我们显式创建的次级表相同,因此查询以与显式创建的表相同的有效方式执行。

ClickHouse服务器日志中对应的追踪日志确认ClickHouse正在对索引标记运行二叉搜索:

选项3:投影

在我们现有表上创建一个投影:

并将投影物化:

备注
  • 投影创建一个隐藏表,其行顺序和主索引基于投影的给定ORDER BY子句。
  • 隐藏表不会由SHOW TABLES查询列出。
  • 我们使用MATERIALIZE关键字立即填充隐式创建的表,填充源表Hits_UserID_URL中的所有887万行。
  • 如果新行插入到源表Hits_UserID_URL中,这些行也会自动插入到隐藏表中。
  • 查询始终(在语法上)针对源表Hits_UserID_URL,但如果隐藏表的行顺序和主索引允许更有效的查询执行,则将使用隐藏表。
  • 请注意,即使ORDER BY与投影的ORDER BY语句匹配,投影也不会使使用ORDER BY的查询更高效(见 https://github.com/ClickHouse/ClickHouse/issues/47333)。
  • 实际上,隐式创建的隐藏表具有与我们显式创建的次级表相同的行顺序和主索引

ClickHouse将隐式创建的隐藏表(及其主索引)存储在源表的数据文件、标记文件和主索引文件旁边的特殊文件夹中(在下面的屏幕截图中用橙色标记):

投影创建的隐藏表(及其主索引)现在可以(隐式)用于显著加速执行我们的示例查询,过滤URL列。请注意,查询在语法上是针对投影的源表。

响应是:

因为隐式创建的隐藏表(及其主索引)与我们显式创建的次级表相同,查询以与显式创建的表相同的有效方式执行。

ClickHouse服务器日志中的相应追踪日志确认ClickHouse正在对索引标记运行二叉搜索:

摘要

我们 复合主键(UserID,URL)的表 的主索引对于加快 基于 UserID 的查询 非常有用。但是,这个索引在加速基于 URL 的查询上并没有提供显著的帮助,尽管 URL 列是复合主键的一部分。

反之亦然: 我们 复合主键(URL,UserID)的表 的主索引对于加快 基于 URL 的查询 很有帮助,但对于加快 基于 UserID 的查询 支持不大。

由于主键列 UserID 和 URL 的基数相似得很高,基于第二个键列的查询 没有太大好处,因为第二个键列在索引中的位置

因此,去掉主索引中的第二个键列是合理的(这将减少索引的内存消耗),并且改为 使用多个主索引

然而,如果复合主键中的键列在基数上有很大的差异,则 对查询是有利的,按照基数升序排列主键列。

键列之间的基数差异越大,键列在复合主键中的顺序越重要。我们将在下一节中演示这一点。

高效排序键列

在复合主键中,键列的顺序可以显著影响:

  • 查询中对次键列的过滤效率,以及
  • 表的数据文件的压缩比。

为了证明这一点,我们将使用我们的 网络流量示例数据集 的一个版本,其中每一行包含三个列,指示互联网“用户”(UserID 列)对一个 URL(URL 列)的访问是否被标记为机器流量(IsRobot 列)。

我们将使用一个包含上述所有三个列的复合主键,加速典型的网络分析查询,这些查询计算

  • 特定 URL 的流量中有多少(百分比)来自机器,或
  • 我们有多大的把握认为特定用户(不)是机器(该用户的流量中有多少百分比(不)被假定为机器人流量)。

我们使用这个查询来计算我们希望用作复合主键中的键列的三个列的基数(注意,我们使用 URL 表函数 来即时查询 TSV 数据,而不需要创建本地表)。在 clickhouse client 中运行这个查询:

响应为:

我们可以看到基数之间存在很大差异,尤其是 URL 和 IsRobot 列之间的差异,因此这些列在复合主键中的顺序对加快对这些列的查询和优化表的列数据文件的压缩比都是重要的。

为了证明这一点,我们为我们的机器人流量分析数据创建两个表版本:

  • hits_URL_UserID_IsRobot,其复合主键为 (URL, UserID, IsRobot),我们按基数降序排列键列。
  • hits_IsRobot_UserID_URL,其复合主键为 (IsRobot, UserID, URL),我们按基数升序排列键列。

创建复合主键为 (URL, UserID, IsRobot) 的表 hits_URL_UserID_IsRobot

并填充 8.87 万行:

这是响应:

接下来,创建复合主键为 (IsRobot, UserID, URL) 的表 hits_IsRobot_UserID_URL

并用我们用来填充前一个表的同样的 8.87 万行填充它:

响应为:

次键列的高效过滤

当一个查询过滤至少一个作为复合键一部分的列,并且是第一个键列时,ClickHouse 会在该键列的索引标记上运行二进制搜索算法

当查询过滤的仅仅是作为复合键一部分的一个列,但不是第一个键列时,ClickHouse 会在该键列的索引标记上使用通用排除搜索算法

对于第二种情况,复合主键中键列的顺序对 通用排除搜索算法 的有效性是重要的。

这是一个过滤表中 UserID 列的查询,我们按基数降序排列键列 (URL, UserID, IsRobot)

响应为:

这是在我们按基数升序排列键列 (IsRobot, UserID, URL) 的表上的相同查询:

响应为:

我们可以看到,在按基数升序排列键列的表上,查询执行显著更有效和更快。

原因在于, 通用排除搜索算法Granules 通过第二个键列选择时,前一个键列的基数较低时工作最为高效。在本指南的 前一节 中我们详细说明了这一点。

数据文件的最佳压缩比

此查询比较我们上面创建的两个表中 UserID 列的压缩比:

这是响应:

我们可以看到,在按基数升序排列键列的表上,UserID 列的压缩比显著更高。

虽然这两个表中存储了完全相同的数据(我们在两个表中都插入了 8.87 万行),但复合主键中键列的顺序对表 列数据文件 中压缩数据所需的磁盘空间有显著影响:

  • 在复合主键为 (URL, UserID, IsRobot) 的表 hits_URL_UserID_IsRobot 中,我们按基数降序排列键列,该 UserID.bin 数据文件占用 11.24 MiB 磁盘空间。
  • 在复合主键为 (IsRobot, UserID, URL) 的表 hits_IsRobot_UserID_URL 中,我们按基数升序排列键列,该 UserID.bin 数据文件仅占用 877.47 KiB 磁盘空间。

保持表中列在磁盘上的数据具有良好的压缩比,不仅可以节省磁盘空间,还可以加快需要从该列读取数据的查询(特别是分析查询),因为将列数据从磁盘移动到主内存(操作系统的文件缓存)所需的 I/O 更少。

以下将说明为何按基数升序排列主键列对表中列的压缩比是有利的。

下图展示了按基数升序排列的主键的行在磁盘上的顺序:

我们讨论过 表的行数据是按主键列的顺序存储在磁盘上的

在上图中,表的行(它们在磁盘上的列值)首先按其 cl 值排序,具有相同 cl 值的行按其 ch 值排序。而且由于第一个键列 cl 的基数低,很可能会有具有相同 cl 值的行。由于这个原因,ch 值在(对于具有相同 cl 值的行)局部有序也是很可能的。

如果在某列中,相似的数据被彼此靠近放置,例如通过排序,那么该数据将会得到更好的压缩。 一般来说,压缩算法有利于数据的运行长度(它看到的数据越多,压缩越好)和局部性(数据越相似,压缩比越好)。

与上述图相对的是,下面的图展示了按基数降序排列的主键的行在磁盘上的顺序:

现在,表的行首先按其 ch 值排序,具有相同 ch 值的行按其 cl 值排序。 但是,由于第一个键列 ch 的基数高,很难有具有相同 ch 值的行。因此,也不太可能在(对于具有相同 ch 值的行)局部有序的 cl 值。

因此,cl 值更可能是随机顺序,因此具有较差的局部性,压缩比也会较低。

摘要

对于次键列查询的高效过滤和表的列数据文件的压缩比,按基数升序排列主键中的列是有利的。

高效识别单行

虽然一般来说 这不是 ClickHouse 的最佳用例,但有时构建在 ClickHouse 之上的应用程序需要识别 ClickHouse 表的单行。

对于此类情况,一个直观的解决方案可能是使用一个每行都有唯一值的 UUID 列,并将该列作为主键列以快速检索行。

为了获得最快的检索,UUID 列 需要是第一个键列

我们讨论过,因为 ClickHouse 表的行数据是按主键列的顺序存储在磁盘上的,在主键或复合主键中含有非常高基数的列(比如 UUID 列)会对其他表列的压缩比 产生不利影响

快速检索与最佳数据压缩之间的折衷是使用一个复合主键,其中 UUID 是最后一个键列,位于使用较低基数键列的后面,以确保某些表列的良好压缩比。

一个具体例子

一个具体的例子是明文粘贴服务 https://pastila.nl,这是 Alexey Milovidov 开发和 写博客 的。

每当文本区域发生变化时,数据就会自动存储到 ClickHouse 表的行中(每次更改一行)。

识别和检索(特定版本的)粘贴内容的一种方法是使用内容的哈希作为包含内容的表行的 UUID。

下面的图示显示了

  • 内容变化时(例如因为输入文本的按键)行的插入顺序,以及
  • 使用 PRIMARY KEY (hash) 时插入行的数据在磁盘上的存储顺序:

由于 hash 列用作主键列

  • 特定行可以 非常快速地检索,但
  • 表的行(它们的列数据)在磁盘上的存储顺序是按(唯一且随机的)哈希值升序排列。因此,内容列的值以随机顺序存储,没有数据局部性,从而导致 内容列数据文件的压缩比不理想

为了显著提高内容列的压缩比,同时仍能快速检索特定行,pastila.nl 使用两个哈希(和一个复合主键)来识别特定行:

  • 上面讨论的内容的哈希,对于不同的数据是独特的,以及
  • 一个 局部敏感哈希(指纹),即使数据发生小变动也不会变化。

下面的图示显示了

  • 内容变化时(例如由于输入文本的按键)行的插入顺序,以及
  • 使用复合 PRIMARY KEY (fingerprint, hash) 时插入行的数据在磁盘上的存储顺序:

现在,磁盘上的行首先按 fingerprint 排序,对于具有相同指纹值的行,哈希值决定最终顺序。

由于仅发生小变化的数据会获得相同的指纹值,因此相似的数据现在在内容列中以接近的方式存储在磁盘上。这种变化对内容列的压缩比非常有利,因为压缩算法通常受益于数据的局部性(数据越相似,压缩比越好)。

折衷在于为了最佳利用由复合 PRIMARY KEY (fingerprint, hash) 生成的主索引,需要两个字段(fingerprinthash)来检索特定行。