AnalyticDB：向量檢索與全文檢索索引雙路召回

混合檢索簡介

ANNS（Approximate Nearest Neighbors Search，近似最近鄰搜尋）向量索引只能解決非結構化資料檢索的問題。但是實際生產環境中，經常會遇到一些結構化資料與非結構化資料需要同時檢索的情境。例如需要查詢特定人員在指定時間範圍內是否出現在特定地區內，這裡的結構化條件就是時間範圍和地區範圍，非結構化條件就是人臉。因此阿里雲在AnalyticDB PostgreSQL版中加入了結構化資料與非結構化資料混合查詢的能力。

業界在解決混合查詢的問題時，一般採用兩個系統，結構化資料存在資料庫中，非結構化資料存在向量檢索系統中；然後對兩個系統求交集後再彙總得到最終的結果。這種方法一般先採用向量檢索系統取出經過放大的amp（放大係數） * topk個結果，然後再通過結構化索引過濾得到最終結果。但該方法因為結構化索引過濾結果比較多，導致召回出現比較大的損失，從而無法滿足最終需要topk個結果的要求。下面以結構化欄位和非結構化欄位的混合查詢來講解混合查詢的實現原理。

混合檢索實現原理

AnalyticDB PostgreSQL版將向量檢索引擎FastANN作為索引外掛程式整合到資料庫中，可以在使用向量檢索的同時使用結構化和半結構化索引。具體是通過最佳化器的RBO（Ranked-Biased Overlap）代價估算規則，產生不同的執行計畫來解決結構化資料與非結構化資料需要同時檢索的問題。

下文通過一個例子來說明混合檢索的原理。

假設有一個帶條件的拍圖尋找商品需求：尋找與輸入圖片相似性最高，價格在100到200元之間，並且上架時間在最近一個月以內的前100件商品。

表和索引結構如下：

CREATE TABLE products (
    id serial primary key, 
    name varchar(256), 
    price real, 
    inTime timestamp, 
    url varchar(256),
    feature real[]
);

-- 設定向量列為內聯模式。
ALTER TABLE products ALTER COLUMN feature SET STORAGE PLAIN;

-- 為結構化欄位建立BTREE索引。
CREATE INDEX ON products(price, intime);

-- 為向量欄位建立向量索引。
CREATE INDEX ON products USING ann(feature) WITH (dim=512);

-- 收集統計資訊，用於產生最優的混合查詢執行計畫。
ANALYZE products;

採用混合查詢的SQL如下：

SELECT id, price FROM products WHERE 
    price > 100 AND price <=200 
    AND inTime > '2019-03-01 00:00:00' AND inTime <= '2019-03-31 00:00:00' 
ORDER BY 
    feature <-> array[10,2.0,…, 512.0] 
LIMIT 100;

為了執行這條SQL，依據結構化條件列（price以及inTime）上是否有索引，以及結構化條件的選擇率大小不同，AnalyticDB PostgreSQL版可能會產生如下3類不同的執行計畫，並在其中選擇最優的一個執行計畫，以滿足使用者對效能和召回的要求：

• 第一類：暴力查詢：

  根據結構化條件擷取所有合格行，再在其中根據向量距離進行排序，選擇距離最小的100條資料進行輸出。這種執行計畫召回為100%，但是查詢速度最慢，在底庫過大或符合結構化條件行數過多時查詢效能低下。執行計畫如下所示（簡化了部分輸出資訊）：

                                         QUERY PLAN
  -----------------------------------------------------------------------------------
   LIMIT
       ->  Gather Motion 3:1  (slice1; segments: 3)   
           Merge Key: (l2_squared_distance($0, feature))     
               ->  LIMIT
                   ->  Sort
                       Sort Key: (l2_squared_distance($0, feature))
                       ->  Index Scan using products_price_idx on products
                           Index Cond: 價格過濾條件
                           Filter: 時間過濾條件
  
   Optimizer: Postgres query optimizer

