用于250K +字符串的通配符搜索的快速(呃)方法

Question

我在MySQL数据库中有一个英文词典,只有超过250K的条目,而我正在使用一个简单的ruby前端在字符串的开头用通配符搜索它.到目前为止,我一直这样做:

SELECT * FROM words WHERE word LIKE '_e__o'

甚至

SELECT * FROM words WHERE word LIKE '____s'

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

这比糖蜜慢,比没有前导通配符的类似查询慢15倍,因为无法使用列的索引.

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

SQLite和PostgreSQL与MySQL一样有限,虽然我对NoSQL系统的经验有限,但我的研究给我的印象是他们在可伸缩性方面表现出色,而不是我需要的那种性能.

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

Answer 1

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

我在使用300k行的表上验证了它LIKE '____1',它确实使用了这样的索引.计算该表中的行数(在旧笔记本电脑上)需要大约120ms.有趣的是,表达LIKE 'd___1'速度并不快,速度大致相同.

它还取决于搜索词中的字符数,它的长度,就我所知,它会变慢.

如果性能可以接受,您需要检查数据.