Full text search(FTS) 技术调研

发表于 |

主要介绍 FTS 的一些实现。

分词技术

ngram

字典结构

ngram bloomfilter

  • 生成 N-gram： 将一个输入字符串生成所有可能的 N-gram。
  • 存储到布隆过滤器： 对每个 N-gram 使用多个哈希函数，将其存储到布隆过滤器中。

查询： 对查询的字符串生成对应的 N-gram，逐个检查它们是否存在于布隆过滤器中。

  • 如果布隆过滤器判定所有 N-gram 存在，说明可能是匹配。
  • 如果至少有一个 N-gram 不存在，可以确定不匹配。

缺点：

  • 存在 FP
  • 不支持删除

BTree

跳表

KV 结构

存储分词后的倒排索引

1
2
3
4
5
6
7
"OceanBase" -> [Doc1, Doc2]
"is" -> [Doc1]
"a" -> [Doc1]
"distributed" -> [Doc1]
"supports" -> [Doc2]
"full-text" -> [Doc2]
"search" -> [Doc2]

FST(Finite-State Transducer)

FST 是一种 Trie 树的结构，被用在倒排索引的词典中。所以，它是用来组织 term 的结构。

对于大量的 term，需要考虑：

  • 这些字符串有大量公共前缀，直接存储会浪费空间
  • 我们希望能快速地按字典序查找 term，例如支持前缀查询，或者范围查询

考虑

1
2
3
cat → 1
car → 2
dog → 3

它的 FST 可能如下

1
2
3
4
5
6
7
8
9
   (start)
     |
     c (out=0)
    / \
   a    d
  /  \    \
r(2)  t(1)  o
            |
           g(3)

MultiValue Index

Tantivy

主要结构

Posting list

在倒排索引中，每一个 term 对应一个 posting list，表示它出现的 docID

1
"rust" -> [{doc1, tf1, ...}, {doc3, tf3, ...}, ...]

Fast field

Tantivy 中的普通字段一般是 STORED | INDEXED 属性。其中：

  • STORED 表示需要存储原文，以便后续返回结果
    存储在 .store 文件中。
  • INDEXED 表示要基于这个字段构建倒排索引
    会对文本进行分词，并且构建 term -> posting list。
    存储在 .fast 文件中。

Tantivy 还支持 FAST 属性。用来加速处理：

  • 按数值字段排序
    如 order by timestamp desc
  • 聚合统计
    如 avg(price)
  • 按数值过滤
    如 price < 100

Fast Field 仅支持定长、可序列化的类型。例如各种整数、布尔值等，而 TEXT 是不支持的。

FieldType

  • TEXT 可分词字符串
  • STRING 不可分词字符串

不同的 FieldType 可以指定不同的分词器。

TermList

一个 Term 的表示如下：

  • 0..4 是 field id
  • 4..5 是 field type
  • 5.. 是 payload

真正写进 .term 文件 FST 的 key 不含前 5 字节头，只放 payload 部分。原因：

  • 每个字段已经有独立的 .term 文件，field id 无需重复
  • 同名字段在不同 segment 的 FST 可以直接合并，而不用担心头部不一致

内存中需要加上 field id 的原因：

  • 全局区分同名字段
    如 title:apple 和 body:apple。

查询

  • TermQuery
    精确匹配某个 term。
  • PhraseQuery
    匹配多个 term 连续出现的短语。
  • AllQuery
  • RangeQuery
  • RegexQuery
  • FuzzyQuery
  • BooleanQuery

向量搜索和 FTS

Inverted File Index(IVF)

Inverted File Index(IVF) 将向量搜索和倒排索引联系到了一起。

主要思想是：

  • 使用 K-means 算法对向量进行分簇，每一簇的中心点 C1/C2/… 就是倒排表的 term

    1
    2
    C1 -> [v1, v5, v7, ...]
    C2 -> [v2, v4, v6, ...]

  • 对查询向量 q 计算它到所有中心点的距离，选出最接近的几个簇，只在这些簇中寻找最近邻

IVF 的核心思想是 向量在高维空间中是可以粗聚类的。它用的多，原因在于：

  • 高维向量在实际应用中通常可聚类
  • 可调节性强
    如果聚类效果不好，可以增大 nprobe，搜索更多的簇，从而提高召回率。
    如果聚类效果好，则可以减小 nprobe，提高搜索的速度。
  • 可以和 Product Quantization 联用