postgresql - 最长匹配子串

Question

如何在 varchar 变量中搜索最长的匹配项？例如，表 GOB 具有如下条目:

magic_word |  prize
===================
         sh|  $0.20
        sha|  $0.40
       shaz|  $0.60
      shaza|  $1.50

我想编写一个 plpgsql 函数，它在其他参数中接受一个字符串作为输入(例如 shazam)，并返回具有最长匹配子字符串的 GOB 行上的“奖品”列。在所示的示例中，在带有 magic_word shaza 的行中，这将是 $1.50。

我能处理的所有函数格式，它只是匹配位。我想不出一个优雅的解决方案。我猜这可能真的很容易，但我挠头。我不知道开头的输入字符串，因为它将从对另一个表的查询结果中派生。

有什么想法吗？

Answer 1

简单的解决方案

SELECT magic_word
FROM   gob
WHERE  'shazam' LIKE (magic_word || '%')
ORDER  BY magic_word DESC
LIMIT  1;

这是可行的，因为最长的匹配排在最后 - 所以我对 DESC 进行排序并选择第一个匹配。

我从你的例子中假设你想匹配左 anchor ，从字符串的开头。如果你想匹配字符串中的任何地方(这更昂贵并且更难用索引备份)，使用:

...
WHERE  'shazam' LIKE ('%' || magic_word || '%')
...

SQL Fiddle.

性能

查询不是sargable .如果您有其他信息(例如可以作为索引基础的最小长度)以减少要考虑的行数，这可能会有很大帮助。它需要是让您少于 ~ 5% 的表格才能有效的标准。因此，首字母(自然的最小选择)可能有用也可能没有用。但开头的两三个字母可能会有很大帮助。

事实上，您可以迭代优化它。沿线的东西:
尝试使用 15 个字母的单词的部分索引+
如果没有找到，试试12个字母+
如果没有找到，试试9个字母+
...

我在 dba.SE 上的相关回答中概述的一个简单案例:

• Can spatial index help a “range - order by - limit” query

另一种方法是使用三元组索引。您需要额外的模块 pg_trgm为了那个原因。通常，您会在包含较长 字符串的表中使用较短的模式进行搜索。但八卦也适用于您的反向方法，但有一些限制。显然，您不能使用三元组匹配一个只有两个字符的字符串，并且位于一个较长的字符串中间……测试极端情况。
这里有很多关于 SO 的答案以及更多信息。示例:

• Effectively query on column that includes a substring

高级解决方案

考虑这个与整个搜索字符串表密切相关的问题下的解决方案。使用递归 CTE 实现:

• Longest Prefix Match