高维向量检索的设计与实践（二）|学习笔记

开发者学堂课程【PostgreSQL 实战进阶：高维向量检索的设计与实践（二）】学习笔记，与课程紧密联系，让用户快速学习知识。

课程地址：https://developer.aliyun.com/learning/course/112/detail/1908

高维向量检索的设计与实践（二）

内容介绍：

一、背景介绍

二、向量检索算法/PG 自定义索引

三、PASE 设计与实现

四、PASE 使用实践

二、向量检索算法/PG 自定义索引：

1.向量检索常用算法

向量检索最简单的一种实现方法，就是逐一比对的方式，也简称为暴力搜索的方式。优点就是它的准确率足够高，逐一比对总能找到最相似的向量，像那种方式的准确率是100%，但是它的缺点是查询耗时很高，这种方式是不能应用于工业界的场景中的，因此业界也研究出来就是很多的这个向量算法，向量检索算法也简称为ANN检索算法，就是近似对近邻的方式。通过这个简称也能发现，一般的实现方式都是运用这个精度来换取来换取性能的大幅提升。因此一个算法好坏的就是来衡量这个转化的效率是否足够高，能用很小的精度损失来换取大幅的竞争，那这个就是一个好的算法。那目前常用的这个算法，经过总结基本可以分为这样四大类，基于树的，基于 Hash 的，基于量化的，还有基于图的。

这四个方式各有优缺点，也各有不同的应用场景，树它的特点是对空间进行逐级的切分，直到树的叶子节点只覆盖空间的一个很小的部分，通过这个方式来大幅的提升这个检索的性能。 

Hash 是一个典型的这个算法，是局部敏感哈希算法，他们的共同特征呢，是通过超平面或者一个曲面将空间进行直接的切分，对切分后的这个空间进行二进制的编码，查询只在部分空间中进行，因此来排除掉大部分就是不相关的一些空间，来达到加速的目的。

第三个量化的方式它的思想其实很简单，就是对象进行聚类等等来进行量化。将这个相邻的向量使用中心点来代替，查询只在这些中心点中进行，排除掉大部分不相关的这些向量类图，从而达到讲述这样一个目的，

最后一个算法就是基于图的算法，它的核心思想都是一个就是近邻近邻也可能是近邻，通过离线构建一张临近关系图，查询到在途中迭代的去查找，不断的去逼近最近的这个近邻。 

2.典型算法讲解

那这四种方式，刚才提到了个优缺点，在使用场景，根据各个业务的这个不同的要求来进行选举，下面会针对一些典型的一些算法，来对他们的算法原理，进行一个详细的一个描述。

首先第一个是粗量化的，简称叫 IVFFlat，就是量化的一种方式。他的算法原理，其实很简单，从图中可以看到这些向量的天然就有聚类的属性，比如把这个空间分成两个类，如图所示，它是上下两个类，每个类它存在一个中心点，比如图中的红点，用红点来表示这个类聚的中心点，这是离线的处理过程，在线查询的时候，根据 query 和两个中心点进行比较，查到它距离哪个中心点最近，只保留这个中心点所在的类图，丢弃其他不相关的类图，比如图中保留上面的这个类图，查询会在这个类中在进行。这是他的算法原理，那这种算法的优缺点其实很明显，优点这个算法足够简单，只需要聚类即可，但它的缺点也很明显，就是它的精度，其实可以足够高，查询的中心点我可以保留很多，比如图中可以留两个中心点，相当于暴力简短，但精度换取性能效率并不高。它适用的场景就是适用于一些就是精度要求可能会很高，但是对查询要求，查询耗时的要求不高的一些场景，一般在百毫秒级的这些要求。

下一个就是 IMI 这样一个算法，它的这个产生的背景，就是解决刚才提到的粗量化的一些问题，比如这里提到的两个背景知识，首先对于粗量化它的候选集质量效果天花板，比如说图中所示通过粗量化，它只保留了这两类图，这个类图它最终效果好坏，决定于这两个类中的点是否足够的相近，另一个它的数量巨大，如图这两个类图，它的点数是很多的，在查询的过程中，会比较好使，这是 IMI 产生的一个背景，我们来看他怎么来解决这样的一个问题。我以两维的为例，x 轴和 y 轴，它的解决方案思想其实很简单的，就是将向量进行两维度的切分，在每个维度上分别进行聚类，比如 X 轴和 Y 轴两个空间，分别进行聚类，它的查询效率，性能与粗量化类似的，它的好处直接把聚类分得更细，从图中这个事例就可以看到，查询的范围都是集中在这个点的周围的这些点上。它的优点和 IVFFlat 类似，它可以达到很高的精度。同时，它的这个查询性能耗时会比粗量化更低。缺点是它的实现要比 IVFFlat 更复杂，图中可以看到会增加这个分段阶段聚类这样一个过程，同时，它的耗时会比IVFFlat 高，但是高的并不是很明显，那这种场景适合 IVFFlat 之类的。对准确率有一定要求，同时对产品耗时要求并不高的这样一个场景。

