《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个浮点数,这里省略查询语法为了表达按照向量相似度返回的语义,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 开源流程进行中。