概述
模糊查詢在日志存儲的場景中非常普遍。ClickHouse作為大數(shù)據(jù)分布式引擎，理所當然地會被作為日志存儲的備選方案。事實上使用ClickHouse作為日志存儲方案，業(yè)界目前也已經(jīng)在多家企業(yè)落地，比如Uber、石墨文檔、映客、快手、攜程、唯品會等。
日志查詢的一個最大的特點是，幾乎極少涉獵點查詢，而模糊查詢則占據(jù)了絕大部分使用場景。這也是為什么ES憑借其逆天的分詞能力在日志存儲領域殺瘋了的原因。但ES存儲的瓶頸近些年也逐漸顯現(xiàn)， 如壓縮率低，需要較大的存儲成本，當數(shù)據(jù)量過大時，查詢性能也比較差。因此，近些年越來越多的企業(yè)開始尋求ES的替代方案。ClickHouse正是選擇之一。
那么，ClickHouse有什么優(yōu)秀的特性，能在一眾大數(shù)據(jù)存儲組件中脫穎而出，殺出一片天地呢？
首先，不論是寫入性能，還是存儲壓縮率，ClickHouse相比ES，都是壓倒性優(yōu)勢。但實事求是地說，ClickHouse擅長的場景其實并不包含模糊查詢，但對模糊查詢也提供了一些優(yōu)化的空間。其中最具代表性的，就是跳數(shù)索引。
跳數(shù)索引
ClickHouse中，跳數(shù)索引又稱為二級索引。它是獨立于主鍵索引之外的另一類索引。
跳數(shù)索引針對不同的查詢場景，提供了不同索引類型，如針對去重的set，針對計算極值的minmax，當然還有針對全文搜索的布隆過濾器家族。
關于跳數(shù)索引的概念以及介紹，本文就不多做展開了，感興趣的可以去看官網(wǎng)文檔，介紹文檔：?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進行分詞的布隆過濾器索引。它會將長文本中的單詞按非字母數(shù)字字符（如空格、-，[]等）進行分詞，每個分詞就是一個token，然后將這個token映射到布隆過濾器的bitmap中。 - 舉個例子，?
https://clickhouse.com/docs/en/engines/table-engines/mergetree-family/mergetree#table_engine-mergetree-data_skipping-indexes這個字符串，經(jīng)過分詞后，會變成如下的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進行分詞，而是根據(jù)長度進行分詞。 - 同樣舉個例子，假設將
A short string按照n=4進行分詞，得到的結果如下 ：
-
['A sh', ' sho', 'shor', 'hort', 'ort ', 'rt s', 't st', ' str', 'stri', 'trin', 'ring']-
-
ngrambf_v1相比于tokenbf_v1，優(yōu)點是終于支持特殊字符，甚至漢字的分詞了 - 缺點是
n的長度一旦確定好就不好修改，如果查詢的關鍵詞長度小于n，那么該索引也不會生效 - 有人說既然如此我把
n設置的盡量小一點不就行了？事實上也不行，這點我們后面實戰(zhàn)的時候再說。 - 因此，
ngrambf_v1非常看具體的查詢場景，如果提前知道查詢的SQL，針對性的設置n的長度，是有非常大的優(yōu)化效果的，比較不適用那種通用的天馬行空的查詢。
-
-
inverted- 很多人一聽倒排索引，第一感覺大概是：就是它了。無限接近
ES分詞的一個索引。 - 這么說未免高看這個倒排索引的能力了。它的原理確實和
ES類似 ，但分詞邏輯仍然是和tobenbf_v1是一樣的，也就是說它同樣是針對non-alphanumeric進行分詞的，同樣不支持特殊字符和漢字的查詢。只不過比tokenbf_v1占用更少的存儲資源，相同查詢場景下，比tokenbf_v1更優(yōu)秀一些罷了。但這也是在索引被命中的前提下，如果索引命中不了，再優(yōu)秀也無用武之地。
- 很多人一聽倒排索引，第一感覺大概是：就是它了。無限接近
針對以上三種索引，最適合的應該是ngrambf_v1， 當然，為了公平，我們在接下來的實戰(zhàn)中，使用相同的查詢場景，來驗證索引的優(yōu)化能力。
實戰(zhàn)演練
為了盡量真實地模擬日志存儲場景 ，我使用一個Java程序循環(huán)寫日志，日志內容包括Java異常、Python的backtrace，?C++的backtrace等，都是一些比較長的長文本。一共循環(huán)寫入1億數(shù)據(jù)。
數(shù)據(jù)的結構大致如下：
{
"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`);這里省略數(shù)據(jù)寫入的過程，最終數(shù)據(jù)如下：
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的數(shù)量。
tokenbf_v1
創(chuàng)建索引：
ALTER TABLE ck_log_test ADD INDEX idx_string_value value TYPE tokenbf_v1(30720, 2, 0) GRANULARITY 1;以上只是將索引創(chuàng)建出來了，對于存量數(shù)據(jù)，并不能生效，想要對存量數(shù)據(jù)生效，需要執(zhí)行物化操作：
ALTER TABLE ck_log_test MATERIALIZE INDEX idx_string_value;創(chuàng)建索引本身是一個輕量級操作，但物化操作是一個比較重的操作，雖然sql執(zhí)行立即就結束了，但實際還在后臺執(zhí)行，可以通過SELECT * FROM system.mutations WHERE is_done = '0';來查看物化進度， 表中的數(shù)據(jù)越多，物化所需要的時間就越長。
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秒，掃描數(shù)據(jù)10061萬條，這就是全表掃描了。說明雖然我們創(chuàng)建了一個跳數(shù)索引，但是對查詢沒有任何的優(yōu)化效果。接下來我們通過執(zhí)行計劃來印證這一點。
在SQL語句前加上EXPLAIN，即可查看執(zhí)行計劃，再加上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.執(zhí)行計劃如何看？
Filter一開始，是9個part，一共12929個索引。每個索引粒度都是8192， 所以一共是?8192 * 12929條數(shù)據(jù)，這個和我們的數(shù)據(jù)總量是對應得上的。
首先有一個MinMax，這個一般是根據(jù)建表時的ORDER BY的字段進行篩選，因為我們沒有帶任何@timestamp的篩選范圍，所以MinMax篩選完還是12929個數(shù)據(jù)塊。
然后是Partition，也就是分區(qū)。正常來說， 如果按天分區(qū)，你查最近一小時數(shù)據(jù)，它肯定不會走到昨天的分區(qū)里去查找數(shù)據(jù)，可以通過這種手段直接排除掉一些不可能走到的分區(qū)。因為我們的數(shù)據(jù)都在同一個分區(qū)，所以過濾不掉，還是12929個數(shù)據(jù)塊。
接下來是PrimaryKey， 我們沒有顯式地指定主鍵索引，所以默認使用ORDER BY的字段作為主鍵索引，也是沒有過濾掉數(shù)據(jù)，還是12929.
注意最后面的Skip，這個指的就是跳數(shù)索引，可以看到idx_string_value正是我們創(chuàng)建的索引，說明這個查詢，這個索引確實走到了，但是過濾完，還是12929個數(shù)據(jù)塊，說明雖然走到了這個索引，但是一條數(shù)據(jù)都沒有過濾掉。
inverted
同樣，先創(chuàng)建索引：
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; ---創(chuàng)建倒排索引
ALTER TABLE ck_log_test MATERIALIZE INDEX inv_idx; ---物化數(shù)據(jù)物化完成后，查詢數(shù)據(jù)：
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秒，掃描數(shù)據(jù)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個數(shù)據(jù)塊，通過inv_idx索引過濾完后，還是12939個數(shù)據(jù)塊，也就是說，這個索引同樣一條數(shù)據(jù)都沒過濾掉。
ngrambf_v1
重頭戲來了，接下來我們來創(chuàng)建ngrambf_v1索引。由于ngrambf_v1這個索引有一個長度n的參數(shù)，為了驗證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，掃描數(shù)據(jù)100.61 million， 也是接近全表掃描，至于是不是全表掃描，我們看一下執(zhí)行計劃：
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個數(shù)據(jù)塊，說明這個索引還是有點作用的。至于說它為什么更慢了，那是因為掃描索引所花的時間，比掃描三個數(shù)據(jù)塊所花的時間要更長，這樣就是負優(yōu)化。
既然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秒多，掃描的數(shù)據(jù)也減少到了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個數(shù)據(jù)塊，一下子就只剩下了2923個，數(shù)據(jù)少了十分之一。這也是它為什么快了這么多的原因。
可如果我們查詢的關鍵詞長度小于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盡可能地小，才能滿足更多的查詢場景。
但是小到多少才是最佳值呢？前面我們已經(jīng)驗證過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 │
└───────────────────────────────────────────────────┘通過跳數(shù)索引過濾完后，只剩下1253個數(shù)據(jù)塊了，比前面的2923還要少了一半多。說明n也并不是越接近查詢的長度效果越好。
我們再將n進一步縮小到20。創(chuàng)建索引過程就不重復了，直接展示查詢效果：
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.)執(zhí)行計劃如下所示：
┌─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 │
└───────────────────────────────────────────────────┘已經(jīng)只能過濾掉100多個granule了，因此查詢效率高不到哪里去。后面也就沒有繼續(xù)測試下去的必要了。
這說明：針對不同的查詢場景，n并不是越小越好。
為什么會出現(xiàn)這種情況呢？
因為n越小，那么bloom過濾器計算出來的基數(shù)就會越大 ，那么假陽性的概率也就越高，當數(shù)據(jù)量足夠多的時候，假陽性的概率就會高得離譜，這時候過濾掉的數(shù)據(jù)塊也就自然少了。
ngrambf_v1源碼剖析
那么ngrambf_v1的分詞原理是怎樣的？查詢的時候又是怎樣進行拆分進行匹配的呢？這恐怕要到源碼里去尋找答案了。關于ngrambf_v1的代碼實現(xiàn)主要在MergeTreeFullText.cpp中。
數(shù)據(jù)插入
每個skipping data index?都會實現(xiàn)一個update的函數(shù)，該函數(shù)的作用是將插入的數(shù)據(jù)在布隆過濾器里增加對應索引。如果類型是array，它會將數(shù)組里的每個元素都拿出來進行分詞，而String類型則比較簡單，直接拿字符串進行分詞就行了，分詞的邏輯在stringPaddedToBloomFilter函數(shù)中。
我們可以看到，它用了一個while循環(huán)來迭代：
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分詞的偏移量起始位置，而具體的分詞的實現(xiàn)，則在nextInString函數(shù)中。
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, 而我們可以看到最終判斷能不能分詞的依據(jù)是code_points是否和n相等，而不是token_length，所以一個漢字也只占n的一個長度。
因此，nextInString的邏輯就是判斷data的內容夠不夠長度n來分詞，如果可以分詞，那么將分詞的內容存在token變量中。并且在外層的while循環(huán)中加入到bloom過濾器中。
因為有了外層的while循環(huán)，所以可以看做它是在data上，以n做為窗口，逐級滑動的。
而加入布隆過濾器的邏輯就比較簡單了，主要根據(jù)創(chuàng)建索引時，指定的布隆過濾器的長度，hash函數(shù)的個數(shù)，以及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函數(shù)越多，假陽性的概率越低，但是計算也越耗時，需要更多的存儲空間。因此，這是一個見仁見智的事情，具體看數(shù)據(jù)規(guī)模來定。
數(shù)據(jù)查詢
查詢的邏輯在MergetreeDataSelectExecutor.cpp這個文件，具體是在filterMarksUsingIndex函數(shù)中。在此之前，我們需要搞明白mark在clickhouse中是個什么概念，mark記錄的是每稀疏索引在列存中的位置。根據(jù)mark，我們很快就能找到每個數(shù)據(jù)塊的位置。
當我們拿到一個數(shù)據(jù)塊后，就可以根據(jù)跳數(shù)索引來過濾數(shù)據(jù)了?；诓悸∵^濾器的特性，如果布隆過濾器里查詢不到這個數(shù)據(jù)塊，那么可以判斷這個數(shù)據(jù)塊里一定沒有我們要的數(shù)據(jù)，那么這個數(shù)據(jù)塊就可以直接跳過。但是如果能找到，卻并不能直接確定這個數(shù)據(jù)塊里有我們需要的數(shù)據(jù)，畢竟還有存在假陽性的可能。
所以這個查詢的函數(shù)叫mayBeTrueOnGranule， 這個mayBe就非常形象了。
MergeTreeConditionFullText這個類列舉了很多會走到跳數(shù)索引的查詢場景，如EQUALS，?NOT_EQUALS，HAS,?IN,?NOT_IN,?MULTI_SEARCH,?NOT,?AND,?OR,?FALSE,?TRUE等。
那么like屬于哪個場景呢？like其實是屬于EQUALS，這個在MergeTreeConditionFullText的構造函數(shù)， 具體在traverseTreeEquals函數(shù)中：
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循環(huán)：
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());
}
說明它匹配的時候，也是根據(jù)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. 從第二輪循環(huán)開始，正常情況下會進入到這段邏輯，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在日志存儲場景，模糊查詢的加速能力。
當然實際上并不是無腦使用這個跳數(shù)索引就行了，而是要根據(jù)實際的查詢場景來定。本文之所以能這么用，是因為數(shù)據(jù)特征以及查詢條件決定。因為查詢條件里帶有[]和-，導致tokenbf_v1和inverted都失效，因此只能使用ngrambf_v1索引。而數(shù)據(jù)的循環(huán)寫入，導致tokenbf_v1分詞的token在每一個granule中都存在，因此也無法根據(jù)token來簡單的做過濾。這就給我們提了個醒，要求我們在做主鍵索引時，盡量考慮存儲排布，使數(shù)據(jù)分布相對合理，如果每個數(shù)據(jù)塊中都有我們需要的目標數(shù)據(jù)，即使二級索引設置得再好，也無法過濾掉任何一個數(shù)據(jù)塊，最終還是會全表掃描。
雖然從本文演示的效果來看，ngrambf_v1的優(yōu)化效果明顯好于tokenbf_v1，但并不是說tokenbf_v1一無是處，只能說在本文的查詢場景下不適用而已。inverted倒排索引由于剛推出不久，尚屬于實驗性質的，暫時倒是不推薦在生產環(huán)境使用。
而ngrambf_v1索引雖然通用性更強，但n的設置比較考驗功底，需要根據(jù)具體的查詢場景來決定。從查詢通用性上來說，n越小越好，但是當數(shù)據(jù)量上去了，n太小的話，產生假陽性的概率就會增大，這就導致很多本來應該要被過濾掉的數(shù)據(jù)塊反而不能過濾掉。
總之，關于ClickHouse的模糊查詢，一定要靈活運用，不能死板的一股腦兒靠二級索引一條路走到黑，比如本文示例中，所有的優(yōu)化其實都是針對后面的長文本的，而不是針對另一個條件[INFO]，因為這個條件重復太多了，幾乎每個granule都有，無法通過索引來做進一步優(yōu)化。事實上，如果確定搜索條件一定或大概率會有日志級別的話，不妨將這其提出來單獨做一個字段，然后通過物化視圖或者projection的手段去優(yōu)化。
最后再提一句：跳數(shù)索引是MergeTree引擎才有的特性，其他Engine并無此用法。文章來源：http://www.zghlxwxcb.cn/news/detail-812146.html
本專欄知識點是通過<零聲教育>的系統(tǒng)學習，進行梳理總結寫下文章，對C/C++課程感興趣的讀者，可以點擊鏈接，查看詳細的服務：C/C++Linux服務器開發(fā)/高級架構師文章來源地址http://www.zghlxwxcb.cn/news/detail-812146.html
到了這里，關于clickhouse 代替 es 如何對文檔做模糊查詢？的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
