11

我在 MySQL 数据库中有一本英语词典，条目刚刚超过 250K，我正在使用一个简单的 ruby​​ 前端在字符串开头使用通配符进行搜索。到目前为止，我一直在这样做：

SELECT * FROM words WHERE word LIKE '_e__o'

甚至

SELECT * FROM words WHERE word LIKE '____s'

我总是知道单词的确切长度，但除了单个字符之外的所有字符都可能是未知的。

这比 molasses 慢，比没有前导通配符的类似查询慢大约 15 倍，因为不能使用列的索引。

我尝试了一些方法来缩小搜索范围。例如，我添加了 26 个额外的列，其中包含每个单词的单个字母计数，并首先使用这些列来缩小搜索范围。我也尝试过按字长缩小。由于前导通配符搜索固有的低效率，这些方法几乎没有区别。我已经尝试过 REGEXP 语句，它甚至更慢。

SQLite 和 PostgreSQL 与 MySQL 一样有限，尽管我对 NoSQL 系统的经验有限，但我的研究给我的印象是它们擅长可扩展性，而不是我需要的那种性能。

那么我的问题是，我应该在哪里寻找解决方案？我是否应该继续尝试寻找优化查询的方法或添加可以缩小潜在记录集的补充列？是否有专门设计用于实现这种快速通配符搜索的系统？

4

8 回答 8

5

使用 PostgreSQL 9.1 和 pg_trgm 扩展，您可以创建可用于您描述的类似条件的索引。

有关示例，请参见此处： http: //www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

我在一个有 300k 行的表上验证了它LIKE '____1'，它确实使用了这样的索引。计算该表中的行数大约需要 120 毫秒（在旧笔记本电脑上）。有趣的是，表达式LIKE 'd___1'并不是更快，而是差不多相同的速度。

它还取决于搜索词中的字符数，据我所知，搜索时间越长，速度就越慢。

如果性能可以接受，您需要检查您的数据。

于 2012-04-11T22:58:21.783 回答
1

我假设最初插入单词和设置索引所花费的时间是无关紧要的。此外，您不会经常更新单词列表，因此它基本上是静态数据。

您可以尝试这样的方法：-

  • 因为你总是知道单词长度，所以创建一个包含所有长度为 1 的单词的表，另一个包含长度为 2 的单词的表，等等。
  • 进行查询时，根据字长从相应的表中选择。它仍然需要对该表进行全面扫描。

如果您的 RDBMS 允许，最好使用单个表和按字长进行分区。

如果这仍然不够快，您可以按长度和已知字母进一步拆分它。例如，您可以有一个表格，列出所有包含“Z”的 8 个字母单词。

当您查询时，您知道您有一个包含“E”和“Z”的 8 个字母的单词。首先查询数据字典，看看8个字母单词中哪个字母最稀有，然后扫描那个表。通过查询数据字典，我的意思是确定表words_8E或表words_8z的记录数是否最少。

关于正常形式和良好实践

这不是我在建模数据时通常会推荐的那种东西。在您的特定情况下，将整个单词存储在单个字符列中实际上并不是第一范式。这是因为您关心单词中的各个元素。给定您的用例，一个单词是一个字母列表，而不是一个单词。与往常一样，如何建模取决于您关心的内容。

您的查询给您带来麻烦，因为它不是第一范式。

这个问题的完全标准化模型将有两个表：word (WordId PK) 和 WordLetter (WordId PK, Position PK, Letter)。然后，您将查询在适当位置具有多个 WHERE EXISTS 字母的所有单词。

虽然根据数据库理论是正确的，但我认为这不会很好。

于 2012-04-11T22:44:53.330 回答
1

这一切都归结为索引。

您可以创建如下表：

create table letter_index (
    id integer not null primary key,
    letter varchar(1),
    position integer
)

create unique index letter_index_i1 (letter, position)

create table letter_index_words (
    letter_index_id integer,
    word_id integer
)

然后索引你所有的单词。

如果您想要第二个位置带有“e”的所有单词的列表：

select words.* from words, letter_index_word liw, letter_index li
where li.letter = 'e' and li.position = 2
and liw.letter_index_id = li.id
and words.id = liw.word_id

如果您想要所有带有“e”的单词在第二个位置，而“s”在第五个位置：

select words.* from words, letter_index_word liw, letter_index li
where li.letter = 'e' and li.position = 2
and liw.letter_index_id = li.id
and words.id = liw.word_id
and words.id in (
    select liw.word_id from letter_index_word liw, letter_index li
    where li.letter = 's' and li.position = 5
    and liw.letter_index_id = li.id
)

