PostgreSQL高維向量檢索索引插件介紹-內核專場（34頁）.pdf

《PostgreSQL高維向量檢索索引插件介紹-內核專場（34頁）.pdf》由會員分享，可在線閱讀，更多相關《PostgreSQL高維向量檢索索引插件介紹-內核專場（34頁）.pdf（34頁珍藏版）》請在三個皮匠報告上搜索。

1、姓名：方概公司：螞蟻金服PostgreSQL高維向量檢索索引插件介紹目錄1.背景2.索引插件實現3.示例和性能4.索引擴展5.展望01背景問題，解決方案近似最近鄰檢索(ANN,Approximate Nearest Neighbor Search)ANN流程向量檢索場景l 開源算法庫：faiss，SPTAG,annoy,nmslib,falconn為什么不直接使用開源算法庫組合查詢分布式和高可用數據遷移問題PostgreSQL(簡稱PG)優勢The Worlds Most Advanced Open Source Relational Database高性能和穩定性開源許可證靈活擴展性強使用廣

2、泛PG現有向量索引插件索引插件實現方式特點限制imgsmlr基于Gist索引內部提供圖像特征提取等方法只能用于16維的向量檢索場景，不適用于大規模的工業應用cube基于Gist索引支持向量的聚類、向量的距離計算僅支持100維以下，測試性能不佳freedy基于上層SQL擴展函數支持豐富的ANN算法大規模數據場景性能無法接受一種可行的通用方案，賦予PG大規模高維向量檢索能力?；赑G的高維向量檢索插件(Pase-PG ANN search extension)復合查詢擴展性高效存儲和檢索02索引插件實現索引結構，實現算法和索引擴展PG索引結構抽象PG索引底層存儲結構底層存儲基于PG定義的基礎結構：

3、PAGEPageHeaderData-PG定義的數據結構，用于Page的管理。special space 部分內容由用戶自定義使用。User define space-用戶使用，內部的存儲單元為DataTuple結構。索引接口函數IndexAmRoutine結構接口名稱作用ambuild創建一個新索引ambuildempty構建一個空索引aminsert向現有索引插入一個新元組ambulkdelete從索引中刪除元組，批量刪除amvacuumcleanup索引的清理和整合amcostestimate估計一次索引掃描的開銷amoptions分析和驗證一個索引的 reloptions 數組ambe

4、ginscan開始一個新掃描amrescan重啟一個掃描amgettuple獲取下一個元組，向給出的方向移動amgetbitmap獲取所有可用的元組amendscan結束掃描并釋放資源插件c代碼組成算法選擇IVFFlat算法適用場景：適合于召回精度要求高，但對查詢耗時要求不嚴格（100ms級別）的場景IVFFlat-存儲結構三類page：l meta page:存儲索引的meta信息，包括：page鏈的起始位置、向量維度等初始化信息。l centroid page:存儲中心點信息。所有中心點連續存儲，形成一條page鏈。l 數據page:存儲原始的向量數據。每個簇對應一條鏈。優化-page連續

5、存儲HNSW算法分層可導航小世界圖（Hierarchical Navigable Small World,HNSW）適用場景：超大規模向量數據集（千萬級別），且對查詢延時有嚴格要求(10ms級別)的場景HNSW算法-存儲結構l meta page存儲索引的meta信息：入口點、最后一個data page id，以及初始化配置參數。ldata page存儲原始向量數據，每個單元內部存儲原始的向量數據、節點所屬層次。形成page鏈。lneighbor page存儲鄰接關系。自定義數據類型自定義數據類型plm(.sql)輸入輸出函數聲明(.sql)輸入輸出函數實現(.c)自定義操作符跟IndexAm

6、Routine的連接SQLC代碼最終成果：Extension(擴展)參考：$PG_SRC/contrib/cube$PG_SRC/contrib/bloom03示例和性能使用示例和性能數據索引構建-HNSW-create tableCREATE TABLE vectors(id serial,vector float4);-insert data.構建性能數據量-維度索引構建時間100w-256維1小時幾小時2500w-512維幾小時十幾小時構建語法索引查詢-HNSW.為逗號分隔的256個浮點數，這里省略查詢語法為了表達按照向量相似度返回的語義，Pase的查詢功能通過order by語句來實現

7、。order by支持通過索引掃描來加速(amgettuple接口)。索引構建-IVFFlat構建性能 中心點數量：1000數據量-維度索引構建耗時100w 256維約7分鐘2500w 512維約48分鐘構建語法性能-索引構建耗時和索引大小測試環境64X Intel(R)Xeon(R)CPU E5-2682 v4 250GB RAM,1.8TB disk,centos 7相同的PG配置，單線程ExtensionBuild time(second)Table size(MB)index size(MB)cube31411162877freedy1020558101IVFFlat255558525

8、HNSW49425588333sift1M(128維)數據集gist1M(960維)數據集Extension Build time(second)Table size(MB)index size(MB)freedy43883813116IVFFlat37238063912HNSW20875380611718性能-耗時和準確率04PG新索引擴展步驟PG擴展新索引步驟抽象l 1.根據算法原理設計索引的page結構和組織關系 l2.定義新數據類型和新距離計算函數l3.實現IndexAmRoutine里的部分接口 build,insert beginscan,rescan,endscan,getdatatuple delete,vacuum數據類型定義l4.Extention打包 腳本文件，控制文件，動態鏈接庫 存儲結構設計接口實現Extension打包05展望l 實現優化：存儲設計優化，并行build，查詢性能優化。l 算法優化和擴充。HNSW算法有很多可優化點。引入優秀的新算法。l 已經進入阿里云pg版本中，外部客戶正在進行測試。l 開源流程進行中。