概述
模糊查询在日志存储的场景中非常普遍。ClickHouse作为大数据分布式引擎，理所当然地会被作为日志存储的备选方案。事实上使用ClickHouse作为日志存储方案，业界目前也已经在多家企业落地，比如Uber、石墨文档、映客、快手、携程、唯品会等。
日志查询的一个最大的特点是，几乎极少涉猎点查询，而模糊查询则占据了绝大部分使用场景。这也是为什么ES凭借其逆天的分词能力在日志存储领域杀疯了的原因。但ES存储的瓶颈近些年也逐渐显现， 如压缩率低，需要较大的存储成本，当数据量过大时，查询性能也比较差。因此，近些年越来越多的企业开始寻求ES的替代方案。ClickHouse正是选择之一。
那么，ClickHouse有什么优秀的特性，能在一众大数据存储组件中脱颖而出，杀出一片天地呢？
首先，不论是写入性能，还是存储压缩率，ClickHouse相比ES，都是压倒性优势。但实事求是地说，ClickHouse擅长的场景其实并不包含模糊查询，但对模糊查询也提供了一些优化的空间。其中最具代表性的，就是跳数索引。
跳数索引
ClickHouse中，跳数索引又称为二级索引。它是独立于主键索引之外的另一类索引。
跳数索引针对不同的查询场景，提供了不同索引类型，如针对去重的set，针对计算极值的minmax，当然还有针对全文搜索的布隆过滤器家族。
关于跳数索引的概念以及介绍，本文就不多做展开了，感兴趣的可以去看官网文档，介绍文档： https://clickhouse.com/docs/en/engines/table-engines/mergetree-family/mergetree#table_engine-mergetree-data_skipping-indexes， 以及使用相关实践：https://clickhouse.com/docs/en/optimize/skipping-indexes。
因为本文主要将模糊查询的加速，因此主要看布隆过滤器家族。
目前比较适合全文查询的索引主要有tokenbf_v1, ngrambf_v1， 以及新版本刚刚推出的倒排索引inverted。那么，这三种索引应该如何选择呢？
-
tokenbf_v1- 这是按照
token进行分词的布隆过滤器索引。它会将长文本中的单词按非字母数字字符（如空格、-，[]等）进行分词，每个分词就是一个token，然后将这个token映射到布隆过滤器的bitmap中。 - 举个例子，
https://clickhouse.com/docs/en/engines/table-engines/mergetree-family/mergetree#table_engine-mergetree-data_skipping-indexes这个字符串，经过分词后，会变成如下的token：
- 这是按照
['https', 'clickhouse', 'com', 'docs', 'en', 'engines', 'table', 'engines', 'mergetree', 'family', 'mergetree', 'table', 'engine', 'data', 'skipping', 'indexes']-
- 因此，
tokenbf_v1的缺点比较明显：- 比较死板，如果查询的条件里有特殊字符，那么这个索引就会失效
- 无法支持中文
- 因此，
-
ngrambf_v1-
ngrambf_v1和tokenbf_v1比较像，不过它不是按照token进行分词，而是根据长度进行分词。 - 同样举个例子，假设将
A short string按照n=4进行分词，得到的结果如下 ：
-
['A sh', ' sho', 'shor', 'hort', 'ort ', 'rt s', 't st', ' str', 'stri', 'trin', 'ring']-
-
ngrambf_v1相比于tokenbf_v1，优点是终于支持特殊字符，甚至汉字的分词了 - 缺点是
n的长度一旦确定好就不好修改，如果查询的关键词长度小于n，那么该索引也不会生效 - 有人说既然如此我把
n设置的尽量小一点不就行了？事实上也不行，这点我们后面实战的时候再说。 - 因此，
ngrambf_v1非常看具体的查询场景，如果提前知道查询的SQL，针对性的设置n的长度，是有非常大的优化效果的，比较不适用那种通用的天马行空的查询。
-
-
inverted- 很多人一听倒排索引，第一感觉大概是：就是它了。无限接近
ES分词的一个索引。 - 这么说未免高看这个倒排索引的能力了。它的原理确实和
ES类似 ，但分词逻辑仍然是和tobenbf_v1是一样的，也就是说它同样是针对non-alphanumeric进行分词的，同样不支持特殊字符和汉字的查询。只不过比tokenbf_v1占用更少的存储资源，相同查询场景下，比tokenbf_v1更优秀一些罢了。但这也是在索引被命中的前提下，如果索引命中不了，再优秀也无用武之地。
- 很多人一听倒排索引，第一感觉大概是：就是它了。无限接近
针对以上三种索引，最适合的应该是ngrambf_v1， 当然，为了公平，我们在接下来的实战中，使用相同的查询场景，来验证索引的优化能力。
实战演练
为了尽量真实地模拟日志存储场景 ，我使用一个Java程序循环写日志，日志内容包括Java异常、Python的backtrace， C++的backtrace等，都是一些比较长的长文本。一共循环写入1亿数据。
数据的结构大致如下：
{
"logType": "Application",
"@timestamp": "2023-10-20 20:14:09.437",
"ip": "192.168.2.212",
"filePath": "/log/[poiuytrewqlkjh-uiop-qwertyuiop]/[container-container-java].log",
"cloudId": 2,
"time": "2023-10-20 20:14:09.437",
"id": "9377ff31-3c2f-45bd-a096-486a0aa35f3e",
"tms": 1697804049437,
"rowNumber": 1941074,
"value": "[2023-10-20 20:14:09.437][poiuytrewqlkjh-uiop-qwertyuiop][container-container-java][uiop-ghjk-poiuytrewqlkjh][ERROR]-> org.apache.hadoop.hive.metastore.RetryingHMSHandler: [pool-5-thread-13]: MetaException(message:Got exception: org.apache.hadoop.ipc.RemoteException Cannot create directory /user/hue/.cloudera_manager_hive_metastore_canary/hive_HIVEMETASTORE_0aaf2807c67ce8ad92924eb12310ef21. Name node is in safe mode.\nThe reported blocks 0 needs additional 15346 blocks to reach the threshold 0.9990 of total blocks 15361.\nThe number of live datanodes 0 needs an additional 1 live datanodes to reach the minimum number 1.\nSafe mode will be turned off automatically once the thresholds have been reached.\n at org.apache.hadoop.hdfs.server.namenode.FSNamesystem.checkNameNodeSafeMode(FSNamesystem.java:1527)\n at org.apache.hadoop.hdfs.server.namenode.FSNamesystem.mkdirsInt(FSNamesystem.java:4471)\n at org.apache.hadoop.hdfs.server.namenode.FSNamesystem.mkdirs(FSNamesystem.java:4446)\n at org.apache.hadoop.hdfs.server.namenode.NameNodeRpcServer.mkdirs(NameNodeRpcServer.java:882)\n at org.apache.hadoop.hdfs.server.namenode.AuthorizationProviderProxyClientProtocol.mkdirs(AuthorizationProviderProxyClientProtocol.java:326)\n at org.apache.hadoop.hdfs.protocolPB.ClientNamenodeProtocolServerSideTranslatorPB.mkdirs(ClientNamenodeProtocolServerSideTranslatorPB.java:640)\n at org.apache.hadoop.hdfs.protocol.proto.ClientNamenodeProtocolProtos$ClientNamenodeProtocol$2.callBlockingMethod(ClientNamenodeProtocolProtos.java)\n at org.apache.hadoop.ipc.ProtobufRpcEngine$Server$ProtoBufRpcInvoker.call(ProtobufRpcEngine.java:617)\n at org.apache.hadoop.ipc.RPC$Server.call(RPC.java:1073)\n at org.apache.hadoop.ipc.Server$Handler$1.run(Server.java:2281)\n at org.apache.hadoop.ipc.Server$Handler$1.run(Server.java:2277)\n at java.security.AccessController.doPrivileged(Native Method)\n at javax.security.auth.Subject.doAs(Subject.java:422)\n at org.apache.hadoop.security.UserGroupInformation.doAs(UserGroupInformation.java:1920)\n at org.apache.hadoop.ipc.Server$Handler.run(Server.java:2275)\n)\n at org.apache.hadoop.hive.metastore.MetaStoreUtils.logAndThrowMetaException(MetaStoreUtils.java:1252)\n at org.apache.hadoop.hive.metastore.Warehouse.mkdirs(Warehouse.java:208)\n at org.apache.hadoop.hive.metastore.HiveMetaStore$HMSHandler.create_database_core(HiveMetaStore.java:934)\n at org.apache.hadoop.hive.metastore.HiveMetaStore$HMSHandler.create_database(HiveMetaStore.java:993)\n at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)\n at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)\n at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)\n at java.lang.reflect.Method.invoke(Method.java:498)\n at org.apache.hadoop.hive.metastore.RetryingHMSHandler.invokeInternal(RetryingHMSHandler.java:140)\n at org.apache.hadoop.hive.metastore.RetryingHMSHandler.invoke(RetryingHMSHandler.java:99)\n at com.sun.proxy.$Proxy9.create_database(Unknown Source)\n at org.apache.hadoop.hive.metastore.api.ThriftHiveMetastore$Processor$create_database.getResult(ThriftHiveMetastore.java:9570)\n at org.apache.hadoop.hive.metastore.api.ThriftHiveMetastore$Processor$create_database.getResult(ThriftHiveMetastore.java:9554)\n at org.apache.thrift.ProcessFunction.process(ProcessFunction.java:39)\n at org.apache.hadoop.hive.metastore.TUGIBasedProcessor$1.run(TUGIBasedProcessor.java:110)\n at org.apache.hadoop.hive.metastore.TUGIBasedProcessor$1.run(TUGIBasedProcessor.java:106)\n at java.security.AccessController.doPrivileged(Native Method)\n at javax.security.auth.Subject.doAs(Subject.java:422)\n at org.apache.hadoop.security.UserGroupInformation.doAs(UserGroupInformation.java:1920)\n at org.apache.hadoop.hive.metastore.TUGIBasedProcessor.process(TUGIBasedProcessor.java:118)\n at org.apache.thrift.server.TThreadPoolServer$WorkerProcess.run(TThreadPoolServer.java:286)\n at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)\n at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)\n at java.lang.Thread.run(Thread.java:748)\n|java-info-apple-zxcv",
"@storageTime": "2023-10-20 20:14:09.437",
"fd": 344678
}建表SQL如下：
CREATE TABLE ck_log_test(
`logType` String,
`@timestamp` DateTime64(3),
`ip` String,
`filePath` String,
`cloudId` UInt64,
`time` DateTime64(3),
`id` String,
`tms` UInt64,
`rowNumber` UInt64,
`value` String,
`@storageTime` DateTime64(3),
`fd` UInt64
) ENGINE = ReplicatedMergeTree() PARTITION BY toYYYYMMDD(`@timestamp`)
ORDER BY (`@timestamp`);这里省略数据写入的过程，最终数据如下：
ck94 :) select count() from ck_log_test;
SELECT count()
FROM ck_log_test
Query id: 683c6cfe-f500-4adb-a89f-11a9d1c57abf
┌───count()─┐
│ 100606527 │
└───────────┘
1 row in set. Elapsed: 0.005 sec.接下来，我们使用不同的索引，查询表中value字段包含[INFO]和gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop的数量。
tokenbf_v1
创建索引：
ALTER TABLE ck_log_test ADD INDEX idx_string_value value TYPE tokenbf_v1(30720, 2, 0) GRANULARITY 1;以上只是将索引创建出来了，对于存量数据，并不能生效，想要对存量数据生效，需要执行物化操作：
ALTER TABLE ck_log_test MATERIALIZE INDEX idx_string_value;创建索引本身是一个轻量级操作，但物化操作是一个比较重的操作，虽然sql执行立即就结束了，但实际还在后台执行，可以通过SELECT * FROM system.mutations WHERE is_done = '0';来查看物化进度， 表中的数据越多，物化所需要的时间就越长。
ck94 :) SELECT * FROM system.mutations WHERE is_done = '0'\G;
SELECT *
FROM system.mutations
WHERE is_done = '0'
Query id: 3b10b7e1-7b81-4602-a26e-7858fe11b314
Row 1:
──────
database: default
table: ck_log_test
mutation_id: 0000000007
command: MATERIALIZE INDEX idx_string_value
create_time: 2023-11-03 10:56:49
block_numbers.partition_id: ['20231021']
block_numbers.number: [915]
parts_to_do_names: ['20231021_0_327_3_914','20231021_328_370_2_914','20231021_371_423_2_914','20231021_424_454_2_914','20231021_455_893_4_914','20231021_894_899_1_914','20231021_900_900_0_914','20231021_901_901_0_914','20231021_902_902_0_914']
parts_to_do: 9
is_done: 0
latest_failed_part:
latest_fail_time: 1970-01-01 08:00:00
latest_fail_reason:
1 row in set. Elapsed: 0.014 sec.只有当查询的is_done结果为1时，才说明物化完成了。
物化完成后，查询：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: f83f5ff6-8fa9-4c57-8f4d-fa13c2eee644
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 18.481 sec. Processed 100.61 million rows, 213.94 GB (5.44 million rows/s., 11.58 GB/s.)从上面的查询结果来看，整个查询耗时18秒，扫描数据10061万条，这就是全表扫描了。说明虽然我们创建了一个跳数索引，但是对查询没有任何的优化效果。接下来我们通过执行计划来印证这一点。
在SQL语句前加上EXPLAIN，即可查看执行计划，再加上indexes = 1， 就可以查看走到的索引的情况：
ck94 :) explain indexes = 1 SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
EXPLAIN indexes = 1
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: a9a93c72-94b4-4b6a-bd87-21d2e24385d0
┌─explain───────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Partition │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Skip │
│ Name: idx_string_value │
│ Description: tokenbf_v1 GRANULARITY 1 │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
└───────────────────────────────────────────────────┘
23 rows in set. Elapsed: 0.263 sec.执行计划如何看？
Filter一开始，是9个part，一共12929个索引。每个索引粒度都是8192， 所以一共是 8192 * 12929条数据，这个和我们的数据总量是对应得上的。
首先有一个MinMax，这个一般是根据建表时的ORDER BY的字段进行筛选，因为我们没有带任何@timestamp的筛选范围，所以MinMax筛选完还是12929个数据块。
然后是Partition，也就是分区。正常来说， 如果按天分区，你查最近一小时数据，它肯定不会走到昨天的分区里去查找数据，可以通过这种手段直接排除掉一些不可能走到的分区。因为我们的数据都在同一个分区，所以过滤不掉，还是12929个数据块。
接下来是PrimaryKey， 我们没有显式地指定主键索引，所以默认使用ORDER BY的字段作为主键索引，也是没有过滤掉数据，还是12929.
注意最后面的Skip，这个指的就是跳数索引，可以看到idx_string_value正是我们创建的索引，说明这个查询，这个索引确实走到了，但是过滤完，还是12929个数据块，说明虽然走到了这个索引，但是一条数据都没有过滤掉。
inverted
同样，先创建索引：
ALTER TABLE ck_log_test DROP INDEX idx_string_value; ---删除旧索引
SET allow_experimental_inverted_index = 1 ---倒排索引属于实验特性，需要开启才能使用
ALTER TABLE ck_log_test ADD INDEX inv_idx(value) TYPE inverted; ---创建倒排索引
ALTER TABLE ck_log_test MATERIALIZE INDEX inv_idx; ---物化数据物化完成后，查询数据：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: d99aa377-5a0b-4a83-a101-bff27381fcdf
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 19.013 sec. Processed 100.61 million rows, 213.94 GB (5.29 million rows/s., 11.25 GB/s.)可以看到，查询时间19秒，扫描数据1亿61万，同上面一样，也进行了全表扫描。来看看查询计划：
ck94 :) explain indexes = 1 SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
EXPLAIN indexes = 1
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 93351134-3596-4f54-b610-a3d3e8eb8391
┌─explain─────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Partition │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Skip │
│ Name: inv_idx │
│ Description: inverted GRANULARITY 1 │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
└─────────────────────────────────────────────────┘
23 rows in set. Elapsed: 0.147 sec.通过查询计划，可以看到，12939个数据块，通过inv_idx索引过滤完后，还是12939个数据块，也就是说，这个索引同样一条数据都没过滤掉。
ngrambf_v1
重头戏来了，接下来我们来创建ngrambf_v1索引。由于ngrambf_v1这个索引有一个长度n的参数，为了验证n的长度对性能的影响，而查询条件里最短的条件[INFO]长度为6， 因此我们一开始定6：
ALTER TABLE ck_log_test DROP INDEX inv_idx;
ALTER TABLE ck_log_test ADD INDEX idx_ngram1 value TYPE ngrambf_v1(6, 307200, 2, 0) GRANULARITY 1;
ALTER TABLE ck_log_test MATERIALIZE INDEX idx_ngram1;物化完成后查询结果如下：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 1a68f491-ca0d-42dd-bbbf-0a62db0a12eb
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 21.445 sec. Processed 100.61 million rows, 213.93 GB (4.69 million rows/s., 9.98 GB/s.)从查询效果来说，甚至不如前面的tokenbf_v1和inverted，扫描数据100.61 million， 也是接近全表扫描，至于是不是全表扫描，我们看一下执行计划：
EXPLAIN indexes = 1
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 2382b001-a80e-4dab-b780-1b33f4d61041
┌─explain───────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Partition │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Skip │
│ Name: idx_ngram1 │
│ Description: ngrambf_v1 GRANULARITY 1 │
│ Parts: 9/9 │
│ Granules: 12926/12929 │
└───────────────────────────────────────────────────┘
23 rows in set. Elapsed: 2.191 sec.可以看到，从12929减少到了12926，说明这个索引虽然拉胯，但是仍然过滤掉了3个数据块，说明这个索引还是有点作用的。至于说它为什么更慢了，那是因为扫描索引所花的时间，比扫描三个数据块所花的时间要更长，这样就是负优化。
既然n=6不行，我们接下来定义一个最大的长度，让n = 48，这是字符串gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop的长度：
ALTER TABLE ck_log_test DROP INDEX idx_ngram1;
ALTER TABLE ck_log_test ADD INDEX idx_ngram2 value TYPE ngrambf_v1(48, 307200, 2, 0) GRANULARITY 1;
ALTER TABLE ck_log_test MATERIALIZE INDEX idx_ngram2;物化完成后再次查询：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 67c86c21-5dc6-4b2f-847c-271c4555d23f
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 4.243 sec. Processed 15.24 million rows, 32.41 GB (3.59 million rows/s., 7.64 GB/s.)这次查询效果立竿见影。可以看到，查询速度一下子从19秒减少到了4秒多，扫描的数据也减少到了1500w，少了近十分之一。这说明索引生效了。我们来看一下查询计划：
┌─explain───────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 255/255 │
│ Granules: 20731/20731 │
│ Partition │
│ Condition: true │
│ Parts: 255/255 │
│ Granules: 20731/20731 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 255/255 │
│ Granules: 20731/20731 │
│ Skip │
│ Name: idx_ngram2 │
│ Description: ngrambf_v1 GRANULARITY 1 │
│ Parts: 230/255 │
│ Granules: 2923/20731 │
└───────────────────────────────────────────────────┘通过索引idx_ngram2过滤之后，原来20731个数据块，一下子就只剩下了2923个，数据少了十分之一。这也是它为什么快了这么多的原因。
可如果我们查询的关键词长度小于n呢，比如我们搜索gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh%') AND (value LIKE '%[INFO]%')
Query id: 6c6f76e7-26fd-4eb3-ae61-ea8dca1fa1c9
┌─count()─┐
│ 38650 │
└─────────┘
1 row in set. Elapsed: 19.996 sec. Processed 100.61 million rows, 213.94 GB (5.03 million rows/s., 10.70 GB/s.)可以看到，它又进行了全表扫描，说明当查询的关键词小于n的时候，这个索引同样是不会生效的。那么，这就要求在满足条件的情况下，n尽可能地小，才能满足更多的查询场景。
但是小到多少才是最佳值呢？前面我们已经验证过n=6不生效了。我们接下来折中一下，尝试一下n=30。
ALTER TABLE ck_log_test DROP INDEX idx_ngram2;
ALTER TABLE ck_log_test ADD INDEX idx_ngram3 value TYPE ngrambf_v1(30, 307200, 2, 0) GRANULARITY 1;
ALTER TABLE ck_log_test MATERIALIZE INDEX idx_ngram3;查询结果：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 67c86c21-5dc6-4b2f-847c-271c4555d23f
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 3.737 sec. Processed 9.97 million rows, 21.21 GB (2.67 million rows/s., 5.68 GB/s.)查询时间进一步缩短，到了3秒多。看一下查询计划：
┌─explain───────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Partition │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Skip │
│ Name: idx_ngram3 │
│ Description: ngrambf_v1 GRANULARITY 1 │
│ Parts: 9/9 │
│ Granules: 1253/12929 │
└───────────────────────────────────────────────────┘通过跳数索引过滤完后，只剩下1253个数据块了，比前面的2923还要少了一半多。说明n也并不是越接近查询的长度效果越好。
我们再将n进一步缩小到20。创建索引过程就不重复了，直接展示查询效果：
ck94 :) SELECT count() FROM ck_log_test WHERE `value` LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%' AND `value` LIKE '%[INFO]%';
SELECT count()
FROM ck_log_test
WHERE (value LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%') AND (value LIKE '%[INFO]%')
Query id: 52a46457-6b4e-43dc-bb95-930be2cb72f0
┌─count()─┐
│ 407 │
└─────────┘
1 row in set. Elapsed: 21.515 sec. Processed 99.63 million rows, 211.85 GB (4.63 million rows/s., 9.85 GB/s.)执行计划如下所示：
┌─explain───────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│ Aggregating │
│ Expression (Before GROUP BY) │
│ Filter (WHERE) │
│ ReadFromMergeTree (ck_log_test) │
│ Indexes: │
│ MinMax │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Partition │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ PrimaryKey │
│ Condition: true │
│ Parts: 9/9 │
│ Granules: 12929/12929 │
│ Skip │
│ Name: idx_ngram4 │
│ Description: ngrambf_v1 GRANULARITY 1 │
│ Parts: 9/9 │
│ Granules: 12768/12929 │
└───────────────────────────────────────────────────┘已经只能过滤掉100多个granule了，因此查询效率高不到哪里去。后面也就没有继续测试下去的必要了。
这说明：针对不同的查询场景，n并不是越小越好。
为什么会出现这种情况呢？
因为n越小，那么bloom过滤器计算出来的基数就会越大 ，那么假阳性的概率也就越高，当数据量足够多的时候，假阳性的概率就会高得离谱，这时候过滤掉的数据块也就自然少了。
ngrambf_v1源码剖析
那么ngrambf_v1的分词原理是怎样的？查询的时候又是怎样进行拆分进行匹配的呢？这恐怕要到源码里去寻找答案了。关于ngrambf_v1的代码实现主要在MergeTreeFullText.cpp中。
数据插入
每个skipping data index 都会实现一个update的函数，该函数的作用是将插入的数据在布隆过滤器里增加对应索引。如果类型是array，它会将数组里的每个元素都拿出来进行分词，而String类型则比较简单，直接拿字符串进行分词就行了，分词的逻辑在stringPaddedToBloomFilter函数中。
我们可以看到，它用了一个while循环来迭代：
while (cur < length && static_cast<const Derived *>(this)->nextInString(data, length, &cur, &token_start, &token_len))
bloom_filter.add(data + token_start, token_len);
上例中，data是字段的内容，length是字段的长度，cur则是token分词的偏移量起始位置，而具体的分词的实现，则在nextInString函数中。
bool NgramTokenExtractor::nextInString(const char * data, size_t length, size_t * __restrict pos, size_t * __restrict token_start, size_t * __restrict token_length) const
{
*token_start = *pos;
*token_length = 0;
size_t code_points = 0;
for (; code_points < n && *token_start + *token_length < length; ++code_points)
{
size_t sz = UTF8::seqLength(static_cast<UInt8>(data[*token_start + *token_length]));
*token_length += sz;
}
*pos += UTF8::seqLength(static_cast<UInt8>(data[*pos]));
return code_points == n;
}
UTF8::seqLength 会取出data[*token_start + *token_length]位置一个完整的UTF-8的字符的长度，也就是说，如果是一个汉字的话，它计算出来的sz应该是3, 而我们可以看到最终判断能不能分词的依据是code_points是否和n相等，而不是token_length，所以一个汉字也只占n的一个长度。
因此，nextInString的逻辑就是判断data的内容够不够长度n来分词，如果可以分词，那么将分词的内容存在token变量中。并且在外层的while循环中加入到bloom过滤器中。
因为有了外层的while循环，所以可以看做它是在data上，以n做为窗口，逐级滑动的。
而加入布隆过滤器的逻辑就比较简单了，主要根据创建索引时，指定的布隆过滤器的长度，hash函数的个数，以及SEED来计算哈希值，存入bitmap中即可。
void BloomFilter::add(const char * data, size_t len)
{
size_t hash1 = CityHash_v1_0_2::CityHash64WithSeed(data, len, seed);
size_t hash2 = CityHash_v1_0_2::CityHash64WithSeed(data, len, SEED_GEN_A * seed + SEED_GEN_B);
for (size_t i = 0; i < hashes; ++i)
{
size_t pos = (hash1 + i * hash2 + i * i) % (8 * size);
filter[pos / (8 * sizeof(UnderType))] |= (1ULL << (pos % (8 * sizeof(UnderType))));
}
}
当然我们知道长度越长，hash函数越多，假阳性的概率越低，但是计算也越耗时，需要更多的存储空间。因此，这是一个见仁见智的事情，具体看数据规模来定。
数据查询
查询的逻辑在MergetreeDataSelectExecutor.cpp这个文件，具体是在filterMarksUsingIndex函数中。在此之前，我们需要搞明白mark在clickhouse中是个什么概念，mark记录的是每稀疏索引在列存中的位置。根据mark，我们很快就能找到每个数据块的位置。
当我们拿到一个数据块后，就可以根据跳数索引来过滤数据了。基于布隆过滤器的特性，如果布隆过滤器里查询不到这个数据块，那么可以判断这个数据块里一定没有我们要的数据，那么这个数据块就可以直接跳过。但是如果能找到，却并不能直接确定这个数据块里有我们需要的数据，毕竟还有存在假阳性的可能。
所以这个查询的函数叫mayBeTrueOnGranule， 这个mayBe就非常形象了。
MergeTreeConditionFullText这个类列举了很多会走到跳数索引的查询场景，如EQUALS， NOT_EQUALS，HAS, IN, NOT_IN, MULTI_SEARCH, NOT, AND, OR, FALSE, TRUE等。
那么like属于哪个场景呢？like其实是属于EQUALS，这个在MergeTreeConditionFullText的构造函数， 具体在traverseTreeEquals函数中：
else if (function_name == "like")
{
out.key_column = *key_index;
out.function = RPNElement::FUNCTION_EQUALS;
out.bloom_filter = std::make_unique<BloomFilter>(params);
const auto & value = const_value.get<String>();
token_extractor->stringLikeToBloomFilter(value.data(), value.size(), *out.bloom_filter);
return true;
}
其中，stringLikeToBloomFilter就是将like的短语进行分词，然后与布隆过滤进行匹配了。
它同样是一个while循环：
void stringLikeToBloomFilter(const char * data, size_t length, BloomFilter & bloom_filter) const override
{
size_t cur = 0;
String token;
while (cur < length && static_cast<const Derived *>(this)->nextInStringLike(data, length, &cur, token))
bloom_filter.add(token.c_str(), token.size());
}
说明它匹配的时候，也是根据n作为窗口进行滑动匹配的。
具体的匹配逻辑在nextStringLike里。
bool NgramTokenExtractor::nextInStringLike(const char * data, size_t length, size_t * pos, String & token) const
{
token.clear();
size_t code_points = 0;
bool escaped = false;
// 我们以 LIKE '%gfdsamnbvcxz-asdfghjkl-poiuytrewqlkjh-qwertyuiop%'， n = 30 举例，来人工跑一下这一段代码
for (size_t i = *pos; i < length;)
{
// 1. 一开始escaped = false， 这段逻辑进不去
if (escaped && (data[i] == '%' || data[i] == '_' || data[i] == '\\'))
{
token += data[i];
++code_points;
escaped = false;
++i;
}
else if (!escaped && (data[i] == '%' || data[i] == '_'))
{
//2. 因为开头有一个%， 所以一开始会进入到这个branch，将token清空
//5. 反之，如果还没达到n长度就遇到了%，那么会把token清空，也就是说，like的短语小于n,该索引就不会生效了
/// This token is too small, go to the next.
token.clear();
code_points = 0;
escaped = false;
*pos = ++i;
}
else if (!escaped && data[i] == '\\')
{
escaped = true;
++i;
}
else
{
//3. 从第二轮循环开始，正常情况下会进入到这段逻辑，i 和 code_points都会不断的++
const size_t sz = UTF8::seqLength(static_cast<UInt8>(data[i]));
for (size_t j = 0; j < sz; ++j)
token += data[i + j]; //把完整的UTF8字符放入token中
i += sz;
++code_points;
escaped = false;
}
// 4. 因为n = 30, 也就是还没遍历完就会进入该逻辑，所以token就是取前n个字符
if (code_points == n)
{
*pos += UTF8::seqLength(static_cast<UInt8>(data[*pos]));
return true;
}
}
return false;
}
从上述的代码逻辑可以看出，如果like的短语长度小于n，其实是无法分词的，那么也就意味着索引无法被命中，这也就是上例中，LIKE的字段小于n，索引未生效的原因。
需要注意的是，这地方虽然也是调用了bloom_filter.add方法，但与前面的bloom_filter并不是同一个，此处的叫out布隆过滤器，而前面我们插入的时候的布隆过滤器则是in。
然后就是判断in的bloom_filter中有没有contains前面构造出来的out的bloom_filter就行了。
else if (element.function == RPNElement::FUNCTION_EQUALS
|| element.function == RPNElement::FUNCTION_NOT_EQUALS
|| element.function == RPNElement::FUNCTION_HAS)
{
rpn_stack.emplace_back(granule->bloom_filters[element.key_column].contains(*element.bloom_filter), true);
if (element.function == RPNElement::FUNCTION_NOT_EQUALS)
rpn_stack.back() = !rpn_stack.back();
}
总结
本文着重介绍了ngrambf_v1在日志存储场景，模糊查询的加速能力。
当然实际上并不是无脑使用这个跳数索引就行了，而是要根据实际的查询场景来定。本文之所以能这么用，是因为数据特征以及查询条件决定。因为查询条件里带有[]和-，导致tokenbf_v1和inverted都失效，因此只能使用ngrambf_v1索引。而数据的循环写入，导致tokenbf_v1分词的token在每一个granule中都存在，因此也无法根据token来简单的做过滤。这就给我们提了个醒，要求我们在做主键索引时，尽量考虑存储排布，使数据分布相对合理，如果每个数据块中都有我们需要的目标数据，即使二级索引设置得再好，也无法过滤掉任何一个数据块，最终还是会全表扫描。
虽然从本文演示的效果来看，ngrambf_v1的优化效果明显好于tokenbf_v1，但并不是说tokenbf_v1一无是处，只能说在本文的查询场景下不适用而已。inverted倒排索引由于刚推出不久，尚属于实验性质的，暂时倒是不推荐在生产环境使用。
而ngrambf_v1索引虽然通用性更强，但n的设置比较考验功底，需要根据具体的查询场景来决定。从查询通用性上来说，n越小越好，但是当数据量上去了，n太小的话，产生假阳性的概率就会增大，这就导致很多本来应该要被过滤掉的数据块反而不能过滤掉。
总之，关于ClickHouse的模糊查询，一定要灵活运用，不能死板的一股脑儿靠二级索引一条路走到黑，比如本文示例中，所有的优化其实都是针对后面的长文本的，而不是针对另一个条件[INFO]，因为这个条件重复太多了，几乎每个granule都有，无法通过索引来做进一步优化。事实上，如果确定搜索条件一定或大概率会有日志级别的话，不妨将这其提出来单独做一个字段，然后通过物化视图或者projection的手段去优化。
最后再提一句：跳数索引是MergeTree引擎才有的特性，其他Engine并无此用法。
本专栏知识点是通过<零声教育>的系统学习，进行梳理总结写下文章，对C/C++课程感兴趣的读者，可以点击链接，查看详细的服务：C/C++Linux服务器开发/高级架构师