HNSW

CREATE/BUILD INDEX

方式二，CREATE/BUILD INDEX

CREATE TABLE sift_1M (
  id int NOT NULL,
  embedding array<float>  NOT NULL  COMMENT ""
) ENGINE=OLAP
DUPLICATE KEY(id) COMMENT "OLAP"
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
  "replication_num" = "1"
);

INSERT INTO sift_1M
SELECT *
FROM S3(
  "uri" = "https://selectdb-customers-tools-bj.oss-cn-beijing.aliyuncs.com/sift_database.tsv",
  "format" = "csv");

导入数据后 CREATE INDEX，此时 table 上已经有了 index 的定义，但是没有真正在存量数据上构建索引。

CREATE INDEX idx_test_ann ON sift_1M (`embedding`) USING ANN PROPERTIES (
  "index_type"="hnsw",
  "metric_type"="l2_distance",
  "dim"="128"
);

SHOW DATA ALL FROM sift_1M

+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
| TableName | IndexName | ReplicaCount | RowCount | LocalTotalSize | LocalDataSize | LocalIndexSize | RemoteTotalSize | RemoteDataSize | RemoteIndexSize |
+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
| sift_1M   | sift_1M   | 1            | 1000000  | 170.001 MB     | 170.001 MB    | 0.000          | 0.000           | 0.000          | 0.000           |
|           | Total     | 1            |          | 170.001 MB     | 170.001 MB    | 0.000          | 0.000           | 0.000          | 0.000           |
+-----------+-----------+--------------+----------+----------------+---------------+----------------+-----------------+----------------+-----------------+
2 rows in set (0.01 sec)

通过 BUILD INDEX 语句来完成索引的构建工作：

BUILD INDEX idx_test_ann ON sift_1M;

BUILD INDEX 是异步执行的，需要通过 SHOW ALTER 来查看任务的执行状态。

SHOW BUILD INDEX WHERE TableName = "sift_1M"
--------------

+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| JobId         | TableName | PartitionName | AlterInvertedIndexes                                                                                                               | CreateTime              | FinishTime              | TransactionId | State    | Msg  | Progress |
+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| 1763603913428 | sift_1M   | sift_1M       | [ADD INDEX idx_test_ann (`embedding`) USING ANN PROPERTIES("dim" = "128", "index_type" = "hnsw", "metric_type" = "l2_distance")],  | 2025-11-20 11:14:55.253 | 2025-11-20 11:15:10.622 | 126128        | FINISHED |      | NULL     |
+---------------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+

DROP INDEX

同样可以通过 ALTER TABLE sift_1M DROP INDEX idx_test_ann 来删除不合适的 Ann 索引。DROP INDEX 通常发生在索引的超参数调优阶段，为了确保足够的召回率需要测试不同的参数组合，需要灵活的索引管理。

索引超参数

HNSW 索引以分层图的形式组织向量。在构建阶段，向量逐个插入索引中，并在多层结构中寻找邻居节点。构建流程包括：

1. 多层随机赋级（Layer assignment）：每个向量被随机分配到多个层中，较高层节点更稀疏，用于快速导航。

2. 使用 ef_construction 搜索候选邻居： 在每一层，HNSW 使用一个最大长度为 ef_construction 的候选队列来执行广度优先的局部搜索。 更大的 ef_construction 能找到更准确的邻居，使图结构更合理、搜索质量更高，但构建时间会更长。

3. 使用 max_degree 限制连接数： 每个节点的邻居数受到 max_degree 的限制，保证图结构不会过于稠密。

在查询阶段：

1. 高层贪心搜索（Coarse search）： 从入口点开始，自顶向下在高层执行贪心搜索，快速找到接近目标区域的节点。

2. 底层使用 ef_search 执行广度搜索（Fine search）： 在第 0 层，HNSW 使用最大长度为 ef_search 的候选队列进行更全面的邻域扩展。

总之：