那以上都是基于量化的方式来实现的这样的两种算法，考虑另外的一种实现方案，就是基于近邻图的这种方式。它的方法论就是近邻的近邻也可能是近邻，如何来实现这个查找过程？首先先将这个离线的这些向量进行近邻图的构造，比如图中实例，将它做成一张邻接图，同时会随机的采用一个入口点，绿色的点是查询点，查询是从入口点进入，查询它和它的邻近点之间哪一个距离 query 更近，比如有两个点都离他更近，那我就保留其中一个点。然后，从这个点再找它和它的邻近点之间哪一个距离 query 更近，依次迭代，最终找到最近的这个向量，这种方式能够比较快速的，就是经过比较少量的向量距离来定位到这个最近邻。

但是这种方式连接图的方式，有一些可以优化的点，比如这张图中，如果点数非常多，这个入口点距离最近邻距离比较远的情况下，可能会经过多次的调整才能查到最近邻，如何来优化这个问题。

一种方法是采用跳表的思想，就是采用多层邻近图的方式，那上层图是下层图的缩略图，可以想象一个场景，就是从一个地方到另一个地方，首先要走的是高速公路，然后会走城市之间的道路，然后再走乡镇之间的这种道路，通过这种方式，能快速的定位到它可能出现的区域，从而达到加速查找的这个目的。

这种多层图的思想就是 HNSW 这种图上的核心思想，这种算法的优点就是查询速度非常高，同时准确率就有一定的保障，但是它的缺点就是这些邻接点的这个存储会浪费一定的内存磁盘，会带来空间的这种伤感，可以适用于大部分的这种场景，对于产品耗时有一定要求，同时这个准确率有要求的这个场景，另外对于存储耗时不敏感的场景都可以采用近邻图的算法。

有了这些图算法之后，其实已经出现了很多的这个 ANN 算法库，比较有名的是faiss，第一个就是 Facebook 开源向量检索库，它的优势是 A NN 算法还是很齐全的，目前业界中的很多研究方向都是基于faiss开的一些库来进行优化，这是它的优势。但是有些问题就是他的这个代码工程质量其实是很一般的，比较适用于这些学术界的研究，其实工业界的使用并不是特别友好。

另外一个是 SPTAG，这个算法，是微软的开源向量检索库，它的优势其实是有一些算法的创新，它是将树算法和这个图算法进行了结合，实现了一种比较高效的一种算盘。但是它支持的 ANN 算法选择其实是比较少的，只有几种优化的算法，同时他的那个测试的这个性能，其实不如 Faiss。

另外一个是proxima，这个是阿里的达摩院提供的一个向量检索库，目前阿里集团内部的这个 向量检索实现其实都是大部分都是基于 proxima 来实现的，他的这个代码质量是很好的，同时还支持 ANN 算法选择，另外，它的性能是足够高的，经过对比实现是优于 faiss。另外，它的缺点是他并不开源，就是集团外其实用不了，

另外一个是 vearch，这个是京东的开源向量检索库，好处是它是完整的一个检索引擎，是一个分布式的一个服务，是一整套的一个服务实现，但是，他的其他的搜索能力其实是比较弱，他的分布式能力是比较弱的，这个是现有的一些开源的典型的这个 ANN 算法库的这个列表。

3.PG 自定义索引方法介绍

有了这些 ANN 算法和一些实现的库之后，要考虑如何来实现一个向量检索引擎，当时我们在做在做这些业务的时候，也做了进行了一般的这个基础选型。根据这个技术选型的经验，可以去评估自己的场景是否适用，是否和我们相匹配一下，我们的这个技术选型，我们的候选集合，选择的是很多的，大概可以分为这样几类：

