ClickHouse字符串匹配探究

0. 总览

1. 在CK中把⽂本串(text)称为haystack,把模式串(pattern)称为needle. 2. CK中的字符串匹配⽀持⼤⼩写敏感与不敏感(Case Sensitive/Insensitive).

3. CK中⽀持ascii和utf-8两种编码格式. 它们的主要区别在于ascii是定长编码,每个char均为1字节,⽽utf-8是变长编码,最长⽀持6字节的char,具体长度⽤⼆进制下前驱1的个数表⽰.

4. CK中函数处理数据时候常把数据分为Constant和Vector,例如locate(k1,'a')中k1就是Vector,'a'则是Constant.分别表⽰参数和具体列数据.显然参数总是较少量的(很多时候是⼀个,取决于具体函的数⼊参形式),⽽具体⼀列则往往有许 5. 根据bdtc_2019⾥的描述,CK总体是根据以下规则选择字符串算法:

* Volnitsky algorithm when needle is constant; 在needle是Constant时使⽤Volnitsky algorithm.

* SIMD optimized brute-force for non-constant needle; 在needle是⾮Constant时使⽤SIMD优化的暴⼒匹配.

* variation of Volnitsky algorithm for a set of constant needles; 在needle是多个constant时使⽤Volnitsky algorithm的变体(此处应该是指MultiVolnitsky). * re2 and hyperscan for regular expressions; ⽤re2和hyperscan去处理正则表达式.

```cpp

// apache doris中获取utf-8编码长度的函数

inline size_t get_utf8_byte_length(unsigned char byte) { size_t char_size = 0;

if (byte >= 0xFC) { // 1111110... char_size = 6;

} else if (byte >= 0xF8) { //111110... char_size = 5;

} else if (byte >= 0xF0) { //11110... char_size = 4;

} else if (byte >= 0xE0) { //1110... char_size = 3;

} else if (byte >= 0xC0) { //110... char_size = 2; } else {

char_size = 1; }

return char_size;}```

1. ⼦串搜索 position

对应的具体函数是position和locate, 它的功能是找到needle在haystack中最早出现的位置.代码实现在`ClickHouse/src/Functions/PositionImpl.h`.

在这⾥根据输⼊参数是常量(Constant)还是列数据(Vector)区分出四种处理⽅式,需要注意的是,由于position函数⼊参的格式,所以这⾥的constant都只有⼀个字符串: 1. vectorConstant 2. constantConstant 3. vectorVector 4. constantVector未完待续