使用 SQL 驱动的 LSH 和随机投影的 ANN 向量搜索

今年早些时候，我们探索了 ClickHouse 中的向量搜索功能。虽然这主要集中在暴力线性技术上，即将搜索向量与 ClickHouse 中满足其他过滤条件的所有向量进行比较，但我们也触及了最近添加的新兴近似最近邻技术。这些技术目前在 ClickHouse 中处于实验阶段，支持 Annoy 和 HNSW。

虽然更传统的博客文章可能会探讨这些算法、它们的实现以及它们在 ClickHouse 中的应用，但我们的 CTO 兼创始人 Alexey Milovidov 认为，大多数数据问题都可以通过 SQL 解决。几个月前，他在西班牙的一次聚会上提出了另一种使用随机投影和 SQL 构建向量索引的方法。在这篇文章中，我们将探索 Alexey 的方法，并测试和评估其有效性。

向量嵌入是概念的数值表示，由一系列浮点数（可能数千个）组成，代表高维空间中的位置。这些嵌入通常由机器学习模型（如亚马逊的 Titan）生成，并且可以为任何媒介（如文本和图像）创建。在这个高维空间中彼此靠近的向量代表相似的概念。对于三个维度（大多数人可以理解的最高维度），这可以可视化

我们在之前的文章中详细探讨了这个概念，包括为什么这很有用。在向量搜索中，问题归结为在一组大型向量嵌入中找到与搜索或输入向量相似的那些。此搜索向量通常是使用相同的模型通过查询生成的。因此，我们实际上是在查找向量以及与我们的搜索查询相似的内容。同样，此查询可以是任何媒介。

同样，在此上下文中，这等同于两个向量之间的距离或角度。数学（通常是余弦相似度或欧几里得距离）用于计算这些统计数据并扩展到 N 维。解决此问题最简单的解决方案是简单的线性扫描

虽然线性扫描可能非常快速且足够，尤其是在像 ClickHouse 这样的高度并行化的情况下，但有些数据结构可以潜在地降低 O(n) 复杂度。这些数据结构或向量索引被近似算法利用，这些算法通常必须在高召回率（检索到的相关记录数与相关记录总数之比 - 假设我们具有最小相似性）和低延迟之间进行权衡。

这些近似算法通常称为近似最近邻 (ANN)。此命名暗示了尝试近似查找最近向量的一般问题。

我们的线性扫描方法具有 100% 的召回率，但在数十亿行的情况下实现可接受的延迟可能具有挑战性。理论上，这些算法通过牺牲一些召回率来以更低的计算成本提供更低延迟的响应。实际上，它们返回一组近似结果，如果仍然存在足够百分比的“最佳结果”，则这些结果可能就足够了。

通常，这些算法的质量以召回率-延迟曲线或召回率-QPS（每秒查询数）曲线表示

参见 ANN 基准

虽然这为我们提供了性能衡量标准，但它通常代表理想的设置。它无法衡量生产环境中出现的其他重要因素。例如，这些算法在多大程度上支持向量更新，以及它们是否可以轻松持久保存到磁盘或必须完全在内存中运行，这些支持程度也各不相同。我们简单的线性扫描不受这些限制中的任何一个的限制。

虽然我们认识到 HNSW 等算法的价值（因此我们已将其添加到 ClickHouse 中），但也许我们可以回到问题的基本原则，并在保留轻松更新向量集的能力且不受内存限制的情况下，加速向量的搜索。

本着这种精神，并且由于 Alexey 喜欢使用 SQL 完成所有操作，因此他提出了一个基于 局部敏感哈希 (LSH) 和随机投影的简单向量索引。

以下方法背后的核心目标是以一种降低向量维度但保持其分布和彼此局部性的表示形式对我们的向量进行编码。通过这种较低维度的表示形式，我们应该能够更有效地（在内存和 CPU 方面）计算它们的相似性。虽然我们预计这将降低相似性计算的准确性和召回率（由于我们通过降低维度而承担的信息丢失，它变成了一种估计），但我们预计质量会足够好，同时仍然受益于更快的搜索时间。正如我们将展示的那样，我们还可以将此方法与准确的距离计算相结合。

此方法依赖于局部敏感哈希或 LSH。LSH 是一种哈希函数，它将数据向量转换为较低维度的表示哈希，以便在原始域中接近的向量在生成的哈希中也很接近。这实际上与传统的哈希函数相反，后者旨在最大程度地减少冲突并确保不保留这种相似性。在我们的例子中，我们的 LSH 基于随机投影，生成的哈希是一个位序列。在原始空间中接近的向量应该具有具有相似 1 和 0 序列的位序列。

此处的实现相对简单，让我们回到一些高中数学。假设我们的向量大致均匀地分布在高维空间中（如果不是，请参阅优点和局限性）。

目标是使用 N 个随机超平面来划分我们的高维空间，其中 N 由用户配置。定义这些平面后，我们记录向量位于每个平面的哪一侧，使用简单的 1 或 0。这为每个向量提供了一个位集表示，其中每个位位置描述了向量位于随机平面的哪一侧。因此，我们的位序列将与我们选择的超平面数量一样长。

