如何编写查询语句获取词表中非重叠词及最长前缀重叠词

前提 #

假设你有一张存储单词的表，部分单词是独立不重叠的，部分单词可重叠，即长单词以某短单词为前缀，示例如下：

---------------
|    word     |
---------------
| dog         | *
| games       | *
| stat        |
| state       | 
| statement   | *
| fulfill     |
| fulfilled   | *
| fulfillment | *
---------------

核心需求 #

编写查询语句，返回该场景下所有非重叠词 + 最长重叠词的列表，示例中标记*的即为符合要求的结果，判定规则如下：

• dog和games无任何重叠匹配，属于*「独立/唯一」*分类下的最长词，因此入选
• statement与state、stat重叠，是三者中的最长词，因此入选
• fulfilled与fulfill重叠且长度更长（与fulfillment无重叠关系），因此入选
• fulfillment与fulfill重叠且长度更长（与fulfilled无重叠关系），因此入选

约束条件 #

实际业务场景需要查询数百万条记录，且无预先已知的搜索词，因此无法直接使用WHERE word LIKE 'stat%'这类硬编码语法。单词最大长度较短，约20。 #

解决方案 #

核心判定逻辑：如果某个单词不存在任何更长的、以它为前缀的单词，那么它就符合入选要求。
以MySQL为例，基础查询语句如下：

SELECT t1.word
FROM words t1
LEFT JOIN words t2 
  ON t2.word LIKE CONCAT(t1.word, '%') 
  AND LENGTH(t2.word) > LENGTH(t1.word)
WHERE t2.word IS NULL;

百万级数据性能优化方案 #

因为单词最长仅20个字符，可通过两个小改动大幅提升查询效率：

1. 给word字段创建长度为20的前缀索引
2. 提前把单词长度存储为word_len字段并创建索引，避免查询时实时计算长度，优化后语句如下：

SELECT t1.word
FROM words t1
LEFT JOIN words t2 
  ON t2.word LIKE CONCAT(t1.word, '%') 
  AND t2.word_len > t1.word_len
WHERE t2.word IS NULL;

结果验证 #

以上述示例数据运行查询，返回结果正好是所有标记*的单词：dog、games、statement、fulfilled、fulfillment，完全符合需求。

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