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

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

虽然一篇更传统的博文可能会探索这些算法、它们的实现以及它们在 ClickHouse 中的使用，但我们的首席技术官兼创始人 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。“月光”的向量位于所有直线上方，因此具有 111 的位序列。“手电筒”相反位于 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 的测试集，该测试集包含 210 万个向量，这些向量是从 8400 亿个CommonCrawl标记中训练出来的。此集合中的每个向量都有 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。我们需要执行向量差来计算我们的“normal”列。简单的减法就可以实现这一点。上述表中称为offset的中点可以使用(v1 + v2)/2计算。

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.)

此查询的第一部分使用带有groupArray函数的 CTE 将我们的平面定向到单行两列中，每列包含 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 位，提供一个值，其中只有第 i 位在点积产生 true 时设置为 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 distance <= 5 ORDER BY cosine	响应时间（秒）	WHERE distance <= 10 ORDER BY cosine	响应时间（秒）
猫	猫 小猫 狗 猫咪 宠物	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 崎 运输 卡车 ids 椅子	0.083	烤箱	0.068	桌子 椅子 椅子 沙发 家具	0.117

这里有一些观察结果

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

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

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.

请注意，由于查询复杂性的降低，我们在这里也获得了一点性能提升。

与 HNSW 等更复杂的 ANN 算法相比，此方法具有许多优势。我们已经证明，当与窗口重新评分结合使用时，我们可以保持相关性准确性并获得不错的加速——大约 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 过滤并重新评分前 N 个结果时，我们的查询可以利用此排序来加快查询速度并避免完全线性扫描。我们的距离条件在PREWHERE 条件中提供，这实际上意味着首先（并行）扫描 bit 列以识别匹配的颗粒。鉴于此列的大小（约 13MiB），这可以在 ClickHouse 高度矢量化的查询管道中非常快速地完成。向量列（在 1.5GiB 处明显更大）仅会为与我们的 PREWHERE 距离子句匹配的那些颗粒加载和扫描。这种两步过滤最大程度地减少了要加载的数据，并有助于提高我们的性能。

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

最重要的是，这些方法始终更好地表示“邻居”的概念。我们对空间的粗略划分假设不了解空间，并将其划分为随机生成的平面（尽管我们的中点方法利用了一些关于空间的信息，但它相当粗糙）。如果我们的向量在每个维度上都均匀地分布在空间中，这将是完全可以的。不幸的是，在现实中，情况并非如此，向量集群更为常见。如果平面划分这些集群，则两个相邻向量的邻近性可能会在编码中丢失。例如，请考虑下图

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

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

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

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

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

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

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

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