ApsaraDB RDS：高效向量檢索（PASE）

前提條件

執行個體為RDS PostgreSQL 11或以上版本。

背景資訊

近年來，深度學習領域內的表示學習技術，作為人工智慧的代表性技術，取得了長足性進展，在工業界中已經被大量應用，例如廣告投放、人臉支付、Image Recognition、語音辨識等情境。資料被嵌入至高維度向量，然後通過向量檢索技術來尋找相關的專案。

PASE（PostgreSQL ANN search extension）是一款為PostgreSQL資料庫研發的高效能向量檢索索引外掛程式，使用業界中成熟穩定且高效的ANN（Approximate nearest neighbor）檢索演算法，包括IVFFlat和HNSW演算法，通過這兩種演算法，可以在PostgreSQL資料庫中實現極高速向量查詢。PASE暫時不支援特徵向量的抽取與產出，您需要自己檢索實體的特徵向量，PASE負責的工作是根據已產出的海量層級的向量進行相似向量的檢索。

目標讀者

限於篇幅，本文不會對機器學習領域的相關名詞做詳細解釋，所以閱讀本文需要您有機器學習、搜尋推薦相關知識基礎。

注意事項

• 索引會有膨脹，大約的膨脹率可以通過select pg_relation_size('index名稱');查詢，當膨脹遠大於資料的大小，並且查詢有明顯變慢時，需要重建索引。

• 資料頻繁更新後索引會不精確，如果要求絕對準確，需要定期重建索引。

• IVFFlat索引如果使用內部中心點（clustering_type=1），需要先在表中插入一定資料，再建立索引。

• 請使用高許可權帳號執行本文SQL樣本。

PASE演算法簡述

• IVFFlat演算法

  IVFFlat是IVFADC的簡化版本，適合於召回精度要求高，但對查詢耗時要求不嚴格（100ms層級）的情境。相比其他演算法，IVFFlat演算法具有以下優點：

  • 如果查詢向量是候選資料集中的一員，那麼IVFFlat可以達到100%的召回率。

  • 演算法簡單，因此索引構建更快，儲存空間更小。

  • 聚類中心點可以由使用者指定，通過簡單的參數調節就可以控制召回精度。

  • 演算法參數可解釋性強，使用者能夠完全地控制演算法的準確性。

  IVFFlat的演算法原理參見下圖。

  

  演算法流程說明：

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

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

  3. 遍曆計算n個類簇中心所在聚類中的所有元素，經過全域排序得到距離最近的k個向量。

  說明

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

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

• HNSW演算法

  HNSW（Hierarchical Navigable Small World）演算法適合超大規模的向量資料集（千萬層級以上），並且對查詢延時有嚴格要求（10ms層級）的情境。

  HNSW基於近鄰圖的演算法，通過在近鄰圖快速迭代尋找得到可能的相近點。在巨量資料量的情況下，使用HNSW演算法的效能提升相比其他演算法更加明顯，但鄰居點的儲存會佔用一部分儲存空間，同時召回精度達到一定水平後難以通過簡單的參數控制來提升。

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

  

  演算法流程說明：

  1. 構造多層圖，每層圖都是下層圖的一個縮減，同時構成下層圖的跳錶，類似高速公路。

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

  3. 第一次搜尋其鄰居點，把它們按距離目標的遠近順序儲存在定長的動態列表中，以後每一次尋找，依次取出動態列表中的點，搜尋其鄰居點，再把這些新探索的鄰居點插入動態列表，每次插入動態列表需要重新排序，保留前k個。如果列表有變化則繼續尋找，不斷迭代直至達到穩態，然後以動態列表中的第一個點作為下一層的進入點，進入下一層。

  4. 迴圈執行第3步，直到進入最底層。

  說明

  HNSW演算法是在NSW演算法的單層構圖的基礎上構造多層圖，在圖中進行最近鄰尋找，可以實現比聚類演算法更高的查詢加速比。

兩種演算法都有特定的適用業務情境，例如IVFFlat適合高精映像對比情境，HNSW適合搜尋推薦的召回情境。

使用PASE

使用方法

1. 建立PASE外掛程式。命令如下：

   CREATE EXTENSION pase;

2. 計算向量相似性。您可以通過以下兩種構造方式計算向量相似性：

   • 採用PASE資料類型構造方式計算

     樣本

     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類型的操作符，表示計算左右兩個向量的相似性。左邊向量資料類型必須為float4[]，右邊向量資料類型必須為pase。

     • pase類型為外掛程式內定義的資料類型，包含如上樣本的三種構造方法，以樣本第三條的float4[], 0, 1部分進行說明：第一個參數為float4[]，代表右向量資料類型；第二個參數在此處沒有特殊作用，可以填入0；第三個參數表示相似性計算方式，0表示歐氏距離，1表示點積（內積）。

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

   • 採用字串構造方式計算

     樣本

     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;

     說明

     採用字串構造方式和採用PASE資料類型構造方式都是計算兩個向量相似性，區別是字串構造方式通過英文冒號（:）分隔。以樣本第三條的3,1,1:0:1部分進行說明：第一個參數表示右向量；第二個參數在此處沒有特殊作用，可以填入0；第三個參數表示相似性計算方式，0表示歐氏距離，1表示點積（內積）。

