通过子字符串的最长公共尾部（右侧部分）在字符串的 table 中找到一行

Question

有一个简化的 table mytable，第 ('id', 'mycolumn') 列分别为 int 和 varchar(255)。

在 mycolumn 中找到当前字符串的最长公共右部分（最长尾部）的行的最快方法是什么？ table 很大。

例如，对于字符串 "aaabbbkr84" 我们会通过找到的最长尾 "bkr84":

找到 2 - "wergerbkr84"

1 - "gbkyugbk9"
2 -  "wergerbkr84"
3 - "gbkyugbk4".

为了提高性能，我的想法是创建另一个包含还原字符串的列。但是我不确定它是否有帮助并且没有更好的方法。这样我会查找（直到我得到 0 个结果 return 到前一个）来查找

SELECT id, mycolumn FROM mytable
where reverted like '4%';
SELECT id, mycolumn FROM mytable
where reverted like '48%';
SELECT id, mycolumn FROM mytable
where reverted like '48r%';
SELECT id, mycolumn FROM mytable
where reverted like '48rk%';
SELECT id, mycolumn FROM mytable
where reverted like '48rkb%'; ' <-- looking for this one
SELECT id, mycolumn FROM mytable
where reverted like '48rkbb%'; ' 0 results.

找到 0 个结果，退一步：48rkb。这意味着 2 - "wergerbkr84" 是答案。

1 查询以通过最长的尾巴查找行将是更可取的（如您所见，我在上面有一个查询循环）。然而，性能是#1.

非常感谢。

Answer 1

这可能有点奇怪，但听起来你遇到了一个奇怪的问题。

您是否尝试过在 SQL 中存储正确的树结构并对其进行查找？例如，您可以创建一个 trie/prefix tree，其中数据库中所有字符串中每个可能的字符选择都有一条边（按相反的字符串顺序）。

请参阅上图，了解对问题中的三个字符串（标记为 1、2、3）进行部分 filled-in 尝试的示例。当您从根遍历时，节点存储对从边缘标签编码的所有字符串的引用。对于搜索字符串“48”，跟随标记为“4”和“8”的边，您将获得对标记为 2 ("wergerbkr84") 的字符串的引用。搜索继续进行，直到没有边被标记为搜索字符串中的下一个字符，此时具有最长匹配尾部的字符串存储在当前节点中。搜索时间为 O(n)，其中 n 是搜索字符串的长度。

请参阅以下内容：How to represent a data tree in SQL?请注意，您必须考虑边缘标签的存储，这在大多数树结构中都不需要。

另请注意，根据您的存储要求，有 compressed/space-optimized 个版本的尝试可能值得研究。

通过子字符串的最长公共尾部（右侧部分）在字符串的 table 中找到一行

Find a row in the table for string by the longest common tail (the right part) of the substring

mysql

sql

string

substring

sql-like