You need to enable JavaScript to run this app.
导航
使用向量检索
最近更新时间:2024.03.14 11:22:40首次发布时间:2024.03.14 11:22:40

本文主要介绍向量检索(Vector Search)功能,以及如何创建和使用向量索引。

概述

向量是一种常见的非结构化数据表现形式。基于向量相似度的 KNN 计算广泛使用于图像搜索、多模态搜索、推荐、大模型推理等场景。ByteHouse 企业版已提供向量数据的管理与近似度查询功能,同时通过支持多种常见近近似最近邻搜索算法(Approximate Nearest Neighbor,ANN)算法来提升检索性能,以提供对非结构化数据的处理能力。
ByteHouse 企业版当前支持 HNSW(hnswlib)、Faiss 两个算法库, 后续还会对 DiskANN 等算法库提供支持。

  • HNSW (Hierarchical Navigable Small World graphs,分层-可导航-小世界-图)索引:热门的基于图的近似最近邻搜索算法(ANN)。HNSW 是一种非常流行和强大的算法,具有超快的搜索速度和出色的召回率。
  • Faiss:Facebook 开源的 ANN 算法库,包含了倒排(IVF,Inverted File)、PQ、SQ 等多种类型的索引,同时多种索引还可以组合使用。我们主要使用 Faiss 的 IVF 类索引,同时支持 PQ、SQ 等向量压缩方法,以减少索引的内存使用。

创建向量索引

构建索引需要遍历数据表中所有值,在大规模的数据集上,需要通过一些参数来限制构建的过程,下面只简述几个参数的使用方法,具体含义请查询 HNSW 算法相关资料。

说明

本文聚焦于通过ByteHouse使用向量检索这一高级功能。
关于 HNSW 算法相关资料较为复杂,这里不再赘述,您可以查阅相关资料并系统性学习。

常用参数如下:

  1. M:默认是 16,范围[2,100]。通过这个参数,创建索引时限制了算法中的连接数量。构建时间随着m值的减小而减小,测试结果对于低召回率和/或者低维数据,较小的m通常产生更好的结果。而对于高召回率和/或者高维数据,较大的m更好。
  2. EF_CONSTRUCTION:EF_CONSTRUCTION 是索引构建期间使用的候选列表大小,默认是200,范围在[4,1000]。EF_CONSTRUCTION 的值越大,索引构建越慢。也即是构建速度与索引质量可以通过此参数进行调整。增加这个值不会带来性能上的提升,可以提高准确率,但换来更多的构建时间。EF_CONSTRUCTION 和 M 之间的关系是 EF_CONSTRUCTION 需要大于等于 M 值的2倍。
  3. ef_search:默认值是40,范围[1,1000]。较小的ef_search值将有更快的查询,但有不准确的风险。

下面,分别介绍 HNSW 和 Faiss 的创建索引语法,以及查询方法。

HNSW

语法

HNSW 使用时可以定义参数 M 和 EF_CONSTRUCTION 两个参数来在性能和准确度之间做权衡。一般来说 M 越大,EF_CONSTRUCTION 越大,索引构建时间越长,准确度越高,搜索 latency 越高。

INDEX v1 vector TYPE HNSW('DIM=960, METRIC=COSINE, M=32, EF_CONSTRUCTION=512')

在创建表时添加索引
一个典型的构造 HNSW 索引的语句如下:

