單表千萬行資料庫 LIKE 搜尋最佳化手記

我們經常在資料庫中使用 LIKE 運算子來完成對資料的模糊搜尋，LIKE 運算子用於在 WHERE 子句中搜索列中的指定模式。

如果需要查詢客戶表中所有姓氏是“張”的資料，可以使用下面的 SQL 語句：

SELECT * FROM Customer WHERE Name LIKE '張%'

如果需要查詢客戶表中所有手機尾號是“1234”的資料，可以使用下面的 SQL 語句：

SELECT * FROM Customer WHERE Phone LIKE '%123456'

如果需要查詢客戶表中所有名字中包含“秀”的資料，可以使用下面的 SQL 語句：

SELECT * FROM Customer WHERE Name LIKE '%秀%'

以上三種分別對應了：左字首匹配、右後綴匹配和模糊查詢，並且對應了不同的查詢最佳化方式。

資料概覽

現在有一張名為 tbl_like 的資料表，表中包含了四大名著中的全部語句，資料條數上千萬：

左字首匹配查詢最佳化

如果要查詢所有以“孫悟空”開頭的句子，可以使用下面的 SQL 語句：

SELECT * FROM tbl_like WHERE txt LIKE '孫悟空%'

SQL Server 資料庫比較強大，耗時八百多毫秒，並不算快：

我們可以在 txt 列上建立索引，用於最佳化該查詢：

CREATE INDEX tbl_like_txt_idx ON [tbl_like] ( [txt] )

應用索引後，查詢速度大大加快，僅需 5 毫秒：

由此可知：對於左字首匹配，我們可以透過增加索引的方式來加快查詢速度。

右後綴匹配查詢最佳化

在右後綴匹配查詢中，上述索引對右後綴匹配並不生效。使用以下 SQL 語句查詢所有以“孫悟空”結尾的資料：

SELECT * FROM tbl_like WHERE txt LIKE '%孫悟空'

效率十分低下，耗時達到了 2.5秒：

我們可以採用“以空間換時間”的方式來解決右後綴匹配查詢時效率低下的問題。

簡單來說，我們可以將字串倒過來，讓右後綴匹配變成左字首匹配。以“防著古海回來再抓孫悟空”為例，將其倒置之後的字串是“空悟孫抓再來回海古著防”。當需要查詢結尾為“孫悟空”的資料時，去查詢以“空悟孫”開頭的資料即可。

具體做法是：在該表中增加“txt_back”列，將“txt”列的值倒置後，填入“txt_back”列中，最後為 “txt_back”列增加索引。

ALTER TABLE tbl_like ADD txt_back nvarchar(1000);-- 增加資料列
UPDATE tbl_like SET txt_back = reverse(txt); -- 填充 txt_back 的值
CREATE INDEX tbl_like_txt_back_idx ON [tbl_like] ( [txt_back] );-- 為 txt_back 列增加索引

資料表調整之後，我們的 SQL 語句也需要調整：

SELECT * FROM tbl_like WHERE txt_back LIKE '空悟孫%'

此番操作下來，執行速度就非常迅速了：

由此可知：對於右後綴匹配，我們可以建立倒序欄位將右後綴匹配變成左字首匹配來加快查詢速度。

模糊查詢最佳化

在查詢所有包含“悟空”的語句時，我們使用以下的 SQL 語句：

SELECT * FROM tbl_like WHERE txt LIKE '%悟空%'

該語句無法利用到索引，所以查詢非常慢，需要 2.7 秒：

遺憾的是，我們並沒有一個簡單的辦法可以最佳化這個查詢。但沒有簡單的辦法，並不代表沒有辦法。解決辦法之一就是：分詞+倒排索引。

分詞就是將連續的字序列按照一定的規範重新組合成詞序列的過程。我們知道，在英文的行文中，單詞之間是以空格作為自然分界符的，而中文只是字、句和段能透過明顯的分界符來簡單劃界，唯獨詞沒有一個形式上的分界符，雖然英文也同樣存在短語的劃分問題，不過在詞這一層上，中文比之英文要複雜得多、困難得多。

倒排索引源於實際應用中需要根據屬性的值來查詢記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的檔案我們稱為倒排索引檔案，簡稱倒排檔案(inverted file)。

以上兩段讓人摸不著頭腦的文字來自百度百科，你可以和我一樣選擇忽略他。

我們不需要特別高超的分詞技巧，因為漢語的特性，我們只需“二元”分詞即可。

所謂二元分詞，即將一段話中的文字每兩個字元作為一個詞來分詞。還是以“防著古海回來再抓孫悟空”這句話為例，進行二元分詞之後，得到的結果是：防著、著古、古海，海回，回來，來再，再抓，抓孫，孫悟，悟空。使用 C# 簡單實現一下：

public static List<String> Cut(String str)
{
       var list = new List<String>();
       var buffer = new Char[2];
       for (int i = 0; i < str.Length - 1; i++)
       {
             buffer[0] = str[i];
             buffer[1] = str[i + 1];
             list.Add(new String(buffer));
       }
       return list;
}

測試一下結果：

我們需要一張資料表，把分詞後的詞條和原始資料對應起來，為了獲得更好的效率，我們還用到了覆蓋索引：

