开发者学堂课程【PostgreSQL 实战进阶：高维向量检索的设计与实践（三）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/112/detail/1908
高维向量检索的设计与实践（三）
内容介绍：
一、背景介绍
二、向量检索算法/PG 自定义索引
三、PASE 设计与实现
四、PASE 使用实践
三、PASE 设计与实现
有了这样这样的一个基础之后，基于这两个基础，设计了 PG 的向量检索插件，取名为 PASE，接下来介绍设计理念和一些方法。
向量检索算法它包含很多种类的方法，需要进行一些算法的选择，来做基础的算法库。选择了两种算法作为我们的基础算法，首先就是IVFFlat这种算法，就是粗量化的方法，这种方法的优势上也提到了，他其实实现很简单，同时它的性能和它的这个准确率能达到一定的要求，在性能要求不高的情况下，这种方法是很适合使用的。
另外一种算法是 HNW 这种多层图的算法，这种方法其实适用于大部分的这种工业的场景，对性能和准确率有一定要求，同时，对于存储的存储量要求并不是特别严格。那这两种方法，都实现在Faiss配置的基础库中，首先来看 IVFFlat 的索引设计。这张图是它的算法索引的原理图。那根据它的原理，把page进行分进行一个分类，分为三种类的这个 page，
首先是 Meta page 是下面即将提到的两种 page 的入口，就是查询的入口，以及一些配置项在 Meta page 存储，
第二类是中心点 page 配置，适用于本土中心点数据，因为我要对这个全局向量进行聚类得到两个中心点，再多可能会有更多的中心点。中心点就是在中心点配置中一个接着一个去存，当一个页面放不下的时候，会通过一个结构来存储下一个页面的起始地址，将这些配置连成一个 page 例子，那这种方式来存储一个中心点 page 链表。
第三种是 Data page,是用于存储原始的这个向量数据的。比如这两个聚类的它的数据存储在 Data page 配置例子中。就是两个数据链条，这个结构的存储结构与中心点的存储结构是类似的，中心点这个 Tuple 的存储了它对应的数据链条的这个具体地址，我们在查询的时候，首先把向量和中心点的向量依次进行比较，查到最近的这个中心点，然后通过这个中心点突破结构定位到它的 Data page 的入口点，从这个入口地址依次遍历它的 Data page 去进行比对，查到最近的 topic 中心点，这个是IVFFlat 这个算法的实现原理。
接下来看 HNSW 这种图的这个设计。图算法怎么进行这个设计来进行存储的。首先简化一下，将图简化成四个点，每个点都有他的邻接点，首先我们能想到的就是需要存储连接关系和原始的数据，整理成这张图，v1对应的邻接点是 V2、V3 、V4这三个点，用N来表示这个边关系，这个 N1就表示 V1到 V2之间的这条边。用N1指向 V2这样连接起来，然后 V1就指向了他对应的这个数据的地址，通过这种方式来进行这个图的邻接关系和原始数据的存储，但是这种存储有一些可以优化的点。
比如为了减少跳转，直接将存储地的指针存在N中，这样就不需要经过一个跳转来定位到它的向量数据，通过这种方式来加速这个查找过程，同时去掉 v 的存储，因为N直接就可以连接关系存储，不需要 V。这个是页面和页面存储关系的一张图，也分为三种，三种配置，
首先是 Meta page，其实也是一些原始数据，包括下面一些 page 的这个入口点，以及初始化 page，第二个是 Data page，和这个 IVFFlat 的 Data page 是类似，存储原始的数据 在 Data page，然后下一个是 Neighbor page。用来存储这个连接关系，比如图中的这个映射关系就是这样，通过在邻接关系之间的跳转，以及这个N Tuble 中，也存储了数据的这个地址，通过不断的查找邻近关系和数据向量的一个距离的比较，来快速的查找到他的一个邻近点，那这个是图算法的存储设计。
那有了这个向量检索算法和 page 这个设计，我们需要设计一个比较高效的一个数据类型来表达向量。因为 PG 支持自定义数据类型，因此设计了一个数据类型来支持向量检索。
SELECT id FROM vectors_table_with_hnsw_idx
ORDER BY
Vector <op> ‘0.0117,0.0115,0.0087,0.01;80;0’::pase ASC LIMIT 10;
//表示的含义就是查询到距离这个四维向量最近的十个向量。通过这个方式来表示向量，这个数据类型，定义了几个段落，比如图中这两个段,其实是通过这个配置项来控制这个索引检索的行为，这是自定义数据类型。
SELECT id WHERE city=’xxx’
FROM vector_table
ORDER BY
Features <op>‘0.0117,0.0115,0.0087,0.01’::pase ASC LIMIT 10;
//另外一个设计中需要注意的一个点,是一种比较常见的一种场景就是组合查询。比如图中这个示例,我们查询距离这个向量最近的,同时又满足ct这个记录，同时要满要返回十条记录，因为这个向量索引查询出来的这个数量其实并不是能保证足够多，经过这个ct这个条件过滤之后,不一定能保证就是查询的条件保证十个，因此设计了一种迭代查询的一个方式，如图中所示，那其实这个就是上述的几种算法我们实现了一个 seek next top K by scan 功能就是查询下K个最近邻的一个迭代的一个接口,这个含义就是说我每次查询K个最近邻，然后和其他条件进行过滤，过滤之后不符合这个返回数量之后，我们再进行下一步去查询，这种不断的迭代查询的这种，一定会满足这个查询数量要求，这个是其中的一个特色功能。
上面是 page 的基本的这个设计原理。如果未来肯定还会有其他的这个 ANN 算法的引入，提供了基本的两个算法，未来新的这个算法的介入，也考虑了一些扩展性。如何在配置的这个插件故障支持新的这个相应的方法，总结下来三个步骤，
第一步，其实是和上面两种算法的一个设计其实是很相似的，就是根据算法原理设计它的配置结构和配置组织关系，考虑第二步，就是它的相似度的计算公式是什么，定义了相似度的计算函数之后，需要设计这个索引实现哪些接口，通过这些接口实现了来支持索引的功能。第二步，自定义索引，自定义这个相似度计算公式，总结了一下，进行一些抽象。目前 page 支持的一种相似度计算公式，包括比较常用的一些方法，对于这几个不支持的这个算法之外这个公式，我们提供给用户开放的自定义的接口，这个接口其实是实现了是使用的是很简单的，抽象两个指针，在内部对两个指针进行操作即可，这是自定义的这个方法。
四、PASE 实践/课后练习：
第四部分做一个小的实践，就是如何使用配置向量检索，首先看这个示例的要求。使用两种索引实现，从5万个512维向量中找到和某个向量最相似的向量，如何来实现？首先创建一个表，然后行数5万个，维度是从1到5万逐渐递增，这种方式来构造一个向量。创建IVFFlat的主页，如图所示，这个参数可以参考这个有官方文档。
（clustering_type = 1,distance_type = 0,dimension =512,clustering_parrams =”10,100”);
//对这个 case，含义是采用内部剧烈的方式，就是我们不需要提供中心点的定义，只需要用数据天然的这种聚类的方式来聚类，然后包含IVFFlat的索引参数，他的维度是512。通过这种方式建立索引。
下面是通过自定义数据类型的方式进行索引查询，这是查询的实例。然后下面是作业构建的这个实例图。构建过程中会打印出来构建的数量以及构建的各部分的时间。这个是注意查询的结果。
接下来构建一个 HAWN 的参数，它的这个构建类型与 IVFFlat 的不一样，同时它的参数也不同。维度是512，查询其实是和 IVFFlat 是类似的，只是它的索引操作符有区别，通过这个操作定位到他是哪种作业。然后他的索引构建过程也会打出一些其他的信息。查询结果，通过这个结果可以看到，两个算法的查询结果还是有些区别的，比如这个数据会有区别的原因在于索引实现有一些区别，所以实际上会导致的结果有些区别，当然这个配置是比较简单的，这个产品中的这个数据，可能这个相似度差距并没有那么明显，导致了两种算法的这个查询结果会有些区别，精度上有区别。
