前提條件

實例為RDS PostgreSQL 11或以上版本。

背景信息

近年來，深度學(xué)習(xí)領(lǐng)域內(nèi)的表示學(xué)習(xí)技術(shù)，作為人工智能的代表性技術(shù)，取得了長足性進(jìn)展，在工業(yè)界中已經(jīng)被大量應(yīng)用，例如廣告投放、人臉支付、圖像識別、語音識別等場景。數(shù)據(jù)被嵌入至高維度向量，然后通過向量檢索技術(shù)來查找相關(guān)的項目。

PASE（PostgreSQL ANN search extension）是一款為PostgreSQL數(shù)據(jù)庫研發(fā)的高性能向量檢索索引插件，使用業(yè)界中成熟穩(wěn)定且高效的ANN（Approximate nearest neighbor）檢索算法，包括IVFFlat和HNSW算法，通過這兩種算法，可以在PostgreSQL數(shù)據(jù)庫中實現(xiàn)極高速向量查詢。PASE暫時不支持特征向量的抽取與產(chǎn)出，您需要自己檢索實體的特征向量，PASE負(fù)責(zé)的工作是根據(jù)已產(chǎn)出的海量級別的向量進(jìn)行相似向量的檢索。

目標(biāo)讀者

限于篇幅，本文不會對機器學(xué)習(xí)領(lǐng)域的相關(guān)名詞做詳細(xì)解釋，所以閱讀本文需要您有機器學(xué)習(xí)、搜索推薦相關(guān)知識基礎(chǔ)。

注意事項

• 索引會有膨脹，大約的膨脹率可以通過select pg_relation_size('index名稱');查詢，當(dāng)膨脹遠(yuǎn)大于數(shù)據(jù)的大小，并且查詢有明顯變慢時，需要重建索引。

• 數(shù)據(jù)頻繁更新后索引會不精確，如果要求絕對準(zhǔn)確，需要定期重建索引。

• IVFFlat索引如果使用內(nèi)部中心點（clustering_type=1），需要先在表中插入一定數(shù)據(jù)，再創(chuàng)建索引。

• 請使用高權(quán)限賬號執(zhí)行本文SQL示例。

PASE算法簡述

• IVFFlat算法

  IVFFlat是IVFADC的簡化版本，適合于召回精度要求高，但對查詢耗時要求不嚴(yán)格（100ms級別）的場景。相比其他算法，IVFFlat算法具有以下優(yōu)點：

  • 如果查詢向量是候選數(shù)據(jù)集中的一員，那么IVFFlat可以達(dá)到100%的召回率。

  • 算法簡單，因此索引構(gòu)建更快，存儲空間更小。

  • 聚類中心點可以由使用者指定，通過簡單的參數(shù)調(diào)節(jié)就可以控制召回精度。

  • 算法參數(shù)可解釋性強，用戶能夠完全地控制算法的準(zhǔn)確性。

  IVFFlat的算法原理參見下圖。

  

  算法流程說明：

  1. 高維空間中的點基于隱形的聚類屬性，按照kmeans等聚類算法對向量進(jìn)行聚類處理，使得每個類簇有一個中心點。

  2. 檢索向量時首先遍歷計算所有類簇的中心點，找到與目標(biāo)向量最近的n個類簇中心。

  3. 遍歷計算n個類簇中心所在聚類中的所有元素，經(jīng)過全局排序得到距離最近的k個向量。

  說明

  • 在查詢類簇中心點時，會自動排除遠(yuǎn)離的類簇，加速查詢過程，但是無法保證最優(yōu)的前k個向量全部在這n個類簇中，因此會有精度損失。您可以通過類簇個數(shù)n來控制IVFFlat算法的準(zhǔn)確性，n值越大，算法精度越高，但計算量會越大。

  • IVFFlat和IVFADC的第一階段完全一樣，主要區(qū)別是第二階段計算。IVFADC通過積量化來避免遍歷計算，但是會導(dǎo)致精度損失，而IVFFlat是暴力計算，避免精度損失，并且計算量可控。

