懶人促進社會進步 - 5種索引的原理和優化Case (btree,hash,gin,gist,brin)

postgresql , 多列聚合 , gin , btree , n_distinct , 選擇性 , 如何選擇索引方法(hash,btree,gin,gist,brin) , 如何優化索引 , 相關性

在廣告行業，精準營銷是一個較熱的話題，之前寫過一個案例，如何使用postgresql的array類型和gin索引實時圈人的場景。

<a href="https://github.com/digoal/blog/blob/master/201612/20161225_01.md">《萬億級營銷(圈人)邁入毫秒時代 - 萬億user_tags級實時推薦系統資料庫設計》</a>

使用以上方法，程式需要作出一些調整（當然，如果使用者原本就是postgresql技術棧，改動量會很少），改動量舉例

假設使用者使用了多個列來表示不同的屬性，每個屬性對應一些tag取值空間。

使用者原有的圈人、次元統計查詢可能是這樣的

例如between and這種連續查詢需要轉換為in的散列查詢。使得程式設計更加複雜，（雖然這樣也許可以将性能最大化）。

那麼postgresql有沒有什麼折中的辦法呢？

當然有，一切辦法都是為懶人準備的，懶人推動了社會的進步。

如果你閱讀一下這些文檔，你會發現pg裡面辦法還是蠻多的。

1、使用bitmapand, bitmapor+任意索引，解決圈人問題。

<a href="https://github.com/digoal/blog/blob/master/201706/20170607_02.md">《多字段，任意組合條件查詢(0模組化) - 毫秒級實時圈人 最佳實踐》</a>

2、使用varbitx插件，解決圈人問題。

<a href="https://github.com/digoal/blog/blob/master/201705/20170502_01.md">《阿裡雲rds for postgresql varbitx插件與實時畫像應用場景介紹》</a>

接下來針對有連續查詢，等值查詢多種組合查詢的圈人場景，我們來看看如何解決。

建構一張tag表

插入一批資料

資料樣式

分析表的統計資訊

檢視每列的散列程度

針對以上統計資訊，對于唯一列，建立btree索引，對于松散列，建立gin索引（倒排），以達到最好的效果。

為了讓普通類型支援gin，需要建立btree_gin插件

建立c1,c6的gin複合索引

查詢測試，查詢c1,c6的任意組合，效果非常棒。

建立其他列的btree索引，因為其他列的n_distinct表明這些列基本唯一，是以我們建立btree索引，可以精準的進行定位。

對于線性相關性好的列，建立brin索引。後面會講到索引的原理和選擇。

多列組合查詢，效果非常好

多個索引通過bitmapand, bitmapor對資料進行過濾，大幅提升任意條件查詢的性能。原理如下

那麼應該如何選擇索引呢？後面會講到。

實際上前面用到的是gin多列複合索引，還有一種方法，将多列轉換為數組，然後建立數組索引(postgresql 表達式索引。)。

1、如何将多列轉換為數組？

例子

2、數組表達式索引

3、如何命中數組表達式索引

查詢條件與索引中的表達式一緻，即可命中。

1、什麼時候選擇btree

btree索引适合選擇性好的列（n_distinct很大，或者=-1），唯一值比例越高越适合btree。

2、什麼時候選擇gin

與btree相反，選擇性越差，采用gin索引效率越高。

另外gin的倒排特性，還特别适合多值類型的元素組合查詢，例如數組、全文檢索類型、token類型、等等。

同時gin索引接口是開放的，使用者可以根據資料特征，自定義gin索引。支援更多的資料類型，例如圖像特征值相似查詢，文本的相似度查詢等。

3、什麼時候選擇gist

gist是pg的一種通用索引接口，适合各種資料類型，特别适合異構的類型，例如幾何類型，空間類型，範圍類型等。

gist索引的原理可參考

<a href="https://github.com/digoal/blog/blob/master/201612/20161231_01.md">《從難纏的模糊查詢聊開 - postgresql獨門絕招之一 gin , gist , sp-gist , rum 索引原理與技術背景》</a>

4、什麼時候選擇hash

如何用好隻有等值查詢，并且被索引的列長度很長，可能超過資料庫block的1/3時，建議使用hash索引。 pg 10 hash索引會産生wal，確定了可靠性，同時支援流複制。

pg 10 以前的版本，不建議使用hash index，crash後需要rebuild，不支援流複制。

5、什麼時候選擇brin

當資料與堆存儲線性相關性很好時，可以采用brin索引。

brin是塊級索引，存儲每個（或者每一段連續的）資料塊的原子資訊（最大值，最小值，平均值，空值比例，count等）。

特别适合範圍掃描。

1、btree

适合排序、&gt;=, &lt;=, =, in, &gt;, &lt; 等查詢。

2、hash

适合=查詢。

3、gin

不同的資料類型，适應不同的查詢需求。

例如數組類型，适合 相交，包含等。

4、gist

例如空間類型，适合，距離排序，knn，包含，相交，左，右等。

5、brin

适合範圍查詢，=查詢。

前面的方法告訴你應該如何選擇索引，但是沒有提索引本身的優化，實際上資料分布會影響索引的效率。

例如

<a href="https://github.com/digoal/blog/blob/master/201404/20140426_01.md">《索引順序掃描引發的堆掃描io放大背後的統計學原理與解決辦法 - postgresql index scan enlarge heap page scans when index and column correlation small.》</a>

是以，根據索引的掃描特點，對資料進行重分布，可以大幅度優化索引查詢的效率。

例如bitmap index scan（按block id順序讀取）就是postgresql用于減少離散io的手段。

1、btree資料分布優化

線性相關越好，掃描或傳回多條資料的效率越高。

2、hash資料分布優化

3、gin資料分布優化

如果是普通類型，則線性相關越好，掃描或傳回多條資料的效率越高。

如果是多值類型（如數組、全文檢索、tokens），則元素越集中（元素聚類分析，橫坐标為行号，縱坐标為元素值，資料分布越集中），效率越高。

元素集中通常不好實作，但是我們可以有集中方法來聚集資料，1. 根據元素的出現頻率進行排序重組，當使用者搜尋高頻詞時，掃描的塊更少，減少io放大。2. 根據（被搜尋元素的次數*命中條數）的值進行排序，按排在最前的元素進行聚集，逐級聚集。

(以上方法可能比較燒腦，下次發一篇文檔專門講gin的資料重組優化)

<a href="https://github.com/digoal/blog/blob/master/201706/20170612_05.md">《索引掃描優化之 - gin資料重組優化(按元素聚合) 想象在玩多階魔方》</a>

4、gist資料分布優化

如果是空間類型，則元素越集中（例如資料按geohash連續分布），效率越高。

5、brin資料分布優化

6、多列複合索引資料分布優化

對于多列符合索引，則看索引的類型，要求與前面一樣。

增加一個，多個列的線性相關性越好，性能越好。

多列線性相關性計算方法如下

<a href="https://github.com/digoal/blog/blob/master/201604/20160403_01.md">《postgresql 計算 任意類型 字段之間的線性相關性》</a>

資料分布還有一個好處，對于列存儲，可以大幅提升壓縮比

<a href="https://github.com/digoal/blog/blob/master/201604/20160404_01.md">《一個簡單算法可以幫助物聯網,金融 使用者 節約98%的資料存儲成本 (postgresql,greenplum幫你做到)》</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170221_01.md">《postgresql gin 單列聚集索引 應用》</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170205_01.md">《寶劍贈英雄 - 任意組合字段等效查詢, 探探postgresql多列展開式b樹 (gin)》</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170204_01.md">《postgresql gin索引實作原理》</a>

<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>