用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卡不存在”的错误。

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

Answer 1

更新：在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 

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

另一方面：

 ORDER BY sim DESC 

因为输出列可以在GROUP BY和ORDER 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个字段上的多列索引