我們知道m(xù)ysql一般的索引結(jié)構(gòu)都是通過B+ tree實(shí)現(xiàn)。一般索引都是通過索引結(jié)構(gòu)可以快速準(zhǔn)確定位需要的數(shù)據(jù)。而向量索引就是快速查詢與給定向量的最相似的N個(gè)向量。所以
- 向量索引主要是一個(gè)近似搜索，而非一般索引的準(zhǔn)確比對(duì)；
- 向量在多維度向量空間上的點(diǎn)，而不像傳統(tǒng)數(shù)據(jù)可以直接比大小，所以傳統(tǒng)索引結(jié)構(gòu)可以利用大小比較快速定位；
- 向量檢索的大部分場(chǎng)景都是返回與該元素相似的topk個(gè)元素，而相似度（即距離相近的向量）可以是歐拉距離，也可以是夾角余弦距離。目前最大的問題就是如何快速找到相似的k個(gè)元素
如果遍歷所有向量，比較獲取相似度最高的k個(gè)向量，就類似全部掃描方式，也就沒有索引的事了。索引就是一種可以快速查找的數(shù)據(jù)結(jié)構(gòu)。
一、HNSW，分層近鄰圖索引
HNSW，即Hierarchical Navigable Small World graphs（分層-可導(dǎo)航-小世界-圖）的縮寫，可以說是在工業(yè)界影響力最大的基于圖的近似最近鄰搜索算法（Approximate Nearest Neighbor，ANN）。下面是參考網(wǎng)上的一些理解，列舉在下面：
引子
問題：假設(shè)我們有一個(gè)海量的圖像庫。給定一張查詢圖像，如何從海量的圖像庫中找到最相似的K張圖像？
我們可以把每個(gè)圖像映射成一個(gè)向量E，假設(shè)在余弦相似度下這個(gè)Embeddding很好的度量圖像間的相似度。那么，一個(gè)可能胚胎小寶寶都能想到的方法是：我們可以把查詢圖片的E和庫里面所有圖像的E計(jì)算相似度，并返回最相似的K個(gè)圖像。
這就是我們熟知的KNN（K Nearest Neighbor）算法，它的時(shí)間復(fù)雜度隨著庫的規(guī)模變大線性遞增。通常情況下，即便使用GPU也無法承受百萬以上量級(jí)的庫。因此，對(duì)其進(jìn)行優(yōu)化是必須的。
對(duì)KNN進(jìn)行優(yōu)化，有兩個(gè)思路：
- 減少相似度的計(jì)算量;
- 減少計(jì)算相似度的次數(shù)。
ANN（Approximate Nearest Neighbor）的提出就是通過優(yōu)化后者從而加速搜索速度。這里ANN返回的Top-K不是真的Top-K，只是近似的Top-K。而基于圖的ANN，目的在于：對(duì)庫中的向量構(gòu)建一個(gè)圖，使得我們只需要遍歷很小的一部分子圖，即可返回Top-K搜索結(jié)果。因此這里構(gòu)建圖的方式是關(guān)鍵中的關(guān)鍵！
什么樣的圖適合檢索？
什么樣的圖適合檢索？要回答這個(gè)問題，我們首先得了解怎么在圖上進(jìn)行搜索。就像樸素的廣度優(yōu)先搜索（BFS）、深度優(yōu)先搜索（DFS）那樣，我們通常是順著節(jié)點(diǎn)的鄰居去搜索的。其實(shí)這就是圖方法最本質(zhì)的優(yōu)勢(shì)：只要圖設(shè)計(jì)得足夠好，我們“無腦”順著圖走幾步就能到達(dá)不錯(cuò)的解。
- 存在一個(gè)搜索入口結(jié)點(diǎn)，從入口結(jié)點(diǎn)開始搜索
- 沿著入口結(jié)點(diǎn)一直往下搜，同時(shí)維護(hù)和查詢節(jié)點(diǎn)最近的K個(gè)節(jié)點(diǎn)
- 當(dāng)某輪搜索的結(jié)果不改變Top-K的結(jié)果時(shí)停止搜索
基于這個(gè)樸素的檢索思路，我們對(duì)圖的屬性有如下要求:
● 最優(yōu)性：檢索結(jié)束條件達(dá)到時(shí)，檢索結(jié)果盡可能最優(yōu)，否則精度損失太多，速度優(yōu)化意義不大。
● 小世界：在有限的幾步內(nèi)找到最優(yōu)解，也就是說我們要求從入口只經(jīng)過幾階鄰居就能找到全局最近的節(jié)點(diǎn)。值得注意的是，小世界的屬性包含了全局聯(lián)通性。
● 每個(gè)節(jié)點(diǎn)的鄰居有上限：如果每個(gè)節(jié)點(diǎn)的鄰居數(shù)量非常龐大，搜幾階鄰居就幾乎覆蓋全圖，那也是沒有意義的。
如果用最近鄰建圖會(huì)如何？
如果我們每個(gè)結(jié)點(diǎn)都用庫中跟該節(jié)點(diǎn)距離最近的M個(gè)結(jié)點(diǎn)作為它的鄰居，且不說建圖成本，這樣聯(lián)通性都是無法保證的，更不用說小世界了。即便運(yùn)氣很好，這樣構(gòu)建出來的圖是聯(lián)通的，如果我們查詢結(jié)點(diǎn)和入口結(jié)點(diǎn)相似度很低，可想而知要搜到最優(yōu)點(diǎn)效率有多低。
如果隨機(jī)建圖如何？
如果我們對(duì)每個(gè)結(jié)點(diǎn)隨機(jī)連M個(gè)鄰居的話，要么搜索條件很快就會(huì)達(dá)到，要么搜很久也搜不到最優(yōu)解。也就是說最優(yōu)性和小世界都無法保證的。甚至聯(lián)通性都是無法保證的。
因此，一個(gè)好圖構(gòu)圖方式似乎是：結(jié)點(diǎn)的鄰居既有相似度高的，又有相似度低的。其中，相似度低的邊，我們稱之為高速公路，它連接了相似結(jié)點(diǎn)簇來提高搜索效率。這樣圖就同時(shí)兼顧了Exploration（探索更大可能性）和Exploitation（已知解里找最優(yōu)）。
NSW
NSW，即Navigable Small World graphs。這是一個(gè)簡(jiǎn)單到讓人懷疑正確性的構(gòu)圖方式：我們把庫中的結(jié)點(diǎn)隨機(jī)插入圖中，每次插入結(jié)點(diǎn)的時(shí)候都找圖中和被插入結(jié)點(diǎn)最近的M個(gè)每個(gè)結(jié)點(diǎn)連邊。這樣就完事了？這樣就完事了！
這樣構(gòu)圖有什么好處呢？
- 這樣是能保證聯(lián)通性的：假設(shè)插入結(jié)點(diǎn)前，圖是聯(lián)通的；插入結(jié)點(diǎn)后，因?yàn)樾虏迦虢Y(jié)點(diǎn)和插入前的圖連上了邊，所以插入后也是聯(lián)通的。又初始一個(gè)點(diǎn)的時(shí)候是聯(lián)通的，所以最終整個(gè)圖是聯(lián)通的。
- 由于插入點(diǎn)找最近鄰連邊的時(shí)候，圖是不完整的，所以即便找了最近鄰，也存在較遠(yuǎn)的點(diǎn)。這某種意義上在擬合小世界的屬性。
- 構(gòu)圖非常結(jié)點(diǎn)，插入結(jié)點(diǎn)和搜索過程渾然一體：插入結(jié)點(diǎn)的時(shí)候，先搜出M個(gè)節(jié)點(diǎn)，然后連上邊。
可是，這樣的做法缺點(diǎn)也是明顯的： - 實(shí)際上小世界屬性依然不能保證。
- 對(duì)節(jié)點(diǎn)插入的順是不公平的：前面插入的結(jié)點(diǎn)“高速公路”比較多；后面插入結(jié)點(diǎn)鄰居都有很接近。
如何選擇入口結(jié)點(diǎn)是個(gè)問題。原文的做法大約是，隨機(jī)取若干個(gè)結(jié)點(diǎn)作為入口，搜多次，多次結(jié)果合在一起取top k。orz...
HNSW
如果我們分層去搜呢？先粗略地搜，然后再精細(xì)地搜。整個(gè)過程就像是，我們先初步定位，逐步把圖放大，持續(xù)更精細(xì)地定位。我們可以這樣構(gòu)圖，層的編號(hào)越大越接近頂層：
- 多層的NSW，每一層都是NSW；
- 頂層包含少量的點(diǎn)，逐層結(jié)點(diǎn)數(shù)倍數(shù)遞增，底層包含所有點(diǎn)；
- 下一層包含所有上一層的結(jié)點(diǎn)，下一層搜索的入口是上一層的結(jié)點(diǎn)中的一個(gè)。因此結(jié)點(diǎn)i在第j層出現(xiàn)，那它在0～j層均出現(xiàn)。
搜索過程
這樣，由于頂層的結(jié)點(diǎn)數(shù)量比較少，能夠保證充分的可能性探索（Exploration）。我們搜索過程如下：
- 從頂層的固定入口開始搜；
- 每一層搜索都返回Top-K的結(jié)果，當(dāng)前層搜到最近的結(jié)點(diǎn)作為下一層搜索的入口結(jié)點(diǎn)，繼續(xù)搜下去；
- 最后一層搜到的Top-k結(jié)果作為最終搜索結(jié)果。
插入結(jié)點(diǎn)過程
有了搜索方法，插入方式跟NSW類似，我們搜一遍，從搜索結(jié)果中選鄰居連上邊就好了，這里原文提出兩種選鄰居方法：1.直接在返回搜索結(jié)果中選Top-K；2. 在搜索返回結(jié)果中，對(duì)返回結(jié)果擴(kuò)一階鄰居計(jì)算相似度和原來結(jié)果放一起取top-K。
最后只剩下一個(gè)問題沒解決了，怎么決定一個(gè)結(jié)點(diǎn)最高出現(xiàn)在哪層呢？答案是：隨機(jī)！但是要注意好分布。也就是說，每次插入一個(gè)結(jié)點(diǎn)，我們都取一個(gè)隨機(jī)數(shù)，隨機(jī)數(shù)的數(shù)值代表了這個(gè)結(jié)點(diǎn)最高出現(xiàn)在哪一層：
其中，mL控制層數(shù)的參數(shù)，注意這里控制不了最高層數(shù)！
二、MariaDB向量索引實(shí)現(xiàn)分析
mariadb就是使用HNSW使用向量索引。下面具體來說明一下vector index的實(shí)現(xiàn)。向量索引實(shí)現(xiàn)在MariaDB的server層而非storage層（InnoDB）。InnoDB并不感知vector index的存在。一個(gè)vector index對(duì)應(yīng)一張內(nèi)部表。所以MariaDB的vector index更準(zhǔn)確的表達(dá)是：vector index on B+Tree index。
創(chuàng)建向量索引
當(dāng)用戶使用如下語法：
CREATE TABLE embeddings (doc_id BIGINT UNSIGNED PRIMARY KEY, embedding VECTOR(1536) NOT NULL,VECTOR INDEX (embedding) M=8 DISTANCE=cosine);
mariadb解析SQl就會(huì)發(fā)現(xiàn)vector index，然后在創(chuàng)建表的同時(shí)，調(diào)用mhnsw_hlindex_table_def 創(chuàng)建索引輔助表，具體調(diào)用關(guān)系如下：
ha_create_table() // handler接口
->ha_create_table_from_share()
->ha_create() // 進(jìn)入引擎層創(chuàng)建
->if (share.hlindexes()) // 如果存在vector index
{
sql= mhnsw_hlindex_table_def(thd, ref_length) // 構(gòu)建索引輔助表sql
index_share.init_from_sql_statement_string() // 使用sql創(chuàng)建table_share
ha_create_table_from_share() // 創(chuàng)建索引輔助表
}
下面我們看一下vector index的索引輔助表具體sql情況
const LEX_CSTRING mhnsw_hlindex_table_def(THD *thd, uint ref_length)
{
const char templ[]="CREATE TABLE i ( "
" layer tinyint not null, "
" tref varbinary(%u), "
" vec blob not null, "
" neighbors blob not null, "
" unique (tref), "
" key (layer)) ";
size_t len= sizeof(templ) + 32;
char *s= thd->alloc(len);
len= my_snprintf(s, len, templ, ref_length);
return {s, len};
}
可以看到，其表文件后綴為#i#1，創(chuàng)建的輔助表結(jié)構(gòu)如下
從上述分析上看，本質(zhì)上向量索引就是基于HNSW索引結(jié)構(gòu)建立了一個(gè)輔助表。
索引插入數(shù)據(jù)
當(dāng)主表插入數(shù)據(jù)時(shí)，相應(yīng)的觸發(fā)調(diào)用mhnsw_insert函數(shù)，對(duì)vector索引輔助表進(jìn)行數(shù)據(jù)插入，具體調(diào)用棧如下：
handler::ha_write_row() // 插入主表
->TABLE::hlindexes_on_insert()
->mhnsw_insert() // 插入vector索引輔助表
下面具體看一下輔助表的插入過程
// 1、獲取輔助表TABLE結(jié)構(gòu)體，向量信息，請(qǐng)進(jìn)行參數(shù)檢驗(yàn)
TABLE *graph= table->hlindex;
String buf, *res= vec_field->val_str(&buf);
DBUG_ASSERT(graph);
DBUG_ASSERT(keyinfo->algorithm == HA_KEY_ALG_VECTOR);
DBUG_ASSERT(keyinfo->usable_key_parts == 1);
DBUG_ASSERT(vec_field->binary());
// 2、獲取原始表當(dāng)前行信息
table->file->position(table->record[0]);
// 3、獲取或者初始化HNSW圖上下文，類似innodb trx事務(wù)上小文信息
// 如果是第一次插入，則初始化圖結(jié)構(gòu)，并直接插入第一個(gè)節(jié)點(diǎn)，設(shè)置為入口節(jié)點(diǎn)（start）
int err= MHNSW_Share::acquire(&ctx, table, true);
SCOPE_EXIT([ctx, table](){ ctx->release(table); });
if (err)
{
if (err != HA_ERR_END_OF_FILE)
return err;
// First insert!
ctx->set_lengths(res->length());
FVectorNode *target= new (ctx->alloc_node())
FVectorNode(ctx, table->file->ref, 0, res->ptr());
if (!((err= target->save(graph)))) // 在索引輔助表中存儲(chǔ)一個(gè)記錄
ctx->start= target; // 設(shè)置搜索開發(fā)位置
return err;
}
// 4、檢查向量長(zhǎng)度一致
if (ctx->byte_len != res->length())
return my_errno= HA_ERR_CRASHED;
// 5、分層插入，這是HNSW的核心，即隨機(jī)決定新節(jié)點(diǎn)的最大層級(jí)（target_layer），層級(jí)越高，概率月底
const double NORMALIZATION_FACTOR= 1 / std::log(ctx->M);
double log= -std::log(my_rnd(&thd->rand)) * NORMALIZATION_FACTOR;
const uint8_t max_layer= candidates.links[0]->max_layer;
uint8_t target_layer= std::min<uint8_t>(static_cast<uint8_t>(std::floor(log)), max_layer + 1);
// 6、基于原始行，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，這里
FVectorNode *target= new (ctx->alloc_node())
FVectorNode(ctx, table->file->ref, target_layer, res->ptr());
/* 7、分層插入與鄰居搜索，從最高層到最低層，逐層搜索最優(yōu)插入位置和鄰居節(jié)點(diǎn)。
search_layer：在指定層查找與新向量最接近的節(jié)點(diǎn)。
select_neighbors：從候選節(jié)點(diǎn)中選擇最優(yōu)鄰居，建立連接。
*/
if (int err= graph->file->ha_rnd_init(0))
return err;
SCOPE_EXIT([graph](){ graph->file->ha_rnd_end(); });
for (cur_layer= max_layer; cur_layer > target_layer; cur_layer--)
{
if (int err= search_layer(ctx, graph, target->vec, NEAREST,
1, cur_layer, &candidates, false))
return err;
}
for (; cur_layer >= 0; cur_layer--)
{
uint max_neighbors= ctx->max_neighbors(cur_layer);
if (int err= search_layer(ctx, graph, target->vec, NEAREST,
max_neighbors, cur_layer, &candidates, true))
return err;
if (int err= select_neighbors(ctx, graph, cur_layer, *target, candidates,
0, max_neighbors))
return err;
}
/* 8、保持新節(jié)點(diǎn)，從save實(shí)現(xiàn)可以看出：
layer 存儲(chǔ)的是之前確定的最大層級(jí)
tref 存儲(chǔ)的是原始行信息
vec 存儲(chǔ)的是原始向量
neighbors 存儲(chǔ)格式為從0層到最大層，每層num+鄰居向量
*/
if (int err= target->save(graph))
return err;
// 9、如果當(dāng)前節(jié)點(diǎn)在最高層，更新入口
if (target_layer > max_layer)
ctx->start= target;
// 10、更新二階鄰居
for (cur_layer= target_layer; cur_layer >= 0; cur_layer--)
{
if (int err= update_second_degree_neighbors(ctx, graph, cur_layer, target))
return err;
}
從上述向量索引插入過程我們可以知道，其節(jié)點(diǎn)是分層計(jì)算鄰居節(jié)點(diǎn)，并且存儲(chǔ)了相應(yīng)的鄰居信息。具體可以看下圖所示。
向量索引查詢
向量索引查詢執(zhí)行典型過程依次調(diào)用mhnsw_read_first，mhnsw_read_next，mhnsw_read_end。三個(gè)函數(shù)最重要的是第一個(gè)函數(shù)mhnsw_read_first，內(nèi)部包含初始化向量查詢上下文以及定位到第一個(gè)最近鄰結(jié)果。后面函數(shù)mhnsw_read_next即依次讀取即可。下面重點(diǎn)看看mhnsw_read_first函數(shù)的主要實(shí)現(xiàn)過程。
// 1、獲取基本信息
THD *thd= table->in_use;
TABLE *graph= table->hlindex;
// 距離計(jì)算函數(shù)
auto *fun= static_cast<Item_func_vec_distance_common*>(dist->real_item());
limit= std::min<ulonglong>(limit, max_ef);
// 2、初始化候選鄰居
Neighborhood candidates;
candidates.init(thd->alloc<FVectorNode*>(limit + 7), limit);
// 3、構(gòu)造一個(gè)向量對(duì)象，便于距離計(jì)算
const longlong max_layer= candidates.links[0]->max_layer;
auto target= FVector::create(ctx->metric, thd->alloc(FVector::alloc_size(ctx->vec_len)),
res->ptr(), res->length());
// 4、分層搜索，每一層，遍歷candidate所有鄰居，選出最優(yōu)的1個(gè)，下降到下一層繼續(xù)，直到0層
// 每層只保留最優(yōu)候選節(jié)點(diǎn)，加速收斂
for (size_t cur_layer= max_layer; cur_layer > 0; cur_layer--)
{
if (int err= search_layer(ctx, graph, target, NEAREST,
1, cur_layer, &candidates, false))
{
graph->file->ha_rnd_end();
return err;
}
}
// 5、底層（0層）查找最近鄰
if (int err= search_layer(ctx, graph, target, NEAREST,
static_cast<uint>(limit), 0, &candidates, false))
{
graph->file->ha_rnd_end();
return err;
}
// 6、保存結(jié)果，方便后續(xù)next函數(shù)獲取
auto result= new (thd->mem_root) Search_context(&candidates, ctx, target);
graph->context= result;
// 7、返回第一個(gè)結(jié)果
return mhnsw_read_next(table);