让我们看一个简化的示例，假设我们的向量只有两个维度。在这种情况下，我们的超平面是由通过原点 0,0 的向量定义的线。

我们有三个平面 p1、p2 和 p3，为每个向量生成一个 3 位序列。对于每个平面，我们记录向量是否在线上方或下方，线上方记录为 1，线下方记录为 0。“moonlight”的向量位于所有线上方，因此位序列为 111。“Flashlight”的向量相反，位于 p1 下方，但位于 p2 和 p3 上方，因此结果为 011。以上假设我们的向量在单位空间内，即 -1 到 1（并非总是如此），并且我们对线的上方和下方有一个概念（上面的示例可能很直观，但对于空间中的所有向量来说并不稳健）。

因此，这里有两个最终问题：我们如何计算向量是在线的上方还是下方？以及 我们如何选择我们的线？

为了选择我们的线，我们有几个选项。如果我们的向量已归一化（-1 到 1），我们可以选择从归一化分布中采样的空间中的随机点。我们希望这些向量理想情况下均匀分布在空间表面上（实际上是一个单位球体）。要实现这一点，需要使用范数。此点可以被认为是随机投影，它将穿过原点，通过作为其正交/法向量来定义我们高维空间中的线和超平面。此法向量将用于与其他向量比较我们的线/平面。

但是，Alexey 的示例假设这些向量未归一化。因此，他使用了一种旨在使向量更接近归一化空间的解决方案。虽然这不会在归一化空间中创建完美的均匀性，但它确实提高了随机性。这是通过在空间v1和v2中取两个随机向量并计算差值，将其标记为法向量 ((v1 - v2)) 来实现的，法向量定义了超平面。还计算了这些向量的偏移量或中点 ((v1 + v2) / 2)，并用于有效地将向量投影到此范围内，以便通过减去其值与法向量进行比较。

我们可以使用与上面定义的法向量的简单点积来计算向量 v 是在线/平面的上方还是下方。计算为两个向量的对应分量的成对乘积之和，此标量值表示输入向量的相似性或对齐方式。如果向量指向同一方向，则该值将为正值（其中 1 表示同一方向）。负值表示它们在相反方向（-1 完全相反），而值 0 表示它们是正交的。因此，我们可以使用正值表示“在线上方”，而使用 0 或更小的值表示“在线下方”。

对于上面的非归一化情况，我们计算normal和 (v - offset) 的点积。展望未来，我们将使用稍后的方法，因为它更稳健，但稍后会回到简单的情况，以显示潜在的更简单语法和略微更好的性能。

显然，此时，我们必须想象更高的维度。但是，原理保持不变。我们选择空间中的两个随机点，计算它们之间的向量，并记录中点。我们使用此平面信息来计算点是否与线正交。

上述计算有效地充当了我们的 LSH 函数，并将每个向量投影到较低维度的空间中，从而为每个向量生成了哈希值，哈希值表示为位序列。可以为表中的每个向量嵌入以及为搜索查询生成的嵌入计算此序列。反过来，我们可以通过比较位序列来估计两个向量的接近程度。理论上，位序列重叠越多，超平面共享侧的数量就越多。简单的汉明距离（衡量不同位的数量）在此处就足够了。

以上内容在 Python 或任何编程语言中实现起来相对简单。但是，ClickHouse 非常适合此任务。我们不仅可以使用几行 SQL 定义上述内容，而且我们将利用 ClickHouse 的所有优势，包括按元数据过滤、聚合以及不受内存限制的能力。插入新向量还需要我们在插入时计算行的嵌入的序列。

对于我们的测试数据集，我们将使用Glove 中的测试集，该测试集由从 840B CommonCrawl 令牌训练的 210 万个向量组成。此集中的每个向量都有 300 个维度，代表一个单词。

对于我们的测试，我们将使用具有 16 个内核的 ClickHouse Cloud 实例。

我们为目标表使用以下架构。正如之前的文章中所讨论的，ClickHouse 中的向量只是 32 位浮点数数组。

CREATE TABLE glove
(
  `word` String,
  `vector` Array(Float32)
)
ENGINE = MergeTree
ORDER BY word

要加载此数据集，我们可以使用clickhouse local来提取单词和向量，并使用字符串和数组函数，然后再将结果通过管道传输到我们的客户端。

clickhouse local --query "SELECT trim(splitByChar(' ', line)[1]) as word, arraySlice(splitByChar(' ', line),2) as vector FROM file('glove.840B.300d.zip :: glove.840B.300d.txt','LineAsString') FORMAT Native" | clickhouse client --host <host> --secure --password '<password>' --query "INSERT INTO glove FORMAT Native" 

加载后，我们需要定义我们的平面。我们将这些平面存储在表中以进行快速查找

CREATE TABLE planes (  		
  normal Array(Float32),	
  offset Array(Float32)
) 
ENGINE = MergeTree 
ORDER BY ()

