什麼是SQL Like操作符的合適替代方法來提高性能？

Question

我正在研究在Windows Mobile 6上運行的應用程序，該應用程序需要能夠從項目描述字段中包含給定字符串（由最終用戶提供）的項目表中檢索所有項目。問題是表中約有170,000個項目。由於我需要返回包含描述中任何位置字符串的所有項目，所以我不得不使用LIKE％字符串％，這消除了使用索引的機會。數據和表格結構最初基於一個Progress數據庫，它在任何字索引字段上都有一個美妙的contains操作符。我們的移動應用程序並非如此，因爲它使用SQL Server Compact 3.5。

基本上，我的DAL運行查詢並檢索SqlCeDataReader，然後使用ItemFactory創建僅包含匹配項的List對象。這顯然可以讓我們將我們的域/業務對象與數據訪問層分開。

除了8m和42s之外，當我搜索包含描述中的「高爾夫球」之類的東西時，需要檢索項目。顯然這對最終用戶來說不是一個可接受的時間框架。我的第一次嘗試是使用SELECT * FROM Item（在一個主索引字段中使用order by子句）從數據庫中取回所有項目，此時我跑過了一個IndexOf檢查SqlCeDataReader和ItemFactory只添加項目到列表對象，如果他們包含請求的描述文本。這提高了速度下降到1米46s。不是太破舊，但仍然太慢。

然後我試了另一種方法，顯示承諾......差不多......在應用程序啓動時，我嘗試創建一個包含數據庫中所有項目對象的列表（需要大約2分鐘來運行查詢並填充整個列表，但至少它只是一次app正在初始化...仍然...呃）。一旦列表是compl ete，我可以很容易地在該列表上運行查詢，如下所示（我希望我的語法是正確的......我現在不在工作，並且我沒有在我正坐在PC上的Visual Studio ）：

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

這種方法將其降低到21秒。非常好（儘管在宏偉計劃中仍然很慢）。但是，問題是，如果我加載數據庫中的所有項目，則內存使用情況太好了。在初始加載期間，我必須切斷最後的20,000個項目（所以21s的時間框架可能更像是25s），因爲OutOfMemoryException被拋出。據模擬器上的內存管理器，我仍然有大約20 MB的可用RAM，但我聽說一個進程只能有32 MB或RAM相關聯（不知道WM 6是否如此，但它似乎所以）。

爲了確保它不是因爲我使用List對象來保存所有項目（我在實例化其構造函數中需要的容量以避免動態調整大小），我也讀過這些項目可能會導致額外的內存使用情況時，它隱含調用EnsureCapacity，我嘗試使用Item []數組（提前大小）。這仍然有內存問題，尺寸差異可以忽略不計。

好吧，漫不經心。我知道我可能將不得不一些如何限制由DataReader的從數據庫返回的記錄（通過在不同類型字段的某些索引搜索），然後可能會使用上的項目，較小的子集的indexOf以獲得最大的性能（因此一起跳過Like操作符）。這會導致最終用戶不得不輸入更多的描述信息（可能是項目層次結構信息，以限制要搜索的項目類型）。

任何想法？我是否以這種錯誤的方式去做？

感謝收聽（對不起，這篇文章很長，我有點大聲思考）。

哦，我應該增加（只是在摘要）我正在使用：

• 的Windows Mobile 6
• SQL Server精簡版3.5
• C＃3.5

更新：雖然下面提到的布盧姆過濾器方法似乎很有趣，我無法滿足一個要求（我沒有真正指出）。我無法真正地匹配其他詞語中包含的詞（例如，「俱樂部」不會返回「俱樂部」）。由於這個原因，我被迫採用了不同的方法（肯特弗雷德裏克......感謝你指出了這一點）。我已經將肯特的答案標記爲正確的答案，因爲他的方法是滿足最多要求的方法（米奇，你的問題與布萊恩過濾器建議的類似問題）。但是，我已經採取了不同的方法（現在......）而不是他的方式。

我所做的是將所有項目對象拉入內存，只有項目編號和描述（它使內存限制，但它仍然會導致更長的初始化比我喜歡...多線程和加載在應用程序運行時幕後的信息可以照顧到我的猜測）。爲了執行搜索，我寫了我自己的包含例程。例程是用非託管的c＃代碼編寫的，它使用兩個指針和幾個循環來遍歷描述和所需的匹配文本。如果它在描述中的任何位置找到匹配項，則會將項目編號添加到數組中。一旦所有項目都被搜索完畢，一個新的查詢將返回到數據庫，並只抓取匹配的項目編號（由於整數字段上的索引，這個編號非常快）。然後，這些項目將在包含所有信息的列表中創建（不僅僅是項目編號和說明）。整個操作大約需要5-10秒（取決於描述），現在已經足夠了。

我仍會研究進一步的優化（可以跟蹤搜索項的字符數......如果項目描述中剩餘的字符少於所需文本，則循環可以直接繼續下一個項目）。

任何建議仍然歡迎。現在我已經將肯特的答案標記爲「我的問題最正確」。

支持Dolch幫助我編寫包含例程。

Answer 1

我投了Mitch Wheat's答案，但還有一些技巧，我也會測試的有效性。

我擔心有一個滿表[char]，[int]的表，你可能仍然會發現自己正在執行大量無意義的字符串比較，特別是如果你在這個新表上使用％word％。 （重複但不匹配我們的搜索條目）。

我可能會選擇與

Words 
----- 
chars | word_id 

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

experimeting，看看數據庫的開銷就是這個可能出現的問題值得緩解（我不能試驗，不好意思）

Answer 2

如何預處理（一次）的項目表（每個新條目添加到它需要被處理），在所有的項目，以形成具有

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

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

迭代一個字occurrance表，分解成單獨的單詞並在發現表中添加入口表。

在[Word]上創建聚集索引並加入ItemId上的Item表應該很快。

Answer 3

你可以嘗試使用布隆過濾器。

1. wikipedia
2. using bloom filters