sql - PostgreSQL，查找字符串相差 n 个字符

Question

假设我有一张这样的桌子

id  data
1   0001
2   1000
3   2010
4   0120
5   0020
6   0002

sql fiddle demo

id是主键，data是固定长度的字符串，其中字符可以是 0、1、2。

有没有办法建立索引，以便我可以快速找到与给定字符串相差 n 个字符的字符串？喜欢字符串0001，n = 1我想获得第 6 行。

谢谢。

Answer 1

levenshtein()附加模块fuzzystrmatch提供了该功能。它完全符合您的要求：

SELECT *
FROM   a
WHERE  levenshtein(data, '1110') = 1;

SQL小提琴。

但这不是很快。大表慢，因为它不能使用索引。

您可能会得到附加模块pg_trgm提供的相似性或距离运算符的某个地方。那些可以使用链接手册页中详细说明的三元索引。我没有得到任何结果，该模块使用了不同的“相似性”定义。

通常，该问题似乎适合KNN（“k 最近邻”）搜索模式。

如果您的情况与问题中的示例一样简单，则可以LIKE与 trigram GIN 索引结合使用，这对于大表应该相当快：

SELECT *
FROM   a
WHERE  data <> '1110'
AND   (data LIKE '_110' OR
       data LIKE '1_10' OR
       data LIKE '11_0' OR
       data LIKE '111_');

显然，这种技术很快就变得不可行，因为字符串更长并且不仅仅是1差异。

但是，由于字符串很短，任何查询都将匹配相当大比例的基表。因此，指数支撑几乎不会给你带来任何好处。大多数情况下，Postgres 顺序扫描会更快。

我测试了 10k 和 100k 行，有和没有 trigram GIN 索引。由于 ~ 19% 符合给定测试用例的标准，因此顺序扫描更快并且levenshtein()仍然获胜。对于匹配少于约 5% 的行（取决于）的更具选择性的查询，使用索引的查询（快得多）。