目录
一、 背景介绍
二、 向量检索算法/PG自定义索引
三、 PASE设计与实现
四、 ASE使用实践
一、背景介绍
什么是向量检索（近似最近邻检索/ANN）
向量检索是从一堆已知的点中，找出给定P点的最相邻的K个点的过程。这些点可以是：1维点、2维的点、3维的点... ... 这些点我们统一叫做向量。
高维：维度大于10，小于1000，称之为高维向量。
超高维：维度大于1000，称之为超高维向量。
应用场景一：以图搜图/人脸识别
以图搜图和人脸识别两个应用场景，属于一个范畴。
图片搜索类，比如在淘宝的搜索框后边的拍立淘。拍立淘的功能是：对感兴趣的商品进行拍照，然后搜索到和它相似的商品。后端实现的技术是，运用多个深度 CNN的模型对图片进行特征抽取，抽取出来的特征就是高维度向量。比如是256维度的向量，查询的时候，将拍照的照片进行同样的特征抽取，也取出256维向量检索过程，运用256维的向量在全库中进行相似的向量查询。如下图所示：
人脸识别是支付宝的特色产品，它的应用场景就是刷脸支付。刷脸支付的技术实现方式和以图搜图类似。在离线训练CNN深度模型，在离线对全局的人脸进行特征抽取，做存库的处理。查询刷脸时，对采集的这张照片进行人脸特征抽取，运用这个特征在全库中进行相似点查询。
以图搜图和人脸识别这两个过程都运用到了向量检索技术。
应用场景二：推荐
个性化推荐场景的方式类似于以图搜图方式，区别在于，推荐基于用户的特征查找和用户感兴趣商品的过程。它的技术实现方式，是采用双塔模型，用户进行用户特征的抽取，商品进行商品特征的抽取。在最后查询阶段，是用用户的特征在商品的特征库中进行检索。这是个性化推荐的项目检索过程。如下图所示：
应用场景三：基于深度模型的语义检索
基于深度模型的语义检索，它的应用场景也很广泛，比如打开支付宝或者淘宝进行搜索，都运用到了相应的技术。最近比较火热的布尔特模型，也适用于这种场景。运用深度模型对词汇进行特征抽取，最后落到检索过程，还有应用向量检索查找到带查询词相匹配的商品。如下图所示：
通过以上场景可以发现向量检索技术广泛的应用于搜索、推荐、人脸识别等等场景，结合深度学习，技术的发展，向量检索技术最近这些年也得到了比较快速的发展和广泛的应用。
二、向量检索算法/PG自定义索引
向量检索最简单的实现方法是逐一比对方式，简称为暴力搜索方式。这种方式优缺点很明显，优点是准确率足够高，逐一比对，总能找到最详细的向量，这种方式的准确率是100%。缺点是查询耗时很高，不能应用于工业界的场景中。
ANN检索算法
业界研究出了很多的向量检索算法，向量检索算法简称为ANN检索算法。类似最近邻的方式，通过简称也能发现一般的实现方式都是运用精度的损失，来换取性能的大幅提升。
因此一个算法的好坏来衡量转换的效率是否足够高，能用很小的精度损失来换取大幅的性能提升，ANN就是一个好的算法。目前常用的相应检索算法，总结基本可以分为4大类，基于树、基于哈希、基于量化、基于图，这4个方式各有优缺点，也各有不同的应用场景。
基于树：KD-tree、KMeans-tree、VP-tree、Ball-tree等等，其共同特点在于利用某种策略，对空间进行逐层切分，直到树的叶子节点只覆盖空间的一个小的局部。通过这个方式大幅提升检索性能。
基于哈希：局部敏感哈希（Locality Sensitive Hashing）、谱哈希（Spectral Hashing）、球哈希（Sphere Hashing）、锚点图哈希（AnchorGraph Hashing）等等。他们的共同特征则是通过超平面或者曲面，将空间进行直接切分，并对切分后得到的各个细小区域进行二进制编码，通过构建哈希表来加速查询。其中，超平面或者曲面可以通过学习或者非学习的方式得到，其表示我们称之为哈希函数。
基于量化：矢量量化（Vector Quantization）、粗量化（Coarse Product）、积量化（ProductQuantization）及其改进的最优积量化（Optimised Product Quantization）、复合积量化（Composite Quantization）。量化的思想是对向量进行kmeans等聚类方式，将相邻向量使用中心点代替，从而通过倒排索引以及子空间距离计算加速等策略提高检索速度。
基于图：近邻的近邻也很可能是近邻。从随机选择的初始点开始，通过检查邻居里距离query更近的点，把该点当作下一次迭代需要检查邻居的点，如此不断迭代，通过邻居的邻居的邻居，我们会逐渐逼近query。
这4种方式各有优缺点，在实际应用场景中，根据各个业务不同的要求进行选取。下边针对一些典型的算法，对算法原理进行详细描述。
1. 粗量化（IVFFlat）
算法原理如下图所示，空间中所有的向量，如最左边的向量天然具有聚类的属性。然后进行centroid聚类，把空间分成两个类，如图所示分成上下占两类，每个类存在一个中心点，比如图中用红点表示类簇的中心点，这是离线的处理过程。在线查询时，根据query和两个中心点进行比较，查到距离哪个中心点最近，只保留中心点所处的类簇，丢弃不相关的类簇。
这种算法优缺点很明显，优点是算法足够简单，只需要聚类即可。缺点是精度其实可以足够高，查询的中心点可以保留很多，比如图中可以保留两个中心点，相当于暴力检索，但是性能都不高，精度换取性能的效率并不高。适用场景是精度要求很高，但是对查询耗时要求不严格的场景，一般在100毫秒级要求的场景。总结粗量化的特征是：
要点：
1. 聚类。
2. 查询中心点集合=>遍历对应类簇。
优缺点与适用场景：
➢ 优点：简单
➢ 缺点：精度高性能不高
➢ 适用场景：召回精度要求高，但对查询耗时要求不严格（100ms级别）的场景。
2.IMI
IMI量化产生的背景是解决粗量化的问题，第一个问题是，候选集质量是效果天花板；第二个问题是，数据量巨大，聚类中心点多耗时长。如下图所示，经过粗量化之后，只保留两个类簇，最终效果的好坏决定两个类簇中的点，距离query足够相近。另一个是数量巨大，两个点的点数很多，聚类中心点多耗时长。这是IMI产生的背景。
怎么来解决上述的问题。如图所示，以两维的向量为例（x轴和y轴），将向量进行两维度的切分，在每个维度上分别进行聚类。比如图中 x轴和y轴两个空间，分别进行聚类。查询效率性能和粗量化类似，好处是把聚类分的更细。如图所示，查询的范围都是集中在两个点的周围。优点是可以达到足够高的精度，同时查询性能耗时比粗量化更低。缺点是实现比粗量化复杂，增加分段聚类过程，耗时比粗量化高，但高的并不明显。适用场景与粗量化类似，对准确率有一定要求，同时对查询要求并不高的场景。IMI总结如下：
背景
• 候选集质量是效果天花板
• 数据量巨大，聚类中心点多耗时长
要点：
1. 向量切割
2. 分段聚类
优缺点：
➢ 优点：精度高
➢ 缺点：实现相对IVFFlat复杂，并且查询耗时依然较高（100ms）
➢ 适用场景：和IVFFlat类似，但对准确率要求更高的场景。
3.近邻图/HNSW
近邻图的方法论是：近邻的近邻也很可能是近邻。如何来实现查找过程？
首先将离线的点进行近邻图构造，如下图所示，连成一张图，随机采用一个点作为入口点。绿色的点是查询点，查询是从入口点进入，查询它和它的临界点之间哪一个距离query更进。保留距离query近的点，然后从这个点再找他和他的邻居点距离query最近的点，一次迭代，最终找到最近的量向。
这种连接图的方式也可以优化，如上图中，如果点数非常多，入口点距离最近邻较远，经过多次的跳转才能查到最近邻。优化方法是采用跳表的思想，采用多层连接图方式，上层图是下层图的缩略图，通过这种方式能快速的定位到它可能出现的区域，从而达到加速查找的目的。
跳表的多层图就是HNSW的核心思想，优点是查询速度快，准确率又能有一定的保障。缺点是临界点存储浪费内存，增加存储空间的开销。使用场景是对于查询耗时有一定要求，同时准确率也有一定要求的场景。另外对于存储耗时的增长不敏感的场景，都可以采用近邻图的算法。近邻图特征总结如下：
背景：量化检索数据量大，精度低。
• 方法论：近邻的近邻也很可能是近邻。
优缺点与使用场景：
➢ 优点：速度快、精度高
➢ 缺点：邻居点存储开销
➢ 使用场景： 超大规模向量数据集（千万级别），且对查询延时有严格要求(10ms级别)的场景。
ANN算法库
ANN算法库典型有Faiss、SPTAG、proxima、vearch。
Faiss：Facebook开源向量检索库，现在比较有名。
·优点：是算法齐全，目前业界中研究方向都是基于Facebook开源的库进行优化。
·缺点：是代码工程质量很一般，比较适用于学术界的研究，工业界使用并不是特别友好，需要产品化。
SPTAG：是微软开源向量检索库。
·优点：有算法创新，将树算法和图算法进行了结合，实现了比较高效的图算法。
·缺点：是支持的ANN算法比较少，只有几种优化的图算法，部分特定场景，测试看能力不如Faiss。
Proxima：是阿里的达摩院向量检索库，目前阿里集团内部的向量检索实现，大部分基于Proxima。
·优点：ANN算法齐全，支持扩展。性能足够高，特定场景，测试看能力优于Faiss。
·缺点：是并不开源，集团外的很同学想用，其实是用不了的。
Vearch：京东开源的向量检索引擎。适用于对搜索需求简单，重在向量检索
的初创公司。
·优点：是完整的检索引擎，是分布式的服务，可服务化部署。
·缺点：其他搜索能力较弱，分布式能力弱。
为何选择PG做向量检索引擎
技术选型的路程，如上图所示，候选集合如左边选择很多，可以分为搜索引擎类，开源搜索引擎和内部资源搜索引擎，还有OLAP数据分析的库，例如阿里自研de AnalyticDB,蚂蚁自研的Explorer。
另一类是数据库类,如OceanBase、MySQL PD，业务场景是需要有轻量级的这种要求，经过筛选之后，有Elasticsearch、MySQL、PostgreSQL三款引擎,经过索引扩展能力的考核之后，剩下的只有PG一个数据库，MySQL索引扩展相比PG不是很丰富。
Elasticsearch扩展对索引层面的扩展相对复杂，因此总结PG的优势，首先是比较轻量级，第二性能比较优越，扩展能力比较强大，稳定性足够高,生态丰富，有很多开源的贡献。
基于PG的优势，首先采用它的业务使用者并不需要数据的迁移，很多的业务数据都存在数据库中，可以直接实现线上检索的这样一个功能：另外支持组合查询的，可以结合线上检索和其他的条件查询进行这个组合的查询。
同时 PG还支持分布式部署，通过第三方插件的支持来实现分布式的部署，经过这些考量，选择PG作为向量检索引擎的技术引擎。
PG已有向量检索方案
在确定了选用PG作为我们引擎之后，对向量检索算法，PG上的已有的线路检索插件进行调研，总结之后，主要的插件如下图所示:
以上调研的情况，结论就是如果基于 PG做向量检索引擎，需要我们自研向量检索插件。
自定义基础一：PG 基本存储单元——Page结构
在上面的背景和目标之后，对 PG的自定义插件能力上进行考量， PG本身支持非常丰富自定义索引的能力，总结有两个基础，基础一是PG的基本的存储单元配置结构，完全可以自定义的。
如图所示，是Page的机表的页面的结构。
大概分为三个组成部分，第一部分是Pageheader部分，结尾是special space部分，中间部分是记录的存储部分，Tuple是一条记录的存储单元，多个Tuple就存储在一个页面内，在页面Page的起始部分会有记录的指针，通过指针进行寻址。
Page的默认结构是存储8k ，当记录数小于8k的时候，就可以存储多个记录在一张Page中。
对于索引所采用的Page结构和此结构是完全一样的，区别在于中间部分不限制，是可以完全自由使用的空间。
可以从图中可以看到，给的Tuple是最小的数据存储单元，存储结构完全可以自定义，这个是PG提供自自定义索引的一个重要的基础。
自定义基础二：PG索引API——IndexAmRoutine
基础二，是Page支持了非常丰富的索引，定义接口API，整个索引的PG的结构可以分为几个层次：第四层是数据的存储，第三层是所有的存储，第二层是索引的接口层，第一层是通过 Index Am Routine结构底来控制索引的各个API的调用。
如图所示，是他的Page的Index Am Routine的 API的定义，从这个定义中可以看到，它支持非常丰富索引操作的接口，例如索引 build和单个索引insert，以及标记和删除，还有查询初始化、返回以及查询相关的接口。
三、PASE索引设计
IVFFlat索引设计
基于这些基础，设计了 PG的向量检索插件，起名为PASE。
向量检索算法包含很多种类，需要进行选择一些算法来作为基础算法库，在这里选择了两种算法作为基础算法，首先是IVFFlat算法，是粗量化的方法，这种方法优势，实现很简单，性能、准确率能达到一定的要求，在性能要求不高的情况下，这种方法是很适合使用的。
另外一种方法，另外一种算法是HNSW,多层图的算法,这种算法适用于大部分工业界的场景,对性能和准确率有一定要求,同时对于存储量要求并不是特别严格，这两种算法都实现在了PASE的基础库中。
IVFFlat索引设计，如上图所示是索引的算法的原理图，根据原理，把Page进分进行了分类，分为三种类的Page，
首先是Meta Page，负责存储两种Page的入口，查询的入口以及一些Page项，在MetaPage这种存储。
第二类是中心点Page，中心点Page是用于存储中心点数据的，要对全局向量进行聚类，例如这张图得到两个中心点，多的话可能会有更多的中心点，这些中心点存储在中心点Page中，一个接着一个去存，当一个页面放不下的时候，会通过PageTaylor这个结构来存储下一个页面的起始地址，将这些Page连成一个Pagelist，这种方式来存储一个中心点Page链表。
第三种类是DataPage，用于存储原始向量数据。
如图所示，分为两个类，这两个聚类数据存储是存储在两个数据链条，存储结构其实和中心点的存储结构类似，中心点存储了它对应的数据链条的起始地址，查询查询的时候，首先把query向量和中心点向量依次进行比较。
查到最近的中心点，通过中心点Tuple结构，定位到datalist的入口地址，从入口地址依次编例它的dataPage去进行比对，查到最近的中心点，这就是IVFFlat算法的实现原理。
HNSW索引设计
HNSW图算法索引设计存储，如图所示，首先简化成4个点，每个点都有它的临界点，能想到的是需要存储连接关系和原始的数据两种数据，如图，V1对应的临界点是 V2、V3、V4这三个点， 用N来表示边关系， N1就表示V1到V2的边，通过N1来指向V2，链接起来。V1又指向了它的对应的数据的地址，通过这种方式来来进行图的连接关系和原始数据的存储。
这种存储也有一些可以优化的点。
例如为了减少跳转，直接将存储D的指针存在N中，就不需要经过一次跳转，定位到它的向量数据，通过这种方式来加速它的过程，同时去掉 V的存储，因为N直接可以存储连接关系了，不需要一个V存储点本身了,因此我们得到图中下侧数据图，这个是页面和页面关系的配置关系的存储关系的一张图，分为三种。
第一Meta page存储源数据，包括下面一些配置的入口点以及初始化的配置。
第二Data page和IVFFlat的 Data page类似，存储原始的数据。
第三Neighbor page是用来存储连接关系。
PASE自定义数据类型/迭代查询设计
有了向量检索算法的和page设计，需要设计一个比较高效的一个数据类型来表达向量，因为PG支持自定义数据类型。
因此设计了一个数据类型来支持向量检索，如图中所示SQL所表示的含义是查询到距离四维向量最近的10个向量，通过这个方式来表示向量，数据类型定义了几个段落，图中还有两个段落，这两个段落是配置项，通过配置项来控制索引检索的行为，是自定义数据类型。
另外一个设计中需要注意的是组合查询的场景，如图中所示事例，查询距离向量最近的同时又满足 city一个条件的记录，同时要返回10条记录，向量索引查询出来的数量其实并不能保证数量，因此设计了一种迭代查询的一个方式，如图中所示。
seek next top K by scan功能是查询下边最近邻的一个迭代的接口，含义就是每次查询下面最近的最近邻，和其他条件进行过滤，过滤之后不符合返回数量，在进行下一次seek去查询，经过不断的迭代查询，最终一定会满足查询数量要求，是其中的一个特色功能。
PG自定义向量索引指南
在page的插库上支持新的相应检索算法有三个步骤。
四、PASE实践/ 课后练习
示例要求，使用两种索引，实现从5万个512维的向量中找到和某个向量最相似的向量，如图所示
1、创建一个表，用这种方式来生成一个表，行数是5万个，第一维度是从1~5万出现逐渐递增的这样一个数字，来构造一个向量。
2、创建IVFFlat索引，创建索引的含义过程参数可以参考官方的文档。对于此示例的含义是采用内部聚类的方式，不需要提供中心点的定义，只需要用数据，天然的聚类的方式来聚类，维度是512维。索引构建的示例图，索引构建过程中印出来构建的数量以及构建的各部分的时间，
3、在此之下构建一个 hnsw索引，它的参数它的构建类型是和IVFFlat索引不一样，参数也有不同。
查询和IVFFlat是类似的，只是索引操作符有区别，通过这个操作符我们来定位到它是哪种索引，索引构建过程会打出一些第8个信息，通过查询结果可以看到，两个索引算法它的查询结果是有一些区别的，顺序上会有一些区别，原因在于索引实现上会有一些区别，导致结果会有一些区别。
真实场景中的数据可能相似度差距并没有这么明显，导致两种算法的查询结果会有一些区别，精度上也会有一些区别。
