通过相似性 Postgres 模糊自连接查询提高性能

Question

我正在尝试运行一个查询，该查询将表与自身连接起来，并进行模糊字符串比较（使用三元组比较）以查找可能的公司名称匹配。我的目标是返回一个记录的公司名称（ref_name 字段）的三元相似度与另一记录的公司名称匹配的记录。目前，我将阈值设置为 0.9，因此它只会返回很可能包含相似字符串的匹配项。

我知道自连接本质上会导致许多比较，但我想尽我所能优化我的查询。我不需要立即得到结果，但目前我正在运行的查询需要 11 个小时才能运行。

我在 Ubuntu 12.04 服务器上运行 Postgres 9.2。我不知道 ref_name 字段（我匹配的字段）的最大长度是多少，所以我将其设置为

varchar(300)

。我想知道将其设置为文本类型是否会影响性能，或者是否有更好的字段类型可用于提高性能。我的

LC_CTYPE

和

LC_COLLATE

语言环境设置为

"en_US.UTF-8"

我正在运行查询的表总共包含大约 160 万条记录，但需要我花费 11 个小时才能运行的查询是针对其中的一小部分（大约 100k）。

表结构：

CREATE TABLE ref_name (
  ref_name_id integer,
  ref_name character varying(300),
  ref_name_type character varying(2),
  name_display text,
  load_date timestamp without time zone
)

索引：

CREATE INDEX ref_name_ref_name_trigram_idx ON ref_name
  USING gist (ref_name COLLATE pg_catalog."default" gist_trgm_ops);

CREATE INDEX ref_name_ref_name_trigram_idx_1 ON ref_name
  USING gist (ref_name COLLATE pg_catalog."default" gist_trgm_ops)
  WHERE ref_name_type::text = 'E'::text;

CREATE INDEX ref_name_ref_name_e_idx ON ref_name
  USING btree (ref_name COLLATE pg_catalog."default")
  WHERE ref_name_type::text = 'E'::text;

查询：

select a.ref_name_id as name_id,a.ref_name AS name,
  a.name_display AS name_display,b.ref_name_id AS matched_name_id,
  b.ref_name AS matched_name,b.name_display AS matched_name_display
from ref_name a
JOIN ref_name b
 ON a.ref_name_id<>b.ref_name_id
 AND a.ref_name_id>b.ref_name_id
 AND a.ref_name % b.ref_name
WHERE 
 a.ref_name ~>=~ 'A' and a.ref_name ~<~'B'
 AND b.ref_name ~>=~ 'A' and b.ref_name ~<~'B'
 AND a.ref_name_type='E'
 AND b.ref_name_type='E'

解释计划：

"Nested Loop  (cost=0.00..8560728.16 rows=3598470 width=96)"
"  ->  Seq Scan on ref_name a  (cost=0.00..96556.12 rows=103901 width=48)"
"        Filter: (((ref_name)::text ~>=~ 'A'::text) AND ((ref_name)::text ~<~ 'B'::text) AND ((ref_name_type)::text = 'E'::text))"
"  ->  Index Scan using ref_name_ref_name_trigram_idx_1 on ref_name b  (cost=0.00..80.41 rows=35 width=48)"
"        Index Cond: ((a.ref_name)::text % (ref_name)::text)"
"        Filter: (((ref_name)::text ~>=~ 'A'::text) AND ((ref_name)::text ~<~ 'B'::text) AND (a.ref_name_id <> ref_name_id) AND (a.ref_name_id > ref_name_id))"

以下是一些示例记录：

1652632;"A 123 SYSTEMS";"E";"A 123 SYSTEMS INC";"2014-11-14 00:00:00"
1652633;"A123 SYSTEMS";"E";"A123 SYSTEMS INC";"2014-11-14 00:00:00"
1652640;"A 1 ACCOUSTICS";"E";"A-1 ACCOUSTICS";"2014-11-14 00:00:00"
1652641;"A 1 ACOUSTICS";"E";"A-1 ACOUSTICS";"2014-11-14 00:00:00"
1652642;"A1 ACOUSTICS";"E";"A1 ACOUSTICS INC";"2014-11-14 00:00:00"
1652650;"A 1 A ELECTRICAL";"E";"A-1 A ELECTRICAL INC";"2014-11-14 00:00:00"
1652651;"A 1 A ELECTRICIAN";"E";"A 1 A ELECTRICIAN INC";"2014-11-14 00:00:00"
1652652;"A 1A ELECTRICIAN";"E";"A 1A ELECTRICIAN INC";"2014-11-14 00:00:00"
1652653;"A1 A ELECTRICIAN";"E";"A1 A ELECTRICIAN INC";"2014-11-14 00:00:00"
1691270;"ALBERT GARLATTI";"E";"ALBERT GARLATTI";"2014-11-14 00:00:00"
1691271;"ALBERT GARLATTI CONSTRUCTION";"E";"ALBERT GARLATTI CONSTRUCTION CO";"2014-11-14 00:00:00"
1680892;"AG HOG PITTSBURGH";"E";"AG-HOG PITTSBURGH CO INC";"2014-11-14 00:00:00"
1680893;"AGHOG PITTSBURGH";"E";"AGHOG PITTSBURGH CO";"2014-11-14 00:00:00"
1680928;"AGILE PURSUITS FRACHISING";"E";"AGILE PURSUITS FRACHISING INC";"2014-11-14 00:00:00"
1680929;"AGILE PURSUITS FRANCHISING";"E";"AGILE PURSUITS FRANCHISING INC";"2014-11-14 00:00:00"
1680956;"AGING COMMUNITY COORDINATED ENTERPRISES & SUPPORT";"E";"AGING COMMUNITY COORDINATED ENTERPRISES & SUPPORT";"2014-11-14 00:00:00"
1680957;"AGING COMMUNITY COORDINATED ENTERPRISES & SUPPORTI";"E";"AGING COMMUNITY COORDINATED ENTERPRISES & SUPPORTI";"2014-11-14 00:00:00"

