向量索引
本文介绍了StarRocks的向量索引功能及如何使用它进行近似最近邻搜索(ANNS)。
向量索引功能仅在v3.4或更高版本的存算一体集群中支持。
概述
目前,StarRocks支持在Segment文件级别进行向量索引。索引将每个搜索项映射到Segment文件中的行ID,通过直接定位相应的数据行实现快速数据检索,而无需进行暴力的向量距离计算。系统目前提供两种类型的向量索引:倒排文件与产品量化(IVFPQ)和分层可导航小世界(HNSW),每种都有其独特的组织结构。
倒排文件与产品量化(IVFPQ)
倒排文件与产品量化(IVFPQ)是一种用于大规模高维向量近似最近邻搜索的方法,常用于深度学习和机器学习中的向量检索任务。IVFPQ由两个主要组件组成:倒排文件和产品量化。
- 倒排文件:这是一个索引方法。它将数据集划分为多个簇(或Voronoi单元),每个簇都有一个质心(种子点),并将每个数据点(向量)分配到其最近的簇中心。对于向量搜索,IVFPQ只需搜索最近的簇,大大减少了搜索范围和复杂性。
- 产品量化:这是一种数据压缩技术。它将高维向量分割为子向量,并将每个子向量量化以映射到预定义集合中的最近 点,从而在保持高精度的同时降低存储和计算成本。
通过结合倒排文件和产品量化,IVFPQ能够在大规模高维数据集中实现高效的近似最近邻搜索。
分层可导航小世界(HNSW)
分层可导航小世界(HNSW)是一种基于图的高维最近邻搜索算法,也广泛用于向量检索任务。
HNSW构建了一个分层图结构,其中每一层都是一个可导航的小世界(NSW)图。在图中,每个顶点代表一个数据点,边表示顶点之间的相似性。图的高层包含较少的顶点和稀疏的连接用于快速全局搜索,而低层包含所有顶点和密集的连接用于精确的局部搜索。
对于向量搜索,HNSW首先在顶层进行搜索,快速识别一个近似的最近邻区域,然后逐层向下移动,在底层找到精确的最近邻。
HNSW提供了效率和精度的平衡,使其适应各种数据和查询分布。
IVFPQ与HNSW的比较
- 数据压缩比:IVFPQ具有较高的压缩比(约为1:0.15)。由于PQ会压缩向量,索引计算仅提供粗略排序后的初步排序结果,需要额外的精细排序以获得最终排序结果,导致更高的计算和延迟。HNSW具有较低的压缩比(约为1:0.8),无需额外处理即可提供精确排序,计算成本和延迟较低,但存储成本较高。
- 召回率调整:两种索引都支持通过参数调整召回率,但在相似的召回率下 ,IVFPQ的计算成本更高。
- 缓存策略:IVFPQ允许通过调整索引块的缓存比例来平衡内存成本和计算延迟,而HNSW目前仅支持全文件缓存。
使用方法
每个表仅支持一个向量索引。
前提条件
在创建向量索引之前,必须通过设置FE配置项enable_experimental_vector
为true
来启用它。
执行以下语句以动态启用:
ADMIN SET FRONTEND CONFIG ("enable_experimental_vector" = "true");
要永久启用它,必须将enable_experimental_vector = true
添加到FE配置文件fe.conf
中并重启FE。
创建向量索引
本教程在创建表时创建向量索引。您也可以将向量索引附加到现有表中。有关详细说明,请参见附加向量索引。
-
以下示例在表
hnsw
的列vector
上创建一个HNSW向量索引hnsw_vector
。CREATE TABLE hnsw (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX hnsw_vector (vector) USING VECTOR (
"index_type" = "hnsw",
"dim"="5",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"M" = "16",
"efconstruction" = "40"
)
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1; -
以下示例在表
ivfpq
的列vector
上创建一个IVFPQ向量索引ivfpq_vector
。CREATE TABLE ivfpq (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX ivfpq_vector (vector) USING VECTOR (
"index_type" = "ivfpq",
"dim"="5",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"nbits" = "16",
"nlist" = "40"
)
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
索引构建参数
USING VECTOR
- 默认值: N/A
- 必需: 是
- 描述: 创建一个向量索引。
index_type
- 默认值: N/A
- 必需: 是
- 描述: 向量索引类型。有效值:
hnsw
和ivfpq
。
dim
- 默认值: N/A
- 必需: 是
- 描述: 索引的维度。索引构建完成后,不符合维度要求的向量将被拒绝加载到基础列中。必须是大于或等于
1
的整数。
metric_type
- 默认值: N/A
- 必需: 是
- 描述: 向量索引的度量类型(测量函数)。有效值:
l2_distance
: 欧氏距离。值越小,相似度越高。cosine_similarity
: 余弦相似度。值越大,相似度越高。
is_vector_normed
- 默认值: false
- 必需: 否
- 描述: 向量是否已归一化。有效值为
true
和false
。仅当metric_type
为cosine_similarity
时生效。如果向量已归一化,计算出的距离值将在[-1, 1]之间。向量必须满足平方和为1
,否则返回错误。
M
- 默认值: 16
- 必需: 否
- 描述: HNSW特定参数。图构建过程中为每个新元素创建的双向连接数。必须是大于或等于
2
的整数。M
的值直接影响图构建和搜索的效率和准确性。在图构建过程中,每个顶点将尝试与其最近的M
个顶点建立连接。如果一个顶点已经有M
个连接,但发现了一个更近的顶点,最远的连接将被删除,并与更近的顶点建立新连接。向量搜索将从一个入口点开始,并沿着与其连接的顶点找到最近的邻居。因此,M
的值越大,每个顶点的搜索范围越大,搜索效率越高,但图构建和存储的成本也越高。
efconstruction
- 默认值: 40
- 必需: 否
- 描述: HNSW特定参数。包含最近邻居的候选列表的大小。必须是大于或等于
1
的整数。用于控制图构建过程中的搜索深度。具体来说,efconstruction
定义了图构建过程中每个顶点的搜索列表(也称为候选列表)的大小。这个候选列表用于存储当前顶点的邻居候选者,列表的大小为efconstruction
。efconstruction
的值越大,在图构建过程中被视为顶点邻居的候选者越多,因此图的质量(如更好的连通性)越好,但图构建的时间消耗和计算复杂度也越高。
nbits
- 默认值: 16
- 必需: 否
- 描述: IVFPQ特定参数。产品量化(PQ)的精度。必须是
8
的倍数。在IVFPQ中,每个向量被分割为多个子向量,然后每个子向量被量化。Nbits
定义了量化的精度,即每个子向量被量化为多少个二进制位。nbits
的值越大,量化精度越高,但存储和计算成本也越高。
nlist
- 默认值: 16
- 必需: 否
- 描述: IVFPQ特定参数。簇的数量或倒排列表。必须是大于或等于
1
的整数。在IVFPQ中,数据集被划分为簇,每个簇的质心对应一个倒排列表。向量搜索将首先找到与数据点最近的簇质心,然后在相应的倒排列表中检索最近邻居。因此,nlist
的值将影响搜索的准确性和效率。nlist
的值越大,聚类的粒度越细,因此搜索的准确性越高,但搜索的复杂性也越高。
M_IVFPQ
- 必需: 是
- 描述: IVFPQ特定参数。原始向量将被分割成的子向量数量。IVFPQ索引将一个
dim
维向量分割成M_IVFPQ
个等长的子向量。因此,它必须是dim
值的因数。
附加向量索引
您还可以使用CREATE INDEX或ALTER TABLE ADD INDEX将向量索引添加到现有表中。
示例:
CREATE INDEX ivfpq_vector
ON ivfpq (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
ALTER TABLE ivfpq
ADD INDEX ivfpq_vector (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
管理向量索引
查看向量索引
您可以使用SHOW CREATE TABLE语句查看向量索引的定义:
示例:
mysql> SHOW CREATE TABLE hnsw \G
*************************** 1. row ***************************
Table: hnsw
Create Table: CREATE TABLE hnsw (
id bigint(20) NOT NULL COMMENT "",
vector array<float> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR("dim" = "5", "efconstruction" = "40", "index_type" = "hnsw", "is_vector_normed" = "false", "M" = "512", "metric_type" = "l2_distance") COMMENT ''
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
"compression" = "LZ4",
"fast_schema_evolution" = "true",
"replicated_storage" = "false",
"replication_num" = "3"
);
1 row in set (0.00 sec)
删除向量索引
您可以使用DROP INDEX或ALTER TABLE DROP INDEX删除向量索引。
DROP INDEX ivfpq_vector ON ivfpq;
ALTER TABLE ivfpq DROP INDEX ivfpq_vector;
使用向量索引执行ANNS
在运行向量搜索之前,请确保FE配置项enable_experimental_vector
设置为true
。