47

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

我有下表

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

目前，我正在使用提供该功能的pg_trgmsimilarity模块，但我遇到了效率问题。我创建了一个像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 不存在”错误的情况下使用条件。

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

4

1 回答 1

98

您拥有它的方式，必须计算表中每个元素与每个其他元素之间的相似性（几乎是交叉连接）。如果您的表有 1000 行，那已经是 1,000,000 (!) 个相似性计算，然后才能根据条件检查并排序。规模非常大。

改用SET pg_trgm.similarity_threshold和%运算符。两者都由pg_trgm模块提供。这样，一个三元组 GiST 索引就可以发挥很大的作用。

配置参数pg_trgm.similarity_threshold替换了 Postgres 9.6 中的函数set_limit()和show_limit()。不推荐使用的函数仍然有效（从 Postgres 13 开始）。此外，自 Postgres 9.1 以来，GIN 和 GiST 索引的性能在许多方面都有所提高。

请尝试：

SET pg_trgm.similarity_threshold = 0.8;  -- Postgres 9.6 or later
  
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;

快几个数量级，但仍然很慢。

pg_trgm.similarity_threshold是一个“自定义”选项，可以像任何其他选项一样处理。看：

您可能希望通过在交叉连接之前添加前置条件（如匹配第一个字母）来限制可能对的数量（并通过匹配的功能索引支持它）。交叉连接的性能会随着O(N²) 下降。

这不起作用，因为您不能在WHEREorHAVING子句中引用输出列：

WHERE ... sim > 0.8

这是根据 SQL 标准（由某些其他 RDBMS 相当松散地处理的）。另一方面：

ORDER BY sim DESC

有效，因为输出列可以在GROUP BY和中使用ORDER BY。看：

测试用例

我在旧的测试服务器上运行了一个快速测试来验证我的声明。
PostgreSQL 9.1.4。用时EXPLAIN ANALYZE（最好的 5 次）。

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 毫秒
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 毫秒

否则结果相同。建议很好。这仅适用于1000 行！

GIN 还是 GiST？

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

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

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

于 2012-06-28T17:36:18.613 回答