投稿
  1. 极客之音首页
  2. 技术漫谈

Clickhouse 主键索引介绍

土豆大侠 • • 技术漫谈 • 阅读 276

在传统的关系型数据库管理系统中，每个表行包含一个主键索引（通常使用 B(+)-Tree），也就是说，表有多少行数据，就有多少条以主键为 key 的索引行

B-Tree 索引的优点：

  • 够快速的定位到特定的行，从而提高查找和更新的效率
  • 时间复杂度为 O(log2n)

B-Tree 缺点：

  • 缺点是额外的内存和磁盘的开销
  • 引入额外的插入成本（插入数据行需要额外向索引中添加条目，有时还需要平衡 B-Tree）

由于 Clickhouse 是定位大数据场景下的的联机分析（OLAP）数据管理系统，OLAP 绝大多数是读场景，并且大多数是一次读取多行。所以 clickhouse 并不需要根据索引快速定位到特定的某一行数据，因此，clickhouse 不是为每一行数据创建索引，而是为一组行（称为 granule，中文为颗粒）构建一个索引条目，这种索引称之为稀疏索引（clickhouse 的主键索引用的就是稀疏索引）

测试环境

我使用的是 M2 Pro 芯片的 MacBook Pro 上运行 docker 的 clickhouse 24.3.2，可以参考下面的 docker-compose 文件启动你的 clickhouse 容器

version: '2'

services:
  clickhouse:
    image: bitnami/clickhouse:24.3.2
    container_name: clickhouse
    environment:
     - ALLOW_EMPTY_PASSWORD=no
     - CLICKHOUSE_ADMIN_PASSWORD=root
    volumes:
     - ./data:/bitnami/clickhouse
    ports:
     - 8123:8123

初识主键索引

为了直观的体会到索引对查询效率的影响，我们使用以下 DDL 语句创建不带索引的表

CREATE TABLE hits_NoPrimaryKey
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY tuple();

MergeTree 表引擎要求创建表的时候必须声明 primary key 或 order by，否则会报错。但是可以使用 primary key tuple() 创建不带主键的表

接着向hits_NoprimaryKey表中插入数据

INSERT INTO hits_NoPrimaryKey SELECT
   intHash32(c11::UInt64) AS UserID,
   c15 AS URL,
   c5 AS EventTime
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz')
WHERE URL != '';

结果：

Ok.

0 rows in set. Elapsed: 859.710 sec. Processed 8.87 million rows, 917.65 MB (10.32 thousand rows/s., 1.07 MB/s.)
Peak memory usage: 642.73 MiB.

可以看到，我们向hits_NoPrimaryKey表中插入了 887w 条数据，为了方便讨论，我们在插入完数据后执行一遍 optimize 操作

OPTIMIZE TABLE hits_NoPrimaryKey FINAL;

现在，我们想查询 id 为749927693 的用户点击次数最多前 10 个 url，可以执行以下 DML 语句

SELECT URL, count(URL) as Count
FROM hits_NoPrimaryKey
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

执行结果如下：

┌─URL─────────────────────────────────────────────────────┬─Count─┐
│ http://auto.ru/chatay-barana.ru/tr...                   │   170 │
│ http://auto.ru/chatay-id=371&rents/41601151             │    52 │
│ http://public_search                                    │    45 │
│ http://kovrik-medvedevushku-zarabota...                 │    36 │
│ http://forumal                                          │    33 │
│ http://korablitz.ru/L_1OFFERS_CRD                       │    14 │
│ http://auto.ru/chatay-id=371&rents/4160115              │    14 │
│ http://auto.ru/chatay-john-Den-Yunan ahtım var b        │    13 │
│ http://auto.ru/chatay-john-Den-Yunan ahtım var&is       │    10 │
│ http://wot/html?page/23600_m/sportbox.ru/               │     9 │
└─────────────────────────────────────────────────────────┴───────┘

10 rows in set. Elapsed: 0.100 sec. 
Processed 8.87 million rows, 70.45 MB (89.11 million rows/s., 707.97 MB/s.)
Peak memory usage: 8.10 MiB.

可以看到，clickhouse 对上面的查询执行了一次全表扫描，耗时 0.1 秒

接着我们创建一张包含 UserID 和 URL 作为联合主键的表，

CREATE TABLE hits_UserID_URL
(
    `UserID` UInt32,
    `URL` String,
    `EventTime` DateTime
)
ENGINE = MergeTree
PRIMARY KEY (UserID, URL)
ORDER BY (UserID, URL, EventTime)
SETTINGS index_granularity = 8192, index_granularity_bytes = 0;

并向表中插入同样的数据

INSERT INTO hits_UserID_URL SELECT
   intHash32(c11::UInt64) AS UserID,
   c15 AS URL,
   c5 AS EventTime
FROM url('https://datasets.clickhouse.com/hits/tsv/hits_v1.tsv.xz')
WHERE URL != '';

同样执行一遍 optimize

OPTIMIZE TABLE hits_UserID_URL FINAL;

同样查询id 为749927693 的用户点击次数最多前 10 个 url

SELECT URL, count(URL) as Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

结果：

┌─URL─────────────────────────────────────────────────────┬─Count─┐
│ http://auto.ru/chatay-barana.ru/tr...                   │   170 │
│ http://auto.ru/chatay-id=371&rents/41601151             │    52 │
│ http://public_search                                    │    45 │
│ http://kovrik-medvedevushku-zarabota...                 │    36 │
│ http://forumal                                          │    33 │
│ http://korablitz.ru/L_1OFFERS_CRD                       │    14 │
│ http://auto.ru/chatay-id=371&rents/4160115              │    14 │
│ http://auto.ru/chatay-john-Den-Yunan ahtım var b        │    13 │
│ http://auto.ru/chatay-john-Den-Yunan ahtım var&is       │    10 │
│ http://wot/html?page/23600_m/sportbox.ru/               │     9 │
└─────────────────────────────────────────────────────────┴───────┘

