PostgreSQL中<->操作符实现拼写纠错的原理及相关疑问

问题背景 #

以下是取自PostgreSQL文档41.3的示例，用于搜索与caterpiler相似的词汇，相关建表语句、查询及执行计划如下：

建表语句 #

CREATE EXTENSION file_fdw;
CREATE SERVER local_file FOREIGN DATA WRAPPER file_fdw;
CREATE FOREIGN TABLE words (word text NOT NULL)
  SERVER local_file
  OPTIONS (filename '/usr/share/dict/words');

查询语句及结果 #

-- 已确认外部表words中不存在'caterpiler'
SELECT word FROM words ORDER BY word <-> 'caterpiler' LIMIT 10;

输出结果：

word
---------------
 cater
 caterpillar
 Caterpillar
 caterpillars
 caterpillar's
 Caterpillar's
 caterer
 caterer's
 caters
 catered
(10 rows)

执行计划（EXPLAIN ANALYZE） #

Limit  (cost=11583.61..11583.64 rows=10 width=32) (actual time=1431.591..1431.594 rows=10 loops=1)
   ->  Sort  (cost=11583.61..11804.76 rows=88459 width=32) (actual time=1431.589..1431.591 rows=10 loops=1)
         Sort Key: ((word <-> 'caterpiler'::text))
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Foreign Scan on words  (cost=0.00..9672.05 rows=88459 width=32) (actual time=0.057..1286.455 rows=479829 loops=1)
               Foreign File: /usr/share/dict/words
               Foreign File Size: 4953699
 Planning time: 0.128 ms
 Execution time: 1431.679 ms

疑问解答 #

1. word <-> 'caterpiler'的工作方式与排序逻辑 #

你猜错了，这里用的不是tsquery <-> tsquery语法，而是text类型的<->操作符，它计算的是两个字符串之间的Levenshtein编辑距离——也就是把一个字符串转换成另一个字符串，需要的最少单字符编辑次数（包括插入、删除、替换）。

排序逻辑很直接：编辑距离越小的字符串越靠前。比如caterpillar和caterpiler的编辑距离是1（仅需删除一个l），cater和caterpiler的编辑距离更大，但因为它是所有候选词里距离相对较小的前10个，所以出现在结果列表中。

2. EXPLAIN中的'caterpiler'::text是什么原因 #

这是因为PostgreSQL调用的是text类型的<->操作符，规划器会自动将字符串字面量'caterpiler'转换为text类型（也就是显式的::text转换），确保参数类型匹配操作符的要求，和tsquery版本的操作符无关。

3. 是否用到词典/词库？ #

这个功能完全是<->操作符的通用特性，没有用到任何词典或词库——它只基于字符串本身的字符序列计算编辑距离，和词汇的语义、词典定义无关。

至于/usr/share/dict/words这个文件，它只是一个普通的文本文件（每行一个单词），被当作外部表的数据源提供待搜索的字符串集合，并没有被PostgreSQL当作全文搜索里的“词典”来使用。

内容的提问来源于stack exchange，提问作者okzoomer