• HNSW算法

  HNSW（Hierarchical Navigable Small World）算法適合超大規(guī)模的向量數(shù)據(jù)集（千萬級別以上），并且對查詢延時有嚴(yán)格要求（10ms級別）的場景。

  HNSW基于近鄰圖的算法，通過在近鄰圖快速迭代查找得到可能的相近點。在大數(shù)據(jù)量的情況下，使用HNSW算法的性能提升相比其他算法更加明顯，但鄰居點的存儲會占用一部分存儲空間，同時召回精度達(dá)到一定水平后難以通過簡單的參數(shù)控制來提升。

  HNSW的算法原理請參見下圖。

  

  算法流程說明：

  1. 構(gòu)造多層圖，每層圖都是下層圖的一個縮略，同時構(gòu)成下層圖的跳表，類似高速公路。

  2. 從頂層隨機選中一個點開始查詢。

  3. 第一次搜索其鄰居點，把它們按距離目標(biāo)的遠(yuǎn)近順序存儲在定長的動態(tài)列表中，以后每一次查找，依次取出動態(tài)列表中的點，搜索其鄰居點，再把這些新探索的鄰居點插入動態(tài)列表，每次插入動態(tài)列表需要重新排序，保留前k個。如果列表有變化則繼續(xù)查找，不斷迭代直至達(dá)到穩(wěn)態(tài)，然后以動態(tài)列表中的第一個點作為下一層的入口點，進(jìn)入下一層。

  4. 循環(huán)執(zhí)行第3步，直到進(jìn)入最底層。

  說明

  HNSW算法是在NSW算法的單層構(gòu)圖的基礎(chǔ)上構(gòu)造多層圖，在圖中進(jìn)行最近鄰查找，可以實現(xiàn)比聚類算法更高的查詢加速比。

兩種算法都有特定的適用業(yè)務(wù)場景，例如IVFFlat適合高精圖像對比場景，HNSW適合搜索推薦的召回場景。

使用PASE

使用方法

1. 創(chuàng)建PASE插件。命令如下：

   CREATE EXTENSION pase;

2. 計算向量相似度。您可以通過以下兩種構(gòu)造方式計算向量相似度：

   • 采用PASE數(shù)據(jù)類型構(gòu)造方式計算

     示例

     SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[]) AS distance;
     SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0) AS distance;
     SELECT ARRAY[2, 1, 1]::float4[] <?> pase(ARRAY[3, 1, 1]::float4[], 0, 1) AS distance;

     說明

     • <?>是PASE類型的操作符，表示計算左右兩個向量的相似度。左邊向量數(shù)據(jù)類型必須為float4[]，右邊向量數(shù)據(jù)類型必須為pase。

     • pase類型為插件內(nèi)定義的數(shù)據(jù)類型，包含如上示例的三種構(gòu)造方法，以示例第三條的float4[], 0, 1部分進(jìn)行說明：第一個參數(shù)為float4[]，代表右向量數(shù)據(jù)類型；第二個參數(shù)在此處沒有特殊作用，可以填入0；第三個參數(shù)表示相似度計算方式，0表示歐氏距離，1表示點積（內(nèi)積）。

     • 左右向量的維度必須相等，否則計算會報錯。

   • 采用字符串構(gòu)造方式計算

     示例

     SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1'::pase AS distance;
     SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0'::pase AS distance;
     SELECT ARRAY[2, 1, 1]::float4[] <?> '3,1,1:0:1'::pase AS distance;

     說明

     采用字符串構(gòu)造方式和采用PASE數(shù)據(jù)類型構(gòu)造方式都是計算兩個向量相似度，區(qū)別是字符串構(gòu)造方式通過英文冒號（:）分隔。以示例第三條的3,1,1:0:1部分進(jìn)行說明：第一個參數(shù)表示右向量；第二個參數(shù)在此處沒有特殊作用，可以填入0；第三個參數(shù)表示相似度計算方式，0表示歐氏距離，1表示點積（內(nèi)積）。

