背景
AnalyticDB Postgres向量版纯向量检索在高维人脸检索的场景下，性能是开源milvus的HNSW算法的2倍，IVFSQ8的10倍。
但是作为一款数据库产品，她本身在结构化数据分析领域也有着超强的性能，TPCH性价比最高的在线数仓【2】，她的更强的能力在于支持向量与结构化数据的融合检索，能在各种条件组合查询的场景中，达到98%的召回率。
我们之前有一篇文章【3】对AnalyticDB Postgres向量版的能力做了部分说明，这篇文章带你走进AnalyticDB Postgres向量版内核。
架构设计
AnalyticDB Postgres向量版兼容开源分布式数据库Greenplum，他们的架构类似(深色部分是向量检索在AnalyticDB Postgres基础上增强的模块)：
与Greenplum类似，整个系统分成2种类型的角色，master和segment，master负责保存元数据，生成执行计划，并负责把执行计划分发到segment节点执行，并对结果做聚合，在master节点，我们主要增加了向量的元数据管理，与优化器部分的优化，能支持选择高召回条件下的融合查询执行计划。
Segment作为数据与计算节点，实际上是一个完整的PostgreSQL实例，把它的细节打开后，如上图右侧所示，是一个典型的PostgreSQL数据库架构，我们对他做了大量的改造，我们分别从SQL层与事务存储层来说明。
SQL层
Fasion query：执行根据RBO规则来生成融合查询的执行计划。
Parallel query：为了降低多分区的执行RT，我们支持多分区并行执行
Resort merge：为了提高多分区向量计算的效率，我们支持多分区聚合重排
Distance plugin：为了更好的支持算法厂商的加密算法，我们把各种算法厂商算法的距离计算作为插件，当前支持标准的L2，宇视和商汤算法距离。
事务存储层
ANN：就是近似距离索引。
Vacuum：通过vacuum，我们实现了对ANN索引的update和delete支持。
Train：后台训练模块，我们实现了对PQ算法的流式训练，而后台训练过程对用户无感。
可插拔的ANN索引
PostgreSQL本身提供了索引插件实现机制，大家可以很容易找到相关的资料，例如对于PostgreSQL 11.3，我们需要实现下面的接口：
但是在实现ANN索引的时候，我们还需要关注下面几个小问题：
Limit下推
一个典型的ANN的检索查询的SQL是这样的，查找符合seq > 9 and deviceId = 'a' or personAppearTime > '2006-05-02' 筛选条件，且与array[10,2.0,…, 512.0]距离最近的前10条记录：
select * from ods_person_feature where seq > 9 and deviceId = 'a' or personAppearTime > '2006-05-02' order by bodyFeature <-> array[10,2.0,…, 512.0] limit 10;
它生成的执行计划中limit参数实际无法传入索引，所以我们需要修改执行计划把limit参数下推到索引层面。
PostgreSQL多进程架构
PostgreSQL多进程架构，每个session会fork一个进程来处理用户请求，我们的1个索引对象不能每个进程都创建一份内存，需要使用PostgreSQL的share memory机制，然后共享给所有的子进程。
所以我们需要使用PostgreSQL的段页式存储管理和shared buffer内存管理来实现索引算法，这块的实现需要优化，否则会成为我们的性能瓶颈，这块在段页式中的实现我们在3.2介绍。
事务处理和HA
对于向量检索的典型业务，事务的ACID中的Isolate并不是强需求,但是ACD是强需求，我们通过wal日志和PostgreSQL的checkpoint机制来实现Atomic和Durable。
写入时，对于修改的共享内存中的page，我们通过wal日志来记录所做的修改，wal日志使用PostgreSQL的标准事务提交模型，修改的page内存数据，并不立即写入磁盘，wal日志在事务提交的时候使用append的方式fsync到磁盘。
由于有了wal日志，我们可以复用PostgreSQL的流式复制机制，通过同步wal日志到备机并回放，实现1主1备的高可用方案。
关键技术
ANN检索算法
OLAP团队一直与达摩院的proxima团队在ANN算法有紧密和合作，AnalyticDB Postgres移植的proxima【1】的算法，它的核心思想是把HNSW图算法与PQ编码算法做一个融合。
ANN检索算法在段页式存储中的实现
PostgreSQL的存储是数据库经典的段页式存储结构，并实现了Buffer Pool来解决数据在内存的换入换出的问题，我们基于段页式存储设计最大的好处在于能够复用PostgreSQL段页式存储的基础设施，不需要自己管理磁盘和内存数据。
为了追求在不同场景下的极致性能，我们实现了2种encoding graph索引，一种为append模式，另一种为update in-place模式。
Append模式：即支持插入和批量删除以及少量随机删除和更新，一般不超过10%的删除和更新，大部分向量检索的场景都是这种模式。
Update in-place模式：支持对向量数据的任意模式的增删改查。
Append ANN索引
这种模式的段页式存储设计如下图：
上图分布从一个索引文件，和索引文件的block，以及block中的tuple 3个维度介绍了ANN索引的数据存储模型。
Index file：与PostgreSQL标准的数据存储类似，一个索引文件划分成8k大小的block，与传统数据库不同的是，ANN索引中的block有3种类型。
- Meta page，保存索引的元数据，例如图的入口点，有效记录条数等；
- ann tuple page，里面保存的都是ann tuple，
- neighbor tuple page，保存的都是neighbor tuple，他们以slot为单位分配，同一个slot里面的block均为同一种block，例如上图橙色为ann tuple page，绿色为neighbor tuple page。
Block：里面保存的都是同一种类型的tuple，因为tuple是append的方式，所以不需要维护PostgreSQL page中标准的line pointer，我们对PostgreSQL中的ItemPointer做了改造，它其中的line pointer我们替换成Block内的offset，避免了需要再次访问line pointer求offset多一次跳转的问题。
AnnTuple：保存插入的向量的基本信息，例如：
- flag：用来实现标记删除，
- pq code：PQ编码
- heap iptr：向量在堆存储的位置
- neighbor iptr：他的邻居在索引中的位置。
AnnNeighorTuple：用来保存邻居信息，可以有多层组成，所以：
- level：保存有多少层
- size：该层实际的邻居个数
- iptr：邻居在索引文件中的位置。
之所以有上述Ann Neighor Tuple和 Ann Tuple分开存储的设计，有下面的几个优势：
- 减少磁盘io，ann neighbor tuple更新频繁/访问频率不同，ann tuple基本不更新，PostgreSQL checkpoint按page为单位刷脏页，分开可以减少磁盘io，PostgreSQL刷盘没有实现mysql的duoble write机制，他的解决办法是第一次修改一个page的时候，会把整个page的数据都写入wal，encoding graph算法在更新邻居的邻居的时候，插入一条记录可能修改非常多的page，wal日志膨胀的比较厉害；
- 加快检索速度。图遍历，读一个ann neighbor tuple，访问邻居的所有ann tuple， ann tuple数据量少，存放的page少，大概率减少缓存的page数量；
- 减少空间浪费。Ann tuple和ann neighbor tuple存一块，一个page存不下的时候，只能存到一个新的page，导致page空间浪费。
基于Slot的free page分配算法
为了实现上述的Ann Neighor Tuple和 Ann Tuple分开存储的设计，我们需要一种新的free page分配算法，因为PostgreSQL自身的FRM算法，有下列局限：
- FRM得到的free page，不支持类型选择。
- FRM分配的Page无法保证同类型page的连续性。
所以我们设计了如下基于slot的free page分配算法：
我们在索引的metadata page中，记录了当前已经分配的slot，slot分为2个类型，AnnTuple Page Slot，AnnNeighborTuple Page Slot，需要对应的Ann neighbor tuple都从这个slot来分配一个page，slot一般分配100个page，只所以分配100个是刚好匹配PostgreSQL的并发数，分配的时候，随机从100个page中选取一个，得到page之后，再判断这个page是否有足够空间，如果没有足够空间，则再次重试，重试的时候不再通过随机，而是以当前page id递增的方式来遍历，如果遍历了所有的page读没有空闲空间则申请一个新的slot，这种分配算法的好处在于，通过random分配一个page，避免了高并发下，大家都写入同一个page造成page的加锁冲突。
Copy-on-write 机制减少page加锁访问冲突
在访问一个点的邻居 的时候，需要把邻居id的page读锁，然后再去访问邻居点的数据page，容易出现锁冲突和死锁。
例如下面的例子：访问在P1上的点的邻居，因为它的邻居数据保存在P10和P11上，所以需要首先把P1加锁，再去访问P10和P11，访问过程就保护ANN检索中耗时的距离计算，然后再把P1 page解锁。
优化前后加锁时间的对比：
Update in-place ANN索引
Update in-place的存储结构如下：
与append模式不同的是，block只有2种类似：
- Meta page：作用同上
- Ann page：里面可能同时保存了ann tuple和neighbor tuple。
因为需要考虑页面的回收，所以我们使用了PostgreSQL标准的FRM来分配页面，使用line pointer来记录记录在page中的位置。
当发生删除或者更新的时候，对应都是如下图构建的图，有对应的点被删除，使用append模式的标记删除有下面的2个问题：
- mark delete删除了重要的连接点导致图的连通性下降，造成召回下降
- mark delete只删除了点，没有删除边，计算性能下降，空间利用率下降
基于此，我们在当索引数据删除超过一定阈值触发bulkdelete函数调用，或者手动vacuum的时候，通过下面4步流程来修复图：
：
- 只所以先做scan，得到被删除的点，是因为我们需要先删除指向被删除的点的边，再删除被删除的点，这样可以避免，同时有读写请求的时候，做图遍历访问到被删除的点，因为这个点还作为别的点的邻居存在。
- 只所以需要重新rebuild index，是因为当删除大量的点的时候，会造成图的边的个数减少，造成图的连通性下降，所以我们会删除边的时候记录点的邻居个数，少于设定阈值的点，需要重新添加邻居。
上述算法存在的问题是，当图的数据量特别大的时候，重建的代价非常大，所以我们后续会对这个算法做进一步改进。
多版本PQ算法
传统的PQ依赖离线训练，但是如果让用户离线手动训练一个码本再注入到数据库中，用户体验太差，另外如何选择合适的参数来训练，也无形中提高了用户使用向量检索的门槛。
我们实现了上图的多版本流式训练算法，训练PQ码后台进行，对用户无感知，它的主要思路是：
- 用户刚开始插入数据的时候，使用原始向量，不使用PQ码，由于这个时候图的规模非常小，写入不会成为瓶颈；
- 当用户写入10w数据的时候，后台启动training 进程，训练出第一个codebook v1，并使用v1的codebook把之前插入，没有填充PQ码的记录，填上PQ码，我们称之为回填PQ码。
- 这个时候，用户就可以使用码本1的PQ码进行写入。
- 因为码本1的训练数据不够，我们后续会持续迭代的训练码本。当写入数据量到100w后，码本2训练出来。这个时候写入就可以使用码本2来生成PQ码。
- 对于查询进程，这个时候一次查询可能同时访问到码本1生成的PQ码和码本2生成的PQ码，所以我们实现了多版本的PQ距离。
通过上述的方式，我们QPS提升5倍，存储压缩 16倍。
流式PQ码本训练
PQ码本训练基于传统的KMeans算法，而KMeans训练算法的计算量较大，为了避免训练的计算任务堆在一起占用大量的CPU，导致用户的写入和查询被阻塞，我们对KMeans算法做了改进，把训练数据分成多批，如下图所示，每写入10w数据，就把这部分数据和之前训练出来的码本（即KMeans算法的类中心），喂给训练算法，从而得到一个新版本的码本，把训练的计算做了均摊，降低了对用户读写的影响。
多分区聚合重排
ANN查询的时候，分为2个阶段，首先通过PQ code计算距离得到近似的结果集合，因为PQ code不够精确，业界标准的策略是先放大再通过长特征重排。例如我们需要topk个最相似的结果，我们通过PQ code会取topk * amp（放大系数）个结果，然后对这topk * amp个结果再查找原始向量计算精确距离，并重新排序。
实际性能定位的过程中，当topk为100，放大系数为50的时候，查找原始向量计算精确距离所占的时间是总的查询时间的一半。
这种情况在分区数特别多的情况下，会特别突出，当一个查询涉及多个分区，会有 n * topk * amp 个长特征计算，我们希望，在多个分区的情况下，也只需要做topk * amp个长特征计算即可。
增加一个resort merge算子，当有多个分区的时候，
- 首先每个分区根据PQ距离得到topK * amp个候选的结果，这样我们一个有n * topk * amp个结果；
- 在resort merge算子中，第一次getnext的时候，首先topk * amp个距离最短的结果，具体做法是，getnext的时候，获取从前一次距离最短的结果所在的分区获取，一直得到topk * amp个结果
- 对topk * amp个结果重新排序，最终getnext从重新排序的结果集中获取topk个结果。
执行计划
一个典型的跨2个分区的查询查询计划如下：
Resort Merge主要有下面的2个关键数据结构：
- pick up heap：本身是一个定长的排序堆数据结构，用来决定下次取候选结果从哪个partition取，大小为 n (n为分区数)
- resort heap：本身是一个定长的排序堆数据结构，用来缓存重排的结果集，大小为topk * amp。
关键流程
- 调用他所有分区的Ann index scan，得到通过PQ距离得到的候选集合，这个集合经过了放大，例如topk是2，放大2倍，我们会取top 4个候选者。如下图所示，2个partition的索引，分别得到1，2，3，4个候选点，他们按照PQ距离排序，高度则代表了他们的实际精确距离；
- 从每个paritition提取一条数据到pick up heap，初始化pick up heap，从partition获取的数据是按照PQ距离排序，取得时候我们才按需计算它的长特征的距离并返回，我们并没有所有的候选集都计算距离，而是按需计算。这个的流程如下图round 1所示，分别从ann index 1和ann index 2选取PQ距离最近的候选点到pick up heap，并得到他们的精确距离：
4. 填充resort heap
从pick up heap中出栈距离最近的一条记录，塞入resort heap，同时我们假设这个partition还有距离更近的记录,又从这个partition继续取一条记录到pick up heap，重复上述步骤，直到填满resort heap，这个过程如上图的round 2，3，4所示。最终在resort heap中的记录就是已经按照长特征排好序的候选集，当达到resort heap长度时停止。
5. Resort Merge 算子返回下一条记录，直接从resort heap取下一条记录，并出栈。
融合查询
当前开源的向量检索系统Faiss和milvus都没有很好的解决融合查询的问题。
例如下面的典型的融合查询的例子：
我们需要从表中检索出摄像头id在xxx中，并且与传入的向量array[x]最相似的前100条记录。
业界大部分厂商使用的是2个系统，例如数据库系统存结构化数据，向量检索系统存向量，2个系统分别求交集后再聚合，在结构化数据过滤结果比较多的情况下，召回有较大的损失。
我们实现的向量检索一开始就是作为一种索引插件，所以我们非常容易根据数据库优化器，生成不同的执行计划来解决这个问题。如上图所示，对于典型的融合查询，我们会生成上面3大类执行计划：
- 当结构化数据选择率最小的时候，例如符合device id的向量结果只有几万条记录的时候，我们直接把这几万条向量读取上来，通过暴力计算得到最相似的100条记录。
- 当结构化数据选择率一般的时候，我们会把结构化选择条件下推到ANN索引的图遍历过程中，一遍做图遍历，一边做结构化过滤，当遇到不符合结构化过滤条件的点的时候，我们会跳过继续遍历，并且我们会根据选择率动态调节图遍历的范围，当遇到较多的点不符合结构化过滤条件，我们会扩大图遍历的范围。对于下推的结构化条件，结构化条件有索引的时候，我们会下推结构化索引过滤的bitmap结果，当结构化条件没有索引的时候，我们会下推结构化条件表达式；
- 当结构化条件选择率最大的时候，我们会先使用ANN索引过滤再使用结构化条件过滤，为了避免结构化过滤减少了返回记录个数，我们会根据结构化条件的选择率动态放大ANN索引返回的记录条数。
下图是我们以某业务在不同选择率条件下对召回率的测试：
由上图可以看到在不同时间和摄像头选择率的组合条件下，都能得到98%以上的召回率。
FP16压缩
与传统结构化数据不同，向量的数据占用的存储空间非常大，典型的一个512维的向量占了2k的存储空间，而一个结构化的float字段只占用4个字节，为了降低数据的存储空间，我们使用FP16对FP32位做了压缩，可以降低一半的存储成本，而向量的类似转换使用SIMD指令完成，具体的用法可以参考【6】。
对于FP16编码导致的召回损失，我们基于512维人脸数据做了测试，这个召回的损失基本可以忽略不计。
产品路标和后续工作
向量团队会继续聚焦于提供更高性能与成本的结构化与非结构化分析产品，我们后续的工作会围绕2个方向展开：
- 持续提升向量检索的性能与产品的易用性。
- 持续提升向量检索的性能，预计最近会有较大提升。
- 基于准度的CBO解决RBO减少在不同场景下调优的工作量。
- 提供AI分析的计算平台，打通非结构化数据分析的桥梁。
- 与DLA/OSS团队合作，提供开箱即用的非结构化数据分析能力（图片视频文本）。
引用
【1】https://www.atatech.org/articles/126943?spm=ata.13269325.0.0.403949faiTz3gK
【2】http://www.tpc.org/tpch/results/tpch_perf_results.asp
【3】https://zhuanlan.zhihu.com/p/82284704
【4】https://arxiv.org/abs/1603.09320
【5】https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf
