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

蔚落 2022-02-12 23:05 345阅读 0赞

### 标签 ###

PostgreSQL , cube , rum , pg\_trgm , smlar , imgsmlr , pg\_similarity , gin , gist , 倒排 , 相似 , 向量 , 特征 , 图像 , 文本 , 字符串 , 全文检索

--------------------

## 背景 ##

在搜索业务场景中，相似搜索是一个非常常见的需求。

PostgreSQL有很多插件、索引可以支持海量数据的高效率搜索。

以下是一些案例：

[《Greenplum 轨迹相似(伴随分析)》][Greenplum]

[《PostgreSQL 相似文本检索与去重 - (银屑病怎么治？银屑病怎么治疗？银屑病怎么治疗好？银屑病怎么能治疗好？)》][PostgreSQL _ -]

[《PostgreSQL 相似搜索分布式架构设计与实践 - dblink异步调用与多机并行(远程 游标+记录 UDF实例)》][PostgreSQL _ - dblink_ _ UDF]

[《PostgreSQL 相似搜索设计与性能 - 地址、QA、POI等文本 毫秒级相似搜索实践》][PostgreSQL _ - _QA_POI_]

[《PostgreSQL 遗传学应用 - 矩阵相似距离计算 (欧式距离,...XX距离)》][PostgreSQL _ - _ _...XX]

[《用PostgreSQL 做实时高效 搜索引擎 - 全文检索、模糊查询、正则查询、相似查询、ADHOC查询》][PostgreSQL _ _ - _ADHOC]

[《HTAP数据库 PostgreSQL 场景与性能测试之 17 - (OLTP) 数组相似查询》][HTAP_ PostgreSQL _ 17 - _OLTP_]

[《HTAP数据库 PostgreSQL 场景与性能测试之 16 - (OLTP) 文本特征向量 - 相似特征(海明...)查询》][HTAP_ PostgreSQL _ 16 - _OLTP_ _ - _...]

[《HTAP数据库 PostgreSQL 场景与性能测试之 13 - (OLTP) 字符串搜索 - 相似查询》][HTAP_ PostgreSQL _ 13 - _OLTP_ _ -]

[《海量数据,海明(simhash)距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践》][simhash_smlar_ - _RDS PosgreSQL]

[《17种文本相似算法与GIN索引 - pg\_similarity》][17_GIN_ - pg_similarity]

[《脑王水哥王昱珩惜败人工智能, 这不可能. - 图像识别到底是什么鬼》][_. -]

[《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 3 rum, smlar应用场景分析》][PostgreSQL_ _ _ - 3 rum_ smlar]

[《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 2 smlar插件详解》][PostgreSQL_ _ _ - 2 smlar]

[《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 1 文本(关键词)分析理论基础 - TF(Term Frequency 词频)/IDF(Inverse Document Frequency 逆向文本频率)》][PostgreSQL_ _ _ - 1 _ - TF_Term Frequency _IDF_Inverse Document Frequency]

[《(AR虚拟现实)红包 技术思考 - GIS与图像识别的完美结合》][AR_ _ - GIS]

[《导购系统 - 电商内容去重\\内容筛选应用(实时识别转载\\盗图\\侵权?) - 文本、图片集、商品集、数组相似判定的优化和索引技术》][- _ -]

[《从相似度算法谈起 - Effective similarity search in PostgreSQL》][- Effective similarity search in PostgreSQL]

[《PostgreSQL 在视频、图片去重，图像搜索业务中的应用》][PostgreSQL]

[《聊一聊双十一背后的技术 - 毫秒分词算啥, 试试正则和相似度》][- _]

[《PostgreSQL 文本数据分析实践之 - 相似度分析》][PostgreSQL _ - 1]

[《弱水三千,只取一瓢,当图像搜索遇见PostgreSQL(Haar wavelet)》][PostgreSQL_Haar wavelet]

本文将分析PG相关的相似搜索的插件，以及他们的差异。

## 类别1 : 元素重叠度相似 ##

类似倒排，以元素重叠度为基准的相似计算。广泛应用于数组、全文检索、字符串、文本特征值、多列任意组合查询的相似搜索。

代表的PostgreSQL插件如下

### 1、rum ###