3. 創(chuàng)建索引。您可以使用兩種算法創(chuàng)建索引：

   說明

   對于要使用PASE向量索引的用戶，如果采用歐氏距離作為向量相似度計算公式，原始向量不需要做任何處理，但如果采用內(nèi)積或余弦作為向量相似度計算公式，需要對向量進(jìn)行歸一化處理，如原始向量為，則需要滿足：，此時內(nèi)積和余弦值相同。

   • IVFFlat算法創(chuàng)建索引

     CREATE INDEX ivfflat_idx ON table_name
     USING
       pase_ivfflat(column_name)
     WITH
       (clustering_type = 1, distance_type = 0, dimension = 256, base64_encoded = 0, clustering_params = "10,100");

     參數(shù)說明如下。

     參數(shù)	說明
     clustering_type	IVFFlat算法對向量數(shù)據(jù)進(jìn)行的聚類操作類型。必填項。取值： 0：外部聚類，加載外部提供的中心點文件，由參數(shù)clustering_params控制。 1：內(nèi)部聚類，即構(gòu)建索引過程首先會在內(nèi)部進(jìn)行聚類操作，采用kmeans算法，由參數(shù)clustering_params控制。 對于初級用戶，建議使用內(nèi)部聚類方式。
     distance_type	相似度計算方式。默認(rèn)值為0。取值： 0：歐式距離。 1：點積（內(nèi)積）。使用此方式需要進(jìn)行向量歸一化，此時點積（內(nèi)積）值的序和歐氏距離的序是反序關(guān)系。 當(dāng)前僅支持歐式距離，點積（內(nèi)積）需要向量歸一化后，采用附錄中提供的方法計算。
     dimension	向量維度。必填項，最大支持512。
     base64_encoded	數(shù)據(jù)是否采用base64編碼。默認(rèn)為0。取值： 0：采用float4[]表示向量類型。 1：采用float[]的base64編碼字符串表示向量類型。
     clustering_params	對于外部聚類，該參數(shù)配置為中心點文件路徑；對于內(nèi)部聚類，該參數(shù)配置為聚類參數(shù)。格式為：clustering_sample_ratio,k。必填項。 clustering_sample_ratio：以1000為分母的聚類采樣比例。取值范圍為(0,1000]內(nèi)的整數(shù)，例如值為1，表示對表中的數(shù)據(jù)按照千分之一的比例采樣后進(jìn)行kmeans聚類。值越大查詢準(zhǔn)確率越高，但創(chuàng)建索引的時間越長，建議采樣的數(shù)據(jù)總量不要超過10萬條。 k：聚類中心數(shù)，值越大查詢準(zhǔn)確率越高，但創(chuàng)建索引時間越長，建議取值范圍為[100,1000]。

   • HNSW算法創(chuàng)建索引

     CREATE INDEX hnsw_idx ON table_name
     USING
       pase_hnsw(column_name)
     WITH
       (dim = 256, base_nb_num = 16, ef_build = 40, ef_search = 200, base64_encoded = 0);

     參數(shù)說明如下。

     參數(shù)	說明
     dim	向量維度。必填項，取值范圍[8,512]。
     base_nb_num	圖中節(jié)點的鄰居數(shù)。必填項。值越大查詢準(zhǔn)確率越高，但建索引時間越慢，同時索引量占空間越大，建議取值范圍[16-128]。
     ef_build	創(chuàng)建索引過程中的堆長度。必填項。越長效果越好，但創(chuàng)建索引越慢，建議取值范圍[40,400]。
     ef_search	查詢過程中的堆長度。必填項。越長效果越好，但查詢性能越差，取值范圍[10,400]。
     base64_encoded	數(shù)據(jù)是否采用base64編碼。默認(rèn)值0。取值： 0：采用float4[]表示向量類型。 1：采用float[]的base64編碼字符串表示向量類型。

