我需要在表格中创建相似字符串的排名。
我有下表
create table names (
name character varying(255)
);
目前,我正在使用提供similarity
功能的pg_trgm 模块,但我遇到了效率问题。我创建了一个类似 Postgres manual suggests 的索引:
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
而不会出现“column sim doesn't exist”错误。
我想要任何提示来加快查询速度。
最佳答案
按照您的方式,必须计算表中每个元素与其他每个元素之间的相似性(几乎是交叉连接)。如果您的表有 1000 行,那已经是 1,000,000 (!) 次相似性计算,在此之前可以对照条件检查并排序。扩展性极强。
使用SET pg_trgm.similarity_threshold
和 %
operator反而。两者均由 pg_trgm
提供模块。这样,一个三元组 GiST 索引就可以发挥很大的作用。
配置参数pg_trgm.similarity_threshold
替换了函数 set_limit()
and show_limit()
在 Postgres 9.6 中。已弃用的功能仍然有效(从 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
是 "customized" option ,可以像任何其他选项一样处理。见:
您可能希望通过在 交叉连接之前添加先决条件(例如匹配首字母)来限制可能的对数(并通过匹配的功能索引支持)。 cross join 的性能随着 O(N²) 而恶化。
这不起作用,因为您不能在WHERE
或HAVING
子句中引用输出列:
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 通常提供卓越的读取性能:
But not in this particular case!
This can be implemented quite efficiently by GiST indexes, but not by GIN indexes.
关于sql - 使用 PostgreSQL 快速查找相似字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11249635/