5 腾讯大数据基于 StarRocks 的向量检索探索

——腾讯大数据 赵裕隆腾讯大数据研发工程师 向量检索技术浅析 StarRocks实现向量检索的原理及优化 StarRocks向量检索在腾讯的实践案例 挑战及未来规划 向量检索技术浅析 什么是向量检索 向量检索 •新型应用不断涌现：听歌识曲、以图搜图、广告推荐、大模型检索增强等等； •Embedding技术的成熟：大量非结构化数据（视频、语音、图像等）可以通过深度学习技术转化成高维向量（数组）； •统一数据特征表达：将非结构化数据Embedding后，对高维特征向量进行最近邻（或k近邻）查询即可查找相似内容：给定查询向量，在特征数据库中寻找距离查询向量最近（即相似度最高）的k个向量； -get_topN(distance),id-id,metrics_distance(query_vector,vector_column): distance-scan_table(id,vector_column) 近似最近邻查询 高维空间的向量很难进行快速而准确的近邻查询，主要原因在于： •高维度导致的计算复杂性：数据维度较高，通用的距离函数都需要成百上千次浮点运算，十分耗时； •维度灾难（Curse of Dimensionality）：随着维度的增大，搜索空间将呈指数增长的现象； •为了解决高维向量KNN查询的效率问题，近似最近邻查询（Approximate Nearest Neighbor Search, ANNS）应运而生，其通过返回近似查询结果，来显著提升查询效率（通常为数百倍以上）。 •目前ANNS使用的最常见的是距离度量是欧式距离和余弦距离。 •通常使用召回率（Recall）来衡量ANNS的查询精度，即近似查询结果中正确答案占实际正确答案的比例。 近邻索引技术 •哈希/树：用于ANNS的哈希方法主要是局部敏感哈希；树索引的基本思路是对空间进行划分，并采用树型结构维护空间划分的层次关系。 •量化与倒排（主流）：乘积量化（ProductQuantization，PQ）先把向量分为多个子段，然后对每段进行分别聚类与编码。量化是一种压缩技术，虽然能够极大的减少存储空间占用和距离计算开销，但是仍然要对全量数据进行距离排序，没有剪枝作用，所以通常需要配合倒排索引技术（Inverted File，IVF），求取TopK个聚类中心的进行剪枝，进一步减少访问的数据量。 •近邻图（主流）：近邻图的基本思想是“近邻的近邻也是近邻”，其将每个向量作为图中的一个Node，在距离相近的向量之间建立边连接构成近邻图。查询时从固定入口出发，不断地贪心遍历离查询向量更近的邻节点，直到没有更近的节点停止搜索。 业务背景 •业务场景：一个典型检索场景 •检索链路复杂：一次检索经过四套系统•写入链路复杂：写入维护三条链路•端到端延迟高：端到端分钟级延迟•数据一致性保障 •业务诉求 •能力支撑：文本检索+向量检索+多维分析•成本：尽可能少的使用和接入成本•业务开发维护成本：高可靠、高可用、用户友好•性能：亚秒/秒级查询延迟，召回率95%+ •如何选型最符合业务现状，并有利于后续发展 •新兴向量库：系统学习成本？链路打通成本？数据迁移成本？后续系统维护成本？•现有传统数据库+向量索引：性能？生态融合成本？稳定性？后期迭代？ 答案： ✓成熟可靠的分布式高性能数据库系统+向量检索； StarRocks实现向量检索的原理及优化 整体架构 ✓基本功能的开发完成，具备服务分析一体的向量数据库雏形 ✓形成了内部索引库TenANN，集成了业界主流的向量索引HNSW和IVFPQ 语法设计 向量检索语义与SQL有gap，如何设计语 法来进行适配？ ？向量检索的近似TopN，意味着其它索引与Filter条件与向量检索有先后关系，而wherepredicate本身是没有先后关系的；？索引自带导出字段Distance，Scan层没有相关的字段，距离如何表达？✓解决思路：忽略SQL表达和实际执行的一致性，统一通过表达式构筑SQL，优化时构建成对应的执行计划； 向量索引支持： ✓纯向量检索✓标量混合向量检索✓范围搜索✓标量混合范围搜索 查询过程 查询过程： •查询解析与优化•执行计划优化：将检索语义执行计划树下推到向量索引中；•TopN下推优化•隐式生成列优化•参数优化：按照hint或者set的方式进行优化•执行参数优化：搜索参数、搜索分桶打折率等•检索谓词优化：前过滤、后过滤•检索模式优化：暴力检索、近似检索 •查询执行 •隐式列生成：为ScanNode生成一个隐式向量距离列，挂载到索引中返回的向量距离 •前过滤模式：先通过columnconjunction得到rowid，再通过标记索引id的方式进行相似度计算；•后过滤模式：同正常索引流程，先通过Segment的indexfilter，再做columnconjunction •距离物化•通过索引过滤，可以得到TopN的行号和具体的距离，将距离和rowid绑定，在列值物化的时候，同时物化对应的距离值； 查询实现—具体索引的计算实现 Selectid,l2_distance(query_vector,vector_column)asscorefromtableorderbyscorelimit10; 查询优化 Tablet级预排序： •方案：通过在Tablet级别进行topK预排序，再分发到Segment内进行物化，可有效减少读放大、计算放大现象。 •效果：可以提升4%-23%的查询性能，证明了tablet级别的聚合可以生效；通过引入并行检索能力，可以有效提升6%-24%查询性能。 查询优化 支持前过滤、混合过滤、迭代式后过滤： ✓引入新的迭代构造模型，支持迭代器之间可自由组合，并支持了新的阻塞迭代方式。 索引写入原理与实现 如何将向量索引的索引逻辑优雅地映射到关系型数据库的索引逻辑？ 存储级别选型：TabletVectorIndexvsSegmentVectorIndex 索引写入流程：索引是如何构建并写入的？ 聚类中心重训练：对于IVFPQ如何保证聚类中心有效性 索引粒度选型 索引级别选型： •Segment级别索引（当前选型）：在该方案中，每一个Segment与一个VectorIndex一一对应，写入和加载都是以一个segment为单位进行； ✓可以应用于主键表和明细表模型✓索引向量到segmentrowid的映射，通过rowid召回其它列✓rowset/segment过多时，会出现读放大（延迟物化segment）和过多地计算合并问题（小文件过多） •Tablet级别索引：在该方案中，每一个Tablet与一个VectorIndex一一对应，写入和加载都是Tablet为单位，类似于主键; ✓只应用于主键表✓索引向量到pkid的映射，当只需要pkid时，可以只检索索引而无需进行召回✓召回其它列时，需要通过pkid多跳召回 索引写入 索引重建 IVFPQ索引重建 ⚫索引与聚类中心 IVFPQ索引的一个通用做法是，它所有分簇共享同一个聚类模型，在构建索引同时进行训练，而后的数据新增也复用这个数据聚类模型进行分类，如果这个聚类模型长期不更新，随着数据变多特征迁移，整个聚类效果会变差；因此需要系统本身，或者用户去手动更新聚类模型，成本很高； ⚫索引合并重建 ✓索引独占聚类中心，写入/合并时训练；✓聚类中心依赖Compaction重建；✓资源分组隔离； Tenann实现 为什么要自研TenANN？ ➢多索引集成：单一索引库无法满足所有性能与功能要求； ➢不跟具体索引耦合，预留更多优化空间； ✓TenANN是一个通用、易用、易扩展、高性能的多功能索引库，支持向量、倒排等多种类型的索引。 ✓TenANN底层支持无缝对接自研索引，上层支持所有索引共享同一套使用接口，从而使得TenANN的用户能够通过不做改动或者少量改动，透明地享受TenANN不断新增的索引和功能。 RangeSearch SQL:selectid,l2_distance(query_vector,vector_column)asscorefromtablewherescore<0.8orderbyscorelimit10; HNSWRangeSearch： IVF-PQRangeSearch： 1NNSearch+r->RangeSearch BlockCache ✓TenANN为了减小IVF-PQ索引无效数据从磁盘加载、实现在小于索引大小的内存容量下加载索引，并避免page_cache之间相互干扰开发的block级别缓存功能。 ✓cache配置为inverted_lists大小的50%，cache命中率约96%，全recall与纯内存基本持平（即开启block_cache后只需要一半内存就可以达到纯内存的查询性能以及Recall） ANN-benchmark HNSW(Faiss)vsHNSW(Tenann) 性能优化测试总结 StarRocks向量检索在腾讯的实践案例 案例 •调用链路过长，维护成本较大•整体检索耗时过长：~15s以上 案例 挑战及未来规划 高并发场景挑战 挑战一：如何在一个OLAP系统上，实现高并发、低延时？ •并发与QPS并非线性关系。•Pipeline计算模式overhead过大。 高并发场景挑战 规划 •Serving/HSAP•Scatter-GathervsPipeline 大数据量场景挑战 挑战二：大数据量下，topK场景仍面临挑战： •数据量巨大•K巨大 大数据量场景挑战 规划 •Tablet级别索引/Tablet级别预排序/增量索引构建 RAG场景挑战 挑战三：RAG完整支持 规划 •支持集成文本预处理•支持集成数据特征化服务•支持自定义重排•支持多路召回 •检索增强：向量索引、关键词表索引、摘要索引等•排序和后处理：经过检索过程可能会得到很多相关文档，就需要进行筛选和排序。常用的筛选和排序策略包括： •基于相似度分数进行过滤和排序•基于关键词进行过滤，比如限定包含或者不包含某些关键词•让LLM基于返回的相关文档及其相关性得分来重新排序•基于时间进行过滤和排序，比如只筛选最新的相关文档•基于时间对相似度进行加权，然后进行排序和筛选 感谢观看！ Thank you!