CREATE TABLE test_ann
(
    `id` UInt64,
    `vector` Array(Float32),
    INDEX v1 vector TYPE HNSW('DIM=960, METRIC=COSINE, M=32, EF_CONSTRUCTION=512')
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 1024

为已存在的表添加索引
除此之外,也可以通过 Allter add index 的方式来为已存在的表添加索引。

ALTER TABLE test_ann ADD INDEX v1 vector TYPE HNSW('DIM=960, METRIC=COSINE')

一个 HAMMING 距离索引的构建语句如下:

CREATE TABLE test_ann
(
    `id` UInt64,
    `simhash` Int64,
    INDEX v1 simhash TYPE HNSW('METRIC=HAMMING, M=32, EF_CONSTRUCTION=500') # dim 设置为 64
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 1024

注意事项:

  • HAMMING 度量方式只能建在 Int64 类型列上

参数说明

  • 索引只接受一个参数,类型为 String,内部的定义格式为 k1=v1, k2=v2, ... ,
  • DIM 是一个必须的参数(HAMMING 除外),代表索引对应 vector 的维度信息,必须与 vector 实际的维度一致。
  • METRIC 参数定义了建立索引时的度量方式。目前 HNSW 以及 Faiss 都支持 L2 与 COSINE 距离。HNSW 还另外支持 HAMMING 距离(仅适用于 Int64 类型数据,需要与 bitHammingDistance 函数结合使用。METRIC 参数可以不指定,缺省值为 L2。需要说明的是,后续只有使用对应 metric 的 distance 函数,才能执行基于索引的查询链路。例如,索引中 metric 为 L2 的话,后续查询需使用 L2Distance 函数进行查询才能使用对应索引,同理,metric 为 COSINE 时,需要使用 cosineDistance 函数进行查询。

注意事项

  • 目前一张表仅支持构建一个 vector index。如果为一个 vector column 定义多个 vector index,或者为多个 vector column 定义 vector index,系统均会报错;
  • 如果插入数据中出现了空 vector 行,如果定义了类似上述 cons_vec_len 的长度检测 constraint,则插入时会报错。如果已经插入成功了,那么在 build index 过程中也会有维度一致性检测,如果发现有维度不一致情况,也会报错,该 part 构建 index 失败。

查询语法

查询时,可以通过设定 hnsw_ef_s 参数来控制准确度和 latency,该值越大,准确度越高,latency 越长,大于 ef_construction 参数后,理论上准确度不会有更大提升

使用方法如下

select
    id, 
    dist 
from test_ann 
order by cosineDistance(vector, [query_vector]) as dist 
limit 100 
settings enable_new_ann=1, hnsw_ef_s=200

说明:

  • 在设置 enable_new_ann 为 1 时,才会进行基于我们新实现的 ann 查询路径执行;
  • 目前只有带有 order by {metric}Distance limit k 这种模式的查询才会使用向量索引进行计算

此外,还支持带有 prewhere 的混合查询使用方式,比如

select 
    id,
    label,
    dist 
from test_ann 
prewhere id > 1000
order by cosineDistance(vector, [query_vector]) as dist 
limit 100 
settings enable_new_ann=1

Faiss

语法

CREATE TABLE test_ann
(
    `id` UInt64,
    `vector` Array(Float32),
    INDEX v1 vector TYPE Faiss('Basic information', 'Index key', 'Build parameters')
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

参数说明
Faiss index的创建语法如下, 包括以下参数:

参数

是否必选

描述

举例

Basic information

必选

数据的维度信息的必须的,除此之外还可以指定metric type。

'DIM=960, METRIC=COSINE'

Index key

可选

Index信息,不同的index决定了准确度,性能和资源使用,没有最优的index,不同index的选择是这3个维度的tradeoff, 最常用的index是IVFPQ,IVF{$nlist},PQ{$m}需要指定nlist和m这2个参数。

'IVF1024,PQ64'

Build parameters

可选

这个参数是控制准确度和性能tradeoff的参数。

'nprobe=512, k_factor_rf=32‘

构造 API

Faiss index的使用有3种方式**~~ (推荐使用前两种, 第三种正在支持中)~~**

  1. 提供几种常用的index类型,并提供微调参数给用户使用。并会根据数据量自动adaptively的调整其中少部分参数,仅保留跟数据静态特征相关的参数给用户。

支持的index类型,加粗的参数表示必须的,IVF*索引实际还要一个参数nlist,跟part数据量相关,引擎会自动推算(计算方法在下面)

  • FLAT('dim', 'metric')
    • Dim: 维度,通常是2的幂
    • Metric:L2,cosine
  • IVF_FLAT('dim', 'metric', 'nprobe')
    • nprobe: 默认是1,越大准确率越好,性能越差,取值为2的n次方,例如32,64,范围介于[1, std::min(nlist/2, 查询里的top n)]
  • IVF_PQ('dim', 'metric', 'm', 'nbit', 'nprobe')
    • m: the number of subvectors that we will split our vectors into, 经验取值通常为64或者32,取值范围为2的n次方,范围介于[1, std::min(dim, 64)]
    • nbit: the number of bits that each subquantizer can use,默认8,通常不用动,取值为偶数, 通常范围为[1, 16]
  • IVF_PQ_FS('dim', 'metric', 'm', 'refine', 'k_factor_rf')
    • fs scan with refine(RFlat)
    • m同上
    • refine,默认使用RFlat,准确度最高,还可以使用SQ4, SQ6, SQ8, SQfp16。准确度RFlat>SQfp16>SQ8,资源使用也从少到多。
    • k_factor_rf:默认是1,越大准确率越好,性能越差,正整数,通常取值范围[1, 64]

例子, 每种索引各给了一个建表事例

#FLAT
CREATE TABLE tab_flat(id Int32, vector Array(Float32), INDEX faiss_index vector TYPE FLAT('dim=4') GRANULARITY 1) ENGINE = MergeTree ORDER BY id SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

#IVF_FLAT
CREATE TABLE tab_ivf_flat(id Int32, vector Array(Float32), INDEX faiss_index vector TYPE IVF_FLAT('dim=4') GRANULARITY 1) ENGINE = MergeTree ORDER BY id SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

#IVF_PQ
CREATE TABLE tab_ivf_pq(id Int32, vector Array(Float32), INDEX faiss_index vector TYPE IVF_PQ('dim=4','m=4','nbit=4') GRANULARITY 1) ENGINE = MergeTree ORDER BY id SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

#IVF_PQ_FS
CREATE TABLE tab_ivf_pq_fs(id Int32, vector Array(Float32), INDEX faiss_index vector TYPE IVF_PQ_FS('dim=4','m=4') GRANULARITY 1) ENGINE = MergeTree ORDER BY id SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

#IVF_PQ_FS_SQ8
CREATE TABLE tab_ivf_pq_fs_sq8(id Int32, vector Array(Float32), INDEX faiss_index vector TYPE IVF_PQ_FS('dim=4','m=2', 'refine=SQ8') GRANULARITY 1) ENGINE = MergeTree ORDER BY id SETTINGS index_granularity = 128, merge_selector_config = '{"name": "simple", "max_total_rows_to_merge": 50000000}'

-- 查询
SELECT *, d
FROM xxx.yyy
ORDER BY L2Distance(vector, [...]) as d limit 3 
settings 
enable_new_ann=1, 
nprobe=256,
k_factor_rf=32;

nlist计算逻辑
建表的时候可以nlist参数指定每个part构建index时候nlist的上限

static size_t decideIndexNlist(size_t n)
{
    if (n < ONE_MILLION)
        return std::min(int(n), int(4 * std::floor(std::sqrt(n))));
    else if (n >= ONE_MILLION && n < ONE_MILLION * 2)
        return 1024;
    else if (n >= ONE_MILLION * 2 && n < TEN_MILLION)
        return 4096;
    else if (n > TEN_MILLION)
        return 65536;
}
  1. 自动选择index,用户不需要指定具体的index类型,引擎会根据用户的数据量自动选择适合的index。建表的时候用户只需要指定维度信息即可。

最简单的构造 Faiss 索引的语句如下:

CREATE TABLE test_ann
(
    `id` UInt64,
    `vector` Array(Float32),
    INDEX v1 vector TYPE Faiss('DIM=960')
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 128

# 指定维度和metric type
CREATE TABLE test_ann
(
    `id` UInt64,
    `vector` Array(Float32),
    INDEX v1 vector TYPE Faiss('DIM=960, METRIC=COSINE')
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 128

#查询
SELECT *, d
FROM xxx.yyy
ORDER BY L2Distance(vector, [...]) as d limit 3 settings enable_new_ann=1;

自动选择适合的index的逻辑

static const String IVF2048 = "IVF2048";
static const String IVF4096 = "IVF4096"; // recommended for 2 * ONE_MILLION <=n < 5 * ONE_MILLION
static const String IVF8192 = "IVF8192"; // recommended for 5 * ONE_MILLION <=n < TEN_MILLION
static const String IVF65536 = "IVF65536"; // recommended for ONE_MILLION <=n < TEN_MILLION
static const String IVF262144  = "IVF262144"; // recommended for TEN_MILLION <=n < HUNDRED_MILLION
static const String IVF1048576  = "IVF1048576"; // recommended for HUNDRED_MILLION <=n < ONE_BILLION

static String getAdaptiveIndexKey(size_t n, size_t d)
{
    if (n < 256)
    {
        // for PQ, if nbits is 8, at least 256 vectors is required
        return "Flat";
    }
    else
    {
        // for simplicity, use ivf pq for auto indexing, adjust nlist and m adaptively, and d % m must be 0,
        // so we required d is power of 2 here, usually dimension is multiple of 32 or 64, pq32 and pq64 are widely used.
        std::ostringstream os;
        size_t pq_m = std::min(64, int(largestPowerOf2LessThan(d)));
        if (d % pq_m != 0)
            throw Exception("d must be power of 2 for ivfpq index", ErrorCodes::BAD_ARGUMENTS);

        size_t nlist;
        if (n < ONE_MILLION)
        {
            nlist = std::min(1024, int(4 * std::floor(std::sqrt(n))));
            os << "IVF" << nlist << ",PQ" << pq_m;
        }
        else if (n >= ONE_MILLION && n < ONE_MILLION * 2)
        {
            os << IVF2048 << ",PQ" << pq_m;
        }   
        else if (n >= ONE_MILLION * 2 && n < TEN_MILLION)
        {
            os << IVF4096 << ",PQ" << pq_m;
        }
        else if (n >= TEN_MILLION && n < HUNDRED_MILLION)
        {
            // exmaple IVF262144_FS="IVF262144(IVF512,PQ64x4fs,RFlat)"
            os << "IVF262144(IVF512,PQ" << pq_m << "x4fs,RFlat),PQ" << pq_m; 
        }
        else if (n >= HUNDRED_MILLION && n < ONE_BILLION)
        {
            os << IVF1048576 << ",PQ" << pq_m;
        }
        else
            throw Exception("Not supported yet for 1B vectors in one part", ErrorCodes::NOT_IMPLEMENTED);

        return os.str();
    }
}
  1. ~~(当前主要给研发调试和测试使用,不推荐用户使用) ~~使用Faiss index的第二个参数index_key指定任意的index。这种方式可以灵活指定特点的index,比较适合开发测试各种index的效果。

一个指定index key和build parameters的例子

CREATE TABLE test_ann
(
    `id` UInt64,
    `vector` Array(Float32),
    INDEX v1 vector TYPE Faiss('DIM=960','IVF1024,PQ64x4fs,Refine(SQ8)','nprobe=512,k_factor_rf=32')
)
ENGINE = MergeTree
ORDER BY id
SETTINGS index_granularity = 128

查询语法

查询时候可以通过settings参数对准确率进行调优支持的参数如下,固定pattern API会用到前面2个参数nprobe和k_factor_rf,通过FAISS创建的自动index,还会用到后两个。

  • nprobe
  • k_factor_rf
  • quantizer_nprobe
  • quantizer_k_factor_rf

Example query:

-- 基本查询
SELECT *, d
FROM xxx.yyy
ORDER BY L2Distance(vector, [...]) as d limit 3 
settings 
enable_new_ann=1;


-- IVF_FLAT, IVF_PQ 可以设置nprobe
SELECT *, d
FROM xxx.yyy
ORDER BY L2Distance(vector, [...]) as d limit 3 
settings 
enable_new_ann=1, nprobe=256;

-- IVF_PQ_FS 可以设置nprobe和k_factor_rf
SELECT *, d
FROM xxx.yyy
ORDER BY L2Distance(vector, [...]) as d limit 3 
settings 
enable_new_ann=1, nprobe=256, k_factor_rf=32;

-- 对于使用FAISS自动index创建的index,还可以指定quantizer_nprobe和quantizer_k_factor_rf
select 
    id, label 
from test_ann 
order by L2Distance(vector, [1.0, 1.0, 1.0]) 
limit 100
settings 
enable_new_ann=1,
nprobe=128, -- 计算使用 128 个聚类中心
k_factor_rf=32,-- refine index 使用至少 32 个结果做结果重排
quantizer_nprobe=96, -- nested ivf index 使用 96 个聚类中心计算
quantizer_k_factor_rf=16,-- nested refine index 使用至少 16 个结果做重排

注意事项

  • Faiss不同于hnsw,构建index的时候会做训练,对cpu消耗比较大,有如下一些注意事项:
  • 使用 faiss index 的时候需要把 merge 上线参数 max_total_rows_to_merge 设置到 50000000,避免build过大的index。
alter table zhaojie.test_1b_3 MODIFY SETTING merge_selector_config='{"name": "simple", "max_total_rows_to_merge": 50000000}'
  • 根据内存大小设置 index cache 大小,参数是 vector_index_cache_size,默认200GB,是一个LRU实现
  • 如果对冷度敏感,内存足够,可以打开 enable_cache_vector_index_after_write 参数,在写入的时候把build的index加载到内存中
  • 测试的时候可以关注下cpu的使用,如果cpu使用过高,
    • 限制merge并发,max_replicated_merges_in_queue
    • 可以考虑限制下train index的并发,参数是vector_index_build_threads,默认是32

相关参考

Filter By Distance

当前可以通过 where 语句来支持基于 distance 的过滤,语法示例如下:

select id, dist from test_ann where dist < 0.9 
order by cosineDistance(embedding_column, [query_vector]) as dist
limit 100

说明:

  • 针对 where dist < max_score 以及 where dist > min_score 这类单一 filter 条件查询,bytehouse 有相对应的优化,目前推荐这种使用方式

Query Profiling Events

Event

Description

SelectedPartsWithVectorIndex

表示 query 执行过程中使用 vector index 进行查询的 part 数量。如果值小于 SelectedParts 这个值,则表示有 part vector index 异常,可能未 build 或者有损坏

TotalVectorSearchPreFilterTime

表示 query prewhere filter 执行的时间总和

TotalVectorSearchWithIndexTime

表示 query 使用 vector index 执行 vector search 的时间总和

TotalVectorSearchWithoutIndexTime

表示 query 没有使用 vector index 执行 vector search 的时间总和,如果出现,一般表示 vector index 还未构建成功,或者存在 vector index 缺失或损坏的 parts

TotalVectorSearchPartReadTime

表示 query 实际执行数据读取的时间。对于 SearchWithIndex 的 case,part read 发生在 vector search 之后,涉及的 mark 会基于 vector search 的结果计算出来。对于 SearchWithoutIndex case,part read 发生在 vector search 之前。

VectorIndexCacheMisses

表示 query 执行过程中有多少个 part 的 index 未存在于 cache 中,导致 vector index cache misses

VectorIndexCacheHits

表示 query 执行过程中有多少个 part 的 index 存在于 vector index cache 中

settings 参数

Name

Description(无特殊说明,都在 users.xml 的 profile 中设置)

Default Value

使用建议

vector_index_cache_size

Vector Index 可使用的 memory cache 大小。采用 LRU 策略淘汰, config.xml 中设置

max_server_memory_usage * 0.5

需要预留一部分给 index build使用,考虑到会有后台的 merge或者 mutation tasks,建议为 index cache 预留小于等于一半最大内存量,如果 merge并发度较高,考虑进一步缩小 index cache 大小。

enable_new_ann

是否使用新的 ann 执行路径

0

设置为 1 开启

vector_index_build_threads

每个 part build threads 数量,支持 insert query 中单独定义

8

单个 part 的 build threads 控制,如果并发导入或者 merge 并发度较高,建议调小

enable_vector_index_cache_async_loading

是否使用 async index load。开启后,在第一次未载入 index 到内存时,采用 brute force search,后台异步 load index。不支持 query 中单独定义

0

主要用于机器重启以后 index 未加载场景。index 进行异步加载后,未加载前的 vector search 走 brute force 查询

vector_index_loading_thread_pool_size

Async index load 线程池数量。不支持 query 中单独定义

16

enable_global_vector_index_preload

是否在 server start up 或者 part 创建以后,直接将 index load 到 cache 中。全 table 生效,不支持 query 中单独定义

0

CE 版本写入加速。写入后的 part 的 vector index 直接进入 cache,消除 index 加载时间。

enable_vector_index_preload

Table level preload 开关。table setting 中设置

0

同上

hnsw_ef_s

基于 HNSW index 进行 search 时,使用的搜索参数,值越大,准确度越高。一般在 query 中定义

10

Recall 90 以上场景,一般需要设置到 128 以上。

nprobe

使用 faiss ivf index 时的搜索参数,表示搜索使用的聚类中心数量。理论上,nprobe 越大,准确度越大,latency 越高。一般在 query 中定义

0 (默认为 0 表示未进行设置,index 中默认使用参数为 1)

Recall 90 以上场景,考虑设置到 nlist 的 1/4 以上

k_factor_rf

使用 faiss 包含 refine 的索引时的搜索参数,k_factor_rf 越大,用于排序的结果越多,准确度越高,latency 越高。一般在 query 中定义

0 (同上)

使用了 refine 的索引,在 recall较低情况,可以尝试调大,可以先尝试设置为 100,视情况进行微调

quantizer_nprobe

使用 faiss nested ivf 类型索引的内部 ivf index 搜索参数,比如,IVF1048576(IVF1024,PQ64x4fs,RFlat),PQ64, 效果同 nprobe 用于设置内部 ivf 索引的搜索范围。一般在 query 中定义

0 (同上)

目前使用场景较少

quantizer_k_factor_rf

使用 faiss nested refine 类型索引的内部 refine index 搜索参数,比如,IVF1048576(IVF1024,PQ64x4fs,RFlat),PQ64,效果同 k_factor_rf,用于设置内部 refine 的结果范围。一般在 query 中定义

0 (同上)

目前使用场景较少

系统表

在用户使用向量检索功能后,系统会自动生成一个专门用于存储 vector_indices 信息的系统表,表名为 system.vector_indices。
【什么权限,可以查询吗】
包含字段如下:

列名

描述

database

数据库名称

table

表名称

name

索引名称

type

索引类型(HNSW、Faiss、DiskANN)

vector_column

构建索引的列名

params

索引构建参数

total_parts

表的总 part 数量

index_built_parts

已经构建 index 的 part 数量

total_rows

表所有数据行数

estimate_memory_size

索引预估内存值。

  • faiss 如果 index_type 为 0 的话,estimate_memory_size 可能为 0。
  • DiskANN 该列为 0