此处的偏移量和法向量将是两个随机向量的中点和差值，如前所述。我们将使用简单的INSERT INTO SELECT填充它。请注意，此时，我们需要定义希望用于划分空间的平面数量。

对于下面的示例，我们选择首先使用 128 个平面。这将为每个向量生成一个 128 位的位掩码，可以使用 UInt128 表示。要创建 128 个平面，我们需要 256 个随机向量（每个平面 2 个）。我们使用表达式intDiv(rowNumberInAllBlocks(), 2)对这个随机集进行分组，并使用min和max函数来确保为每个随机点选择不同的向量。

SELECT min(vector) AS v1, max(vector) AS v2
FROM
(
	SELECT vector
	FROM glove
	ORDER BY rand() ASC
	LIMIT 256
)
GROUP BY intDiv(rowNumberInAllBlocks(), 2)

上面给了我们 128 行，每行都有两个随机向量，v1和v2。我们需要执行向量差值以计算我们的“法向量”列。简单的减法即可实现此目的。可以使用(v1 + v2)/2计算中点，在上面的表中称为offset。

INSERT INTO planes SELECT v1 - v2 AS normal, (v1 + v2) / 2 AS offset
FROM
(
	SELECT
    	  min(vector) AS v1,
    	  max(vector) AS v2
	FROM
	(
    	  SELECT vector
    	  FROM glove
    	  ORDER BY rand() ASC
    	  LIMIT 256
	)
	GROUP BY intDiv(rowNumberInAllBlocks(), 2)
)

0 rows in set. Elapsed: 0.933 sec. Processed 2.20 million rows, 2.65 GB (2.35 million rows/s., 2.84 GB/s.)
Peak memory usage: 4.11 MiB.

在 Alexey 最初的演讲中，他使用了表达式“`arrayMap((x, y) -> (x - y), v1, v2)`”和“`arrayMap((x, y) -> ((x + y) / 2), v1, v2)`”来计算向量差值和中点。向量算术随后已添加到 ClickHouse，允许使用简单的“`+`”、“`-`”和“`/`”来构造这些运算。这具有显著提高速度的额外好处！

创建平面后，我们可以继续为每个现有向量创建位哈希。为此，我们将使用早期架构创建一个新表glove_lsh，其中包含 UInt128 类型的bits字段（因为我们有 128 个平面）。这将有效地成为我们的索引。请注意，我们按列对表进行排序，以加速后续的过滤操作。有关这如何有利于过滤的更多详细信息，请参阅优点和局限性。

CREATE TABLE glove_lsh
(
  `word` String,
  `vector` Array(Float32),
  `bits` UInt128
)
ENGINE = MergeTree
ORDER BY (bits, word)
SETTINGS index_granularity = 128

我们还将表的index_granularity降低到 128。这被认为是一项重要的优化，因为通常，我们将返回少量结果，并且相关向量应分布在同一组粒度中，即具有相似的位哈希。修改此设置会减小我们的粒度大小，从而对更少的行执行辅助扫描。稍后显示，我们可能还希望使用距离函数重新对向量进行评分（以获得更准确的相关性分数）。此函数的计算量更大，减少执行它的行数将有利于响应时间。

要填充我们的表，我们需要计算每个向量的位掩码。请注意，我们在此处使用 16 核实例在 100 秒内加载了 200 万个向量。

INSERT INTO glove_lsh
WITH
   128 AS num_bits,
   (
       SELECT
           groupArray(normal) AS normals,
           groupArray(offset) AS offsets
       FROM
       (
           SELECT *
           FROM planes
           LIMIT num_bits
       )
   ) AS partition,
   partition.1 AS normals,
   partition.2 AS offsets
SELECT
   word,
   vector,
   arraySum((normal, offset, bit) -> bitShiftLeft(toUInt128(dotProduct(vector - offset, normal) > 0), bit), normals, offsets, range(num_bits)) AS bits
FROM glove
SETTINGS max_block_size = 1000

0 rows in set. Elapsed: 100.082 sec. Processed 2.20 million rows, 2.69 GB (21.94 thousand rows/s., 26.88 MB/s.)

此查询的第一部分使用 CTE 和groupArray函数将我们的平面定向到单行两列，每列包含 128 个向量。这两列包含我们之前讨论的所有中点和差向量。在这种结构中，我们能够将这些向量传递到负责计算每个向量的位哈希的表达式中

arraySum((normal, offset, bit) -> bitShiftLeft(toUInt128(dotProduct(vector - offset, normal) > 0), bit), normals, offsets, range(num_bits)) AS bits

此表达式针对每一行执行。arraySum函数对 128 个 (num_bits) 元素的数组的结果求和。这是通过 lambda 函数执行的，该函数对于每个数组元素i，计算(vector - offset) ⋅ normal，其中 offset 和 normal 是来自第 i 个平面的向量。这是我们之前描述的点积计算，它确定向量位于平面的哪一侧。将此计算的结果与 0 进行比较，生成一个布尔值，我们通过toUInt128函数将其转换为 UInt128。此值向左位移 n 位，生成一个值，其中仅当点积产生 true 时，第 i 位才设置为 1，否则设置为 0。此第 i 位有效地表示此向量与第 i 个平面的关系。我们将这些整数相加得到一个十进制 UInt128，其二进制表示形式是我们的位哈希。

