用PostgreSQL快速find类似的string

我需要在表格中创build类似string的排名。

我有下面的表格

create table names ( name character varying(255) ); 

目前,我使用pg_trgm模块,它提供了similarityfunction,但是我有一个效率问题。 我创build了一个像Postgres手册所示的索引:

 CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops); 

并执行以下查询:

 select (similarity(n1.name, n2.name)) as sim, n1.name, n2.name from names n1, names n2 where n1.name != n2.name and similarity(n1.name, n2.name) > .8 order by sim desc; 

查询起作用了,但是当你有数百个名字的时候真的很慢。 此外,也许我忘了一些SQL,但我不明白为什么我不能使用条件and sim > .8没有得到“列SIM卡不存在”的错误。

我想任何提示使查询更快。

更新:在Postgres 9.6 (testing阶段),函数set_limit()show_limit()被replace为configuration参数pg_trgm.similarity_threshold (以及对模块pg_trgm其他一些改进)。 function已被弃用,但仍然有效。

另外,自从Postgres 9.1以来,GIN和GiST索引的性能在几个方面得到了改进。


改用set_limit()%运算符 。 两者都由pg_trgm模块提供。

你有它的方式,每个元素和表的每个其他元素之间的相似性必须计算(几乎是一个交叉连接)。 如果你的表有1000行,那就是1000000(!)计算出来的相似之处, 然后才能根据条件检查并sorting。 尝试:

 SELECT set_limit(0.8); SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name FROM names n1 JOIN names n2 ON n1.name <> n2.name AND n1.name % n2.name ORDER BY sim DESC; 

应该快几个数量级,但仍然会很慢。

您可能希望通过交叉连接之前引入更多的先决条件(如匹配第一个字母)来限制可能的对的数量(并支持匹配的function索引)。 随着越来越多的logging – O(N 2)交叉连接的性能呈二次 曲线下降


至于你的子公司的问题:

 WHERE ... sim > 0.8 

因为无法引用WHEREHAVING子句中的输出列,所以不起作用 。 这是根据(有点令人困惑,被认可的)SQL标准来处理的,这个标准是由某些其他的RDBMS松散地处理的。

另一方面:

 ORDER BY sim DESC 

因为输出列可以GROUP BYORDER BY 。 细节:

  • PostgreSQL重用计算结果在select查询

testing用例

我在旧的testing服务器上运行了一个快速testing来validation我的说法。
PostgreSQL 9.1.4。 用EXPLAIN ANALYZE (五个最好的时间)采取的时间。

 CREATE TEMP table t AS SELECT some_col AS name FROM some_table LIMIT 1000; -- real life test strings 

GIN指数第一轮testing:

 CREATE INDEX t_gin ON t USING gin(name gin_trgm_ops); -- round1: with GIN index 

GIST指数第二轮testing:

 DROP INDEX t_gin; CREATE INDEX t_gist ON t USING gist(name gist_trgm_ops); 

新的查询:

 -- SELECT show_limit(); SELECT set_limit(0.8); -- fewer hits and faster with higher limit SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name FROM t n1 JOIN t n2 ON n1.name <> n2.name AND n1.name % n2.name ORDER BY sim DESC; 

使用GIN索引,64次命中:总运行时间:484.022毫秒
使用GIST索引,64次命中:总运行时间: 248.772毫秒

旧查询:

 SELECT (similarity(n1.name, n2.name)) as sim, n1.name, n2.name FROM t n1, t n2 WHERE n1.name != n2.name AND similarity(n1.name, n2.name) > 0.8 ORDER BY sim DESC; 

使用GIN索引,64个命中:总运行时间:6345.833毫秒
使用GIST索引,64个命中:总运行时间: 6335.975毫秒

否则相同的结果。 build议是好的。 而这只是1000行

GIN还是GiST?

GIN经常提供卓越的读取性能:

  • GiST和GIN指数的区别

但不是在这个特定的情况下:

这可以通过GiST索引非常有效地实现,而不是由GIN索引实现。

  • 多列数据types的3个字段上的多列索引