4. 查詢。您可以使用兩種索引查詢：

   • 使用IVFFlat索引查詢

     SELECT id, vector <#> '1,1,1'::pase as distance
     FROM table_name
     ORDER BY
     vector <#> '1,1,1:10:0'::pase
     ASC LIMIT 10;

     說明

     • <#>為IVFFlat算法索引的操作符。

     • 向量索引通過ORDER BY語句生效，支持ASC升序排序。

     • pase數(shù)據(jù)類型為三段式，通過英文冒號（:）分隔。以示例的1,1,1:10:0進(jìn)行說明：第一段為查詢向量；第二段為IVFFlat的查詢效果參數(shù)，取值范圍為(0,1000]，值越大查詢準(zhǔn)確率越高，但查詢性能越差，建議根據(jù)實際數(shù)據(jù)進(jìn)行調(diào)試確定；第三段為查詢時相似度計算方式，0表示歐式距離，1表示點積（內(nèi)積）。使用點積（內(nèi)積）方式需要進(jìn)行向量歸一化，此時點積（內(nèi)積）值的序和歐氏距離的序是反序關(guān)系。

   • 使用HNSW索引查詢

     SELECT id, vector <?> '1,1,1'::pase as distance
     FROM table_name
     ORDER BY
     vector <?> '1,1,1:100:0'::pase
     ASC LIMIT 10;

     說明

     • <?>為HNSW算法索引的操作符。

     • 向量索引通過ORDER BY語句生效，支持ASC升序排序。

     • pase數(shù)據(jù)類型為三段式，通過英文冒號（:）分隔。以示例的1,1,1:100:0進(jìn)行說明：第一段為查詢向量；第二段為HNSW的查詢效果參數(shù)，取值范圍為(0,∞)，值越大查詢準(zhǔn)確率越高，但查詢性能越差，建議根據(jù)實際數(shù)據(jù)進(jìn)行調(diào)試確定，初始值建議從40開始；第三段為查詢時相似度計算方式，0表示歐式距離，1表示點積（內(nèi)積）。使用點積（內(nèi)積）方式需要進(jìn)行向量歸一化，此時點積（內(nèi)積）值的序和歐氏距離的序是反序關(guān)系。

使用示例

本示例已使用IVFFlat索引查詢?yōu)槔?/p>

1. 創(chuàng)建PASE插件。命令如下：

   CREATE EXTENSION pase;

2. 創(chuàng)建測試表，并插入測試數(shù)據(jù)。

   創(chuàng)建測試表。

   CREATE TABLE vectors_table ( id SERIAL PRIMARY KEY, vector float4[] NOT NULL );

   插入測試數(shù)據(jù)。

   INSERT INTO vectors_table (vector) VALUES ('{1.0, 0.0, 0.0}'), ('{0.0, 1.0, 0.0}'), ('{0.0, 0.0, 1.0}'), ('{0.0, 0.5, 0.0}'), ('{0.0, 0.5, 0.0}'), ('{0.0, 0.6, 0.0}'), ('{0.0, 0.7, 0.0}'), ('{0.0, 0.8, 0.0}'), ('{0.0, 0.0, 0.0}');

3. 使用IVFFlat算法創(chuàng)建索引。

   CREATE INDEX ivfflat_idx ON vectors_table
   USING
     pase_ivfflat(vector)
   WITH
     (clustering_type = 1, distance_type = 0, dimension = 3, base64_encoded = 0, clustering_params = "10,100");

4. 使用IVFFlat索引進(jìn)行查詢。

   SELECT id, vector <#> '1,1,1'::pase as distance
   FROM vectors_table
   ORDER BY
   vector <#> '1,1,1:10:0'::pase
   ASC LIMIT 10;

附錄

• 點積（內(nèi)積）方式計算示例

  示例采用HNSW算法索引，創(chuàng)建function示例如下：

  CREATE OR REPLACE FUNCTION inner_product_search(query_vector text, ef integer, k integer, table_name text) RETURNS TABLE (id integer, uid text, distance float4) AS $$
  BEGIN
      RETURN QUERY EXECUTE format('
      select a.id, a.vector <?> pase(ARRAY[%s], %s, 1) AS distance from 
      (SELECT id, vector FROM %s ORDER BY vector <?> pase(ARRAY[%s], %s, 0) ASC LIMIT %s) a
      ORDER BY distance DESC;', query_vector, ef,  table_name,  query_vector, ef, k);
  END
  $$
  LANGUAGE plpgsql;

  說明

  對于歸一化的向量，內(nèi)積=余弦，所以余弦值也可以用上述方式計算。

• IVFFlat索引自定義中心點文件

  此功能為高級功能，需要在服務(wù)器上指定路徑上傳中心點文件，并作為索引參數(shù)構(gòu)建索引。詳細(xì)參數(shù)請參見IVFFlat索引參數(shù)描述。文件格式如下：

  向量維度|中心點個數(shù)|中心點向量集合

  示例

  3|2|1,1,1,2,2,2

相關(guān)文檔

• Product Quantization for Nearest Neighbor Search

  Herv ?e J ?egou, Matthijs Douze, Cordelia Schmid. Product quantization for nearest neighbor search.

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

  Yu.A.Malkov, D.A.Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.