如何让OLAP具备高性能的向量检索能力
本文根据田昕晖老师在〖2024 XCOPS智能运维管理人年会-广州站〗现场演讲内容整理而成。**（文末有PPT获取方式，不要错过）******
作者介绍
**田昕晖，**ByteHouse技术专家。本科毕业于北京大学，博士毕业于中国科学院大学计算技术研究所，研究方向为分布式图计算。毕业后长期从事分布式系统相关研究工作，近两年专注于分析型数据库与向量检索相关方面的工作，目前在火山引擎ByteHouse团队负责向量搜索相关功能开发。
分享概要
一、向量检索相关背景
二、OLAP + Vector Search 相关挑战
三、ByteHouse + Vector Search
四、性能评测 & Future Work
一、向量检索相关背景
随着视频、图像等非结构化数据的激增，其处理需求日益增长。与以往主要处理的结构化数据不同，在处理这类数据时，一个常见的做法是利用嵌入模型（embedding model），即一种机器学习模型，根据数据内部的组成关系为其生成嵌入向量（embedding），即我们所说的向量，进行近似度相关计算，也就是向量检索。
在NLP领域，同样存在众多嵌入模型，这些模型能够有效发现词与词之间或段落之间的语义级相似度。
向量检索的流行离不开大模型的火热态势，这些模型需要在各种场景中实现检索增强，其主要目标在于缓解这些模型可能产生的幻觉现象（即生成与上下文不符或不合理的回答）和数据过时问题。
实现这一目标的常见方法是，将私有或专业的文档通过嵌入模型转换为向量，并存入向量数据库。在实际查询时，通常会带有一个提示（prompt），此时将查询问题也转换为向量，从向量数据库（VectorDB）中选取语义最接近的几条结果，并将其填充到提示中，再输入给大语言模型进行处理。
以ByteHouse的应用场景为例，假设我们拥有大量ByteHouse文档，在这种情况下，可以利用如langchain或Llama index等成熟框架，通过应用embedding模型为这些文档生成embedding，并随后将其存储于VectorDB中。
在进行后续的问答（QA）任务时，大模型能够基于问题相关的信息给出相对准确的答案。即便这些信息不在大模型的原始训练数据中，通过应用RAG（Retriever-Augmented Generation）方法，模型也能够得到较为准确的答案。
关于向量检索的实际应用，面临的主要问题是：在给定查询向量时，如何在庞大的基础向量库中高效地找到与之最相似的k个邻居，这通常涉及传统的KNN（k-最近邻）问题。
然而，当数据量达到百万或十亿级别时，KNN的计算成本会变得极为庞大。因此，实际应用中，我们通常将KNN问题转化为ANN（Approximate Nearest Neighbor）问题，即采用近似计算的方法来获取 K 个最近似邻居。
在进行ANN计算时，我们并非逐个比较所有向量，而是预先利用ANN结构对底层待比较向量进行组织。这种方法基于向量的相似度，以特定方式构建数据结构，使得在查询向量出现时，能以极少的步骤找到近似的最近k个邻居。
目前，ANN的实现方式多种多样，包括基于哈希的方法（hash-based），如将数据按照哈希表的形式整理；基于树的方法（tree-based），如使用树形结构组织数据；以及基于聚类和树的方法（cluster-based和tree-based）等。
下面重点讲解Cluster-based和 Graph-based这两种比较流行的做法。
1、Cluster-based
以Faiss库中的ivfflat算法为例，Cluster-based方法的核心思想在于首先对所有待查询向量执行聚类算法，通常利用kmeans算法计算出n个中心点。随后，数据根据这些中心点进行聚类。在搜索过程中，算法首先从这n个中心点中筛选出与查询向量最为接近的k个中心点，然后仅在这些选定的k个中心点所代表的聚类中搜索具体的向量，从而实现了一种有效的剪枝策略。
此算法的优势在于其构建过程相对迅速，主要得益于kmeans算法的简单高效。同时，它在内存占用上也较为节省，因为仅需存储n个中心点及向量原始数据。
然而，其缺点同样显著，特别是在实际应用中，查询速度易受向量维度的影响。具体而言，算法需要从n个中心点中挑选出k个最接近的，随后需遍历这k个中心点所代表的所有向量进行计算，因此向量的维度越高，计算开销理论上也会相应增大。
此外，对于追求高精度查询的场景，计算量也会显著增加。例如，若要达到99%的精确度，在拥有1024个中心点的情况下，可能需选取大量（如100或200个）中心点，这将导致计算量急剧膨胀。
2、Graph-based
另一种广泛应用的向量检索算法是基于图的算法，典型代表为HNSW（Hierarchical Navigable Small World）算法。该算法的核心思想是将所有向量根据其近似度关系构建成一个多层次的图结构。此图结构不仅包含所有向量作为最底层，还通过分层机制（如layer1、layer2等）形成逐渐缩小的子图，以确保在检索过程中能够迅速在前几层中排除不满足条件的向量。
HNSW算法的优势在于其查询速度极快。由于图结构的构建基于向量的近似度，理论上相近的向量会被组织在一起，因此在查询时所需的遍历步数大幅减少，同时支持良好的并发性能。
然而，该算法也存在一些缺点。首先，图结构的构建过程相对复杂且耗时较长，这增加了算法的预处理成本。其次，由于需要完整保存图信息于相关数据结构中，HNSW算法的内存占用较高，对硬件资源提出了更高要求。
3、量化（Quantization）
向量检索中，量化（Quantization）作为一个重要的概念，类似于向量压缩，旨在处理高维向量数据在数据量增大时导致的存储结构庞大问题。由于向量维度普遍较高，如OpenAI基础模型中的向量可能达到1500维以上，因此，如何有效压缩这些向量同时保持较高的精确度成为研究焦点。
其中，Product Quantization（PQ）是一种常用的向量压缩方法。其核心理念是将向量分割成多个子向量段，并对每段子向量分别进行kmeans聚类训练。随后，每段子向量仅由其最近的聚类中心点表示，从而实现向量的有效压缩。此外，还有Scalar Quantization方法，通过将浮点数直接转换为int8类型，实现数据大小压缩至原来的1/4。而Binary Quantization则更为极端，将浮点数简化为0和1的二进制表示，尽管此方法能极大压缩数据，但会伴随显著的信息损失，因此通常仅在特定领域且基于用户数据分布特点时采用。
针对PQ等向量压缩算法，还有如FastScan等优化技术，旨在提升压缩向量的计算效率，感兴趣的读者可进一步了解。
4、向量检索相关负载特性
1）CPU Heavy
将向量检索技术引入数据库领域时，需充分考虑其负载特征。此类应用往往呈现CPU密集型特点，特别是在构建索引（如我们前述的ANN结构）时，CPU资源消耗显著。同时，由于高并发查询场景普遍存在，CPU负担进一步加重。因此，在设计数据库支持的向量检索功能时，需优化算法与硬件资源的协同工作，以确保系统的高效稳定运行。
2）内存资源消耗高
关于内存资源，如之前提及的HNSW和IVFFlat等算法，为了实现高性能表现，它们通常需要将整个索引结构驻留在内存中，这导致了显著的内存资源消耗。
3）混合计算
此外，混合计算是向量检索应用中的一个重要方面。在实际查询中，用户往往不仅关注最相似的向量本身，更希望获取这些向量所关联的额外信息，如图像检索中的URL或图片文件。因此，计算过程中需要设计有效的机制，以确保向量检索结果与对应属性信息的准确匹配。
针对向量检索可能存在的不准确性问题，引入标量过滤条件是一种常见策略。如何高效处理这些过滤条件，以进一步提升检索精度，是向量检索技术发展中需重点考虑的问题。同时，将向量检索与数据库现有操作相结合，如跨数据集向量的相似度比较、文档级多向量相似度匹配等，也是当前研究的热点。
5、向量数据库
向量检索技术的兴起促进了专用向量数据库和库的开发。这些解决方案主要分为两类：一是专用向量数据库，它们专注于向量检索场景，通过vector-centric设计实现极致性能；二是数据库扩展方案，即在现有关系数据库或表引擎上增加向量检索功能，以满足更广泛的数据管理和检索需求。
近期，Oracle的23AI版本及TiDB等数据库系统纷纷引入了向量检索功能，这标志着向量检索正逐步融入通用数据库架构中。这些系统通过将向量检索的ANN（Approximate Nearest Neighbor）结构作为向量索引接入，充分利用了现有数据库对复杂数据类型和查询操作的支持，实现了向量计算与传统数据库功能的融合。这种“all-in-one”的查询模式，不仅扩展了数据库的应用范围，也提升了数据处理的灵活性。
6、现有数据库扩展
然而，向量检索的计算特性与现有数据库系统之间存在一定的适配问题。数据库系统作为结构数据为中心（structure-data-centric）的设计，其查询路径主要围绕结构数据的特性构建，而向量检索则是以向量为中心（vector-centric）的，两者在查询链路和索引计算模式上存在显著差异。具体而言，传统数据库的索引通常具有强单调性，能够基于索引准确找到目标数据；而向量索引则可能展现出较松散的单调性（如RS单调性），即初次查询可能无法直接定位到最邻近的向量，需经过多轮计算才能逼近。
因此，在将向量检索融入数据库系统时，需重点考虑如何弥合这些差异，实现向量计算与现有数据库功能的兼容与互补。这包括优化查询链路设计，使之既能适应结构数据的查询需求，又能有效支持向量检索的复杂计算过程；同时，还需探索新的索引计算模式，以更好地平衡查询精度与效率，满足多样化的数据处理需求。
二、OLAP + Vector Search 相关挑战
对于OLAP来说，添加Vector Search 有哪些好处呢？我们可以基于 OLAP 的存储优化以及高性能的查询引擎，构建高效的向量数仓，满足大规模的向量检索需求。
在为现有的 OLAP 框架添加高性能向量检索支持时，我们需要分析当前框架还有哪些问题，以及面临哪些挑战。
首先，需考虑到向量检索的负载特性，即其显著的CPU密集性和高内存资源消耗。此外，混合计算模式要求系统既需维护高效的内存缓存以支撑内存结构的快速访问（尤其是考虑到向量索引的随机访问特性），又需妥善处理混合计算中的各项任务，确保向量检索结果的迅速获取与关联属性访问的高效性，同时减轻系统开销，如LSM树设计下的读放大问题。
在资源管理方面，向量检索作为资源密集型任务，其资源调度尤为关键。如何在保障向量索引构建所需资源的同时，避免对其他计算任务造成干扰，也是我们引入向量检索支持时需要考虑的重点问题。
以ClickHouse为例，我们进一步分析现有OLAP数据库在支持向量检索方面的局限性。ClickHouse的查询处理流程基于推送数据（Push Data）模型，数据从底层表逐级推送至上层节点进行处理，直至最终结果的生成。
作为典型的 OLAP数据库，ClickHouse主要依赖 Data Skipping Index 进行数据过滤，该索引在查询计划执行前通过过滤条件快速排除不符合条件的数据块，从而优化读取效率。这种基于数据块的过滤机制（如存储每个数据块的最大值）虽能有效减少不必要的数据读取，但在处理向量检索等复杂查询时，其局限性逐渐显现。
采用当前设计进行向量检索时，存在显著问题。以查询需求为例，若需从表中选取ID并计算L2Distance作为相似度度量，以获取前10个近似邻居，采用data skipping index的方法虽能初步过滤数据块，但存在以下不足：
这是ClickHouse社区版在向量检索领域当前设计思路所面临的问题。
三、ByteHouse + Vector Search
我们在ByteHouse系统中实现了高性能向量检索功能。与ClickHouse相比，ByteHouse在高性能计算方面进行了更为深入的优化，包括但不限于优化器的增强、底层计算能力的提升、复杂查询与数据类型的广泛支持、数据管理的精细化以及表引擎的多样化（如唯一键引擎、高可用引擎和BitEngine引擎等）。
在ByteHouse上实现向量检索时，核心思路是探索如何在OLAP数据库中实现以向量为中心（Vector-centric）的设计。为此，我们首先从执行链路入手，设计了一套One Pass Computation机制，即专为向量检索定制了一个算子，该算子集成了向量检索所需的所有计算步骤，形成了一个紧凑的内嵌处理单元。
此外，我们实施了Column Pruning 策略，确保在能够利用向量索引完成检索计算时，避免不必要的向量列数据读取，从而减少了I/O开销。同时，我们引入了Vector Index Cache，一个基于LRU策略的内存缓存机制，以进一步提升检索效率。
在资源管理方面，我们将索引构建视为特殊任务，实施了线程级别的资源控制，并针对每种索引算法进行了内存资源使用的深度优化。此外，我们还借鉴了专用向量数据库的设计思路，对多种广泛使用的向量搜索算法（如HNSW及其SQ变种、IVFFlat以及最新的SCANN等）提供了支持，以满足不同场景下的需求。
ByteHouse目前提供两种架构：一种是存算一体的架构，即Share Everything架构；另一种是存算分离的架构。本设计主要聚焦于存算一体架构，但存算分离架构的思路亦有所相通。
设计方案概览如上图所示。
首先，在每个数据分区（Data Part）内部，我们维护了一个支持持久化的Vector Index文件。同时，我们对Query Engine进行了深度改造，涵盖了从解析层到查询生成层，再到算子执行层的多个环节。此外，我们引入了Vector Index Manager，负责Vector Search的执行、Cache管理、元数据管理以及第三方库的管理。
在计算逻辑上，以上述查询为例，该查询旨在从特定表中检索与给定向量最相似的10条记录，并附加了WHERE条件。处理流程如下：首先利用ClickHouse的data skipping Index进行数据过滤，随后执行Pre-filter计算生成bitset，该bitset作为输入传递给Vector Index进行Vector Search。Vector Search的结果包含需读取数据的行号及特定标记信息，据此生成读取任务，读取并拼接数据后，执行ORDER BY操作以获取最终排序结果。
为进一步优化性能，我们实施了多项策略。首要优化是计算前置与算子拆分。
鉴于原设计中将向量检索与读操作置于同一算子内可能导致的读放大问题（特别是在LSM Tree结构下，数据块增多时尤为显著），我们将Read Processor拆分为三部分：Vector Search负责在所有数据分区中执行Top-K操作，随后进行全局Order By加Limit以提取全局最相似结果，最后基于这些结果执行实际的读操作。此优化在数据分区数量超过100的场景下，实现了两倍以上的速度提升。
另一项优化针对冷读场景，即数据刚写入Index且尚未加载至内存时的情况。我们设计了Cache Preload机制，以加速新数据或后台默认数据的Index生效过程。同时，引入Auto GC机制，确保当数据分区失效时，能够自动回收Cache中的相关数据，以维护系统资源的高效利用。
四、性能评测 & Future Work
1、性能测试
关于性能测试数据，我们采用了Zilliz公司提供的 VectorDBBench 基准测试框架。测试聚焦于多个关键指标：首先是查询处理量（QPS），即在10,000条查询请求全部执行完毕后，评估整体的每秒查询次数；其次是召回率（recall），衡量在执行查询时，返回的相关结果所占的比例；再者是加载时长（load duration），该指标涵盖了数据写入与索引构建的整体耗时；最后是串行延迟（serial latency），通过串行执行多条 query 得到P99延迟值，即99%的查询请求所经历的最大延迟时间。
在对比测试中，我们选用了Milvus 2.3.0这一较新版本，并评测了 ByteHouse 支持的三种索引类型。测试环境配置为单节点，配备80核CPU及376GB内存。
结果显示，在包含一百万条数据的数据集上，我们的系统实现了高达3,300的QPS，加载时长相较于Milvus有显著优化，这得益于ByteHouse在数据加载方面的深度优化策略，而Milvus则受限于使用Python SDK进行逐条数据插入的方式。这一对比凸显了在成熟数据库平台上构建系统所带来的性能优势。
进一步地，在 recall 94 条件下，Bytehouse 的 QPS可达到4,000以上，同时维持了较低的加载时长。这一结果表明，通过创新算子设计及前置优化策略，我们的系统能够在保证精度的同时，实现超越专用向量数据库的性能表现。
2、Future Work
1）索引算法优化
致力于结合OLAP（在线分析处理）及现有数据库的优势，以实现资源更高效的管控，深入探索disk-based索引的优化策略，采用更先进的压缩算法与策略，以提升性能并降低存储成本。
2）向量检索与其他查询操作融合
探索更复杂的查询策略，如iterative search，即先执行初步查询再进行过滤，以提高高 selective ratio 场景的查询精度与效率。
计划支持基于UDF（用户定义函数）的embedding计算融合，利用API接口集成embedding模型，使得在数据插入时即可通过UDF将用户输入直接转换为embedding，从而实现AI处理流程的完整化。
致力于实现与全文检索的混合搜索功能。鉴于当前大模型领域对混合搜索能力的日益重视，我们认为将向量检索与全文检索相结合，通过Rerank技术整合两者结果，能够为用户提供更加精确的信息，不仅保留向量检索的语义相似性优势，还能捕捉到精确匹配的信息，进一步提升搜索效果。
3）性能优化
继续减少读放大现象，并与优化器紧密合作，以生成更合理的执行计划，提升系统整体性能。
4）易用性与生态
与langchain、LLAMA index等大模型框架结合，并寻找自身在更多优势领域的应用场景，以丰富我们的产品生态并提升用户体验。
--
>>>>****
Q&A
**Q：**对于IVF和HNSW这类索引，在大数据场景下（如处理数百万条向量数据），索引创建时CPU资源消耗巨大。除了优化算子，还有哪些方法可以优化索引创建时间，尤其是考虑到HNSW等基于图的索引随数据量增加而创建速度显著下降？
**A：**优化向量索引构建的开销主要可从几个方面考虑。首先，识别主要开销来源，通常在于构建过程中大量的距离计算。为提升效率，可考虑采用更高效的硬件（如支持更多SIMD指令的处理器）或优化距离计算方法（如利用PQ或SQ量化减少计算开销）。
在数据库层面，可将索引构建视为长期任务处理。由于ClickHouse在数据插入时生成数据块并即时构建索引，初始索引构建可能相对较快。然而，随着后台数据合并过程的进行，大规模数据块的索引重建成为挑战。此时，可将索引重建设为异步任务，并限制其资源使用，确保前台服务不受影响。通过异步处理和资源限制，即便在索引重建期间，数据库服务也能保持连续运行。
dbaplus社群欢迎广大技术人员投稿，投稿邮箱：editor@dbaplus.cn
↓↓ 点击阅读原文获取本期PPT**(提取码：0524)**
