HNSW 索引

HNSW是一种用于近似最近邻搜索的算法。它是一种常用的索引类型，在查询高维向量（比如表示嵌入的向量）时可以提升性能。

🌐 HNSW is an algorithm for approximate nearest neighbor search. It is a frequently used index type that can improve performance when querying highly-dimensional vectors, like those representing embeddings.

用法 #

🌐 Usage

你创建 HNSW 索引的方式取决于你使用的距离运算符。pgvector 包含 3 个距离运算符：

🌐 The way you create an HNSW index depends on the distance operator you are using. pgvector includes 3 distance operators:

使用以下 SQL 命令为你查询中使用的操作符创建 HNSW 索引。

🌐 Use the following SQL commands to create an HNSW index for the operator(s) used in your queries.

欧几里得 L2 距离（vector_l2_ops#

🌐 Euclidean L2 distance (vector_l2_ops)

1
create index on items using hnsw (column_name vector_l2_ops);

内积 (vector_ip_ops#

🌐 Inner product (vector_ip_ops)

1
create index on items using hnsw (column_name vector_ip_ops);

余弦距离 (vector_cosine_ops#

🌐 Cosine distance (vector_cosine_ops)

1
create index on items using hnsw (column_name vector_cosine_ops);

对于 pgvector 0.7.0 及以上版本，可以在向量上创建如下最大维度的索引：

🌐 For pgvector versions 0.7.0 and above, it's possible to create indexes on vectors with the following maximum dimensions:

• 向量：最多 2,000 维
• halfvec：最多 4000 个维度
• 位：高达 64,000 维

你可以通过运行 SELECT * FROM pg_extension WHERE extname = 'vector'; 来查看你当前的 pgvector 版本，或者在你的 Supabase 项目仪表板中导航到 扩展 标签查看。

🌐 You can check your current pgvector version by running: SELECT * FROM pg_extension WHERE extname = 'vector'; or by navigating to the Extensions tab in your Supabase project dashboard.

如果你使用的是早期版本的 pgvector，你应该在这里升级你的项目。

🌐 If you are on an earlier version of pgvector, you should upgrade your project here.

高维向量的例子 #

🌐 Example with high-dimensional vectors

对于维度超过 2,000 的向量，你可以使用 halfvec 类型来创建索引。这里有一个 3,072 维的示例：

🌐 For vectors with more than 2,000 dimensions, you can use the halfvec type to create indexes. Here's an example with 3,072 dimensions:

1
CREATE TABLE documents (
2
    id bigint GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
3
    content text,
4
    embedding vector(3072)
5
);
6
7
CREATE INDEX ON documents
8
    USING hnsw ((embedding::halfvec(3072)) halfvec_cosine_ops);

HNSW 是怎么运作的？ #

🌐 How does HNSW work?

HNSW 使用邻近图（基于节点之间的距离连接节点的图）来近似最近邻搜索。要理解 HNSW，我们可以把它分成两部分：

🌐 HNSW uses proximity graphs (graphs connecting nodes based on distance between them) to approximate nearest-neighbor search. To understand HNSW, we can break it down into 2 parts:

• 分层 (H): 这个算法在多个层次上运行
• 可导航小世界（NSW）： 每个向量都是图中的一个节点，并且与多个其他节点相连

层级的 #

🌐 Hierarchical

HNSW 的层次结构是建立在跳表的概念之上的。

🌐 The hierarchical aspect of HNSW builds off of the idea of skip lists.

跳表是多层链表。最底层是一个普通的链表，连接着有序的元素序列。上面每一层都会从下层去掉一些元素（基于固定概率），生成一个更稀疏的子序列，可以“跳过”一些元素。

🌐 Skip lists are multi-layer linked lists. The bottom layer is a regular linked list connecting an ordered sequence of elements. Each new layer above removes some elements from the underlying layer (based on a fixed probability), producing a sparser subsequence that “skips” over elements.

下面的图显示了一个多层跳跃表。最底层链接了所有有序元素，每一层上方都保留了一个更稀疏的子集，可以跳过一些元素。

🌐 The diagram below shows a multi-layer skip list. The bottom layer links every ordered element, and each layer above keeps a sparser subset that skips over elements.

在搜索一个元素时，算法会从最顶层开始，沿着它的链表水平遍历。如果找到了目标元素，算法就会停止并返回它。否则，如果链表中的下一个元素大于目标（或 NULL），算法就会下降到下一层。由于下面的每一层都比上层稀疏度低（最底层连接所有元素），最终会找到目标元素。跳表在搜索和插入/删除操作上平均都能达到 O(log n) 的复杂度。

🌐 When searching for an element, the algorithm begins at the top layer and traverses its linked list horizontally. If the target element is found, the algorithm stops and returns it. Otherwise if the next element in the list is greater than the target (or NULL), the algorithm drops down to the next layer below. Since each layer below is less sparse than the layer above (with the bottom layer connecting all elements), the target will eventually be found. Skip lists offer O(log n) average complexity for both search and insertion/deletion.

可导航的小世界 #

🌐 Navigable Small World

可导航小世界（NSW）是一种特殊类型的邻近图，它还包括节点之间的长距离连接。这些长距离连接支持图的“小世界”特性，也就是说几乎每个节点都可以通过几步就从其他节点到达。如果没有这些额外的长距离连接，达到远处的节点可能需要很多步。

🌐 A navigable small world (NSW) is a special type of proximity graph that also includes long-range connections between nodes. These long-range connections support the “small world” property of the graph, meaning almost every node can be reached from any other node within a few hops. Without these additional long-range connections, many hops would be required to reach a far-away node.

下图显示了一个可导航的小世界图。每个节点都连接到附近的邻居，还有一些远程链接，所以几乎任何节点都可以在几步之内到达其他节点。

🌐 The diagram below shows a navigable small world graph. Each node connects to nearby neighbors plus a few long-range links, so almost any node can reach any other in a few hops.

新南威尔士州（NSW）中所谓的“可导航”部分，具体指的是能够在图上对贪婪搜索算法进行对数级别的扩展，这种算法试图在每一步只做局部最优选择。如果没有这个特性，这个图仍然可能被认为是一个小世界，远距离节点之间的路径很短，但贪婪算法往往找不到它们。贪婪搜索非常适合NSW，因为它导航起来很快，计算成本也低。

🌐 The “navigable” part of NSW specifically refers to the ability to logarithmically scale the greedy search algorithm on the graph, an algorithm that attempts to make only the locally optimal choice at each hop. Without this property, the graph may still be considered a small world with short paths between far-away nodes, but the greedy algorithm tends to miss them. Greedy search is ideal for NSW because it is quick to navigate and has low computational costs.

分层 +#

🌐 Hierarchical + Navigable Small World

HNSW结合了这两个概念。从层级的角度来看，最底层由一个由节点间短链接组成的NSW构成。每一层向上都会“跳过”一些元素，并在距离较远的节点之间创建更长的链接。

🌐 HNSW combines these two concepts. From the hierarchical perspective, the bottom layer consists of a NSW made up of short links between nodes. Each layer above “skips” elements and creates longer links between nodes further away from each other.

像跳表一样，搜索从最顶层开始，然后一直向下，直到找到目标元素。不过，不同的是，每一层不是通过比较标量值来决定是否往下走，而是使用多维度的距离测量（比如欧几里得距离）。

🌐 Like skip lists, search starts at the top layer and works its way down until it finds the target element. However, instead of comparing a scalar value at each layer to determine whether or not to descend to the layer below, a multi-dimensional distance measure (such as Euclidean distance) is used.

你什么时候应该创建 HNSW 索引？ #

🌐 When should you create HNSW indexes?

在创建向量索引时，HNSW 应该是你的默认选择。当你不需要 100% 的准确性，并且愿意用一点准确性换取大量吞吐量时，就可以添加这个索引。

🌐 HNSW should be your default choice when creating a vector index. Add the index when you don't need 100% accuracy and are willing to trade a small amount of accuracy for a lot of throughput.

与 IVFFlat 索引不同，你可以在表创建后立即构建 HNSW 索引。HNSW 索引是基于图的，本身不会受到 IVFFlat 的相同限制。随着新数据的加入，索引会自动填充，并且索引结构会保持最佳状态。

🌐 Unlike IVFFlat indexes, you are safe to build an HNSW index immediately after the table is created. HNSW indexes are based on graphs which inherently are not affected by the same limitations as IVFFlat. As new data is added to the table, the index will be filled automatically and the index structure will remain optimal.

使用 HNSW 索引进行过滤 #

🌐 Filtering with HNSW indexes

在向向量查询添加 where 子句时，并不会绕过 HNSW 索引。Postgres 的规划器会根据过滤器的选择性和表的大小，在使用索引和顺序扫描之间进行选择。当使用索引时，过滤器会在索引返回候选项时应用。

🌐 Adding a where clause to a vector query does not bypass the HNSW index. The Postgres planner picks between using the index and a sequential scan based on the selectivity of the filter and the size of the table. When the index is used, the filter is applied as the index returns candidates.

当过滤器具有选择性时，就会出现权衡：HNSW 扫描会按距离返回前 k 行，如果其中大多数被过滤掉，你最终可能得到的行数比 LIMIT 少。从 pgvector 0.8.0 起，规划器支持迭代索引扫描，会自动扫描更多索引直到找到足够的结果，这由 hnsw.iterative_scan GUC 控制。默认值是 off。启用的两种模式是：

🌐 The trade-off shows up when the filter is selective: an HNSW scan returns the top k rows by distance, and if most of those are filtered out you can end up with fewer rows than your LIMIT. From pgvector 0.8.0, the planner supports iterative index scans that automatically scan more of the index until enough results are found, controlled by the hnsw.iterative_scan GUC. The default is off. The two enabled modes are:

• strict_order 在多次迭代中保持精确的距离顺序。
• relaxed_order 允许在多次迭代中稍微调整顺序，以便更好地回忆。

hnsw.max_scan_tuples（默认 20,000）和 hnsw.scan_mem_multiplier（默认 1）决定了迭代扫描的范围。完整参考请查看 pgvector 迭代扫描文档。

想看一个完整的 JavaScript 示例，演示如何通过另一列过滤向量搜索，可以参考 按元数据过滤向量搜索。

🌐 For an end-to-end JavaScript example of filtering a vector search by another column, see Filtering vector search by metadata.

资源 #

🌐 Resources

在 pgvector 的 GitHub 页面 上阅读更多关于索引的信息。

🌐 Read more about indexing on pgvector's GitHub page.