分享人：digoal
正文：
今天给大家介绍多维向量的搜索。多维向量可以理解为浮点数的数组向量，它在每一个数组位即对应的位置上叫做维度。
多维向量这种数据类型通常被用来存储什么呢？比如精准的实时圈选中相似人群的扩选用的就是多维向量，存的就是每一个人在每一个维度上面的一个浮点数的属性，所以这是用来做特征值的相似圈选的一类场景。
实际上还有一类场景，比如图像识别的场景，我们知道图像也是可以提取图像在多个维度上面特征值的。举个例子，一个1024×1024的图片，每一个像素根据它的色彩、明暗程度、灰阶等各种维度的属性提取出一个值，那我们就可以存成1024×1024的特征矩阵，那么这个矩阵当然就是非常的大。每一个图片存每一个像素，向量是特别大的。所以，我们就有了图像特征值转换这样一些手段，比如可以把它的缩略图提取出来，针对缩略图的每个像素再去计算它的特征值。举个例子，我们可以把1024×1024切成16×16，每一个小方块代表的是原来1024×1024图片的一个位置，然后提取每一小块的特征值，就会变成16×16=2 56个维度这样一个特征值。所以图像识别里面我们通常会用的手段，就是首先把一个大的图片的特征值提取出来，而这个特征值的向量维度通常是512维或者256维，然后基于这个维度再去做图片的相似的检索，这个相似其实指的还是向量相似，多维向量相似。
所以我们今天会围绕着数据库里面有哪些向量类型？不同的向量类型分别支持的向量距离的算法有哪些？
具体分为以下四个方面：
l CUBE
l IMGSMLR
l PASE
l 应用场景介绍
一、CUBE
1）CUBE介绍
首先介绍内置向量cube。
它是pg它内置的一个向量类型，我们可以来看下实例来，比如这个这个向量类型cube
首先我们要create这个向量类型的插件cube。 cube里面一个cube的类型可以存一个n维的点类型，当然也存可以存一个cube，比如你存的是平面类型的二维，也可以存一个范围。二维其实就是一个正方形或者长方形box，在三维就是一个立方体box即 xyz。x1、x2、x3；y1、y2、y3分别代表的是什么？x1代表的是x轴上面的一个对角线的左下角，以平面下我们存的一个方块为例， x1对应的是这个点坐标的x轴坐标， y1对应的是这个点在x轴上面的坐标，x2对应的是这个点在y轴上面的坐标， y2对应的是这个点在y轴上面的坐标，这就是说用两个在平面上面的点来代表一个box，一个方块儿。如果是n维，实际上每一个维度上面的mini值跟每一个维度上面的max值形成了对角的两个属性值， 然后去表示这是一个cube，这是一个空间。而n维点: (x1,x2,...,xn)代表的是点。n维cube(采用2个对角point表示): [(x1,...,xn),(y1,...,yn)]代表的是一个立体的空间。
向量距离可以通过这几个符号<-><#><=>计算，a和b都是cube类型。
l <->是算欧式距离。
l <#>是taxicab距离。
l <=>是一种类似于国际象棋的棋盘距离。
2）欧式距离
欧式距离实际上算的是两个点在多维的空间里面的直线距离或者叫最短距离。如一个平面， p跟q的距离实际上就是在这个平面上的直线距离。
3）Taxicab distance 
Taxicab distance算的是什么？如图，把每一个维度都用一个轴表示，那么p跟q之间的距离实际上就是它的直线距离，但是不能做点的跳跃，必须要划线，能够有线连通这种距离，所以图上不管是红色、黄色，还是蓝色，它的距离都是12，这也是它的直线最短距离。绿线其实就是在这个图上的欧式距离，即最短距离，直线距离。
4）Chebyshew distance
棋盘距离指的是比如我们一个二维平面，要皇冠的点为例，它到达我们指定的这格子的距。比如到达这个格子（红色方框）距离就是5，为什么呢？把皇冠包住的框的位置，这些距离都是1；再紧接周围都是2，以此类推最终距离就是5，这就是棋盘距离。
4）例子
这三种距离在cube向量类型里面，它的距离计算方法包括排序都是用<-><#><=>几个符号来完成的。我们可以来看个例子：
1、创建插件
2、创建测试表create table tt (id int , c1 cube)，id是in类型，c1是cube类型。
3、创建索引create index idx_tt_1 on tt using gist(c1)，用的是空间索引gist。4、创建一个函数可以随机生成cube，如下图：
这是一个16维的cube类型，每一个维度上都是一个随机值，每一个维度的取值范围的是1~1万，插入了100万条。
接着我们去查询：
select * from tt order by
c1 <=> '(6671, 1730, 2177, 4208, 2613, 4877, 3942, 4402, 244, 9945, 2581, 3640, 2384, 8457, 9126, 1102)' limit 10;
执行计划用的是索引扫描，算的是欧式距离。
如果我们把这个方法换一下，比如<#>算的是直线距离，<->是欧式距离直线距离，<=>是棋盘距离，所以我们用了这样的方法去搜索离这个向量最近的距离。
我们也可以把它的值打印出来执行一下，比如直线距离是18330，如果我们算欧式距离是7189.65，棋盘距离是6009。
通过cube的多个维度来存储用户在不同维度上的属性，如16维，每一个维度上的属性取值是多少？通过指定一个cube的范围，这个维度的属性是7079~17079，范围是3124~13124等，每一个维度都给一个范围，然后把人群取出来，我们用的就是这个方法。cube包含c1的值是哪些，也可以取出来。
刚刚这个查询就用到了索引扫描，差不多花了9个毫秒的时间就把它包含的每一个维度都落在这个空间内的数据给找出了。
我们还可以应用在什么场景呢？比如我们的数据结构是存储了若干个维度的属性的值，要求你去查指定某一些维度，做一些范围查询也可以用cube这个类型来支撑。
那么同样我们也可以用它来做相似人群的扩选，或者相似人群指定一个立方体去圈选落在这个立方体内的人群，这些都是可以通过cube来做。
值得一提的是，1、cube最多能存100个维度，如果超过100个维度，编译的时候就要指定；2、cube的每一个维度是用浮点double float来表示的，所以它的空间占用是每一个维度8个字节。
二、IMGSMLR
1）IMGSMLR介绍
紧接着我们来介绍专门针对图像识别的一个插件IMGSMLR，它是一个开源的插件，在rdspg10里面有支持，后面在rdspg11、12里，我们会支持另外一个插件pase，也是用来做图像识别，并且比IMGSMLR好。
IMGSMLR的内部，每一个维度是用float4即4字节的浮点数——单晶浮点数。cube用的是双晶浮点数表示每个维度的属性。
IMGSMLR内置了图像特征值转换的接口函数。比如把一个图片的二进制作为一个输入值传给这个函数，那么这个函数就能返回一个IMGSMLR16维的图像特征值。
2）接口函数
我们简单介绍一下它的一些接口函数。
它的用法也很简单：
1、创建create extension imgsmlr。
2、创建一个table，这个table有主键、id、图像的原始值pic。这个图像的原始值存的是二进制的原始值bytea字节流。
3、另外创建一个表，存的是图像的特征值create table t_img_sig。这个特征值有两种类型：全特征值pattern和简略特征值signature。signature实际上就是16维的图像向量， pattern是一个128维的图像向量。
为什么会出现16维和128维？1、维度越高，搜索的效率会越低，同时占用的索引空间会越大，所以我们通常建议在16维的特征值上创建向量索引。2、我们在16维的值上做检索之后，比如过滤了100条记录，在这100条记录里再去基于它的较长的128维的向量上再去算这128维向量的相似性，这样就过滤出一个更加精准的相似性。所以我们创建了tig_img_sig这样一个表，同样也包含了主键，vid，16维的特征向量，且包含了128维的特征向量。
4、create index idx_t_img_sig_1 on t_img_sig using gist(sig)，创建索引是在16维的特征向量上创建的。
5、紧接着我们就可以往这个数据表里插入原始图像insert into t_img_bytea values (.......)
6、把原始图像插入完之后通过insert into t_img_sig select id可以把pic这个字段，通过函数，比如我们插入的是png图像格式——png2pattern，那么它就会被转成png2signature，把128维转换成16维的签名或者叫图像特征签名，然后把它写入img_sig的这样的一个字段里面去
7、图像已经生成完了之后，我们怎么去搜索？比如用户上传一个照片的二进制，怎么去基于这个照片的二进制找到跟他相似的照片？我们就是order by sig。同样它也是用的欧式距离符号<->，然order by pattern2signature(png2pattern limit，如果出现limit1就表示这张图片是跟我们用户上传的图片的相似性是最高的。
同样有个例子，大家可以登录上图图网址去查看。
三、PASE
1）PASE介绍
pase插件是我们跟蚂蚁合作的一个专门用来做人脸识别的插件，相比较于cube相、IMGSMLR，在性能、存储空间、支持的索引算法上会更优。
这个插件目前支持rdspg11版本，将来会覆盖所有的主流版本，包括12版本在内。这个插件的文档，在我们的官方产品文档里面有介绍，今天主要介绍它的使用case。
它支持两种索引接口， ivfflat和hnnw。两个索引接口不一样的地方在于它的存储和搜索方法、数据组织的方法以及搜索方法不一样。内部每一个维度都是使用的float4单晶浮点数进行存储， 跟图像识别IMGSMLR是一样的，比cube减少了一倍的空间。
2)背景原理
我们来简单介绍一下背景原理。
l Ivfflat
ivfflat可以理解为归类索引，比如拿到了图像特征值之后，针对这个特征值去做聚类，比如有1000万条记录，把它聚类成为1000个类或者1万个类或者10万个类。
聚完类之后，每一个类就有一个中心点，比如这个点围绕着这个点，有这么多的其他周边的点，而围绕着红色的点周边又有一堆的点。在索引组织的时候，首先会存所有的中心点位置，比如总共有10万个中心点，那么就会存下10万个中心点，同时每一个中心点又会指向它的另外一个链表，这个链表指围绕着这个中心点有多少个点。
搜索的时候是先搜什么呢？
比如我要搜离某一个点最近的或者离我的某一个输入的多维向量最近或者最相似的10个取出来，这个时候它会到中心点里筛选出n个，基于这个中心点再去扩散，找每一个中心点再输出n个，然后nxn，再去做相似性的排序，最终把结果反馈给你，所以它是一个聚类的收敛的算法。
l Hnsw
hnsw跟ivfflat不一样的地方在于它是图的空间算法去组建出多层的图的结构.
比如我们看上图，之前说到相似用户圈选的时候，其实我们也讲到了hnsw索引，它会把数据把切成好多个层，最高层的精度是最低的，比如我们真正的点有这么多个，抽象一层之后，把关键点抽象出来之后，第一层就只剩下4个点；再抽象一次，在第二层就变成了只有2个点，也就是说它越往上会越缩略出更少的点，这样就把它的关键点逐渐的提取出来了。
所以我们在搜索时，比如要搜离这个绿色的点最近的点有哪一些时，实际上是先从最上层开始搜，随机地取一个点；然后基于这个点搜索它的相邻点里面离这个绿色点最近的点；找到了在第二层离这个绿色的点最近的点之后，再往下沉到了layer1，到layer1里面也用同样的算法，先找它的相邻点里离这个绿色的点最近的点，找到之后再搜下一层，最终就能够在最下层找到离这个绿色点最近的点。所以它是一个从缩略图开始搜，再搜比它更明细的图，然后再往下搜，一直搜到完整的图为止。
3）参数介绍
这两种索引在创建的时候是有一些参数可以指定的。
如果我们要指定ivfflat聚集索引，要聚多少个类，就是多少个中心点？当然中心点的也可以由用户以文件的形式来提供。比如我提供100个中心点，这些中心点已经人为或者机器学习算好了，这是第一种。
第二种方法是只要告诉你帮我提取多少个中心点出来，采样的方式，比如我要采样千分之十也就1%，这张表有1000万条记录也就采样1万条记录。然后基于这1万条记录我们生成1000个中心点，那么我们的参数用内部聚类class=1, clustering_params用的是10,1000，也就1000万应该是10万条，10万条里面内部再用kmeans算法生成1万个中心点，然后再基于这1万个中心点再去构建出1万个bucket。所以我们搜索时会先在这1万个中心点里面找到n个离我最近的点，然后基于这些点对应的bucket再去找离我的目标点最近的点，用的核心算法是kmeans。
hnsw在创建索引的时候，最核心的参数是base_nb_num，指的是我的这个点的邻居点有多少个。比如我们在创建索引时指定每一个点，最多有16个邻居点，当然邻居点越多，搜索精度会越高，但是搜索的速度就会越慢，通常邻居点建议是16个。另外构图时会有一些构图参数，包括ef_build、ef_search。构图的参数，我们有一些建议值可以去选择。
4）例子
这个例子是一个80维的向量，向量用的是float4来存储，再创建一个随机浮点——单晶浮点数组函数。之后我们往table里面去插入，比如每一个维度的取值范围是1~1万， 80维。然后去插入100万条，创建ivfflat索引。索引指定采样千分之一百也就是10%的数据，那么100万就会采样10万条，然后通过kmeans算法生成1001个中心点，这样索引就创建好了。
创建好了之后我们做查询，ivfflat索引来查询的时候用的是<#>来代表计算距离的算子，也支持ORDER BY 。
比如这样一个查询大概要花掉4.5个毫秒的时间，很明显同样的记录数比cube的效率会好很多。
实际上pase相比cube、IMGSMLR，它支持的维度更多，可以支持到512个维度，可以做要求特别精准图像识别，比如人脸识别。同样它的效率比IMGSMLR都要高，存储的空间占用也比较小的，因为它用的是float4去存储每一个维度的特征值。
