postgresql , gist , sp-gist , gin , rum index , 模糊查詢 , 搜尋引擎 , token位置搜尋 , pg_hint_plan , 自動優化 , 分詞 , like '%xxx%'
模糊查詢，是一個需求量很大，同時也是一個對資料庫來說非常難纏的需求。
對于前模糊(like '%xxx')，可以使用倒排b-tree索引解決，對于後模糊(like 'xxx%')，可以使用b-tree索引解決。
b-tree索引通常支援的查詢包括 > , < , = , <= , >= 以及排序。 目前大多數資料庫都支援b-tree索引方法。
但是對于前後模糊(like '%xxxx%')，對于以及前後模糊的正規表達式(~ '.ab?cd[e-f]{1,10}-0.')，則很多資料庫無從下手，無法優化，隻能全表掃描，對每條記錄進行單獨的處理。
postgresql資料庫的開放性使得這一切成為了可能，在資料庫中進行前後模糊，正則表達查詢的索引檢索成為可能。
原因是postgresql開放的索引接口，資料類型。（比如支援gin, gist, rum, 自定義索引方法，你可以認為這是pg的獨門絕技之一，目前還沒有其他資料庫支援這一特性）。
其實我在之前介紹過很多模糊查詢的索引優化方法，很多第一次接觸的同學會認為打開了新世界的大門。
<a href="https://github.com/digoal/blog/blob/master/201305/20130516_01.md">《postgresql 9.3 pg_trgm imporve support multi-bytes char and gist,gin index for reg-exp search》</a>
<a href="https://github.com/digoal/blog/blob/master/201605/20160506_02.md">《中文模糊查詢性能優化 by postgresql trgm》</a>
<a href="https://github.com/digoal/blog/blob/master/201610/20161019_01.md">《postgresql 全文檢索加速 快到沒有朋友 - rum索引接口(潘多拉魔盒)》</a>
<a href="https://github.com/digoal/blog/blob/master/201611/20161118_01.md">《聊一聊雙十一背後的技術 - 毫秒分詞算啥, 試試正則和相似度》</a>
<a href="https://github.com/digoal/blog/blob/master/201612/20161231_01_pdf_002.pdf">postgresql internal</a>
<a href="https://github.com/digoal/blog/blob/master/201612/20161231_01_pdf_001.pdf">postgresql index internal</a>
目前有三種索引可以參與模糊查詢的優化，到底用哪個好呢？
本文将給大家分享一下 gin,gist,rum 索引背後的原理，大夥就知道該如何選擇了，看好就該迎接2017新年啦，提前祝大家新年快樂，明年步步高升。
gin索引，是将列(比如數組，全文檢索類型)中的值拿出來，再存儲到樹形結構中（類似b+tree，值+行号s），對于高頻值，為了減少樹的深度，行号s會存儲在另外的頁中。
由于gin存儲的是元素索引，是以當一條記錄被插入或更新時，可能涉及到很多個元素，對gin索引來說，就會涉及到很多item的變更。
為了提升插入，更新，删除的性能，postgresql支援類似mysql的索引組織表類似的buffer ，先寫入buffer，然後再合并到樹裡去。
而相比mysql索引組織表更優一些的地方是，查詢不會堵塞合并，也不會堵塞寫入。因為查詢時不需要等待buffer中的資料合并到樹中，而是直接查詢buffer（如果buffer非常大，可能查詢速度會受到一定的影響）。 、
使用者可通過參數來控制buffer的大小，gin會在buffer增長到一定程度後自動進行合并。或者等vacuum來合并。
是以一個完整的gin索引長這樣
1. 為了提高更新速度，使用了faster update技術，當buffer很大時（可自己設定），查詢速度可能會較慢。是以權衡插入和查詢，建議設定合理的buffer大小。
2. 僅支援bitmap查詢，也就是說取到所有的行号之後，排序，然後再去檢索，好處顯然是可以減少随機的heap page掃描，但是壞處是，當涉及的行非常多（比如每行都包含了某個元素）很大時，排序耗費資源較多，耗時較長，從執行到獲得第一條的時間較長，如果使用者使用了limit，也要等排序結束。
<a href="https://github.com/digoal/blog/blob/master/201612/20161225_01.md">《恭迎萬億級營銷(圈人)潇灑的邁入毫秒時代 - 萬億user_tags級實時推薦系統資料庫設計》</a>
<a href="https://github.com/digoal/blog/blob/master/201612/20161222_02.md">《從相似度算法談起 - effective similarity search in postgresql》</a>
generalized search tree，或者叫歸納樹，用于解決一些b-tree, gin難以解決的資料減少問題，例如，範圍是否相交，是否包含，地理位置中的點面相交，或者按點搜尋附近的點，當然，它能實作的功能還不僅于此。
以範圍類型為例，下圖每一條線段表示某條記錄，某個字段上面存儲的範圍類型所覆寫的範圍。
找到存儲的範圍有相交的記錄s
按範圍的最小值（左值）排序（請忽略紅色框框的存在）
按範圍的最大值（右值）排序（請忽略紅色框框的存在）
首先把它們聚集到不同的分組（有點類似k-means幹的事情）（請忽略紅色框框的存在）
聚集之後的資料，你可以了解為就是對應gist的單個index page裡包含的資訊（可以多級聚集，即對應後面的2級結構）。
gist單個index page長這樣：
key + 行号 (索引和記錄一一對應)
在index内無序存放。
藍色框框中，左邊列的值代表key，右邊列的值代表行号（第幾個heap page，裡面的第幾條記錄）。
gist兩級索引長這樣，上一級代表下一級中單個index page的大範圍。
例如搜尋[55,60]這個範圍，如何搜尋的呢？
gist的靈魂是聚集，是以首先是聚集的動作，聚集後，在單個組内包含的key+heap行号會放到單個index page中。
聚集的範圍作為一級結構，存儲在gist的entry 中，便于檢索。
既然靈魂是聚集，那麼gist的性能就和他的聚集算法息息相關，postgresql把這個接口留給了使用者，使用者在自定義資料類型時，如果要自己實作對應的gist索引，那麼就好好考慮這個類型聚集怎麼做吧。
postgresql内置的range, geometry等類型的gist已經幫你做好了，你隻需要做新增的類型，比如你新增了一個存儲人體結構的類型，存儲圖檔的類型，或者存儲x光片的類型，怎麼快速檢索它們，那就是你要實作的gist索引聚集部分了。
<a href="https://github.com/digoal/blog/blob/master/201611/20161126_01.md">《postgresql 在視訊、圖檔去重，圖像搜尋業務中的應用》</a>
<a href="https://github.com/digoal/blog/blob/master/201611/20161114_01.md">《聊一聊雙十一背後的技術 - 物流、動态路徑規劃》</a>
<a href="https://github.com/digoal/blog/blob/master/201601/20160119_01.md">《postgresql 百億地理位置資料 近鄰查詢性能》</a>
space-partitioned gist
可以了解為gist的擴充，有以下特點
1. nodes無交叉，（gist是有交叉的，隻是做了聚集，但是nodes（不同的index page)包含的内容是有交叉的）。
2. 索引深度是可變的
3. 每個實體的index page可能對應多個nodes
sp-gist支援的檢索類型
1. kd-tree , points only ; ( because shapes might overlap )
2. prefix tree for text
與gist的場景類似
rum 參考了gin的實作，并改進了gin在全文檢索時的一些弱點，比如：
1. slow ranking. (gin沒有存儲全文檢索的lexem位置資訊，是以無法支援索引級的ranking，需要掃描heap page後，通過cpu運算得到)
it is need position information about lexems to ranking. gin index doesn't store positions of lexems. so after index scan we need additional heap scan to retreive lexems positions.
2. slow phrase search with gin index. (同樣由于gin沒有存儲位置資訊，是以無法支援索引級的phrase搜尋，例如 '速度' <1> '激情' 不能支援，或者 '中國:100' 無法支援到索引級别的搜尋. )
this problem relates with previous problem. it is need position information to perform phrase search.
3. slow ordering by timestamp. (因為gin隻存儲了tsvector token，沒有任何附帶字段資訊（例如全文檢索+索引字段 雙字段索引），是以一些炫酷或者業務擴充的功能，都需要heap page的掃描和cpu的處理)
gin index can't store some related information in index with lexemes. so it is necessary to perform additional heap scan.
rum的改進方法，在index 中加入了附加資訊，比如token位置，進而可以支援以上查詢。 同時支援雙字段索引（如 tsvector+timestamp）
rum solves this problems by storing additional information in posting tree.
for example, positional information of lexemes or timestamps.
you can get an idea of rum by the following picture:
rum帶來的問題，建立索引以及資料變更的時間，比gin長，這個已經在rum的todo 中，會是後面的改進重點。
drawback of rum is that it has slower build and insert time than gin.
it is because we need to store additional information besides keys and because rum uses generic wal.
<a href="https://github.com/digoal/blog/blob/master/201611/20161115_01.md">《聊一聊雙十一背後的技術 - 分詞和搜尋》</a>
b-tree
hash
gin
gist
sp-gist
brin
<a href="https://github.com/digoal/blog/blob/master/201512/20151215_01.md">《"物聯網"流式處理應用 - 用postgresql實時處理(萬億每天)》</a>
<a href="https://github.com/digoal/blog/blob/master/201603/20160320_01.md">postgresql 如何潇灑的處理每天上百tb的資料增量</a>
<a href="https://github.com/digoal/blog/blob/master/201504/20150419_01.md">《postgresql 9.5 new feature - brin (block range index) index》</a>
<a href="https://github.com/digoal/blog/blob/master/201505/20150526_01.md">《postgresql 9.5 new feature - lets brin be used with r-tree-like indexing strategies for "inclusion" opclasses》</a>
rum
bloom
<a href="https://github.com/digoal/blog/blob/master/201605/20160523_01.md">《postgresql 9.6 黑科技 bloom 算法索引，一個索引支撐任意列組合查詢》</a>
還有開放的接口，你可以自定義你的索引方法，請參考bloom索引的實作。
介紹完postgresql支援的索引方法，目前對于前模糊和後模糊，我們同樣可以使用b-tree來搜尋。
而對于前後模糊，以及正規表達式，我們也有了索引的支援
前後模糊：
gin, gist, rum
正則表達：
gin, gist
有例子如下
接下來對比一下gin, gist, rum在不同輸入條件下的性能，以及我們如何選擇
為了達到測試效果，我們需要在一個列上建立多個索引，需要使用pg_hint_plan選擇合适的索引。
postgresql允許你在一個列上面建立多個索引，比如我們接下來的測試，我們需要使用gin, gist, rum來建立不同的索引。
<a href="https://github.com/digoal/blog/blob/master/201604/20160401_01.md">《阿裡雲 postgresql pg_hint_plan插件的用法》</a>
<a href="https://github.com/digoal/blog/blob/master/201607/20160723_02.md">《關鍵時刻hint出彩 - pg優化器的參數優化、執行計劃固化case》</a>
<a href="https://github.com/digoal/blog/blob/master/201602/20160203_01.md">《postgresql sql hint的使用》</a>
<a href="https://github.com/digoal/blog/blob/master/201605/20160523_02.md">《postgresql 特性分析 plan hint》</a>
為了達到測試rum支援模糊查詢的目的，我們需要将字元串轉換為全文檢索類型，同時檢索是需要輸入tsquery，是以也需要轉換為tsquery類型。
找到轉義字元\的ascii值
将字元串轉換為帶位置标記的tsvector
将字元串轉換為帶位置标記的tsquery
安裝插件啥的就不寫了，需要三個插件pg_trgm, pg_hint_plan, rum
info字段的字元串就是我們接下來要進行模糊測試的字段
寫入100萬測試資料
轉換後的tsvector長什麼樣？
中間結果集很大（比對精度低，滿足條件的記錄數多），傳回結果也很大，未使用limit
完整執行計劃，注意評估行數，評估成本，後期可作為我們可用于評估哪個索引方法好的判斷标準。
中間結果集很大（比對精度低，滿足條件的記錄數多），傳回結果很少，使用limit
如果這個好，那麼使用分頁也很有效
中間結果集很小（比對精度高）
當中間結果集較少（輸入條件的精确度高）時，建議使用gin索引。
當中間結果集較大（輸入條件的精确度低）時，不管是不是分頁輸出，或者是否使用limit，或者是否使用遊标，都建議使用gist索引。
什麼時候使用rum呢？當真的需要全文檢索時，或者需要tsvector+timestamp複合查詢時，建議使用rum。
設定統計粒度
找到對應的node，并評估中間結果數
檢視對應節點的rows, 如果沒有limit， 則選擇頂級node的rows，如果是limit，則選擇第二個node的rows。
如果是更複雜的查詢，比如使用了多個條件查詢時，則最好使用hint, 通過hint對應的索引，找到對應的node.
如
跟進中間結果數，以及前面我給點建議，選擇合适的hint，開始執行query。