快速找到与PostgreSQL相似的字符串

Question

我需要在表中创建类似字符串的排名.

我有下表

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

目前,我正在使用提供该功能的pg_trgm模块similarity,但我遇到了效率问题.我创建了一个像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(测试版作为写入的)的功能pg_trgm.similarity_threshold和set_limit()与所述配置参数被替换show_limit()(与其他一些改进的模块一起set_limit()).这些函数已弃用但仍然有效.

此外,自Postgres 9.1以来,GIN和GiST指数的表现在几个方面得到了改善.

使用%和pg_trgm操作员代替.两者都由WHERE模块提供.

你拥有它的方式,必须计算每个元素和表的每个其他元素之间的相似性(几乎是交叉连接).如果你的表有1000行,那就是1,000,000(!)计算的相似度,然后才能根据条件检查并排序.尝试:

SET pg_trgm.similarity_threshold = 0.8; -- Postgres 9.6 or later
-- SELECT set_limit(0.8);               -- for older versions

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;

应该更快几个数量级,但它仍然会很慢.

您可能希望通过在交叉连接之前引入更多前提条件(如匹配第一个字母)来限制可能的对的数量(并使用匹配的功能索引支持).交叉连接的性能随着记录数量的增加而呈二次方式恶化- O(N²).

至于你的附属问题:

WHERE ... sim > 0.8

不起作用,因为您无法引用HAVING或GROUP BY子句中的输出列.这是根据(有点混乱,授予)SQL标准 - 由某些其他RDBMS相当松散地处理.

另一方面:

ORDER BY sim DESC

作品因为输出列可以在使用ORDER BY和EXPLAIN ANALYZE.细节:

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

测试用例

我在旧的测试服务器上运行了一个快速测试来验证我的声明.
PostgreSQL 9.1.4.用时间pg_trgm.similarity_threshold(最好的五个).

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

第一轮GIN指数测试:

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

GIST指数的第二轮测试:

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

新查询:

SELECT set_limit(0.8);

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 ms使用的
GIST索引,64次点击:总运行时间:248.772 ms

旧查询:

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 ms 未使用
GIST索引,64次点击:总运行时间:6335.975 ms

否则结果相同.建议很好.这只是1000行.

GIN还是GiST？

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

• GiST和GIN指数之间的差异

但不是在这种特殊情况下:

这可以通过GiST索引非常有效地实现,但不能通过GIN索引实现.

• 具有异构数据类型的3个字段的多列索引