带有向量相似性索引的近似最近邻搜索

ClickHouse Cloud 中的私有预览

最近邻搜索是在 N 维向量空间中查找与给定向量最接近的 M 个向量的问题。解决此问题最直接的方法是穷举（暴力）搜索，该方法计算参考向量与向量空间中所有其他点之间的距离。虽然该方法保证了完全准确的结果，但对于实际应用来说通常太慢。作为替代方案，近似算法使用贪婪启发式方法更快地找到最接近的 M 个向量。这允许在毫秒内对图片、歌曲、文本嵌入进行语义搜索。

博客

在 SQL 方面，最近邻搜索可以表示如下

SELECT [...]
FROM table, [...]
ORDER BY DistanceFunction(vectors, reference_vector)
LIMIT N

其中

DistanceFunction 计算两个向量之间的距离（例如 L2Distance 或 cosineDistance），
vectors 是 Array(Float64) 或 Array(Float32) 或 Array(BFloat16) 类型的列，通常存储嵌入，
reference_vector 是 Array(Float64) 或 Array(Float32) 或 Array(BFloat16) 类型的字面量，以及
N 是一个限制返回结果数量的常数整数。

查询返回 vectors 中与 reference_vector 最接近的 N 个点。

穷举搜索计算 reference_vector 和 vectors 中所有向量之间的距离。因此，其运行时与存储向量的数量成线性关系。近似搜索依赖于特殊的数据结构（例如，图、随机森林等），这些数据结构允许快速（即亚线性时间）找到与给定参考向量最接近的向量。ClickHouse 以“向量相似性索引”的形式提供了这种数据结构，这是一种跳数索引类型。

创建和使用向量相似性索引

创建向量相似性索引的语法

CREATE TABLE table
(
  id Int64,
  vectors Array(Float32),
  INDEX index_name vectors TYPE vector_similarity(method, distance_function[, quantization, hnsw_max_connections_per_layer, hnsw_candidate_list_size_for_construction]) [GRANULARITY N]
)
ENGINE = MergeTree
ORDER BY id;

注意

USearch 索引目前是实验性的，要使用它们，您首先需要 SET allow_experimental_vector_similarity_index = 1。

索引可以构建在 Array(Float64) 或 Array(Float32) 类型的列上。

索引参数

method：目前仅支持 hnsw。
distance_function：L2Distance（欧几里得距离：欧几里得空间中两点之间线的长度）或 cosineDistance（余弦距离：两个非零向量之间的角度）。
quantization：f64、f32、f16、bf16 或 i8，用于以降低的精度存储向量（可选，默认值：bf16）
hnsw_max_connections_per_layer：每个 HNSW 图节点的邻居数，也称为 HNSW 论文中的 M。可选，默认值：32。值 0 表示使用默认值。
hnsw_candidate_list_size_for_construction：构建 HNSW 图时动态候选列表的大小，也称为原始 HNSW 论文中的 ef_construction。可选，默认值：128。值 0 表示使用默认值。

对于归一化数据，L2Distance 通常是最佳选择，否则建议使用 cosineDistance 来补偿比例。

示例

CREATE TABLE table
(
  id Int64,
  vectors Array(Float32),
  INDEX idx vectors TYPE vector_similarity('hnsw', 'L2Distance') -- Alternative syntax: TYPE vector_similarity(hnsw, L2Distance)
)
ENGINE = MergeTree
ORDER BY id;

所有数组必须具有相同的长度。为避免错误，您可以使用 CONSTRAINT，例如，CONSTRAINT constraint_name_1 CHECK length(vectors) = 256。INSERT 语句中不支持空 Arrays 和未指定的 Array 值（即默认值）。

向量相似性索引基于 USearch 库，该库实现了 HNSW 算法，即，一个分层图，其中每个节点代表一个向量，节点之间的边代表相似性。这种分层结构在大型集合上可能非常高效。它们通常可以从整个数据集中提取 0.05% 或更少的数据，同时仍提供 99% 的召回率。这在使用高维向量时尤其有用，因为高维向量加载和比较成本很高。USearch 还利用 SIMD 加速现代 x86（AVX2 和 AVX-512）和 ARM（NEON 和 SVE）CPU 上的距离计算。