在上面的插入中，我们将max_block_size减小到 1000。这是因为arraySum函数的状态由于平面驻留在内存中而具有较高的内存开销。因此，具有许多行的大块可能成本很高。通过减小块大小，我们减少了每次处理的行数和状态数。

SELECT *
FROM glove_lsh
LIMIT 1
FORMAT Vertical

Row 1:
──────
word:   CountyFire
vector: [-0.3471,-0.75666,...,-0.91871]
bits:   6428829369849783588275113772152029372 <- how bit hash in binary

创建索引后，我们使用以下查询评估其大小

SELECT name, formatReadableSize(sum(data_compressed_bytes)) AS compressed_size,
	formatReadableSize(sum(data_uncompressed_bytes)) AS uncompressed_size,
	round(sum(data_uncompressed_bytes) / sum(data_compressed_bytes), 2) AS ratio
FROM system.columns
WHERE table LIKE 'glove_lsh'
GROUP BY name
ORDER BY name DESC

┌─name───┬─compressed_size─┬─uncompressed_size─┬─ratio─┐
│ word   │ 8.37 MiB    	   │ 12.21 MiB     	   │  1.46 │
│ vector │ 1.48 GiB    	   │ 1.60 GiB      	   │  1.08 │
│ bits   │ 13.67 MiB   	   │ 21.75 MiB     	   │  1.59 │
└────────┴─────────────────┴───────────────────┴───────┘

我们的bits列比我们的vector小 100 多倍。现在的问题是，这种空间的压缩表示形式是否可以更快地查询...

在使用我们的索引之前，让我们使用余弦距离（如 Glove 建议的那样）测试一个简单的暴力搜索，以提供绝对质量的基准以及我们可以认为是权威结果的内容。在下面的示例中，我们搜索与单词“dog”相似的单词

WITH
   'dog' AS search_term,
   (
       SELECT vector
       FROM glove
       WHERE word = search_term
       LIMIT 1
   ) AS target_vector
SELECT
   word,
   cosineDistance(vector, target_vector) AS score
FROM glove
WHERE lower(word) != lower(search_term)
ORDER BY score ASC
LIMIT 5


┌─word────┬──────score─┐
│ dogs    │ 0.11640698 │
│ puppy   │ 0.14147866 │
│ pet     │ 0.19425482 │
│ cat     │ 0.19831467 │
│ puppies │ 0.24826884 │
└─────────┴────────────┘

10 rows in set. Elapsed: 0.515 sec. Processed 2.21 million rows, 2.70 GB (2.87 million rows/s., 3.51 GB/s.)
Peak memory usage: 386.24 MiB.

为了简单起见，我们使用我们的 Glove 索引来查找结果。在实际的搜索场景中，我们的单词不太可能在索引中，并且需要生成向量嵌入，例如使用embed UDF 函数。

对于相同的查询，我们需要使用我们的索引为我们的术语构建上面的位哈希。对于我们的目标向量的位与每行中的位之间的汉明距离计算，我们使用bitHammingDistance函数。

UInt128 的 bitHammingDistance 函数的使用需要 ClickHouse 23.11。早期版本的用户应使用bitCount(bitXor(bits, target))来计算 UInt128 的汉明距离。

WITH 'dog' AS search_term,
   (
       SELECT vector
       FROM glove
       WHERE word = search_term
       LIMIT 1
   ) AS target_vector,
   128 AS num_bits,
   (
       SELECT
           groupArray(normal) AS normals,
           groupArray(offset) AS offsets
       FROM
       (
           SELECT *
           FROM planes
           LIMIT num_bits
       )
   ) AS partition,
   partition.1 AS normals,
   partition.2 AS offsets,
   (
       SELECT arraySum((normal, offset, bit) -> bitShiftLeft(toUInt128(dotProduct(target_vector - offset, normal) > 0), bit), normals, offsets, range(num_bits))
   ) AS target
SELECT word
FROM glove_lsh WHERE word != search_term
ORDER BY bitHammingDistance(bits, target) ASC
LIMIT 5

┌─word─────┐
│ animal   │
│ pup 	   │
│ pet 	   │
│ kennel   │
│ neutered │
└──────────

5 rows in set. Elapsed: 0.086 sec. Processed 2.21 million rows, 81.42 MB (25.75 million rows/s., 947.99 MB/s.)
Peak memory usage: 60.40 MiB.

快多了！结果与cosineDistance函数返回的精确结果不同，但似乎在很大程度上是有意义的。

此距离估计返回的质量可能会因向量空间本身以及随机位置对其进行分区的程度而异。在某些情况下，质量估计不足。如果质量较差，或者我们需要更精确的排序，则此索引也可以用于预过滤结果集，然后再对匹配结果重新评分，并可能限制为满足阈值的那些结果。这是一种常用技术，并且在历史上是许多传统搜索系统中的方法，在这些系统中，使用术语查找，并使用向量（或其他相关性）函数重新评分窗口。