如您所见，我创建了一个要点三元组索引来加快速度（到目前为止尝试了两种不同类型进行比较）。有人对如何提高此查询的性能并将其从 11 小时缩短到更易于管理的时间有任何建议吗？最终我想在整个表上运行这个查询来比较记录，而不仅仅是这个小子集。

Answer 1

指数

部分 GiST 索引很好，我至少会测试这另外两个索引：

杜松子酒指数：

CREATE INDEX ref_name_trgm_gin_idx ON ref_name
USING gin (ref_name gin_trgm_ops)
WHERE ref_name_type = 'E';

这可能会也可能不会被使用。如果您升级到 Postgres 9.4，机会会更好，因为 GIN 索引有了重大改进。

varchar_pattern_ops 索引：

CREATE INDEX ref_name_pattern_ops_idx
ON ref_name (ref_name varchar_pattern_ops)
WHERE ref_name_type = 'E';

查询

此查询的核心问题是，在对照所有行检查所有行时，您会遇到与 O(N²) 的交叉联接。当行数非常大时，性能变得难以忍受。您似乎很了解动态。防御措施是限制可能的组合。您已经朝这个方向迈出了一步，限制为相同的第一个字母。

这里一个非常好的选择是建立在GiST索引的特殊能力之上，用于最近邻居搜索。对于这种查询技术，手册中有提示：

这可以通过 GiST 索引非常有效地实现，但不能通过 GIN 索引。当只有一个时，它通常会击败第一个配方需要少量最接近的匹配。

除了

GiST 索引之外，仍然可以使用 GIN 索引。你必须权衡成本和收益。在 9.4 之前的版本中，坚持使用一个大索引总体上可能会更便宜。但在第 9.4 页中这可能是值得的。

Postgres 9.3+

使用

LATERAL

 连接来匹配集合到集合。类似于此相关答案中的第

2a章：

优化 GROUP BY 查询以检索每个用户的最新行

SELECT a.ref_name_id
     , a.ref_name
     , a.name_display
     , b.ref_name_id  AS match_name_id
     , b.ref_name     AS match_name
     , b.name_display AS match_name_display
FROM   ref_name a
CROSS  JOIN LATERAL (
   SELECT b.ref_name_id, b.ref_name, b.name_display
   FROM   ref_name b
   WHERE  b.ref_name ~~ 'A%'
   AND    b.ref_name_type = 'E'
   AND    a.ref_name_id < b.ref_name_id
   AND    a.ref_name % b.ref_name  -- also enforce min. similarity
   ORDER  BY a.ref_name <-> b.ref_name
   LIMIT  10                                -- max. 10 best matches
   ) b
WHERE  a.ref_name ~~ 'A%'   -- you can extend the search
AND    a.ref_name_type = 'E'
ORDER  BY 1;

fiddle - 与根据您的案例建模的 40k 行的原始查询相比，所有变体。
旧_sqlfiddle

查询速度比小提琴中的原始查询快 2 - 5 倍。我希望它们能够“更好地扩展”数百万行。你必须测试一下。

将 b

中的匹配搜索扩展到所有行（同时将

a

 中的候选者限制在合理的数量）也相当便宜。我在小提琴中添加了另外两个变体。

旁白：我用

text

而不是

varchar

 运行了所有测试，但这应该不会产生影响。

基础知识和链接：

使用 LIKE、SIMILAR TO 或正则表达式进行模式匹配

Postgres 9.2

使用

通过相似性 Postgres 模糊自连接查询提高性能

问题描述投票：0回答：1

1个回答

指数

查询

相关子查询

最新问题

通过相似性 Postgres 模糊自连接查询提高性能

问题描述 投票：0回答：1

1个回答

指数

查询

相关子查询

最新问题

问题描述投票：0回答：1