向量相似性索引在列插入和合并期间构建。已知 HNSW 算法提供较慢的插入速度。因此，具有向量相似性索引的表上的 INSERT 和 OPTIMIZE 语句将比普通表慢。向量相似性索引理想情况下仅与不可变或很少更改的数据一起使用，分别是在读取请求远多于写入请求时。建议使用以下三种附加技术来加速索引创建

索引创建可以并行化。可以使用服务器设置 max_build_vector_similarity_index_thread_pool_size 配置最大线程数。
可以使用设置 materialize_skip_indexes_on_insert 禁用在新插入的部分上创建索引。在此类部分上的搜索将回退到精确搜索，但由于插入的部分通常与整个表大小相比很小，因此性能影响可以忽略不计。
ClickHouse 在后台将多个部分增量合并为更大的部分。这些新部分可能会稍后合并为更大的部分。每次合并都会从头开始重建输出部分（以及其他跳数索引）的向量相似性索引。这可能会浪费创建向量相似性索引的工作。为避免这种情况，可以抑制在合并期间创建向量相似性索引，方法是使用 merge tree 设置 materialize_skip_indexes_on_merge。这与语句 ALTER TABLE [...] MATERIALIZE INDEX [...] 结合使用，可以显式控制向量相似性索引的生命周期。例如，索引构建可以推迟到低负载时段（例如周末）或大量数据摄取之后。

向量相似性索引支持以下类型的查询

WITH [...] AS reference_vector
SELECT *
FROM table
WHERE ...                       -- WHERE clause is optional
ORDER BY Distance(vectors, reference_vector)
LIMIT N

要使用不同的 HNSW 参数 hnsw_candidate_list_size_for_search 值（默认值：256）进行搜索，也称为原始 HNSW 论文中的 ef_search，请使用 SETTINGS hnsw_candidate_list_size_for_search = <value> 运行 SELECT 查询。

从向量相似性索引重复读取得益于大型跳数索引缓存。如果需要，您可以使用服务器设置 skipping_index_cache_size 增加默认缓存大小。

限制：近似向量搜索算法需要限制，因此没有 LIMIT 子句的查询无法利用向量相似性索引。限制还必须小于设置 max_limit_for_ann_queries（默认值：100）。

与常规跳数索引的区别 与常规跳数索引类似，向量相似性索引是在粒度上构建的，每个索引块由 GRANULARITY = [N] 个粒度组成（对于普通跳数索引，默认情况下 [N] = 1）。例如，如果表的主索引粒度为 8192（设置 index_granularity = 8192），并且 GRANULARITY = 2，则每个索引块将包含 16384 行。但是，用于近似邻域搜索的数据结构和算法本质上是面向行的。它们存储一组行的紧凑表示，并且还返回用于向量搜索查询的行。这导致向量向量相似性索引的行为方式与普通跳数索引相比存在一些相当违反直觉的差异。

当用户在列上定义向量相似性索引时，ClickHouse 内部会为每个索引块创建一个向量相似性“子索引”。子索引是“本地”的，因为它只了解其包含索引块的行。在前面的示例中，并假设列有 65536 行，我们获得四个索引块（跨越八个粒度）以及每个索引块的向量相似性子索引。理论上，子索引能够直接返回索引块内具有 N 个最接近点的行。但是，由于 ClickHouse 以粒度为单位将数据从磁盘加载到内存，因此子索引将匹配的行外推到粒度级别。这与常规跳数索引不同，后者以索引块的粒度跳过数据。

GRANULARITY 参数确定创建多少个向量相似性子索引。较大的 GRANULARITY 值意味着更少但更大的向量相似性子索引，直到列（或列的数据部分）只有一个子索引。在这种情况下，子索引具有所有列行的“全局”视图，并且可以直接返回具有相关行的列（部分）的所有粒度（最多有 LIMIT [N] 个此类粒度）。在第二步中，ClickHouse 将加载这些粒度，并通过对粒度的所有行执行暴力距离计算来识别实际的最佳行。对于较小的 GRANULARITY 值，每个子索引最多返回 LIMIT N 个粒度。因此，需要加载和后过滤更多粒度。请注意，两种情况下的搜索精度都同样好，只是处理性能不同。通常建议对向量相似性索引使用较大的 GRANULARITY，并且仅在出现诸如向量相似性结构过度消耗内存等问题时才回退到较小的 GRANULARITY 值。如果未为向量相似性索引指定 GRANULARITY，则默认值为 1 亿。