• max_degree 定义了图中每个节点保存的双向边的个数，该参数会影响召回率，内存使用率以及查询性能。更大的 max_degree 会提高召回率，但是会降低查询性能。

• ef_construction 定义了索引阶段用来保存候选节点的队列的最大长度，增大 ef_construction 可以提高图的质量，获得更高的召回率，但是也会导致索引构建时间变长。

• 对应 ef_search 定义了查询阶段候选节点队列的最大长度，更大的 ef_search 也会提高召回率，但是会导致搜索时距离计算次数变多，查询延迟变高，并且 CPU 开销变大。

SelectDB 默认的 max_degree 为 32，默认的 ef_construction 和 ef_search 分别为 40 和 32。

上述测试都是对这三个超参数定性的分析，通过实际实验，在 SIFT_1M 数据集上有如下的测试结果

从实际测试结果来看，为了达到同一水平的召回率，可以有不同的超参数组合方案。比如假设目标是 top 100 的召回率大于 95%，满足条件的组合有：

虽然很难事先给出超参数的具体取值，但是我们可以给出一个关于如何选取超参数的实践方法：

1. 建立一张无索引的表 table_multi_index，table_multi_index 可以有 2 或者 3 个向量列。

2. 通过 stream load 等方式将数据导入到无索引的 table_multi_index。

3. 通过 CREATE INDEX 和 BUILD INDEX 在所有的向量列上构建索引。

4. 不同的列选择不同的索引参数，等索引构建完成后在不同的列上计算召回率，找到最合适的超参数组合。

索引覆盖的行数

SelectDB 内表的数据是分层组织的。最高层级的概念是 Table，Table 按照分桶键把原始数据尽可能均匀地分布到 N 个 tablets 里面，tablet 是用来进行数据迁移与rebalance的基本单位。每次导入或者compaction会在tablet下新增一个rowset，rowset是进行版本管理的单位，其本身只是代表一组具有版本号的数据，这组数据真正存储在 segment 文件里。

与倒排索引一样，向量索引也作用在 segment 粒度上。segment 本身的大小取决于 be conf 中的 write_buffer_size 和 vertical_compaction_max_segment_size，在导入和 compaction 过程中，当内存中 memtable 的积累到一定大小后就会下刷生成一个 segment 文件，并且为该 segment 构造一个向量索引（如果有多个索引列那么就有多个索引），该索引能够覆盖的范围就是这个 segment 中对应列的行数。根据前面对 HNSW 算法搜索与构建过程的介绍，对于某组索引参数，其能够有效覆盖的数据范围是有限的，当数据量超过某个阈值后，召回率就无法满足要求。

这里我们给出一些索引超参数和其能够覆盖的 segment 行数的经验值

通过 SHOW TABLETS FROM table 可以看到某张表的 Compaction 状态，点开对应的 URL 可以看到这张表有多少个 segment。

Compaction 对召回率的影响

Compaction 之所以会影响召回率是因为 compaction 有时会生成更大的 segment，导致原先的索引超参数无法在新的更大的 segment 上保障覆盖率。因此建议在 BUILD INDEX 之前触发一次 FULL COMPACTION，在充分合并过的 segment 上构建索引不光可以保持召回率稳定，还可以减少索引构建引入的写放大。

索引文件的冷加载

SelectDB 的 ANN 索引是基于 Meta 开源的 faiss实现的。HNSW 索引需要在完整的图结构全部被加载进内存后才能进行查询加速，因此建议在高并发查询之前，先进行一次冷查询，确保涉及到的 segment 的索引文件全部加载进了内存，否则对于查询性能会有较大影响。

内存空间与性能

HNSW 索引（无量化压缩）占用的内存空间近似等于其所能检索的向量的内存大小的 1.2 倍。比如对于 128 维，1M 的数据集，HNSW FLAT 索引需要的内存空间大约为 128 * 4 * 1000000 * 1.3 约等于 650 MB。

为了保证查询性能，需要 BE 有足够的内存空间，否则索引的频繁 IO 会导致查询性能大幅衰减。