WITH
   'dog' AS search_term,
   (
       SELECT vector
       FROM glove
       WHERE word = search_term
       LIMIT 1
   ) AS target_vector,
   128 AS num_bits,
   (
       SELECT
           groupArray(normal) AS normals,
           groupArray(offset) AS offsets
       FROM
       (
           SELECT *
           FROM planes
           LIMIT num_bits
       )
   ) AS partition,
   partition.1 AS normals,
   partition.2 AS offsets,
   (
       SELECT arraySum((normal, offset, bit) -> bitShiftLeft(toUInt128(dotProduct(target_vector - offset, normal) > 0), bit), normals, offsets, range(num_bits))
   ) AS target
SELECT
   word,
   bitHammingDistance(bits, target) AS approx_distance,
   cosineDistance(vector, target_vector) AS score
FROM glove_lsh
PREWHERE approx_distance <= 5
WHERE word != search_term
ORDER BY score ASC
LIMIT 5

┌─word───┬─approx_distance─┬──────score─┐
│ dogs   │           	4  │ 0.11640698 │
│ pet	 │           	3  │ 0.19425482 │
│ cat	 │           	4  │ 0.19831467 │
│ pup	 │           	2  │ 0.27188122 │
│ kennel │           	4  │  0.3259402 │
└────────┴─────────────────┴────────────┘

5 rows in set. Elapsed: 0.079 sec. Processed 2.21 million rows, 47.97 MB (28.12 million rows/s., 609.96 MB/s.)
Peak memory usage: 32.96 MiB.

因此，我们实现了 10 倍的性能提升并保留了质量！精明的读者会注意到按值 5 进行过滤 - 实际上，这是不同的位数。这在最大范围 128 内。我们是如何选择此值的？

反复试验。此值在不同的搜索词中应保持稳健，但这将取决于向量在空间中的分布。值太高，则在距离评分之前过滤掉的行不足，从而提供的性能优势最小。值太低，则所需的結果将被过滤掉。显示值分布的查询可能在此处有所帮助。此分布是正态分布（更具体地说是二项分布）

WITH
   'dog' AS search_term,
   (
       SELECT vector
       FROM glove
       WHERE word = search_term
       LIMIT 1
   ) AS target_vector,
   128 AS num_bits,
   (
       SELECT
           groupArray(normal) AS normals,
           groupArray(offset) AS offsets
       FROM
       (
           SELECT *
           FROM planes
           LIMIT num_bits
       )
   ) AS partition,
   partition.1 AS normals,
   partition.2 AS offsets,
   (
       SELECT arraySum((normal, offset, bit) -> bitShiftLeft(toUInt128(dotProduct(target_vector - offset, normal) > 0), bit), normals, offsets, range(num_bits))
   ) AS target
SELECT
    bitCount(bitXor(bits, target)) AS approx_distance,
    bar(c,0,200000,100) as scale,
    count() c
FROM glove_lsh
GROUP BY approx_distance ORDER BY approx_distance ASC

