什么是 SQL Like 运算符的合适替代品以提高性能？

Question

我正在开发一个在 Windows Mobile 6 上运行的应用程序，该应用程序需要能够从项目表中检索项目描述字段中包含给定字符串（由最终用户提供）的所有项目。问题是表中大约有 170,000 个项目。由于我需要返回描述中任何位置包含该字符串的所有项目，因此我被迫使用 LIKE %string%，这消除了使用索引的任何机会。数据和表结构最初基于 Progress 数据库，该数据库在任何单词索引字段上都有一个出色的 contains 运算符。我们的移动应用程序并非如此，因为它使用 SQL Server Compact 3.5。

基本上，我的 DAL 运行查询并检索 SqlCeDataReader，然后使用 ItemFactory 创建仅包含匹配项的 List 对象。显然，这使我们能够将域/业务对象与数据访问层分开。

一切都很好，除了当我搜索描述中包含“高尔夫”之类的所有项目时检索项目所需的时间为 8 米和 42 秒。显然，这对于最终用户来说不是可接受的时间范围。

我的第一次尝试是使用“SELECT * FROM Item”（在主索引字段之一上使用 order by 子句）从数据库检索所有项目。此时，我在运行 SqlCeDataReader 时运行了 IndexOf 检查，并且让 ItemFactory 仅将项目添加到 List 对象（如果它们包含所请求的描述文本）。这将速度提高到 1m 46s。不算太破烂，但还是太慢了。

然后我尝试了另一种有希望的方法......几乎...当应用程序启动时，我尝试创建一个包含数据库中所有项目对象的列表（需要大约 2 分钟来运行查询并填充整个列表，但至少在应用程序初始化时只需要一次......仍然...啊）。列表完成后，我可以轻松地对该列表运行查询，执行以下操作（我希望我的语法是正确的......我现在不在工作，并且我所坐的电脑上没有 Visual Studio）：

List<Item> specificItems = 
    AllItems.FindAll(i => i.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0);

这种方法将时间缩短至 21 秒。非常好（尽管在宏伟的计划中仍然很慢）。然而，问题是，如果我从数据库加载所有项目，内存使用量太大。在初始加载期间，我实际上必须切断最后 20,000 个项目（因此 21 秒的时间范围可能更像 25 秒），因为抛出了 OutOfMemoryException。根据模拟器上的内存管理器，我仍然有大约 20 MB 的可用 RAM，但我听说一个进程只能有 32 MB 或与其关联的 RAM（不确定 WM 6 是否如此，但看起来所以）。

为了确保这不是因为我使用 List 对象来保存所有项目（我在其构造函数中使用所需的容量进行实例化，以避免动态调整大小），我还读过可能会导致额外的内存使用隐式调用 EnsureCapacity，我尝试使用 Item[] 数组（提前调整大小）。这仍然存在内存问题，并且大小差异可以忽略不计。

好吧，够漫漫的了。我知道我可能需要对数据读取器从数据库返回的记录进行一些限制（通过对不同类型字段的一些索引搜索），然后可能会在较小的项目子集上使用 indexOf 以获得最大性能（从而跳过 Like 运算符）。这将导致最终用户必须输入的不仅仅是描述搜索（可能是项目层次结构信息来限制要搜索的项目类型）。

有任何想法吗？我是否以错误的方式处理这个问题？

感谢您的聆听（抱歉这篇文章很长，我正在大声思考）。

哦，我应该添加（只是总结）我正在使用的内容：

• 视窗移动6
• SQL Server 紧凑版 3.5
• C#3.5

更新：虽然下面提到的布隆过滤器方法看起来很有趣，但我无法满足一项要求（我在上面没有真正指定）。我无法真正匹配其他单词中包含的单词（例如“club”不会返回“clubs”）。因此，我被迫完全使用不同的方法（肯特·弗雷德里克......感谢您指出了这一点）。我已将 Kent 的答案标记为正确的答案，因为他的方法满足了最多的要求（Mitch，您的答案与 Jaunder 建议的 Bloom 过滤器有类似的问题）。然而，我也采取了与他不同的方法（目前......）。

我所做的是将所有项目对象拉入内存，仅包含项目编号和描述（这使其处于内存限制之下，但它仍然导致初始化时间比我喜欢的要长......我猜多线程并在应用程序运行时在幕后加载该信息可以解决这个问题）。为了执行搜索，我编写了自己的包含例程。该例程是用非托管 C# 代码编写的，该代码使用两个指针和几个循环来运行描述和所需的匹配文本。如果它在描述中的任何位置找到匹配项，则会将项目编号添加到数组中。搜索完所有项目后，新查询将返回数据库并仅获取匹配的项目编号（由于整数字段上的索引，速度非常快）。然后，这些项目将在包含所有信息（而不仅仅是项目编号和描述）的列表中创建。整个操作大约需要 5 - 10 秒（取决于描述），目前来说已经足够了。

我仍然会考虑进一步优化它（也许能够跟踪搜索词有多少个字符......如果项目描述中剩余的字符少于所需文本，则循环可以直接继续到下一个项目）。

仍然欢迎任何建议。目前，我已将肯特的答案标记为对于我的问题“最正确”。

感谢 Dolch 帮助我编写 contains 例程。

Answer 1

我投票给了 米奇·麦斯 答案，但我也会测试一些技巧的有效性。

我对充满 [char],[int] 的表最大的担心是，您可能仍然会发现自己执行大量无意义的字符串比较，特别是如果您在这个新表上使用 %word% 。（重复但不匹配我们的搜索条目）。

我可能会选择尝试

Words
-----
chars  | word_id 

WordsToEntry
------------
word_id | entry_id 

看看数据库开销是否值得缓解这个可能的问题（我无法测试，抱歉）

Answer 2

如何预处理（一次）项目表（并且添加到其中的每个新条目都需要处理），以创建一个具有以下内容的单词出现表

CREATE TABLE WordItemOccurance
(
    [Word] varchar(50) not null,

    ItemId int not null
        constraint FK_Items references ItemTable(ID)
)

迭代所有项目，分解成单独的单词，并在找到条目时将其添加到出现表中。

在 [Word] 上创建聚集索引并在 ItemId 上加入 Item 表应该很快。

Answer 3

您可以尝试使用布隆过滤器。

1. 维基百科
2. 使用 Bloom 过滤 器