[QUERY] IndexType： GIN - Full Text Search (FTS)

15th鐵人賽

後端里長伯 hohshen

2023-10-07 22:52:14

294 瀏覽

分享至

IndexType: GIN-Full Text Search

前言

是否曾經想過該如何做出有效率的字典搜尋呢?
像是一堆文章，每個文章中出現過哪些單字，
利用那些單字來搜出所以用所有相關的文章，
類似搜尋引擎般的效果呢?
今天就是要來使用資料庫來模擬一個簡單的搜尋引擎.
假設我們今天資料庫裡已經有了一堆文章，我們想要為這些文章做搜尋，
一步步的從無腦的直接搜尋，到有計畫地搜尋，最後使用GIN來做優化，
那麼就請各位聽我娓娓道來吧!

直接搜尋

table_a中的doc欄位就是我們存文章的地方，
目標是想要搜尋出現過cat這個單字的文章。
如果直接搜尋的話可能會這樣下
select doc from table_doc where doc like %cat%
這樣的話可能會遺漏掉字首大寫的Cat，所以我們可以使用不管大小寫的ilike
變成這樣
select doc from table_doc where doc ilike %cat%

其實ilike/like都會回傳true/false，
想要更直覺的看每筆紀錄是否有被找到，可以而外建立一個match欄位。
SELECT doc， doc ILIKE '%cat%' AS matches FROM table_doc;

將文章先做好前處理

看完上面的範例後，可能會覺得，這樣的搜尋根本就是暴力解，
每次搜尋都要將整張table和整個文章都找過一輪，
是否有什麼方法來避免每個文章都找過一輪呢?
有，我們可以做一個像是字典一樣表，
利用程式先每次插入的文章所使用的單字，
在解析完成的每個單字都記錄下來寫到一張keyword table，
然後再利用一張多對多的search table來將keyword table與doc做對應，
用來查詢該文章有哪些keyword，或該keyword會有那些文章出現過.
我們會在keyword table上的keyword加上index，
然後再doc table的id上加上index.

在搜尋時就可以直接透過search table來找下keyword，
來搜尋那些使用那些key word的文章了。
最後可能會變成這樣

使用GIN

咦?使用到兩層B+Tree不就是GIN的專長嗎?
那麼我們來時做看看利用GIN來做搜尋吧!
這裡我們來手把手實做。

1. 建表建資料

create table table_doc(doc text， doc_tsv tsvector);

insert into table_doc(doc) values
('the fat black cat chased after the rat')，
('one cat， two cats， many cats!')，
('the kitten and the dog played together')，
('that is one fine feline')，
('it is raining cats and dogs')，
('after eating the whole lasagne， he was a fat cat.')，
('don''t go into the catacombs after dark')，
('the bobcat has a spotted coat')，
('check the library catalog')，
('for a filesystem with deduplication look at zfs')，
('add one or more predicates to the query');

2. 建立關鍵字欄位

這裡就是將每筆紀錄的關鍵字都解析出來，放到doc_tsv這個tsvector結構中
其實postgres內建就有一個函數可以幫我們做字典的解析。
to_tsvector這個函數可以幫我們將每個關鍵字來做解析，而且還移除了一些單字的變化與用不到的be動詞與冠詞等字.然後產出多筆tsvector結構來.
像是第二筆紀錄的cat單字有cat，cats，而且出現在第2，4，6個字，
to_tsvector就幫我們利用tsvector結構存下來了。

update table_doc set doc_tsv=to_tsvector(doc);

你會得到像是這個樣子

postgres目前只有支援英文，尚未支持其他語言。
有興趣的朋友可以上網找一些其他人撰寫的中文字典外掛。

3. 建立GIN index

CREATE INDEX gin_xxx ON table_doc USING gin(doc_tsv);

4. 大功告成!

蛤?已經完成了?
對，在你加入index後就完成了，
因為GIN幫你利用keyword建立了entry tree，e.g. cat
然後再最下方也建立了posting tree， e.g. cat: 2，4，6
我們來搜尋看看吧!

select doc from table_doc WHERE doc_tsv @@ to_tsquery('cat');
-- 輸出
the fat black cat chased after the rat
one cat， two cats， many cats!
it is raining cats and dogs
after eating the whole lasagne， he was a fat cat.

來explain看看
explain analyze select doc from table_doc WHERE doc_tsv @@ to_tsquery('cat');

Bitmap Heap Scan on table_doc  (cost=8.78..13.05 rows=1 width=32) (actual time=7.131..7.135 rows=4 loops=1)
  Recheck Cond: (doc_tsv @@ to_tsquery('cat'::text))
  Heap Blocks: exact=1
  ->  Bitmap Index Scan on gin_xxx  (cost=0.00..8.78 rows=1 width=0) (actual time=7.102..7.103 rows=4 loops=1)
        Index Cond: (doc_tsv @@ to_tsquery('cat'::text))
Planning Time: 0.123 ms
Execution Time: 7.378 ms

Remark:因筆數較少pg容易直接掃整張表，所以可以設定`set enable_seqscan=off;`來禁止掃表。

結語

看完了利用GIN來做Full Text Search後，
是否覺得這個index type是個好東西呢?
雖然說其實市面上有許許多多Full Text Search或search engine等更厲害的工具可以使用.
如果需求夠大，已經不太需要自幹這些東西了。
但因為這些工具會需要花到而外的資源，
對於資源斤斤計較的又想要簡單的達到目標的需求者，
建議可以利用原本就會使用的db來DIY一下喔。