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大规模高维向量检索能力。基于PG的高维向量检索插件(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个浮点数，这里省略查询语法为