20190815_01.md

阿里云PostgreSQL 向量搜索、相似搜索、图像搜索 插件 palaemon - ivfflat , hnsw , nsg , ssg

作者

digoal

日期

2019-08-15

标签

PostgreSQL , 向量计算 , cube , ivfflat , hnsw , nsg , ssg , 向量搜索 , 图像搜索

---

背景

使用向量检索的业务场景越来越多，如人脸识别、图像识别、视频音频检索、商品搜索推荐等场景。

向量搜索服务在云服务，尤其在私有云上部署，主要面临如下挑战：

• 机器少，很多私有云甚至只有1台机器
• 机器资源配置一般不会太高，尤其是内存
• 部署要求尽量简单，底层依赖少

搜索引擎方案大都依赖环境较多，部署较重，不便于应对以上场景。基于以上背景，我们开展了sparrow项目，提供包括向量、全文、空间等检索能力的轻量级搜索服务。

社区对比：

• cube 是PG的多维插件，支持最多100纬的向量距离搜索，支持索引。

《PostgreSQL 多维、图像 欧式距离、向量距离、向量相似 查询优化 - cube,imgsmlr - 压缩、分段、异步并行》

《PostgreSQL 多维空间几何对象 相交、包含 高效率检索实践 - cube》

《PostgreSQL 相似人群圈选，人群扩选，向量相似 使用实践 - cube》

《PostgreSQL 相似搜索插件介绍大汇总 (cube,rum,pg_trgm,smlar,imgsmlr,pg_similarity) (rum,gin,gist)》

《PostgreSQL cube 插件 - 多维空间对象》

• imgsmlr 是PG社区开源的图像搜索插件，只支持16纬。

《PostgreSQL 11 相似图像搜索插件 imgsmlr 性能测试与优化 3 - citus 8机128shard (4亿图像)》

《PostgreSQL 11 相似图像搜索插件 imgsmlr 性能测试与优化 2 - 单机分区表 (dblink 异步调用并行) (4亿图像)》

《PostgreSQL 11 相似图像搜索插件 imgsmlr 性能测试与优化 1 - 单机单表 (4亿图像)》

《PostgreSQL 相似搜索插件介绍大汇总 (cube,rum,pg_trgm,smlar,imgsmlr,pg_similarity) (rum,gin,gist)》

我们需要更加专业的向量搜索插件。

palaemon：蚂蚁搜索团队打造的pg索引内核扩展，目前支持hnsw、ivfflat向量检索算法，支持超过1000个纬度。框架支持更多的搜索算法，后面还会引入更多。这个插件会整合到阿里云的rds PostgreSQL以及POLARDB for PostgreSQL.

用法

CREATE EXTENSION palaemon;    
    
-- with constructor    
SELECT  ARRAY[2, 1, 1]::float4[]     <?>    plm(ARRAY[3, 1, 1]::float4[])          AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]     <?>    plm(ARRAY[3, 1, 1]::float4[], 82)      AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]     <?>    plm(ARRAY[3, 1, 1]::float4[], 82, 1)   AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]     <?>    plm(ARRAY[3, 1, 1]::float4[], 82, 0)   AS distance;    
    
-- with io function    
SELECT  ARRAY[2, 1, 1]::float4[]    <?>    '3,1,1'::plm       AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]    <?>    '3,1,1:82'::plm    AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]    <?>    '3,1,1:82:1'::plm  AS distance;    
SELECT  ARRAY[2, 1, 1]::float4[]    <?>    '3,1,1:82:0'::plm  AS distance;    

hnsw 算法测试

-- create a table and insert test data.    
CREATE TABLE vectors_hnsw_test (    
  id serial,    
  vector float4[]    
);    
    
create or replace function gen_float4_arr(int) returns float4[] as $$    
  select array_agg((random()*100)::float4) from generate_series(1,$1);    
$$ language sql strict;    
    
create or replace function gen_plm(int) returns text as $$    
  select string_agg((random()*100)::float4::text, ',') from generate_series(1,$1);    
$$ language sql strict;    
    
INSERT INTO vectors_hnsw_test SELECT id, gen_float4_arr(512) FROM generate_series(1, 5000000) id;    
    
    
-- create index    
CREATE INDEX v_hnsw_idx_t ON vectors_hnsw_test    
USING    
  palaemon_hnsw(vector)    
WITH    
  (dim = 512, base_nb_num = 16, ef_build = 40, ef_search = 200, base64_encoded = 0);    
  
-- building index info
INFO:  final build blkid is 16667
INFO:  build options, dim=[512], base_nb_num=[16], ef_build=[40], ef_search=[200], base64_encoded=[0]
INFO:  build count: 1000, total use time: [1.749716], distance fun calls 864430
INFO:  build count: 2000, total use time: [5.444488], distance fun calls 3405822
INFO:  build count: 3000, total use time: [10.184407], distance fun calls 6788621
..........
    
-- test index scan in order by sql    
SET enable_seqscan=off;    
SET enable_indexscan=on;    
    
do language plpgsql $$    
declare    
  vid int;    
  vdist real;    
  v_vector text := gen_plm(512) ;    
begin    
  for vid,vdist in     
    execute format('select id,vector <?> %L::plm as dist from vectors_hnsw_test order by vector <?> %L::plm limit 10', v_vector , v_vector)      
  loop    
    raise notice 'id:% , dist:%', vid, vdist;    
  end loop;    
end;    
$$;    

ivfflat 算法测试

-- create a table and insert test data.    
CREATE TABLE vectors_ivfflat_test (    
  id serial,    
  vector float4[]    
);    
    
INSERT INTO vectors_ivfflat_test SELECT id, gen_float4_arr(512) FROM generate_series(1, 5000000) id;    
    
CREATE INDEX v_ivfflat_idx ON vectors_ivfflat_test    
USING    
  palaemon_ivfflat(vector)    
WITH    
  (clustering_type = 1, distance_type = 0, dimension = 512, clustering_params = "10,100");    

-- index building info
INFO:  parse clustering parameters succeed, clustering_sample_ratio[10], k[100]
INFO:  begin inner kmeans clustering
INFO:  begin, ivfflat index building
INFO:  ivfflat index build done, build tuple number[5000000], totalTimeCost[932.885278s], centroidBuildTimeCost[893.368568s], indexBuildTimeCost[39.516710s]
CREATE INDEX
    
-- test index scan in order by sql    
SET enable_seqscan=off;    
SET enable_indexscan=on;    
    
do language plpgsql $$    
declare    
  vid int;    
  vdist real;    
  v_vector text := gen_plm(512) ;    
begin    
  for vid,vdist in     
    execute format('select id,vector <?> %L::plm as dist from vectors_ivfflat_test order by vector <?> %L::plm limit 10', v_vector , v_vector)      
  loop    
    raise notice 'id:% , dist:%', vid, vdist;    
  end loop;    
end;    
$$;    

其他算法

https://github.com/ZJULearning/nsg

https://github.com/ZJULearning/SSG

PostgreSQL 许愿链接

您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.

PolarDB 学习图谱: 训练营、培训认证、在线互动实验、解决方案、生态合作、写心得拿奖品

购买PolarDB云服务折扣活动进行中, 55元起

About 德哥