[https://github.com/postgrespro/rum][https_github.com_postgrespro_rum]

### 2、pg\_trgm ###

[https://www.postgresql.org/docs/devel/static/pgtrgm.html][https_www.postgresql.org_docs_devel_static_pgtrgm.html]

### 3、smlar ###

[http://sigaev.ru/git/gitweb.cgi?p=smlar.git;a=summary][http_sigaev.ru_git_gitweb.cgi_p_smlar.git_a_summary]

### 4、smlar+海明码(向量相似) ###

[《海量数据,海明(simhash)距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践》][simhash_smlar_ - _RDS PosgreSQL]

### 5、pg\_similarity ###

[https://github.com/eulerto/pg\_similarity][https_github.com_eulerto_pg_similarity]

## 类别2 : 向量相似(类似knn距离) ##

向量相似与元素重叠度计算，显然是不同的，基于元素的重叠度相似，可以利用倒排来实现，如上节描述。而基于元素向量相似，需要用到自定义的索引接口，典型的代表是GiST索引在空间距离上的计算，以及imgsmlr插件在图像特征值相似方面的计算。

### 1、imgsmlr(图片向量相似) ###

[https://github.com/postgrespro/imgsmlr][https_github.com_postgrespro_imgsmlr]

原理如下

64\*64的图像，取16个区域的平均值，生成16个浮点数，作为图像特征值。

一个值求相似，相减绝对值最小。

2个值求相似，可以理解为平面坐标，求距离最小（GiST knn距离排序）。

3个值求相似，可以理解为3D坐标里面的点，求距离最小的点。

...

16个值求相似，与上类似。imgsmlr插件使用gist索引接口实现了16个元素的向量相似索引排序。

例子

数据量

postgres=# select count(*) from t_img;  
       count     
    -----------  
     319964709  
    (1 row)  
      
    Time: 698.075 ms

图像特征值搜索例子，速度杠杠的。(以上使用citus+postgres+128 shard)

postgres=# select * from t_img order by sig <-> '(3.539080, 0.243861, 1.509150, 1.781380, 8.677560, 4.232060, 8.979810, 1.665030, 1.294100, 4.449800, 9.200450, 1.859860, 5.440250, 7.788580, 0.514258, 8.424920)' limit 1;  
        id     |                                                                               sig                                                                                  
    -----------+------------------------------------------------------------------------------------------------------------------------------------------------------------------  
     148738668 | (2.554440, 0.310499, 2.322520, 0.478624, 7.816080, 4.360440, 8.287050, 1.011060, 2.114320, 3.541110, 9.166300, 1.922250, 4.488640, 7.897890, 1.600290, 7.462080)  
    (1 row)  
      
    Time: 337.301 ms

### 2 CUBE ###

[https://www.postgresql.org/docs/devel/static/cube.html][https_www.postgresql.org_docs_devel_static_cube.html]

a <-> b	float8	Euclidean distance between a and b.
    a <#> b	float8	Taxicab (L-1 metric) distance between a and b.
    a <=> b	float8	Chebyshev (L-inf metric) distance between a and b.

计算图片向量相似时，cube比imgsmlr性能稍差，因为cube使用的是float8，而imgsmlr使用的是float4。

例子

cube

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_img0 order by sig::Text::cube <-> '(0.435404, 6.602870, 9.050220, 9.379750, 2.483920, 1.534660, 0.363753, 4.079670, 0.124681, 3.611220, 7.127460, 7.880070, 2.574830, 6.778820, 5.156320, 8.329430)' limit 1;
                                                                                                       QUERY PLAN                                                                                                   
    ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
     Limit  (cost=0.36..0.37 rows=1 width=76) (actual time=147.432..147.434 rows=1 loops=1)
       Output: id, sig, ((((sig)::text)::cube <-> '(0.435404, 6.60287, 9.05022, 9.37975, 2.48392, 1.53466, 0.363753, 4.07967, 0.124681, 3.61122, 7.12746, 7.88007, 2.57483, 6.77882, 5.15632, 8.32943)'::cube))
       Buffers: shared hit=16032
       ->  Index Scan using idx_t_img0_1 on public.t_img0  (cost=0.36..13824.28 rows=754085 width=76) (actual time=147.430..147.430 rows=1 loops=1)
             Output: id, sig, (((sig)::text)::cube <-> '(0.435404, 6.60287, 9.05022, 9.37975, 2.48392, 1.53466, 0.363753, 4.07967, 0.124681, 3.61122, 7.12746, 7.88007, 2.57483, 6.77882, 5.15632, 8.32943)'::cube)
             Order By: (((t_img0.sig)::text)::cube <-> '(0.435404, 6.60287, 9.05022, 9.37975, 2.48392, 1.53466, 0.363753, 4.07967, 0.124681, 3.61122, 7.12746, 7.88007, 2.57483, 6.77882, 5.15632, 8.32943)'::cube)
             Buffers: shared hit=16032
     Planning Time: 0.096 ms
     Execution Time: 148.905 ms
    (9 rows)

imgsmlr

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_img0 order by sig <-> '(0.435404, 6.602870, 9.050220, 9.379750, 2.483920, 1.534660, 0.363753, 4.079670, 0.124681, 3.611220, 7.127460, 7.880070, 2.574830, 6.778820, 5.156320, 8.329430)' limit 2;
                                                                                                        QUERY PLAN                                                                                                    
    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
     Limit  (cost=0.36..0.37 rows=2 width=72) (actual time=40.284..48.183 rows=2 loops=1)
       Output: id, sig, ((sig <-> '(0.435404, 6.602870, 9.050220, 9.379750, 2.483920, 1.534660, 0.363753, 4.079670, 0.124681, 3.611220, 7.127460, 7.880070, 2.574830, 6.778820, 5.156320, 8.329430)'::signature))
       Buffers: shared hit=2914
       ->  Index Scan using t_img0_sig_idx on public.t_img0  (cost=0.36..7032.36 rows=754085 width=72) (actual time=40.282..48.179 rows=2 loops=1)
             Output: id, sig, (sig <-> '(0.435404, 6.602870, 9.050220, 9.379750, 2.483920, 1.534660, 0.363753, 4.079670, 0.124681, 3.611220, 7.127460, 7.880070, 2.574830, 6.778820, 5.156320, 8.329430)'::signature)
             Order By: (t_img0.sig <-> '(0.435404, 6.602870, 9.050220, 9.379750, 2.483920, 1.534660, 0.363753, 4.079670, 0.124681, 3.611220, 7.127460, 7.880070, 2.574830, 6.778820, 5.156320, 8.329430)'::signature)
             Buffers: shared hit=2914
     Planning Time: 0.091 ms
     Execution Time: 48.210 ms
    (9 rows)

cube相比imgsmlr的好处是：cube可以计算任意维度的向量相似，imgsmlr则仅用于计算16维(signation类型)的向量相似

[Greenplum]: https://github.com/digoal/blog/blob/master/201806/20180607_02.md
[PostgreSQL _ -]: https://github.com/digoal/blog/blob/master/201803/20180329_01.md
[PostgreSQL _ - dblink_ _ UDF]: https://github.com/digoal/blog/blob/master/201802/20180205_03.md
[PostgreSQL _ - _QA_POI_]: https://github.com/digoal/blog/blob/master/201802/20180202_01.md
[PostgreSQL _ - _ _...XX]: https://github.com/digoal/blog/blob/master/201712/20171227_01.md
[PostgreSQL _ _ - _ADHOC]: https://github.com/digoal/blog/blob/master/201712/20171205_02.md
[HTAP_ PostgreSQL _ 17 - _OLTP_]: https://github.com/digoal/blog/blob/master/201711/20171107_18.md
[HTAP_ PostgreSQL _ 16 - _OLTP_ _ - _...]: https://github.com/digoal/blog/blob/master/201711/20171107_17.md
[HTAP_ PostgreSQL _ 13 - _OLTP_ _ -]: https://github.com/digoal/blog/blob/master/201711/20171107_14.md
[simhash_smlar_ - _RDS PosgreSQL]: https://github.com/digoal/blog/blob/master/201708/20170804_01.md
[17_GIN_ - pg_similarity]: https://github.com/digoal/blog/blob/master/201705/20170524_01.md
[_. -]: https://github.com/digoal/blog/blob/master/201701/20170122_01.md
[PostgreSQL_ _ _ - 3 rum_ smlar]: https://github.com/digoal/blog/blob/master/201701/20170116_04.md
[PostgreSQL_ _ _ - 2 smlar]: https://github.com/digoal/blog/blob/master/201701/20170116_03.md
[PostgreSQL_ _ _ - 1 _ - TF_Term Frequency _IDF_Inverse Document Frequency]: https://github.com/digoal/blog/blob/master/201701/20170116_02.md
[AR_ _ - GIS]: https://github.com/digoal/blog/blob/master/201701/20170113_01.md
[- _ -]: https://github.com/digoal/blog/blob/master/201701/20170112_02.md
[- Effective similarity search in PostgreSQL]: https://github.com/digoal/blog/blob/master/201612/20161222_02.md
[PostgreSQL]: https://github.com/digoal/blog/blob/master/201611/20161126_01.md
[- _]: https://github.com/digoal/blog/blob/master/201611/20161118_01.md
[PostgreSQL _ - 1]: https://github.com/digoal/blog/blob/master/201608/20160817_01.md
[PostgreSQL_Haar wavelet]: https://github.com/digoal/blog/blob/master/201607/20160726_01.md
[https_github.com_postgrespro_rum]: https://github.com/postgrespro/rum
[https_www.postgresql.org_docs_devel_static_pgtrgm.html]: https://www.postgresql.org/docs/devel/static/pgtrgm.html
[http_sigaev.ru_git_gitweb.cgi_p_smlar.git_a_summary]: http://sigaev.ru/git/gitweb.cgi?p=smlar.git;a=summary
[https_github.com_eulerto_pg_similarity]: https://github.com/eulerto/pg_similarity
[https_github.com_postgrespro_imgsmlr]: https://github.com/postgrespro/imgsmlr
[https_www.postgresql.org_docs_devel_static_cube.html]: https://www.postgresql.org/docs/devel/static/cube.html