CREATE TABLE tbl_like_word (
  [id] int identity,
  [rid] int NOT NULL,
  [word] nchar(2) NOT NULL,
  PRIMARY KEY CLUSTERED ([id])
);
CREATE INDEX tbl_like_word_word_idx ON tbl_like_word(word,rid);-- 覆蓋索引（Covering index）

以上 SQL 語句建立了一張名為 ”tbl_like_word“的資料表，併為其 ”word“和“rid”列增加了聯合索引。這就是我們的倒排表，接下來就是為其填充資料。

為了便於演示，筆者使用了 LINQPad 來做資料處理，對該工具感興趣的朋友，可以參看筆者之前的文章：《.NET 程式設計師的 Playground ：LINQPad》，文章中對 LINQPad 做了一個簡要的介紹，連結地址是：https://www.coderbusy.com/archives/432.html 。

我們需要先用 LINQPad 自帶的資料庫連結功能連結至資料庫，之後就可以在 LINQPad 中與資料庫互動了。首先按 Id 順序每 3000 條一批讀取 tbl_like 表中的資料，對 txt 欄位的值分詞後生成 tbl_like_word 所需的資料，之後將資料批次入庫。完整的 LINQPad 程式碼如下：

void Main()
{
       var maxId = 0;
       const int limit = 3000;
       var wordList = new List<Tbl_like_word>();
       while (true)
       {
             $"開始處理：{maxId} 之後 {limit} 條".Dump("Log");
             //分批次讀取
             var items = Tbl_likes
             .Where(i => i.Id > maxId)
             .OrderBy(i => i.Id)
             .Select(i => new { i.Id, i.Txt })
             .Take(limit)
             .ToList();
             if (items.Count == 0)
             {
                    break;
             }
             //逐條生產
             foreach (var item in items)
             {
                    maxId = item.Id;
                    //單個字的資料跳過
                    if (item.Txt.Length < 2)
                    {
                           continue;
                    }
                    var words = Cut(item.Txt);
                    wordList.AddRange(words.Select(str => new Tbl_like_word {  Rid = item.Id, Word = str }));
             }
       }
       "處理完畢，開始入庫。".Dump("Log");
       this.BulkInsert(wordList);
       SaveChanges();
       "入庫完成".Dump("Log");
}
// Define other methods, classes and namespaces here
public static List<String> Cut(String str)
{
       var list = new List<String>();
       var buffer = new Char[2];
       for (int i = 0; i < str.Length - 1; i++)
       {
             buffer[0] = str[i];
             buffer[1] = str[i + 1];
             list.Add(new String(buffer));
       }
       return list;
}

以上 LINQPad 指令碼使用 Entity Framework Core 連線到了資料庫，並引用了 NuGet 包“EFCore.BulkExtensions”來做資料批次插入。

之後，就可以把查詢安排上，先查詢倒排索引，然後關聯到主表：

SELECT TOP 10 * FROM tbl_like WHERE id IN (
SELECT rid FROM tbl_like_word WHERE word IN ('悟空'))

查詢速度很快，僅需十幾毫秒：

因為我們將所有的語句分成了二字元片語，所以當需要對單個字元模糊查詢時，直接使用 LIKE 是一個更加經濟的方案。如果需要查詢的字元多於兩個時，就需要對查詢詞進行分詞。如需查詢“東土大唐”一詞，構造出的查詢語句可能會是這樣：

SELECT TOP 10*FROM tbl_like WHERE id IN (
SELECT rid FROM tbl_like_word WHERE word IN ('東土','土大','大唐'))

但是，該查詢並不符合我們的預期，因為其將只包含“土大”的語句也篩選了出來：

我們可以採取一些技巧來解決這個問題，比如先 GROUP 一下：

SELECT TOP
    10 *
FROM
    tbl_like
WHERE
    id IN (
    SELECT
        rid
    FROM
        tbl_like_word
    WHERE
        word IN ( '東土', '土大', '大唐' )
    GROUP BY
        rid
    HAVING
    COUNT ( DISTINCT ( word ) ) = 3
    )

在上述 SQL 語句中，我們對 rid 進行了分組，並篩選出了不重複的片語數量是三個（即我們的查詢詞數量）的。於是，我們可以得到正確的結果：

由此可知：對於模糊查詢，我們可以透過分詞+倒排索引的方式最佳化查詢速度。

後記

雖然在講述時使用的是 SQL Server 資料庫，但是以上最佳化經驗對大部分關係型資料庫來說是通用的，比如 MySQL、Oracle 等。

如果你和筆者一樣在實際工作中使用 PostgreSQL 資料庫，那麼在做倒排索引時可以直接使用陣列型別並配置 GiN 索引，以獲得更好的開發和使用體驗。需要注意的是，雖然 PostgreSQL 支援函式索引，但是如果對函式結果進行 LIKE 篩選時，索引並不會命中。

對於 SQLite 這種小型資料庫，模糊搜尋並不能使用到索引，所以左字首搜尋和右後綴搜尋的最佳化方式對其不生效。不過，一般我們不會使用 SQLite 去儲存大量的資料，儘管分詞+倒排索引的最佳化方式也可以在 SQLite 中實現。