微信全文搜索技術優化
一、iOS 微信全文搜索技術的現狀
全文搜索是使用倒排索引進行搜索的一種搜索方式。倒排索引也稱爲反向索引,是指對輸入的內容中的每個Token
建立一個索引,索引中保存了這個Token
在內容中的具體位置。全文搜索技術主要應用在對大量文本內容進行搜索的場景。
微信終端涉及到大量文本搜索的業務場景主要包括聯繫人、聊天記錄、收藏的搜索。這些搜索功能從 2014 年上線至今,已經多年沒有更新底層搜索技術,聊天記錄使用的全文搜索引擎還是 SQLite FTS3,而現在已經有 SQLite FTS5,收藏首頁的搜索還是使用簡單的Like
語句去匹配文本,聯繫人搜索甚至用的是內存搜索(在內存中遍歷所有聯繫人的所有屬性進行匹配)。隨着用戶在微信上積累的數據越來越多,提升微信底層搜索技術的需求也越來越迫切。在 2021 年,我們對 iOS 微信的全文搜索技術進行了一次全面升級,本文主要介紹本次技術升級的工作經驗。
二、全文搜索引擎的選型與優化
1、搜索引擎選型
iOS 客戶端可以使用的全文搜索引擎並不多,主要有 SQLite 三個版本的 FTS 組件、Lucene 的 C++ 實現版本 CLucene 和 C 語言橋接版本 Lucy。這裏給出了這些引擎在事務能力、技術風險、搜索能力、讀寫性能等方面的比較。
在事務能力方面,Lucene 沒有提供完整的事務能力,因爲 Lucene 使用了多文件的存儲結構,它沒有保證事務的原子性。SQLite 的 FTS 組件因爲底層還是使用普通的表來實現的,可以完美繼承 SQLite 的事務能力。
在技術風險方面,Lucene 主要應用於服務端,在客戶端沒有大規模應用的案例,而且 CLucene 和 Lucy 自 2013 年後官方都停止維護了,技術風險較高。SQLite 的 FTS3 和 FTS4 組件則是屬於 SQLite 的舊版本引擎,官方維護不多了,而且這兩個版本都是將一個詞的索引存到一條記錄中,極端情況下有超出 SQLite 單條記錄最大長度限制的風險。SQLite 的 FTS5 組件作爲最新版本引擎也已經推出超過六年了,在安卓微信上也已經全量應用,所以技術風險是最低的。
在搜索能力方面,Lucene 的發展歷史比 SQLite 的 FTS 組件長很多,搜索能力相比也是最豐富的。特別是 Lucene 有豐富的搜索結果評分排序機制,但這個在微信客戶端沒有應用場景。因爲我們的搜索結果要麼是按照時間排序,要麼是按照一些簡單的自定義規則排序。在 SQLite 幾個版本的引擎中,FTS5 的搜索語法更加完備嚴謹,提供了很多接口給用戶自定義搜索函數,所以搜索能力也相對強一點。
在讀寫性能方面,下面是用不同引擎對 100 萬條長度爲 10 的隨機生成中文語句生成 Optimize 狀態的索引的性能數據,其中每個語句的漢字出現頻率按照實際的漢字使用頻率:
可以看到,Lucene 讀取命中數量的性能比 SQLite 好很多,說明 Lucene 索引的文件格式很有優勢,但是微信沒有隻讀取命中數量的應用場景,Lucene 的其他性能數據跟 SQLite 的差距不明顯。SQLite FTS3 和 FTS5 的大部分性能很接近,FTS5 索引的生成耗時比 FTS3 高一截,這個有優化方法。
綜合考慮這些因素,我們選擇 SQLite FTS5 作爲 iOS 微信全文搜索的搜索引擎。
2、實現 FTS5 的 Segment 自動 Merge 機制
SQLite FTS5 會把每個事務寫入的內容保存成一個獨立的 b 樹,稱爲一個segment
,segment
中保存了本次寫入內容中的每個詞在本次內容中行號(rowid
)、列號和字段中的每次出現的位置偏移,所以這個segment
就是該內容的倒排索引。多次寫入就會形成多個segment
,查詢時就需要分別查詢這些segment
再彙總結果,從而segment
數量越多,查詢速度越慢。
爲了減少segment
的數量,SQLite FTS5 引入了merge
機制。新寫入的segment
的level
爲 0,merge
操作可以把level
爲i
的現有segment
合併成一個level
爲i+1
的新的segment
。merge
的示例如下:
FTS5 默認的merge
操作有兩種:
-
某一個
level
的segment
達到4
時就開始在寫入內容時自動執行一部分merge
操作,稱爲一次automerge
。每次automerge
的寫入量跟本次更新的寫入量成正比,需要多次automerge
才能完整合併成一個新segment
。Automerge
在完整生成一個新的segment
前,需要多次裁剪舊的segment
的已合併內容,引入多餘的寫入量。 -
本次寫入後某一個
level
的segment
數量達到 16 時,一次性合併這個level
的segment
,稱爲crisismerge
。
FTS5 的默認merge
操作都是在寫入時同步執行的,會對業務邏輯造成性能影響,特別是crisismerge
會偶然導致某一次寫入操作特別久,這會讓業務性能不可控。之前的測試中 FTS5 的建索引耗時較久,也主要因爲 FTS5 的merge
操作比其他兩種引擎更加耗時。
我們在 WCDB 中實現 FTS5 的segment
自動merge
機制,將這些merge
操作集中到一個單獨子線程執行,並且優化執行參數,具體如下:
-
監聽有 FTS5 索引的數據庫每個事務變更到的 FTS5 索引表,拋通知到子線程觸發 WCDB 的自動
merge
操作。 -
Merge 線程檢查所有 FTS5 索引表中
segment
數超過1
的 level 執行一次merge
。 -
Merge
時每寫入16
頁數據檢查一次有沒有其他線程的寫入操作因爲merge
操作阻塞,如果有就立即commit
,儘量減小merge
對業務性能的影響。
自動merge
邏輯執行的流程圖如下:
限制每個level
的segment
數量爲1
,可以讓 FTS5 的查詢性能最接近optimize
(所有segment
合併成一個)之後的性能,而且引入的寫入量是可接受的。假設業務每次寫入量爲M
,寫入了N
次,那麼在 merge 執行完整之後,數據庫實際寫入量爲 MN(log2(N)+1)。業務批量寫入,提高M
也可以減小總寫入量。
性能方面,對一個包含 100w 條中文內容,每條長度 100 漢字的 fts5 的表查詢三個詞,optimize
狀態下耗時2.9ms
,分別限制每個level
的segment
數量爲2
、3
、4
時的查詢耗時分別爲4.7ms
、8.9ms
、15ms
。100w 條內容每次寫入 100 條的情況下,按照 WCDB 的方案執行merge
的耗時在10s
內。
使用自動Merge
機制,可以在不影響索引更新性能的情況下,將 FTS5 索引保持在最接近Optimize
的狀態,提高了搜索速度。
3、分詞器優化
分詞器性能優化
分詞器是全文搜索的關鍵模塊,它實現將輸入內容拆分成多個Token
並提供這些Token
的位置,搜索引擎再對這些Token
建立索引。SQLite 的 FTS 組件支持自定義分詞器,可以按照業務需求實現自己的分詞器。
分詞器的分詞方法可以分爲按字分詞和按詞分詞。前者只是簡單對輸入內容逐字建立索引,後者則需要理解輸入內容的語義,對有具體含義的詞組建立索引。相比於按字分詞,按詞分詞的優勢是既可以減少建索引的Token
數量,也可以減少搜索時匹配的Token
數量,劣勢是需要理解語義,而且用戶輸入的詞不完整時也會有搜不到的問題。
爲了簡化客戶端邏輯和避免用戶漏輸內容時搜不到的問題,iOS 微信之前的 FTS3 分詞器OneOrBinaryTokenizer
是採用了一種巧妙的按字分詞算法,除了對輸入內容逐字建索引,還會對內容中每兩個連續的字建索引,對於搜索內容則是按照每兩個字進行分詞。下面是一個用 “北京歡迎你” 去搜索相同內容的分詞例子:
相比於簡單的按字分詞,這種分詞方式的優勢是可以將搜索時匹配的Token
數量接近降低一半,提高搜索速度,而且在一定程度上可以提升搜索精度,比如搜索 “歡迎你北京” 就匹配不到“北京歡迎你”;這種分詞方式的劣勢就是保存的索引內容很多,基本輸入內容的每個字都在索引中保存了三次,是一種用空間換時間的做法。
因爲OneOrBinaryTokenizer
用接近三倍的索引內容增長才換取不到兩倍的搜索性能提升,不是很划算,所以我們在 FTS5 上重新開發了一種新的分詞器VerbatimTokenizer
,這個分詞器只採用基本的按字分詞,不保存冗餘索引內容。同時在搜索時,每兩個字用引號引起來組成一個Phrase
,按照 FTS5 的搜索語法,搜索時Phrase
中的字要按順序相鄰出現的內容纔會命中,實現了跟OneOrBinaryTokenizer
一樣的搜索精度。VerbatimTokenizer
的分詞規則示意圖如下:
分詞器能力擴展
VerbatimTokenizer 還根據微信實際的業務需求實現了五種擴展能力來提高搜索的容錯能力:
-
支持在分詞時將繁體字轉換成簡體字。這樣用戶可以用繁體字搜到簡體字內容,用簡體字也能搜到繁體字內容,避免了因爲漢字的簡體和繁體字形相近導致用戶輸錯的問題。
-
支持 Unicode 歸一化。Unicode 支持相同字形的字符用不同的編碼來表示,比如編碼爲
\ue9
的é
和編碼爲\u65\u301
的é
有相同的字形,這會導致用戶用看上去一樣的內容去搜索結果搜不到的問題。Unicode 歸一化就是把字形相同的字符用同一個編碼表示。 -
支持過濾符號。大部分情況下,我們不需要支持對符號建索引,符號的重複量大而且用戶一般也不會用符號去搜索內容,但是聯繫人搜索這個業務場景需要支持符號搜索,因爲用戶的暱稱裏面經常出現顏文字,符號的使用量不低。
-
支持用
Porter Stemming
算法對英文單詞取詞幹。取詞幹的好處是允許用戶搜索內容的單複數和時態跟命中內容不一致,讓用戶更容易搜到內容。但是取詞幹也有弊端,比如用戶要搜索的內容是 “happyday”,輸入“happy” 作爲前綴去搜索卻會搜不到,因爲 “happyday” 取詞幹變成 “happydai”,“happy” 取詞幹變成“happi”,後者就不能成爲前者的前綴。這種 badcase 在內容爲多個英文單詞拼接一起時容易出現,聯繫人暱稱的拼接英文很常見,所以在聯繫人的索引中沒有取詞幹,在其他業務場景中都用上了。 -
支持將字母全部轉成小寫。這樣用戶可以用小寫搜到大寫,反之亦然。
這些擴展能力都是對建索引內容和搜索內容中的每個字做變換,這個變換其實也可以在業務層做,其中的 Unicode 歸一化和簡繁轉換以前就是在業務層實現的。但是這樣做有兩個弊端,一個是業務層每做一個轉換都需要對內容做一次遍歷,引入冗餘計算量,另一個是寫入到索引中的內容是轉變後的內容,那麼搜索出來的結果也是轉變後的,會和原文不一致,業務層做內容判斷的時候容易出錯。鑑於這兩個原因,VerbatimTokenizer
將這些轉變能力都集中到了分詞器中實現。
4、索引內容支持多級分隔符
SQLite 的 FTS 索引表不支持在建表後再添加新列,但是隨着業務的發展,業務數據支持搜索的屬性會變多,如何解決新屬性的搜索問題呢?特別是在聯繫人搜索這個業務場景,一個聯繫人支持搜索的字段非常多。一個直接的想法是將新屬性和舊屬性用分隔符拼接到一起建索引。但這樣會引入新的問題,FTS5 是以整個字段的內容作爲整體去匹配的,如果用戶搜索匹配的Token
在不同的屬性,那這條數據也會命中,這個結果顯然不是用戶想要的,搜索結果的精確度就降低了。
我們需要搜索匹配的Token
中間不存在分隔符,那這樣可以確保匹配的Token
都在一個屬性內。同時,爲了支持業務靈活擴展,還需要支持多級分隔符,而且搜索結果中還要支持獲取匹配結果的層級、位置以及該段內容的原文和匹配詞。這個能力 FTS5 還不沒有,而 FTS5 的自定義輔助函數支持在搜索時獲取到所有命中結果中每個命中Token
的位置,利用這個信息可以推斷出這些Token
中間有沒有分隔符,以及這些Token
所在的層級,所以我們開發了SubstringMatchInfo
這個新的 FTS5 搜索輔助函數來實現這個能力。這個函數的大致執行流程如下:
三、全文搜索應用邏輯優化
1、數據庫表格式優化
1.1 非文本搜索內容的保存方式
在實際應用中,我們除了要在數據庫中保存需要搜索的文本的 FTS 索引,還需要額外保存這個文本對應的業務數據的id
、用於結果排序的的屬性(常見的是業務數據的創建時間)以及其他需要直接跟隨搜索結果讀出的內容,這些都是不參與文本搜索的內容。根據非文本搜索內容的不同存儲位置,我們可以將 FTS 索引表的表格式分成兩種:
- 第一種方式是將非文本搜索內容存儲在額外的普通表中,這個表保存 FTS 索引的
Rowid
和非文本搜索內容的映射關係,而 FTS 索引表的每一行只保存可搜索的文本內容,這個表格式類似於這樣:
這種表格式的優勢是 FTS 索引表的內容很簡單,不熟悉 FTS 索引表配置的同學不容易出錯,而且普通表的可擴展性好,支持添加新列;劣勢則是搜索時需要先用 FTS 索引的Rowid
讀取到普通表的Rowid
,這樣才能讀取到普通表的其他內容,搜索速度慢一點,而且搜索時需要聯表查詢,搜索 SQL 語句稍微複雜一點。
- 第二種方式是將非文本搜索內容直接和可搜索文本內容一起存儲在 FTS 索引表中,表格式類似於這樣:
這種方式的優劣勢跟前一種方式恰好相反,優勢是搜索速度快而且搜索方式簡單,劣勢是擴展性差且需要更細緻的配置。
因爲 iOS 微信以前是使用第二種表格式,而且微信的搜索業務已經穩定不會有大變化,我們現在更加追求搜索速度,所以我們還是繼續使用第二種表格式來存儲全文搜索的數據。
1.2 避免冗餘索引內容
FTS 索引表默認對錶中的每一列的內容都建倒排索引,即便是數字內容也會按照文本來處理,這樣會導致我們保存在 FTS 索引表中的非文本搜索內容也建了索引,進而增大索引文件的大小、索引更新的耗時和搜索的耗時,這顯然不是我們想要的。
FTS5 支持給索引表中的列添加UNINDEXED
約束,這樣 FTS5 就不會對這個列建索引了,所以給可搜索文本內容之外的所有列添加這個約束就可以避免冗餘索引。
1.3 降低索引內容的大小
前面提到,倒排索引主要保存文本中每個Token
對應的行號(rowid
)、列號和字段中的每次出現的位置偏移,其中的行號是 SQLite 自動分配的,位置偏移是根據業務的實際內容,這兩個我們都決定不了,但是列號是可以調整的。
在 FTS5 索引中,一個Token
在一行中的索引內容的格式是這樣的:
從中可以看出,如果我們把可搜索文本內容設置在第一列的話(多個可搜索文本列的話,把內容多的列放到第一列),就可以少保存列分割符0x01
和列號,這樣可以明顯降低索引文件大小。
所以我們最終的表格式是這樣:
1.4 索引文件大小優化數據
下面是 iOS 微信優化前後的平均每個用戶的索引文件大小對比:
2、索引更新邏輯優化
爲了將全文搜索邏輯和業務邏輯解耦,iOS 微信的 FTS 索引是不保存在各個業務的數據庫中的,而是集中保存到一個專用的全文搜索數據庫,各個業務的數據有更新之後再異步通知全文搜索模塊更新索引。整體流程如下:
這樣做既可以避免索引更新拖慢業務數據更新的速度,也能避免索引數據更新出錯甚至索引數據損壞對業務造成影響,讓全文搜索功能模塊能夠充分獨立。
2.1 保證索引和數據的一致
業務數據和索引數據分離且異步同步的好處很多,但實現起來也很難,最難的問題是如何保證業務數據和索引數據的一致,也即要保證業務數據和索引數據要逐條對應,不多不少。曾經 iOS 微信在這裏踩了很多坑,打了很多補丁都不能完整解決這個問題,我們需要一個更加體系化的方法來解決這個問題。
爲了簡化問題,我們可以把一致性問題可以拆成兩個方面分別處理,一個是保證所有業務數據都有索引,這個用戶的搜索結果就不會有缺漏;第二個是保證所有索引都對應一個有效的業務數據,這樣用戶就不會搜到無效的結果。
要保證所有業務數據都有索引,首先要找到或者構造一種一直增長的數據來描述業務數據更新的進度,這個進度數據的更新和業務數據的更新能保證原子性,而且根據這個進度的區間能拿出業務數據更新的內容,這樣我們就可以依賴這個進度來更新索引。在微信的業務中,不同業務的進度數據不同,聊天記錄是使用消息的rowid
,收藏是使用收藏跟後臺同步的updateSequence
,而聯繫人找不到這種一直增長的進度數據,我們是通過在聯繫人數據庫中標記有新增或有更新的聯繫人的微信號來作爲索引更新進度。進度數據的使用方法如下:
無論業務數據是否保存成功、更新通知是否到達全文搜索模塊、索引數據是否保存成功,這套索引更新邏輯都能保證保存成功的業務數據都能成功建到索引。這其中的一個關鍵點是數據和進度要在同個事務中一起更新,而且要保存在同個數據庫中,這樣才能保證數據和進度的更新的原子性(WCDB 創建的數據庫因爲使用WAL
模式而無法保證不同數據庫的事務的原子性)。還有一個操作圖中沒有畫出,具體是微信啓動時如果檢查到業務進度小於索引進度,這種一般意味着業務數據損壞後被重置了,這種情況下要刪掉索引並重置索引進度。
對於每個索引都對應有效的業務數據,這就要求業務數據刪除之後索引也要必須刪掉。現在業務數據的刪除和索引的刪除是異步的,會出現業務數據刪掉之後索引沒刪除的情況。這種情況會導致兩個問題,一個是冗餘索引會導致搜索速度變慢,但這個問題出現概率很小,這個影響可以忽略不計;第二個問題是會導致用戶搜到無效數據,這個是要避免的。因爲要完全刪掉所有無效索引成本比較高,所以我們採用了惰性檢查的方法來解決這個問題,具體做法是搜索結果要顯示給用戶時,才檢查這個數據是否有效,無效的話不顯示這個搜索結果並異步刪除對應的索引。因爲用戶一屏能看到的數據很少,所以檢查邏輯帶來的性能消耗也可以忽略不計。而且這個檢查操作實際上也不算是額外加的邏輯,爲了搜索結果展示內容的靈活性,我們也要在展示搜索結果時讀出業務數據,這樣也就順帶做了數據有效性的檢查。
2.2 建索引速度優化
索引只有在搜索的時候纔會用到,它的更新優先級並沒有業務數據那麼高,可以儘量攢更多的業務數據纔去批量建索引。批量建索引有以下三個好處:
-
減少磁盤的寫入次數,提高平均建索引速度。
-
在一個事務中,建索引 SQL 語句的解析結果可以反覆使用,可以減少 SQL 語句的解析次數,進而提高平均建索引速度。
-
減少生成 Segment 的數量,從而減少
Merge Segment
帶來的讀寫消耗。
當然,也不能保留太多業務數據不建索引,這樣用戶要搜索時會來不及建索引,從而導致搜索結果不完整。有了前面的Segment
自動Merge
機制,索引的寫入速度非常可控,只要控制好量,就不用擔心批量建索引帶來的高耗時問題。我們綜合考慮了低端機器的建索引速度和搜索頁面的拉起時間,確定了最大批量建索引數據條數爲 100 條。同時,我們會在內存中 cache 本次微信運行期間產生的未建索引業務數據,在極端情況下給沒有來得及建索引的業務數據提供相對內存搜索,保證搜索結果的完整性。因爲 cache 上一次微信運行期間產生的未建索引數據需要引入額外的磁盤 IO,所以微信啓動後會觸發一次建索引邏輯,對現有的未建索引業務數據建一次索引。總結一下觸發建索引的時機有三個:
-
未建索引業務數據達到 100 條。
-
進入搜索界面。
-
微信啓動。
2.3 刪除索引速度優化
索引的刪除速度經常是設計索引更新機制時比較容易忽視的因素,因爲被刪除的業務數據量容易被低估,會被誤以爲是低概率場景,但實際被用戶刪除的業務數據可能會達到 50%,是個不可忽視的主場景。而且 SQLite 是不支持並行寫入的,刪除索引的性能也會間接影響到索引的寫入速度,會爲索引更新引入不可控因素。
因爲刪除索引的時候是拿着業務數據的 id 去刪除的,所以提高刪除索引速度的方式有兩種:
-
建一個業務數據
id
到 FTS 索引的rowid
的普通索引。 -
在 FTS 索引表中去掉業務數據
Id
那一列的UNINDEXED
約束,給業務數據Id
添加倒排索引。
這裏倒排索引其實沒有普通索引那麼高效,有兩個原因:
-
倒排索引相比普通索引還帶了很多額外信息,搜索效率低一些。
-
如果需要多個業務字段才能確定一條倒排索引時,倒排索引是建不了聯合索引的,只能匹配其中一個業務字段,其他字段就是遍歷匹配,這種情況搜索效率會很低。
2.4 索引更新性能優化數據
聊天記錄的優化前後索引性能數據如下:
收藏的優化前後索引性能數據如下:
3、搜索邏輯優化
用戶在 iOS 微信的首頁輸入內容搜索時,搜索的整體流程如下:
用戶變更搜索框的內容之後,會並行發起所有業務的搜索任務,各個搜索任務執行完之後纔再將搜索結果返回到主線程給頁面展示。這個邏輯會隨着用戶變更搜索內容而繼續重複。
3.1 單個搜索任務支持並行執行
雖然現在不同搜索任務已經支持並行執行,但是不同業務的數據量和搜索邏輯差別很大,數據量大或者搜索邏輯複雜的任務耗時會很久,這樣還不能充分發揮手機的並行處理能力。我們還可以將並行處理能力引入單個搜索任務內,這裏有兩種處理方式:
-
對於搜索數據量大的業務(比如聊天記錄搜索),可以將索引數據均分存儲到多個 FTS 索引表(注意這裏不均分的話還是會存在短板效應),這樣搜索時可以並行搜索各個索引表,然後彙總各個表的搜索結果,再進行統一排序。這裏拆分的索引表數量既不能太多也不能太少,太多會超出手機實際的並行處理能力,也會影響其他搜索任務的性能,太少又不能充分利用並行處理能力。以前微信用了十個 FTS 表存儲聊天記錄索引,現在改爲使用四個 FTS 表。
-
對於搜索邏輯複雜的業務(比如聯繫人搜索),可以將可獨立執行的搜索邏輯並行執行。比如在聯繫人搜索任務中,我們將聯繫人的普通文本搜索、拼音搜索、標籤和地區的搜索、多羣成員的搜索並行執行,搜完之後再合併結果進行排序。這裏爲什麼不也用拆表的方式呢?因爲這種搜索結果數量少的場景,搜索的耗時主要是集中在搜索索引的環節,索引可以看做一顆 B 樹,將一顆 B 樹拆分成多個,搜索耗時並不會成比例下降。
3.2 搜索任務支持中斷
用戶在搜索框持續輸入內容的過程中可能會自動多次發起搜索任務,如果在前一次發起的搜索任務還沒執行完時,就再次發起搜索任務,那前後兩次搜索任務就會互相影響對方性能。這種情況在用戶輸入內容從短到長的過程中還挺容易出現的,因爲搜索文本短的時候命中結果就很多,搜索任務也就更加耗時,從而更有機會撞上後面的搜索任務。太多任務同時執行還會容易引起手機發燙、爆內存的問題。所以我們需要讓搜索任務支持隨時中斷,這樣就可以在後一次搜索任務發起的時候,能夠中斷前一次的搜索任務,避免任務量過多的問題。
搜索任務支持中斷的實現方式是給每個搜索任務設置一個CancelFlag
,在搜索邏輯執行時每搜到一個結果就判斷一下CancelFlag
是否置位,如果置位了就立即退出任務。外部邏輯可以通過置位CancelFlag
來中斷搜索任務。邏輯流程如下圖所示:
爲了讓搜索任務能夠及時中斷,我們需要讓檢查CancelFlag
的時間間隔儘量相等,要實現這個目標就要在搜索時避免使用 OrderBy 子句對結果進行排序。因爲 FTS5 不支持建立聯合索引,所以在使用OrderBy
子句時,SQLite 在輸出第一個結果前會遍歷所有匹配結果進行排序,這就讓輸出第一個結果的耗時幾乎等於輸出全部結果的耗時,中斷邏輯就失去了意義。不使用OrderBy
子句就對搜索邏輯添加了兩個限制:
-
從數據庫讀取所有結果之後再排序。我們可以在讀取結果時將用於排序的字段一併讀出,然後在讀完所有結果之後再對所有結果執行排序。因爲排序的耗時佔總搜索耗時的比例很低,加上排序算法的性能大同小異,這種做法對搜索速度的影響可以忽略。
-
不能使用分段查詢。在全文搜索這個場景中,分段查詢其實是沒有什麼作用的。因爲分段查詢就要對結果排序,對結果排序就要遍歷所有結果,所以分段查詢並不能降低搜索耗時(除非按照 FTS 索引的
Rowid
分段查詢,但是Rowid
不包含實際的業務信息)。
3.3 搜索讀取內容最少化
搜索時讀取內容的量也是決定搜索耗時的一個關鍵因素。FTS 索引表實際是有多個 SQLite 普通表組成的,這其中一些表格存儲實際的倒排索引內容,還有一個表格存儲用戶保存到 FTS 索引表的全部原文。當搜索時讀取Rowid
以外的內容時,就需要用Rowid
到保存原文的表的讀取內容,索引表輸出結果的內部執行過程如下:
所以讀取內容越少輸出結果的速度越快,而且讀取內容過多也會有消耗內存的隱患。我們採用的方式是搜索時只讀取業務數據 id 和用於排序的業務屬性,排好序之後,在需要給用戶展示結果時,才用業務數據 id 按需讀取業務數據具體內容出來展示。這樣做的擴展性也會很好,可以在不更改存儲內容的情況下,根據各個業務的需求不斷調整搜索結果展示的內容。
這裏還有一個要特別提一下的地方,就是搜索時儘量不要讀取高亮信息(SQLite 的highlight
函數有這個能力)。因爲要獲取高亮字段不僅要將文本的原文讀取出來,還要對文本原文再次分詞,才能定位命中位置的原文內容,搜索結果多的情況下分詞帶來的消耗非常明顯。那展示搜索結果時如何獲取高亮匹配內容呢?我們採用的方式是將用戶的搜索文本進行分詞,然後在展示結果時查找每個Token
在展示文本中的位置,然後將那個位置高亮顯示。同樣因爲用戶一屏看到的結果數量是很少的,這裏的高亮邏輯帶來的性能消耗可以忽略。
當然在搜索規則很複雜的情況下,直接讀取高亮信息是比較方便,比如聯繫人搜索就使用前面提到的SubstringMatchInfo
函數來讀取高亮內容。這裏主要還是因爲要讀取匹配內容所在的層級和位置用於排序,所以逐個結果重新分詞的操作在所難免。
3.4 搜索性能優化數據
下面是微信各搜索業務優化前後的搜索耗時對比:
四、總結
目前 iOS 微信已經將這套新全文搜索技術方案全量應用到聊天記錄、聯繫人和收藏的搜索業務中。使用新方案之後,全文搜索的索引文件佔用空間更小,索引更新耗時更少,搜索速度也更快了,可以說全文搜索的性能得到了全方位提升。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/2L4fYm5WPtPQSv9WzzHg_A