• 第二類：純向量查詢 + 結構化過濾：

  為了加速查詢，先使用向量索引查詢出與輸入圖片最接近的N行資料，再在其中根據結構化條件進行過濾。這種執行計畫的優點是查詢速度最快，缺點是如果結構化查詢的篩選率太小（即一行資料通過過濾的機率太小），則查詢最終輸出的資料行數可能比使用者要求的行數少。執行計畫如下所示（簡化了部分輸出資訊）：

                                         QUERY PLAN
  -----------------------------------------------------------------------------------
   LIMIT 
      ->  Gather Motion 3:1  (slice1; segments: 3) 
          Merge Key: ((feature <-> $0))     
              ->  LIMIT
                  ->  Ann Index Scan using products_feature_idx on products
                      ORDER BY: (feature <-> $0)
                      Filter: 價格和時間列過濾條件
  
   Optimizer: Postgres query optimizer

• 第三類：向量結構化混合查詢：

  向量結構化混合查詢結合了第一類和第二類執行計畫，既能使用索引，又能解決第二類執行計畫返回資料變少的問題。同時，如果結構化條件列上有索引，且索引類型支援Bitmap（左子樹）產生，則混合查詢還可以利用其他索引來產生Bitmap，從而進一步加速混合查詢。執行計畫如下所示（簡化了部分輸出資訊）：

                                         QUERY PLAN
  -----------------------------------------------------------------------------------
   LIMIT
       ->  Gather Motion 3:1  (slice1; segments: 3)   
           Merge Key: ((feature <-> $0))   
           ->  LIMIT
               ->  Fusion Ann Scan
                   ->  Bitmap Index Scan on products_price_idx
                       Index Cond: 價格過濾條件
                       ->  Ann Index Scan with filter using products_feature_idx on products
                           ORDER BY: (feature <-> $0)
                           Filter: 時間過濾條件
  
   Optimizer: Postgres query optimizer

  上述執行計畫中包含了Fusion Ann Scan節點或者Ann Index Scan with filter節點的執行計畫都是使用了混合查詢能力。這兩種執行計畫說明如下：

  • Ann Index Scan with filter：此節點的作用是將過濾條件下壓到向量索引內部，在索引的執行過程中同時考慮過濾條件。

  • Fusion Ann Scan：此節點在某些結構化條件列上有索引時可能出現，其作用是根據結構化條件產生Bitmap（左子樹），將Bitmap下壓到向量索引（右子樹）中，加速結構化條件的計算。出現Fusion Ann Scan節點時，其右子樹可能是Ann Index Scan也可能是Ann Index Scan with filter。如果右子樹是Ann Index Scan，說明除了Bitmap外沒有其他結構化條件下壓。反之會出現Ann Index Scan with filter。

混合檢索使用方法

AnalyticDB PostgreSQL版向量資料庫混合查詢既支援結構化欄位過濾，也支援半結構化欄位過濾，同時也支援和文字欄位的全文檢索索引一起進行雙路召回。混合查詢具體可以劃分為三類：

• 向量查詢和結構化欄位過濾組成的混合查詢。當前支援的結構化欄位類型包括：bigint、boolean、bytea、char、varchar、integer、float、double、date、smallint、timestamp和serial等所有結構化欄位，這些結構化欄位可以通過建立預設的BTREE索引在混合查詢中進行加速。結構化欄位類型的詳細資料請參見資料類型。

• 向量查詢和半結構化欄位過濾組成的混合查詢。當前支援的半結構化類型包括：JSON、JSONB和Array等所有半結構化欄位，這些結構化欄位可以通過建立GIN索引在混合查詢中進行加速。半結構化類型的詳細資料請參見JSON & JSONB 資料類型和Array數群組類型。

• 向量查詢和全文檢索索引組成的雙路召回。

在混合檢索實現原理中，已經介紹了混合查詢中對結構化欄位類型的加速最佳化方式，下面舉例說明半結構化欄位在混合檢索中的使用，以及向量檢索與全文檢索索引進行雙路召回的使用。