比如第一类，是搜索引擎类的，开源的引擎和我们内部的资源做引擎，然后有这个数据分析的库，比如 AnalyticDB，另外一个是 explorer，另外一个大类，是数据库类的，比如 OceanBase 和 mysql,我们的业务场景，是需要我们有轻量级的这种要求，精简之后剩下的其实并不多的,只有 Elasticsearch、mysql、PostgreSql 这三款引擎，经过这个扩展能力的考核之后，其实剩下的只有 PostgreSql 这样一个数据库，mysql其实它的索引扩展能力没有这么丰富。另外 Elasticsearch 它的扩展对索引层面是复杂的，

总结一下 PostgreSql 的优势，首先它是轻量级，第二个是它的性能比较优越，然后它的作战能力比较强大，稳定性就足够高，同时，它的生态是很丰富的，有很多的这个开源的这献在里面。然后采用一些业务的使用者，并不需要数据的迁移，很多的业务数据都存在数据库中的，PostgreSql 是一个选择，在 PostgreSql 上直接实现检索的这样一个功能，就不需要实现这个数据的迁移，这是很重要的一点。另外是支持组合查询的，我们可以结合其他的这个条件查询来进行这个组合查询。同时PostgreSql 还支持这个分布式的这种部署，通过一些第三方插件的这个支持来实现这个分布式的部署。经过这些考量，最终选择 PostgreSql 做为我们将检索引擎的这样一个技术引擎。

确定了选用的 PostgreSql 作为引擎之后，对这个向量检索算法，对已有的向量检索插件进行一番调研，经过总结之后，主要的插件是三个，第一个是开源的，因为是imdsmlr 这样一个插件去实现，它是基于 PostgreSql 的内置的 Gist 来实现的，它的特点是提供了图像特征的处理方法，但是他的限制也是很明显的，它只能用于这个16维向量检索场景，它并不能适用于大规模的工业应用。

第二个 cube 索 引，是 PostgreSql 自带的一个索引类型，也是基于 Gist 索引来出现的。它的特点就是支持向量的聚类、向量的距离计算等等，他的维度有一定提升和支持100维度一下，但是经过我们实测，性能并不能达到要求，同时，其实100维度对于未来深度学习越来越广泛之后，这个维度是捉襟见肘的。

最后一个是 freedy,它是一个爱好者开源的一个向量检索的插件库，实现是基于 SQL function 这个方式来实现，它的优点是支持比较多的这个 ANN 算法，但是它的问题，是基于 SQL function这种思考方式实现的这种性能，其实并不能达到这个工业界使用的这个要求。那基于以上这些调研的情况，得出一个结论，就是如果PostgreSql 想做引擎，需要我们自研插件这样一个现状。

有了这样一个背景和目标之后，对 PostgreSql 的这个自定义插件的能力，做了一番的考量，PostgreSql 其实本身就是非常丰富的自定义索引的这个能力，总结了这样两个基础。第一个基础，是 PostgreSql 的基本的这个存储单元配置结构，它是完全可以自定义的，这张图就是配置基表的这个页面的结构，看一下它的组成部分，

首先大概分为三个组成部分，第一部分是 PageHeaderDats 部分，最后结尾是special space 部分，中间这个部分，Tuple 是记录的存储部分，多个 Tuple 就存储在一个页面内，同时在页面这个配置的起始部分，会有像这些记录的指针，通过指针来进行这个寻址。这个配置的默认结构是存储8K，当记录数小于8K的时候，就可以推出多个记录在一张 Page 中。

那对于索引所采用的这个配置结构和这个结构是完全一样的，区别在于中间的一部分是不限制的，这个是可以完全自由使用的空间，总结为右边这张图，可以从图中可以看到，DataTupleN 是最小的数据存储单元的,存储结构完全可以自定义，这个时候 PostgreSql 的提供自定义索引的这样一个基础，

第二个基础主要就是 PostgreSql 这个支持了非常丰富的索引定义的这个接口 API。整个这个 PostgreSql 的结构可以分为这样几个层次，最下面一层是数据的存储，在往上一层是索引的存储，在往上一层，是索引的接口层，再往上通过一个结构体来控制这个索引的 API 调用。

如下图是 PG 索引 API 的定义，这个定义中可以看到它支持非常丰富的索引操作的接口，比如索引的 build 和单个 insert，以及标记删除，还有查询初始化，返回以及它的查询相关的这个接口。你可以看到它的索引接口还是非常丰富。