MySQL:如何在包含数百万个字符串的表中搜索尽可能多的子字符串匹配项

Question

假设我在 MySQL 表中有以下字符串:

id  |  hash
1   |  462a276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f2654
2   |  5c2670355b6e503f39427a435a423d6d4c7c5156344c336c6c244a7234
3   |  35785c5f45373c495b70522452564b6f4531792b275e40642854772764
... 
millions of records !

现在我有一组子字符串(6 个字符大小)，例如:[“76e262”，“435a42”，“75e406”，“95b705”，“344c33”]

我想要知道每个字符串中有多少个子字符串，因此结果可能是:

id  | matches
63  | 5
34  | 5
123 | 3
153 | 3
13  | 2
9   | 1

如何快速实现这一目标？

实际数字和尺寸为:

1) 具有 100.000/200.000 哈希值的表

2) 主哈希大小:256 字节

3) 迷你哈希子串:每 32 个中的 16 个

注意:我想避免使用“%LIKE%”，因为每行有 16 个点赞，而且有数百万行

Answer 1

您可以使用 Aho-Corasick 算法来完成此操作:http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

MySQL 没有相应的函数，因此您需要编写自己的函数或考虑使用 java 或 c 等语言来处理数据。

换一种方法怎么样？

您还可以考虑为您的数据建立一个转移机制并检查转移。例如，如果您的 key 是 462a276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f2654 并且您知道您的哈希将有 58 个字符，那么您将有以下变体:

62a276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f265442a276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f265446a276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f2654462276e262067573e553b5f6a2b4a323e35272d3c6b6227417c4f2654462a...

其中每个都将在一列中，每个都将被索引。

所以你的查询很简单:

从表中选择*，其中散列如“a27e262%”或s1如“a27e262%”...

请注意，这比 LIKE "%value%"快得多，因为该列已建立索引，并且 LIKE 仅检查开头。

此解决方案有很多缺点:额外列所需的空间、插入和更新时间会增加，因为计算移位列的时间以及处理选择结果所需的时间。但你不需要在 mysql 中实现该算法。

您还可以要求搜索的字符串的最小长度为 6 个字符，因此您不需要移动整个字符串，只需保留前 6 位数字。如果找到匹配项，那么您将继续查找下一个匹配项的接下来的 6 位数字。