10 rows in set. Elapsed: 0.016 sec. Processed 8.19 thousand rows, 740.18 KB (515.85 thousand rows/s., 46.61 MB/s.)
Peak memory usage: 49.32 KiB.

可以看到，clickhouse 这次只扫描了 8 千多行数据，耗时 0.016 秒，证明此次扫描走了主键索引，可以用 explain 验证一下

EXPLAIN indexes=1
SELECT URL, count(URL) as Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

explain 结果：

┌─explain─────────────────────────────────────────────────────────┐
│ Expression (Project names)                                      │
│   Limit (preliminary LIMIT (without OFFSET))                    │
│     Sorting (Sorting for ORDER BY)                              │
│       Expression ((Before ORDER BY + Projection))               │
│         Aggregating                                             │
│           Expression (Before GROUP BY)                          │
│             Expression                                          │
│               ReadFromMergeTree (hxy_test.hits_UserID_URL)      │
│               Indexes:                                          │
│                 PrimaryKey                                      │
│                   Keys:                                         │
│                     UserID                                      │
│                   Condition: (UserID in [749927693, 749927693]) │
│                   Parts: 1/1                                    │
│                   Granules: 1/1083                              │
└─────────────────────────────────────────────────────────────────┘

15 rows in set. Elapsed: 0.002 sec.

主键索引原理

到这里，我们对主键索引的使用已经有个大概的认知，下面介绍主键索引的原理

以hits_UserID_URL表为例，clickhouse 会在磁盘上创建 *.bin 文件，数据以UserID, URL, EventTime的顺序按字典序升序进行存储，每一列对应单独的 .bin 文件Clickhouse 主键索引介绍

基于数据处理的目的，clickhouse 将表的数据划分为多个颗粒（granule），一个颗粒代表多行相邻数据组成的数据集，下面展示了hits_UserID_URL表中 887w 行数据，被切分成 1083 个颗粒的示意图Clickhouse 主键索引介绍

颗粒（granule）的大小由 index_granularity 参数指定，hits_UserID_URL 建表语句指定 index_granularity = 8192，故 887w 行数据被切分成 1083 个颗粒。其中，每个颗粒的首行被标记为橙色

主键索引是根据每个颗粒中的数据集的首行进行创建的，这个索引是一个未压缩的扁平数据文件（primary.idx），下面是主键索引文件的示意图Clickhouse 主键索引介绍

Clickhouse 主键索引介绍
image.png

这就是稀疏索引这个名称的由来，clickhouse 并不会为每行数据创建一条索引记录，而是为每个颗粒创建一条索引

有了主键索引之后，clickhouse 在查询的时候，clickhouse 就能基于主键索引（稀疏索引）来快速定位所选的颗粒，并将所有颗粒的所有行流到 clickhouse 引擎中，以便找到实际匹配的行

那么，clickhouse 是如何利用索引文件（primary.idx）加快 SQL 的查询效率的呢？还是之前的查询 SQL

SELECT URL, count(URL) AS Count
FROM hits_UserID_URL
WHERE UserID = 749927693
GROUP BY URL
ORDER BY Count DESC
LIMIT 10;

查询主要分两步进行：

  • 第一步：利用主键索引选择所需要的颗粒
  • 第二步：利用标记文件定位颗粒

利用主键索引选择所需要的颗粒

Clickhouse 主键索引介绍如图所示，基于主键索引，利用二分法可以很快定位到，UserID=749927693 的行位于颗粒 176 上，因为颗粒 176 的起始 UserID=747148242（小于749927693），下一个颗粒，也就是颗粒 177 的起始值为 751802947（大于749927693）

利用标记文件定位颗粒

第一步筛选了所需要的颗粒后，还需要知道颗粒对应的物理位置。与数据文件类似，clickhouse 为每个表的列都创建一个.mkr标记文件，存储颗粒对应的物理位置，hits_UserID_URL表的三个标记文件UserID.mrk、URL.mrk、EventTime.mrk如下所示Clickhouse 主键索引介绍

与primary.idx一样，.mrk标记文件也是一个扁平的数据，下标从 0 开始，存储两个值

  • block_offset：存储列数据压缩文件中，包含该颗粒的压缩块的位置，这个压缩块可能包含几个压缩颗粒，所定位的压缩文件被读取到内存中
  • granule_offeset：存储颗粒在解压数据块中的位置

下面显示 clickhouse 如何利用标记文件定位 UserID.bin 文件中的数据Clickhouse 主键索引介绍

  • 根据UserID.mrk标记文件，定位到数据块 176 在压缩块中的位置
  • 解压压缩块
  • 利用UserID.mrk标记文件的 granule_offset 值，定位到解压数据块中颗粒 176 的起始位置
  • 加载颗粒 176 中的数据到 clickhouse 引擎进行进一步处理

同样的，对 URL.bin 执行同样的操作，就能计算出 UserID=749927693 的用户点击次数最多前 10 个 url 了

总结

在大数据的场景下，磁盘和内存的效率是非常重要的，因此，clickhouse 不为每行数据创建一个索引行，而是为一组数据创建一行索引来构建稀疏索引。基于primary.idx和.mrk标记文件，clickhouse 能够快速的定位到查询所需要的数据行的颗粒，并将颗粒中的数据行加载到 clickhouse 引擎中进行进一步的计算


原文始发于微信公众号（huangxy）：Clickhouse 主键索引介绍

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/289285.html

赞 (0)
土豆大侠的头像土豆大侠
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！