跳至主要内容

近似最近邻搜索索引[实验性]

最近邻搜索是指在 N 维向量空间中，为给定点查找 M 个最近点的难题。解决此问题的最直接方法是暴力搜索，其中计算向量空间中所有点与参考点之间的距离。此方法保证了完美的准确性，但对于实际应用来说通常过于缓慢。因此，最近邻搜索问题通常使用近似算法来解决。近似最近邻搜索技术结合嵌入方法可以使在几毫秒内搜索海量的媒体（图片、歌曲、文章等）。

博客

从 SQL 的角度来看，最近邻问题可以表示如下

SELECT *
FROM table
ORDER BY Distance(vectors, Point)
LIMIT N

vectors 包含类型为Array(Float32) 或 Array(Float64) 的 N 维值，例如嵌入。函数 Distance 计算两个向量之间的距离。通常，欧几里得（L2）距离被选为距离函数，但其他距离函数也是可能的。Point 是参考点，例如 (0.17, 0.33, ...)，而 N 限制搜索结果的数量。

此查询返回与参考点最接近的前 N 个点。参数 N 限制返回的值的数量，这对于难以提前确定 MaxDistance 的情况很有用。

使用暴力搜索，查询代价很高（与点数成线性关系），因为必须计算 vectors 中所有点与 Point 之间的距离。为了加快此过程，近似最近邻搜索索引（ANN 索引）存储搜索空间的紧凑表示（使用聚类、搜索树等），这使得能够更快地计算近似答案（以次线性时间）。

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

在Array(Float32) 列上创建向量相似性索引的语法

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

参数

  • method：目前仅支持 hnsw。
  • distance_function：可以是 L2Distance（欧几里得距离 - 欧几里得空间中两点之间线段的长度），或 cosineDistance（余弦距离 - 两个非零向量之间的夹角）。
  • quantization：可以是 f64、f32、f16、bf16 或 i8，用于以降低的精度存储向量（可选，默认值：bf16）
  • m：每个图节点的邻居数量（可选，默认值：16）
  • ef_construction：（可选，默认值：128）
  • ef_search：（可选，默认值：64）

参数 m、ef_construction 和 ef_search 的值为 0 表示使用默认值。

示例

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;

向量相似性索引基于USearch 库，该库实现了HNSW 算法，即每个点表示一个向量，边表示相似性的分层图。这种分层结构在大型集合上可以非常有效。它们通常可以从整个数据集中获取 0.05% 或更少的数据，同时仍然提供 99% 的召回率。这在处理高维向量时尤其有用，因为高维向量加载和比较的成本很高。该库还具有多个硬件特定的 SIMD 优化，以进一步加速现代 Arm（NEON 和 SVE）和 x86（AVX2 和 AVX-512）CPU 上的距离计算，以及 OS 特定的优化，以允许在不可变的持久文件中有效地导航，而无需将其加载到 RAM 中。

USearch 索引目前处于实验阶段，要使用它们，您首先需要 SET allow_experimental_vector_similarity_index = 1。

向量相似性索引目前支持两种距离函数

  • L2Distance，也称为欧几里得距离，是欧几里得空间中两点之间线段的长度（维基百科）。
  • cosineDistance，也称为余弦相似度，是两个（非零）向量之间夹角的余弦（维基百科）。

向量相似性索引允许以降低的精度格式存储向量。支持的标量类型为 f64、f32、f16 或 i8。如果在索引创建期间未指定标量类型，则默认使用 f16。

对于归一化数据，L2Distance 通常是更好的选择，否则建议使用 cosineDistance 来补偿比例。如果在索引创建期间未指定距离函数，则默认使用 L2Distance。

注意

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

注意

向量相似性索引目前不适用于每个表的非默认 index_granularity 设置（参见此处）。如有必要，必须在 config.xml 中更改该值。

众所周知，向量索引创建速度很慢。为了加快速度，可以并行化索引创建。可以使用服务器配置设置max_build_vector_similarity_index_thread_pool_size配置线程的最大数量。

ANN 索引是在列插入和合并期间构建的。因此，INSERT 和 OPTIMIZE 语句将比普通表慢。ANN 索引理想情况下仅与不可变或很少更改的数据一起使用，或者当读取请求远多于写入请求时使用。

ANN 索引支持此类型的查询

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

为了避免写入大型向量，您可以使用查询参数，例如

clickhouse-client --param_vec='hello' --query="SELECT * FROM table WHERE L2Distance(vectors, {vec: Array(Float32)}) < 1.0"

限制：用于确定最近邻的近似算法需要一个限制，因此没有 LIMIT 子句的查询无法利用 ANN 索引。此外，只有当查询的 LIMIT 值小于设置 max_limit_for_ann_queries（默认值：100 万行）时，才会使用 ANN 索引。这是一项安全措施，可以防止外部库为近似邻搜索分配大量内存。

与跳过索引的区别 与常规跳过索引类似，ANN 索引是在数据块上构建的，每个索引块包含 GRANULARITY = [N] 个数据块（对于普通跳过索引，[N] 默认值为 1）。例如，如果表的 primary index 的粒度为 8192（设置 index_granularity = 8192）且 GRANULARITY = 2，则每个索引块将包含 16384 行。但是，近似邻域搜索的数据结构和算法（通常由外部库提供）本质上是面向行的。它们存储一组行的紧凑表示，并且还为 ANN 查询返回行。这导致 ANN 索引的行为与普通跳过索引相比存在一些相当不直观的差异。

当用户在列上定义 ANN 索引时，ClickHouse 在内部为每个索引块创建一个 ANN “子索引”。子索引在某种意义上是“局部的”，因为它只了解其包含的索引块的行。在前面的示例中，假设一个列有 65536 行，我们得到四个索引块（跨越八个数据块）以及每个索引块的 ANN 子索引。理论上，子索引能够直接返回其索引块内具有 N 个最近点的行。但是，由于 ClickHouse 以数据块粒度从磁盘加载数据到内存，因此子索引将匹配的行外推到数据块粒度。这与普通跳过索引不同，普通跳过索引以索引块粒度跳过数据。

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