3. 建立索引。您可以使用兩種演算法建立索引：

   說明

   對於要使用PASE向量索引的使用者，如果採用歐氏距離作為向量相似性計算公式，原始向量不需要做任何處理，但如果採用內積或餘弦作為向量相似性計算公式，需要對向量進行歸一化處理，如原始向量為，則需要滿足：，此時內積和餘弦值相同。

   • IVFFlat演算法建立索引

     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");

     參數說明如下。

     參數	說明
     clustering_type	IVFFlat演算法對向量資料進行的聚類操作類型。必填項。取值： 0：外部聚類，載入外部提供的中心點檔案，由參數clustering_params控制。 1：內部聚類，即構建索引過程首先會在內部進行聚類操作，採用kmeans演算法，由參數clustering_params控制。 對於初級使用者，建議使用內部聚類方式。
     distance_type	相似性計算方式。預設值為0。取值： 0：歐式距離。 1：點積（內積）。使用此方式需要進行向量歸一化，此時點積（內積）值的序和歐氏距離的序是反序關係。 當前僅支援歐式距離，點積（內積）需要向量歸一化後，採用附錄中提供的方法計算。
     dimension	向量維度。必填項，最大支援512。
     base64_encoded	資料是否採用base64編碼。預設為0。取值： 0：採用float4[]表示向量類型。 1：採用float[]的base64編碼字串表示向量類型。
     clustering_params	對於外部聚類，該參數配置為中心點檔案路徑；對於內部聚類，該參數配置為聚類參數。格式為：clustering_sample_ratio,k。必填項。 clustering_sample_ratio：以1000為分母的聚類採樣比例。取值範圍為(0,1000]內的整數，例如值為1，表示對錶中的資料按照千分之一的比例採樣後進行kmeans聚類。值越大查詢準確率越高，但建立索引的時間越長，建議採樣的資料總量不要超過10萬條。 k：聚類中心數，值越大查詢準確率越高，但建立索引時間越長，建議取值範圍為[100,1000]。

   • HNSW演算法建立索引

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

     參數說明如下。

     參數	說明
     dim	向量維度。必填項，取值範圍[8,512]。
     base_nb_num	圖中節點的鄰居數。必填項。值越大查詢準確率越高，但建索引時間越慢，同時索引量占空間越大，建議取值範圍[16-128]。
     ef_build	建立索引過程中的堆長度。必填項。越長效果越好，但建立索引越慢，建議取值範圍[40,400]。
     ef_search	查詢過程中的堆長度。必填項。越長效果越好，但查詢效能越差，取值範圍[10,400]。
     base64_encoded	資料是否採用base64編碼。預設值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資料類型為三段式，通過英文冒號（:）分隔。以樣本的1,1,1:10:0進行說明：第一段為查詢向量；第二段為IVFFlat的查詢效果參數，取值範圍為(0,1000]，值越大查詢準確率越高，但查詢效能越差，建議根據實際資料進行調試確定；第三段為查詢時相似性計算方式，0表示歐式距離，1表示點積（內積）。使用點積（內積）方式需要進行向量歸一化，此時點積（內積）值的序和歐氏距離的序是反序關係。

   • 使用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資料類型為三段式，通過英文冒號（:）分隔。以樣本的1,1,1:100:0進行說明：第一段為查詢向量；第二段為HNSW的查詢效果參數，取值範圍為(0,∞)，值越大查詢準確率越高，但查詢效能越差，建議根據實際資料進行調試確定，初始值建議從40開始；第三段為查詢時相似性計算方式，0表示歐式距離，1表示點積（內積）。使用點積（內積）方式需要進行向量歸一化，此時點積（內積）值的序和歐氏距離的序是反序關係。

使用樣本

本樣本已使用IVFFlat索引查詢為例。

1. 建立PASE外掛程式。命令如下：

   CREATE EXTENSION pase;

2. 建立測試表，並插入測試資料。

   建立測試表。

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

   插入測試資料。

   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演算法建立索引。

   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索引進行查詢。

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

附錄

• 點積（內積）方式計算樣本

  樣本採用HNSW演算法索引，建立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;

  說明

  對于歸一化的向量，內積=餘弦，所以餘弦值也可以用上述方式計算。

• IVFFlat索引自訂中心點檔案

  此功能為進階功能，需要在伺服器上指定路徑上傳中心點檔案，並作為索引參數構建索引。詳細參數請參見IVFFlat索引參數描述。檔案格式如下：

  向量維度|中心點個數|中心點向量集合

  樣本

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

相關文檔

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