向量索引
Beta 功能
本文介绍了 StarRocks 的向量索引功能，以及如何使用它执行近似最近邻搜索 (ANNS)。
向量索引功能仅在 v3.4 或更高版本的 Shared-nothing 集群中支持。
概述
目前，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。
基于向量索引的查询的要求
SELECT *, <vector_index_distance_func>(v1, [1,2,3]) as dis
FROM table_name
WHERE <vector_index_distance_func>(v1, [1,2,3]) <= 10
ORDER BY <vector_index_distance_func>(v1, [1,2,3])
LIMIT 10
要在查询中使用向量索引，必须满足以下所有要求
- ORDER BY 要求
- ORDER BY 子句格式：
ORDER BY子句必须遵循格式ORDER BY <vector_index_distance_func>(vector_column, constant_array)，不包括额外的 ORDER BY 列。<vector_index_distance_func>的函数名称要求- 如果
metric_type为l2_distance，则函数名称必须为approx_l2_distance。 - 如果
metric_type为cosine_similarity，则函数名称必须为approx_cosine_similarity。
- 如果
<vector_index_distance_func>的参数要求- 其中一个列
constant_array必须是维度与向量索引dim匹配的常量ARRAY<FLOAT>。 - 另一个列
vector_column必须是与向量索引对应的列。
- 其中一个列
- ORDER 方向要求
- 如果
metric_type为l2_distance，则顺序必须为ASC。 - 如果
metric_type为cosine_similarity，则顺序必须为DESC。
- 如果
- 需要
LIMIT N子句。
- ORDER BY 子句格式：
- 谓词要求
- 所有谓词都必须是
<vector_index_distance_func>表达式，使用AND和比较运算符 (>或<) 组合。比较运算符方向必须与ASC/DESC顺序一致。具体来说 - 要求 1
- 如果
metric_type为l2_distance：col_ref <= constant。 - 如果
metric_type为cosine_similarity：col_ref >= constant。 - 此处，
col_ref是指<vector_index_distance_func>(vector_column, constant_array)的结果，可以转换为FLOAT或DOUBLE类型，例如approx_l2_distance(v1, [1,2,3])CAST(approx_l2_distance(v1, [1,2,3]) AS FLOAT)CAST(approx_l2_distance(v1, [1,2,3]) AS DOUBLE)
- 如果
- 要求 2
- 谓词必须使用
AND，并且每个子谓词都满足要求 1。
- 谓词必须使用
- 所有谓词都必须是
准备工作
创建具有向量索引的表并将向量数据插入其中
CREATE TABLE test_hnsw (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR (
"index_type" = "hnsw",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"M" = "512",
"dim"="5")
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
INSERT INTO test_hnsw VALUES
(1, [1,2,3,4,5]),
(2, [4,5,6,7,8]);
CREATE TABLE test_ivfpq (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"nlist" = "256",
"nbits"="8",
"dim"="5",
"M_IVFPQ"="1")
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
INSERT INTO test_ivfpq VALUES
(1, [1,2,3,4,5]),
(2, [4,5,6,7,8]);
执行向量搜索
近似搜索
近似搜索将命中向量索引，从而加速搜索过程。
以下示例搜索向量 [1,1,1,1,1] 的前 1 个近似最近邻。
SELECT id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
标量-向量联合搜索
您可以将标量搜索与向量搜索结合使用。
SELECT id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
WHERE id = 1
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
范围搜索
您可以对向量数据执行范围搜索。
以下示例将 score < 40 条件下推到索引，并按 score 范围过滤向量。
SELECT * FROM (
SELECT id, approx_l2_distance([1,1,1,1,1], vector) score
FROM test_hnsw
) a
WHERE score < 40
ORDER BY score
LIMIT 1;
精确计算
精确计算将忽略向量索引，并直接计算向量之间的距离以获得精确结果。
SELECT id, l2_distance([1,1,1,1,1], vector)
FROM test_hnsw WHERE id = 1
ORDER BY l2_distance([1,1,1,1,1], vector)
LIMIT 1;
注意
不同的距离度量函数以不同的方式定义“相似性”。对于
l2_distance，值越小表示相似度越高；对于cosine_similarity，值越大表示相似度越高。因此，在计算topN时，排序 (ORDER BY) 方向应与度量的相似性方向匹配。对于l2_distance使用ORDER BY ASC LIMIT x，对于cosine_similarity使用ORDER BY DESC LIMIT x。
微调索引参数以进行搜索
参数调整在向量搜索中至关重要，因为它会影响性能和准确性。建议在小型数据集上调整搜索参数，并在达到预期的召回率和延迟后才移动到大型数据集。
搜索参数通过 SQL 语句中的提示传递。
对于 HNSW 索引
在继续之前，请确保向量列已使用 HNSW 索引构建。
SELECT
/*+ SET_VAR (ann_params='{efsearch=256}') */
id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
WHERE id = 1
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
参数:
efsearch
- 默认: 16
- 必需：否
- 描述：控制精度-速度权衡的参数。在分层图结构搜索期间，此参数控制搜索期间候选列表的大小。
efsearch的值越大，准确性越高，但速度越慢。
对于 IVFPQ 索引
在继续之前，请确保向量列已使用 IVFPQ 索引构建。
SELECT
/*+ SET_VAR (ann_params='{nprobe=256,max_codes=0,scan_table_threshold=0,polysemous_ht=0,range_search_confidence=0.1}') */
id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_ivfpq
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
参数:
nprobe
- 默认: 1
- 必需：否
- 描述：搜索期间检查的倒排列表的数量。
nprobe的值越大，准确性越高，但速度越慢。
max_codes
- 默认: 0
- 必需：否
- 描述：每个倒排列表中检查的最大代码数。此参数也会影响准确性和速度。
scan_table_threshold
- 默认: 0
- 必需：否
- 描述：控制多义哈希的参数。当元素的哈希与要搜索的向量的哈希之间的汉明距离低于此阈值时，该元素将添加到候选列表中。
polysemous_ht
- 默认: 0
- 必需：否
- 描述：控制多义哈希的参数。当元素的哈希与要搜索的向量的哈希之间的汉明距离低于此阈值时，该元素将直接添加到结果中。
range_search_confidence
- 默认: 0.1
- 必需：否
- 描述：近似范围搜索的置信度。取值范围：[0, 1]。将其设置为
1会产生最准确的结果。
计算近似召回率
您可以通过将暴力检索中的 topK 元素与近似检索中的元素相交来计算近似召回率：召回率 = TP / (TP + FN)。
-- Approximate retrieval
SELECT id
FROM test_hnsw
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 5;
8
9
7
5
1
-- Brute-force retrieval
SELECT id
FROM test_hnsw
ORDER BY l2_distance([1,1,1,1,1], vector)
LIMIT 5;
8
9
5
7
10
在前面的示例中，近似检索返回 8、9、7 和 5。但是，正确的结果是 8、9、5、7 和 10。在这种情况下，召回率为 4/5=80%。
检查向量索引是否生效
针对查询语句执行 EXPLAIN。如果 OlapScanNode 属性显示 VECTORINDEX: ON，则表示向量索引已应用于近似向量搜索。
示例
> EXPLAIN SELECT id FROM t_test_vector_table ORDER BY approx_l2_distance([1,1,1,1,1], vector) LIMIT 5;
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
| Explain String |
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
| PLAN FRAGMENT 0 |
| OUTPUT EXPRS:1: id |
| PARTITION: UNPARTITIONED |
| |
| RESULT SINK |
| |
| 4:Project |
| | <slot 1> : 1: id |
| | limit: 5 |
| | |
| 3:MERGING-EXCHANGE |
| limit: 5 |
| |
| PLAN FRAGMENT 1 |
| OUTPUT EXPRS: |
| PARTITION: RANDOM |
| |
| STREAM DATA SINK |
| EXCHANGE ID: 03 |
| UNPARTITIONED |
| |
| 2:TOP-N |
| | order by: <slot 3> 3: approx_l2_distance ASC |
| | offset: 0 |
| | limit: 5 |
| | |
| 1:Project |
| | <slot 1> : 1: id |
| | <slot 3> : 4: __vector_approx_l2_distance |
| | |
| 0:OlapScanNode |
| TABLE: t_test_vector_table |
| VECTORINDEX: ON |
| IVFPQ: OFF, Distance Column: <4:__vector_approx_l2_distance>, LimitK: 5, Order: ASC, Query Vector: [1, 1, 1, 1, 1], Predicate Range: -1.0 |
| PREAGGREGATION: ON |
| partitions=1/1 |
| rollup: t_test_vector_table |
| tabletRatio=1/1 |
| tabletList=11302 |
| cardinality=2 |
| avgRowSize=4.0 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
局限性
- 每张表仅支持一个向量索引。