或者您可以运行两个简单的查询并自己合并结果。

当然，简单地缓存和遍历内存中的列表可能比其中任何一个都快。但速度不够快，不值得每次都从数据库中加载 250K 列表。

于 2012-04-11T22:57:04.480 回答
1

您可以完全索引此查询，而无需扫描超过最佳结果集大小的任何内容。

像这样创建一个查找表：

Table:  lookup
pattern     word_id
_o_s_       1
_ous_       1
...

其中引用了您的单词表：

Table:  word
word_id     word
1           mouse

在模式上放置一个索引并执行如下选择：

select w.word
from lookup l, word w
where l.pattern = '_ous_' and
l.word_id = w.word_id;

当然，您需要一个小红宝石脚本来创建这个查找表，其中模式是字典中每个单词的所有可能模式。换句话说，鼠标的模式是：

m____
mo___
mou__
mous_
mouse
_o___
_ou__
...

为给定单词生成所有模式的 ruby​​ 可能如下所示：

def generate_patterns word
  return [word, '_'] if word.size == 1
  generate_patterns(word[1..-1]).map do |sub_word|
    [word[0] + sub_word, '_' + sub_word]
  end.flatten
end

例如：

> generate_patterns 'mouse'
mouse
_ouse
m_use
__use
mo_se
_o_se
m__se
___se
mou_e
_ou_e
m_u_e
__u_e
mo__e
_o__e
m___e
____e
mous_
_ous_
m_us_
__us_
mo_s_
_o_s_
m__s_
___s_
mou__
_ou__
m_u__
__u__
mo___
_o___
m____
_____
于 2012-04-12T00:01:02.273 回答
1

将其降低 10 倍左右的一种快速方法是为字符串长度创建一个列，在其上放置一个索引，然后在 where 子句中使用它。

于 2012-04-12T02:28:08.043 回答
0

您可以尝试使用全文搜索引擎Apache Lucene 。它是为了回答这样的查询而设计的，所以你可能会有更多的运气。

使用 lucene 进行通配符搜索。

于 2012-04-11T22:18:08.390 回答
0

创建内存查找表解决方案：您可以为每个长度创建一个排序表。

然后匹配，假设你知道第 4 个和第 8 个字母，循环检查每个第 4 个字母的单词。它们都是相同的长度，所以会很快。仅当字母匹配时检查第 8 个字母。

这是蛮力，但会很快。假设最坏的情况是您有 50,000 个 8 个字母的单词。那是 50,000 次比较。假设 ruby​​ 运行时性能问题，它仍应小于 1 秒。

所需的内存为 250k x 10。所以 2.5 Meg。

于 2012-04-11T22:36:23.820 回答
0

这更像是一种练习，而不是现实生活中的解决方案。这个想法是将单词分成字符。

让我们先设计所需的表。我假设您的words表有以下列word_id, word, size：

CREATE TABLE letter_search
( word_id INT NOT NULL
, position UNSIGNED TINYINT NOT NULL
, letter CHAR(1) NOT NULL
, PRIMARY KEY (word_id, position)
, FOREIGN KEY (word_id)
    REFERENCES words (word_id)
      ON DELETE CASCADE 
      ON UPDATE CASCADE
, INDEX position_letter_idx (position, letter)
, INDEX letter_idx (letter)
) ENGINE = InnoDB ;

我们需要一个辅助“数字”表：

CREATE TABLE num
( i UNSIGNED TINYINT NOT NULL
, PRIMARY KEY (i)
) ;

INSERT INTO num (i)               --- I suppose you don't have
VALUES                            --- words with 100 letters
  (1), (2), ..., (100) ;

填充我们的letter_search表格：

INSERT INTO letter_search
  ( word_id, position, letter )
SELECT
    w.word_id
  , num.i
  , SUBSTRING( w.word, num.i, 1 ) 
FROM 
    words AS w
  JOIN
    num
       ON num.i <= w.size

此搜索表的大小约为 10 * 250K 行（其中 10，放置您的单词的平均大小）。

最后，查询：

SELECT * FROM words WHERE word LIKE '_e__o'

将写为：

SELECT w.* 
FROM 
    words AS w
  JOIN
    letter_search AS s2
        ON (s2.position, s2.letter, s2.word_id) = (2, 'e', w.word_id)
  JOIN
    letter_search AS s5
        ON (s5.position, s5.letter, s5.word_id) = (5, 'o', w.word_id)
WHERE
    w.size = 5
于 2012-04-11T22:58:54.767 回答