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

基于StarRocks的向量检索探索 ——腾讯大数据 赵裕隆 腾讯大数据研发工程师 向量检索技术浅析 StarRocks实现向量检索的原理及优化StarRocks向量检索在腾讯的实践案例挑战及未来规划 向量检索技术浅析 01 什么是向量检索 向量检索 •新型应用不断涌现：听歌识曲、以图搜图、广告推荐、大模型检索增强等等； •Embedding技术的成熟：大量非结构化数据（视频、语音、图像等）可以通过深度学习技术转化成高维向量（数组）； •统一数据特征表达：将非结构化数据 Embedding后，对高维特征向量进行最 近邻（或k近邻）查询即可查找相似内容：给定查询向量，在特征数据库中寻找距离查询向量最近（即相似度最高）的k个向量； -get_topN(distance),id -id,metrics_distance(query_vector,vector_column):distance -scan_table(id,vector_column) 近似最近邻查询 维度灾难 高维空间的向量很难进行快速而准确的近邻查询，主要原因在于： •高维度导致的计算复杂性：数据维度较高，通用的距离函数都需要成百上千次浮点运算，十分耗时； •维度灾难（CurseofDimensionality）：随着维度的增大，搜索空间将呈指数增长的现 象； •为了解决高维向量KNN查询的效率问题，近似最近邻查询（ApproximateNearestNeighborSearch,ANNS）应运而生，其通过返回近似查询结果，来显著提升查询 效率（通常为数百倍以上）。 •目前ANNS使用的最常见的是距离度量是欧式距离和余弦距离。 •通常使用召回率（Recall）来衡量ANNS的查询精度，即近似查询结果中正确答案占实际正确答案的比例。 近邻索引技术 •哈希/树：用于ANNS的哈希方法主要是局部敏感哈希；树索引的基本思路是对空间进行划分，并采用树型结构维护空间划分的层次关系。 •量化与倒排（主流）：乘积量化（ProductQuantization，PQ）先把向量分为多个子段，然后对每段进行分别聚类与编码。量化是一种压缩技术，虽然能够极大的减少存储空间占用和距离计算开销，但是仍然要对全量数据进行距离排序，没有剪枝作用，所以通常需要配合倒排索引技术（InvertedFile，IVF），求取TopK个聚类中心的进行剪枝，进一步减少访问的数据量。 •近邻图（主流）：近邻图的基本思想是“近邻的近邻也是近邻”，其将每个向量作为图中的一个Node，在距离相近的向量之间建立边连接构成近邻图。查询时从固定入口出发，不断地贪心遍历离查询向量更近的邻节点，直到没有更近的节点停止搜索。 各索引技术对比 业务背景 •业务场景：一个典型检索场景 •检索链路复杂：一次检索经过四套系统 •写入链路复杂：写入维护三条链路 •端到端延迟高：端到端分钟级延迟 •数据一致性保障 •业务诉求 •能力支撑：文本检索+向量检索+多维分析 •成本：尽可能少的使用和接入成本 •业务开发维护成本：高可靠、高可用、用户友好 •性能：亚秒/秒级查询延迟，召回率95%+ •如何选型最符合业务现状，并有利于后续发展 •新兴向量库：系统学习成本？链路打通成本？数据迁移成本？ 后续系统维护成本？ •现有传统数据库+向量索引：性能？生态融合成本？稳定性？ 后期迭代？ 答案： 成熟可靠的分布式高性能数据库系统+向量检索； StarRocks实现向量 02检索的原理及优化 整体架构 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绑定，在列值物化的时候，同时物化对应的距离值； 查询实现—具体索引的计算实现 HNSW：IVFPQ： Selectid,l2_distance(query_vector,vector_column)asscorefromtableorderbyscorelimit10; 查询优化 Tablet级预排序： •方案：通过在Tablet级别进行topK预排序，再分发到Segment内进行物 化，可有效减少读放大、计算放大现象。 •效果：可以提升4%-23%的查询性能，证明了tablet级别的聚合可以生 效；通过引入并行检索能力，可以有效提升6%-24%查询性能。 查询优化 支持前过滤、混合过滤、迭代式后过滤： 引入新的迭代构造模型，支持迭代器之间可自由组合，并支持了新的阻塞迭代方式。 StarRocks目前支持的过滤类型： 过滤类型 是否支持 召回率稳定性 性能 后过滤前过滤混合过滤迭代式后过滤 索引写入原理与实现 如何将向量索引的索引逻辑优雅地映射到关系型数据库的索引逻辑？ MemtableRowsetWriter SegmentWrite SegmentLevel ColumnWriterColumnVector 存储级别选型： TabletVectorIndexvsSegmentVectorIndex r MemtableRowsetWriter SegmentWrite Flush Index TabletLevel TabletVectorIndexUpdate 索引写入流程： 索引是如何构建并写入的？ 聚类中心重训练： 对于IVFPQ如何保证聚类中心有效性 rColumnWriter 查询 聚类中心如何设置？ Tablet.rowset_commit index index index index index index inde x inde x inde x Tablet Tablet Tablet 索引粒度选型 索引级别选型： •Segment级别索引（当前选型）：在该方案中，每一个 Segment与一个VectorIndex一一对应，写入和加载都是 以一个segment为单位进行； 可以应用于主键表和明细表模型 索引向量到segmentrowid的映射，通过rowid召回其它列 rowset/segment过多时，会出现读放大（延迟物化segment）和过多地计算合并问题（小文件过多） •Tablet级别索引：在该方案中，每一个Tablet与一个 VectorIndex一一对应，写入和加载都是Tablet为单位， 类似于主键; 只应用于主键表 索引向量到pkid的映射，当只需要pkid时，可以 只检索索引而无需进行召回 召回其它列时，需要通过pkid多跳召回 Segment级别索引 Tablet级别索引 索引写入 索引写入流程：索引写入 正常索引写入 空索引写入 DeltaWriter Memtable RowsetWriter 增量自适应刷写 大Segment解决计算放大 刷写内存控制 空索引or正常索引？ SegmentWrite Chunk IVFPQ •过少的聚类中心无法 构建索引 HNSW •过少的点索引性能小 于等于暴力搜索 r ChunkColumn ColumnWriter ColumnVector Index Flush Chunk >flush_threshold_size TenANN VectorIndex 索引重建 IVFPQ索引重建 索引与聚类中心 QUERYGroupCompaction/writeGroup VectorIndex VectorIndex New Vector Index Query IVFPQ索引的一个通用做法是，它所有分簇共享同一个聚类模型，在构建索引同时进行训练，而后的数据新增也复用这个数据聚类模型进行分类，如果这个聚类模型长期不更新，随着数据变多特征迁移，整个聚类效果会变差；因此需要系统本身，或者用户去手动更新聚类模型，成本很高； 索引合并重建 索引独占聚类中心，写入/合并时训练； 聚类中心依赖Compaction重建； 资源分组隔离； Search BE TabletRowset VectorIndex Segment Materialize BE Tablet VectorIndex RowsetSegment VectorIndex BE Tablet RowsetSegment VectorIndex …… Tenann实现 为什么要自研TenANN？ 多索引集成：单一索引库无法满足所有性能与功能要求； 不跟具体索引耦合，预留更多优化空间； TenANN是一个通用、易用、易扩展、高性能 的多功能索引库，支持向量、倒排等多种类型的索引。 TenANN底层支持无缝对接自研索引，上层支 持所有索引共享同一套使用接口，从而使得TenANN的用户能够通过不做改动或者少量改动，透明地享受TenANN不断新增的索引和功 能。 RangeSearch SQL:selectid,l2_distance(query_vector,vector_column)asscorefromtablewherescore<0.8 orderbyscorelimit10; HNSWRangeSearch： 1NNSearch+r->RangeSearch IVF-PQRangeSearch： b–c=L<a BlockCache TenANN为了减小IVF-PQ索引无效数据从磁盘加载、实现在小于索引大小的内存容量下加载索引，并避免page_cache之间相互干扰开发的block级别缓存功能。 cache配置为inverted_lists大小的50%，cache命中率约96%，全recall与纯内存基本持平（即开启block_cache后只需要一半内存就可以达到纯内存的查询性能以及Recall） ANN-benchmark HNSW(Faiss)vsHNSW(Tenann) 性能优化测试总结 结论 单机（76core/128G)，30w–100w数据集，在50并发场景下，平均耗时<20ms，qps为2000召回率测试：在A业务、B业务、100w随机测试集上，通过动态调整tenannsearch参数召回率可以全部对齐，性能数据均无明显影响，符合预期。写入稳定性测试：100w，1000w，1亿，10亿标准数据集，写入均符合预期。对比ES，使用内部专业测试集，耗时(StarRocks)4.42msvs(ES)7.97ms。精确检索经过内存分配优化、SIMD指令优化、解析特化后，性能提升62%~70%迭代式后过滤