┌─approx_distance─┬──────c─┬─scale─────────────────────────────────────────────────────────────────────────┐
│           	0 │  	 1 │                                                                           	   │
│           	2 │  	 2 │                                                                           	   │
│           	3 │  	 2 │                                                                           	   │
│           	4 │ 	10 │                                                                           	   │
│           	5 │ 	37 │                                                                           	   │
│           	6 │	   106 │                                                                           	   │
│           	7 │	   338 │ ▏                                                                         	   │
│           	8 │	   783 │ ▍                                                                         	   │
│           	9 │   1787 │ ▉                                                                         	   │
│          	   10 │   3293 │ █▋                                                                        	   │
│          	   11 │   5735 │ ██▊                                                                       	   │
│          	   12 │   8871 │ ████▍                                                                     	   │
│          	   13 │  12715 │ ██████▎                                                                   	   │
│          	   14 │  17165 │ ████████▌                                                                 	   │
│          	   15 │  22321 │ ███████████▏                                                              	   │
│          	   16 │  27204 │ █████████████▌                                                            	   │
│          	   17 │  32779 │ ████████████████▍                                                         	   │
│          	   18 │  38093 │ ███████████████████                                                       	   │
│          	   19 │  44784 │ ██████████████████████▍                                                   	   │
│          	   20 │  51791 │ █████████████████████████▉                                                	   │
│          	   21 │  60088 │ ██████████████████████████████                                            	   │
│          	   22 │  69455 │ ██████████████████████████████████▋                                       	   │
│          	   23 │  80346 │ ████████████████████████████████████████▏                                 	   │
│          	   24 │  92958 │ ██████████████████████████████████████████████▍                           	   │
│          	   25 │ 105935 │ ████████████████████████████████████████████████████▉                     	   │
│          	   26 │ 119212 │ ███████████████████████████████████████████████████████████▌              	   │
│          	   27 │ 132482 │ ██████████████████████████████████████████████████████████████████▏       	   │
│          	   28 │ 143351 │ ███████████████████████████████████████████████████████████████████████▋  	   │
│          	   29 │ 150107 │ ███████████████████████████████████████████████████████████████████████████   │
│          	   30 │ 153180 │ ████████████████████████████████████████████████████████████████████████████▌ │
│          	   31 │ 148909 │ ██████████████████████████████████████████████████████████████████████████▍   │
│          	   32 │ 140213 │ ██████████████████████████████████████████████████████████████████████    	   │
│          	   33 │ 125600 │ ██████████████████████████████████████████████████████████████▊           	   │
│          	   34 │ 106896 │ █████████████████████████████████████████████████████▍                    	   │
│          	   35 │  87052 │ ███████████████████████████████████████████▌                              	   │
│          	   36 │  66938 │ █████████████████████████████████▍                                        	   │
│          	   37 │  49383 │ ████████████████████████▋                                                 	   │
│          	   38 │  35527 │ █████████████████▊                                                        	   │
│          	   39 │  23526 │ ███████████▊                                                              	   │
│          	   40 │  15387 │ ███████▋                                                                  	   │
│          	   41 │   9405 │ ████▋                                                                     	   │
│          	   42 │   5448 │ ██▋                                                                       	   │
│          	   43 │   3147 │ █▌                                                                        	   │
│          	   44 │   1712 │ ▊                                                                         	   │
│          	   45 │	   925 │ ▍                                                                         	   │
│          	   46 │	   497 │ ▏                                                                         	   │
│          	   47 │	   245 │                                                                           	   │
│          	   48 │	   126 │                                                                           	   │
│          	   49 │    66  │                                                                           	   │
│          	   50 │    46  │                                                                           	   │
│          	   51 │    16  │                                                                           	   │
│          	   52 │    6   │                                                                           	   │
│          	   53 │    5   │                                                                           	   │
│          	   54 │    3   │                                                                           	   │
│          	   55 │    6   │                                                                           	   │
│          	   56 │    1   │                                                                           	   │
│          	   60 │    1   │                                                                               │
└─────────────---─┴─-──────┴───────────────────────────────────────────────────────────────────────────────┘

57 rows in set. Elapsed: 0.070 sec. Processed 2.21 million rows, 44.11 MB (31.63 million rows/s., 630.87 MB/s.)

正态分布在这里很明显，大多数单词的距离约为 30 位。在这里，我们可以看到，即使距离为 5，实际上也将我们的过滤结果限制为 52 个(1+2+2+10+37)。

此距离限制在其他查询中有多稳健？下面，我们显示了各种搜索词和方法的结果：（1）如果我们按暴力搜索的余弦距离排序，（2）按汉明距离排序，（3）按距离 5 过滤并按余弦距离重新排序，（4）按距离 10 过滤并按余弦距离重新排序。对于这些方法中的每一种，我们都提供了响应时间。

搜索词	按余弦值排序	响应时间（秒）	按汉明距离排序	响应时间（秒）	WHERE 距离 <= 5 按余弦值排序	响应时间（秒）	WHERE 距离 <= 10 按余弦值排序	响应时间（秒）
猫	猫 小猫 狗 小猫 宠物	0.474	动物 小狗 宠物 虐待 狗舍	0.079	狗 小猫 宠物 猫科动物 小狗	0.055	猫 小猫 狗 小猫 宠物	0.159
青蛙	青蛙 蟾蜍 乌龟 猴子 蜥蜴	0.480	孔雀 蝴蝶 淡水 爱达荷州外部陆地	0.087	蝴蝶 孔雀 淡水	0.073	青蛙 蟾蜍 乌龟 猴子 蜥蜴	0.101
房子	房子 家 公寓 卧室 住宅	0.446	人 其他 笑 注册 旋转	0.080	一个 放 区域 阴影 每个人	0.063	房子 家 住宅 房屋 车库	0.160
老鼠	鼠标 小鼠 光标 键盘 兔子	0.499	运营 坚持 福利 鼠标 冗余	0.073	状态 冗余 网络摄像头 运营 挖掘机	0.045	大鼠 光标 仓鼠 啮齿动物 打字	0.141
桌子	桌子 餐桌 椅子 椅子 书桌	0.488	烤箱 xb saki 卡车 ids 椅子	0.083	烤箱	0.068	桌子 椅子 椅子 沙发 家具	0.117

这里有一些观察结果

• 按汉明距离排序比简单的暴力余弦距离搜索快大约 6 倍。但是，结果质量会大大降低，并且不太可能对我们稍后将解释的原因保持稳健。
• 与按汉明距离排序相比，过滤到距离 5 并按余弦距离重新排序可提高结果质量。性能也更优越，响应时间比暴力搜索快 10 倍。但是，结果质量似乎并非在所有搜索词中都保持稳健，这促使我们将最小距离增加到 10。
• 过滤到距离 10 并按余弦距离重新排序可提供始终如一的高质量结果。这种方法比标准余弦距离快 4 倍。

