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

Question

假设我有这样一张 table

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 Fiddle.

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

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

一般来说，问题似乎适合 KNN ("k nearest neighbours") search pattern .

如果您的情况与问题中的示例一样简单，您可以将 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% 的行(视情况而定)的更多选择性查询，使用索引的查询(快得多)。