使用 pg_trgm 将小的 table（<1,000 行）匹配到大的 table（>100m 行）——最有效的方法？

Question

这是我在处理各种不同数据集时经常遇到的问题，所以请原谅我用笼统的术语来介绍它，而不是使用具体的例子。

我经常需要从一个大的 table（通常是数百万行）中获取记录，其中文本列类似于更小的 table（10 到 100 行）中的列行）。我目前的做法如下，其中 targets 是较小的 table 和 matches 较大的

set pg_trgm.similarity_threshold = .9;

select *
from targets as t
inner join matches as m on
  t.name % m.name;

matches.name会有一个GIN索引，一般会有比较高的唯一性，大概有10-20%的记录是重复的。 matches.name 和 targets.name 几乎总是少于 50 个字符，通常更短。

据我了解，这是一个稍微不寻常的用例：Postgres 文档和大多数 SO 答案似乎都集中在针对单个值的匹配进行优化。所以我很想听听关于两个问题的想法：

用非常笼统的术语（几十分钟、几小时等），并假设数据库配置最佳，这种类型的查询在性能方面的合理目标是什么，比如说，给定 300 个目标和 300 个目标百万潜在匹配项？
在给定参数的情况下，我目前使用的策略是最有效的策略吗？例如，是否值得尝试使用 GiST 索引并使用 <-> 运算符为每一行取前 n 匹配项？是否有完全不同的方法可以更有效？

在此先感谢您的帮助！

Answer 1

无论你怎么做，它都会很慢，除非targets很小。

连接必须是嵌套循环连接，因为连接条件中没有 =。执行时间会随着targets.

中的行数线性增长

Answer 2

这种性质的批量操作没有奖励。他们只说做一次，因为没什么好说的。执行 300 次（t 中的行）大约是 t 中执行一行的 300 倍。

这将取决于三字母组频率的直方图，因此如果这些是街道地址或英语短语或序列 numbers/part 数字或其他什么，它会产生很大的不同。作为一个粗略的估计，我会说（在 0.9 的阈值处，它会随着它的减少而变得更糟）你正在查看 t 中每行 30 秒到一分钟。

我预计使用 GiST 而不是 GIN 会导致性能下降。

一种更有效的方法是用 C 语言手动编写一些不需要处理事务、可变性、并发性、抽象数据类型等的代码。如果我们有一些改进，也可能会有所改进巨人 table 中每个 trigram 频率的统计估计，但我认为这对于当前 PostgreSQL 基础架构中的扩展来说不太可行。

Matching a small table (<1,000 rows) to a large table (>100m rows) using pg_trgm—most efficient method?