我们之前使用中点创建平面相对复杂。如前所述，如果我们的向量已归一化（如 Glove 的情况），则平面创建可以像在空间中生成随机点（代表其法向量）一样简单。这些需要归一化为 -1 到 1 之间的值，并从正态分布中选择，即我们实际上希望从单位球体中均匀采样点。从数学上讲，这需要我们使用向量的范数，这在 ClickHouse 中可用作L2Norm函数。以下INSERT INTO在单位球体上生成 128 个点/平面，每个点/平面具有 300 个维度，并使用 ClickHouse 中的randNormal和L2Norm函数。这里使用数组函数有一些复杂性 - 为了保持文章的简洁性，我们将其留给用户分解。

INSERT INTO planes_simple SELECT projection / L2Norm(projection) AS projection
FROM
(
    SELECT arrayJoin(arraySplit((x, y) -> y, groupArray(e), arrayMap(x -> ((x % 300) = 0), range(128 * 300)))) AS projection
    FROM
    (
        SELECT CAST(randNormal(0, 1), 'Float32') AS e
        FROM numbers(128 * 300)
    )
)

在这种情况下，我们的平面仅由一个点组成。这简化了填充我们的表glove_lsh_simple和位哈希所需的查询。这种简化显著缩短了插入时间 - 现在仅需 43 秒（从 100 秒减少）。

INSERT INTO glove_lsh_simple
WITH
    128 AS num_bits,
    (
        SELECT groupArray(projection) AS projections
        FROM
        (
            SELECT *
            FROM planes_simple
            LIMIT num_bits
        )
    ) AS projections
SELECT
    word,
    vector,
    arraySum((projection, bit) -> bitShiftLeft(toUInt128(dotProduct(vector, projection) > 0), bit), projections, range(num_bits)) AS bits
FROM glove
SETTINGS max_block_size = 1000

0 rows in set. Elapsed: 43.425 sec. Processed 2.20 million rows, 2.69 GB (50.57 thousand rows/s., 61.95 MB/s.)

查询也更简单，并产生可比较的结果

WITH
    'dog' AS search_term,
    (
        SELECT vector
        FROM glove
        WHERE word = search_term
        LIMIT 1
    ) AS target_vector,
    128 AS num_bits,
    (
        SELECT groupArray(projection) AS projections
        FROM
        (
            SELECT *
            FROM planes_simple
            LIMIT num_bits
        )
    ) AS projections,
    (
        SELECT arraySum((projection, bit) -> bitShiftLeft(toUInt128(dotProduct(target_vector, projection) > 0), bit), projections, range(num_bits))
    ) AS target
SELECT word
FROM glove_lsh_simple
WHERE word != search_term
ORDER BY bitCount(bitXor(bits, target)) ASC
LIMIT 5

┌─word────┐
│ dogs    │
│ puppy   │
│ pet     │
│ doggy   │
│ puppies │
└─────────┘

5 rows in set. Elapsed: 0.066 sec. Processed 2.21 million rows, 81.26 MB (33.63 million rows/s., 1.24 GB/s.)
Peak memory usage: 53.71 MiB.

请注意，由于查询复杂性降低，我们在此处也获得了小的性能提升。

与更复杂的 ANN 算法（如 HNSW）相比，此方法具有许多优点。我们已经表明，当与窗口上的重新评分结合使用时，我们在保持相关性准确性的同时实现了不错的加速 - 大约 4 倍。上面的结果还表明，我们的查询具有非常低的内存开销 - 大约 50MiB。虽然这可以归因于 ClickHouse 没有将所有位集存储在内存中，但索引表示形式也非常高效，每个向量只有 128 位。此方法也不需要将索引保存在内存中，在磁盘上具有非常紧凑的表示形式，如下所示

SELECT
    table,
    name,
    formatReadableSize(sum(data_compressed_bytes)) AS compressed_size,
    formatReadableSize(sum(data_uncompressed_bytes)) AS uncompressed_size
FROM system.columns
WHERE table = 'glove_lsh'
GROUP BY table, name

┌─table─────┬─name───┬─compressed_size─┬─uncompressed_size─┐
│ glove_lsh │ word   │ 8.37 MiB        │ 12.21 MiB         │
│ glove_lsh │ vector │ 1.48 GiB        │ 1.60 GiB          │
│ glove_lsh │ bits   │ 13.67 MiB       │ 21.75 MiB         │
└───────────┴────────┴─────────────────┴───────────────────┘

5 rows in set. Elapsed: 0.024 sec.

从上面我们可以看到，我们的 bits 列（实际上是我们的索引）在磁盘上压缩后消耗大约 13MiB，而向量的存储需要 1.5GiB。此外，添加其他行也很简单且计算成本低廉 - 我们在插入时计算我们的 bits 列。最后，此方法适用于 ClickHouse 的并行执行模型，并且易于分发。这可以通过向节点添加更多内核（即纵向扩展）或通过跨节点分片数据来实现。或者，在 ClickHouse Cloud 中，仅在对象存储中保留数据的单个副本，并且计算与存储分离，用户可以动态扩展其节点。这些方法中的任何一种都允许并行化工作，以便加速查询或支持更高的 QPS 率。

最后，这里可能有趣的是此方法如何专门适用于 ClickHouse 及其磁盘上的列式结构。精明的读者会注意到，我们按 bits 列本身对表进行了排序，即ORDER BY (bits, word)。当按距离 N 过滤并重新评分前几条结果时，我们的查询可以利用此排序来加速查询并避免完全线性扫描。我们的距离条件在PREWHERE条件中提供，这实际上意味着首先（并行）扫描位列以识别匹配的粒度。考虑到此列的大小（大约 13MiB），可以在 ClickHouse 的高度向量化查询管道中非常快速地完成此操作。向量列（在 1.5GiB 时明显更大）将仅针对与我们的 PREWHERE 距离子句匹配的那些粒度加载和扫描。这种两步过滤最大限度地减少了要加载的数据，并有助于提高我们的性能。

虽然以上优点列表令人信服，但仍存在一些局限性。虽然我们尚未严格评估召回率，但上述方法不太可能像基于图的方法（如 HNSW）那样有效。所有 ANN 算法通常都会在它们的参数化程度以及用于划分和表示高维空间的数据结构的大小方面做出妥协。基于图的算法是高度参数化的，并计算空间的精细表示。

最重要的是，这些方法通常能更好地表示“邻居”的概念。我们相当粗糙的空间划分方式假设对空间一无所知，并将其划分为随机生成的平面（虽然我们的中点方法使用了一些关于空间的信息，但这非常粗略）。如果我们的向量在每个维度上均匀分布在空间中，这将完全没问题。不幸的是，在现实中，情况并非如此，向量簇更为常见。如果平面划分了这些簇，那么两个相邻向量的邻近性可能会在编码中有效地丢失。例如，请看下图

在这个例子中，我们丢失了一些类似于“狗”的概念，因为它们落在分隔平面的两侧。随着我们增加平面的数量，这个问题变得不那么严重，例如，不太可能再有 127 个平面会分隔这两个点。然而，它们很可能会以不完美的方式划分空间，从而导致不完美的相关性。

此外，我们的距离度量相当粗糙，无法在搜索之间进行比较。特定的距离度量对于“接近度”或两个向量是否为“邻居”具有不同的概念，这取决于空间的位置。例如，距离 4 可能表示空间稀疏区域中的近邻。相反，在向量密集区域中，它可能毫无意义。

这里可能的一个类比是，人们对邻居的概念如何相对于人口密度而言是相对的——纽约的邻居可能是住在对面公寓的人。在怀俄明州偏远地区，邻居可能在 10 英里之外。诸如 HNSW 之类的基于图的算法通过使用更多的参数，并以更好的点划分方式更详细地映射空间来解决这个问题，从而提供了一种更优越的最近邻度量方法。然而，它们在更新和有效地持久化到磁盘上时，计算成本更高。

这些因素使得我们使用汉明距离计算的距离度量变得粗糙，仅仅是一个估计值。我们使用精确余弦距离的重评分方法确实有助于很好地解决这个问题，同时保留了性能优势。

最后，我们将简要讨论实际需要多少个超平面的问题，以及我们的位哈希应该有多大。这将导致一篇更长的博客文章，但总而言之，这取决于向量的数量及其维度。通常，更多的位 = 更好的搜索质量（和召回率），因为空间具有更大的参数化和划分，以及我们的 LSH 值中更少的冲突，但代价是查询性能较慢。

对于 glove，我们的 LSH 中有 128 位，这有效地给了我们哈希中 2*128 = 3.4^10^38 个桶。对于 200 万个向量，这应该会导致非常低的冲突概率。哈希可能会减少到 32 位（通过 UInt32 表示），并且有足够的桶来减少冲突。然而，我们对 glove 的简短测试表明，128 位的值提供了最佳的结果质量，尽管大多数桶从未被填充——每个桶中的向量数量可以通过对位列进行简单的聚合和计数来确定。虽然我们的平均每个桶少于一个向量且没有冲突，但将分辨率提高到避免冲突所需的数量以上可以提高桶的精度和空间划分。

具有更高维度向量的用户可能希望尝试使用更多位，例如通过 UInt256 使用 256 位。这些更大的空间将需要更多的平面来有效地划分向量。但是请注意，这将需要更多的计算开销，因为需要比较更多的位。总而言之，位/平面的数量通常取决于数据集，并且需要进行一些测试（特别是当与距离阈值和重评分结合使用时），尽管 128 位似乎是一个不错的起点。

在这篇文章中，我们研究了 ClickHouse 用户如何仅使用 SQL 创建向量索引来加速最近邻搜索。更具体地说，通过在高维空间中创建随机超平面并计算位序列，我们可以使用汉明距离计算来估计向量之间的距离。这种方法可能会将向量搜索速度提高 10 倍或精确匹配提高 4 倍。我们介绍了这种方法的优点和缺点。请告诉我们您是否觉得这很有用，并在您自己的数据集上尝试了这种方法！