postgresql , 多列索引 , btree , gin , gist , brin , btree_gist , btree_gin , 複合索引 , composite index , 任意字段等效查詢
很多人小時候都有一個武俠夢，獨孤求敗更是金庸武俠小說裡的一位傳奇人物。
縱橫江湖三十馀載，殺盡仇寇奸人，敗盡英雄豪傑，天下更無抗手，無可奈何，惟隐居深谷，以雕為友。 嗚呼，生平求一敵手而不可得，誠寂寥難堪也。
獨孤老前輩的佩劍描寫非常有意思，從使用的佩劍，可以看出一個人的武功修為。
第一柄是一柄青光閃閃的無名利劍。「淩厲剛猛，無堅不摧，弱冠前以之與河朔群雄争鋒。」
第二柄是紫薇軟劍，「三十歲前所用，誤傷義士不祥，乃棄之深谷。」
第三柄是玄鐵重劍，「重劍無鋒，大巧不工，四十歲之前恃之橫行天下。」
第四柄是柄已腐朽的木劍，原因是獨孤求敗「四十歲後，不滞于物，草木竹石均可為劍。」
個人感覺和我們現在搞it的也很相似哦，開發語言有c, python, java, ....各式各樣的可選，資料庫有oracle, postgresql, mysql等等，也是各式各樣的産品可選。
寶劍贈英雄，美玉配佳人。
不管你是李逍遙、還是楊過、小龍女，希望你也能找到合适你的武器。
進入正題。
多列的組合查詢在實際的應用中也較為常見，比如淘寶購物網站的商品搜尋
有發貨地、分類、是否包郵、是否貨到付款、是否天貓、二手、等等許多選項，這些選項在設計時可能使用多個字段來表示（當然，有些可能會使用bit合并成單個字段來表述）。
舉個非常簡單的例子
查詢條件中，包含test2表的兩個字段的檢索
這種情況下，我們可以使用兩個索引，也可以使用一個複合索引（多列索引）。
以上例子可以轉化為對多個字段的任意組合查詢需求(任意單一、任意兩個、任意三個，任意若幹個字段的查詢需求)。
看過我寫的文檔的童鞋，可能會聯想到我在之前寫過一篇文檔
<a href="https://github.com/digoal/blog/blob/master/201605/20160523_01.md">《postgresql 9.6 黑科技 bloom 算法索引，一個索引支撐任意列組合查詢》</a>
不過本文并不是要講bloom，本文要講一講另一種技術（gin索引的暗藏功能，多列展開式b樹）。
在開始正文之前，大家有沒有想過這些問題呢？
1. 哪些索引方法支援多列索引?
postgresql目前支援btree, hash, gin, gist, sp-gist, brin, bloom, rum等衆多索引通路方法，哪些通路方法支援多列索引呢？
2. 多列索引的内部存儲結構如何?
比如b-tree單列索引很好了解，就是以被索引列值為key的類b-tree(nbtree)結構。但是當使用多列索引時，内部是如何組織的呢？
不同的索引方法，内部組織有什麼差異呢？
3. 多列索引支援哪些查詢組合
比如index on (a,b,c)三列，那麼哪些查詢條件能用上多列索引呢？比如where a=? and b>?
不同的索引方法，适用的查詢條件是不是都一樣呢？
4. 不同的查詢組合，使用多列索引的效率如何，效率是否一樣（是否與索引通路方法有關？）
比如b-tree index on (a,b,c)三列，where a=? and b>? 以及 where b>? and c=? 效率一樣嗎？
5. 多列索引，每個列的順序是否可以指定
比如，是不是所有的索引方法都可建立這樣的索引 index on (a,b desc, c desc nulls first)
6. 同樣的查詢組合，使用什麼索引方法更高效
比如 where a=? and b=? and c=? 這樣的查詢，适用gin好還是b-tree好呢？
7. 如何選擇合适的索引方法，與查詢條件，資料分布有關系嗎？
要回答這些問題，需要對索引方法，内部存儲結構有一定的了解。
本文将以gin和btree為例，講解一下multi column index，它們的内部存儲結構，适應的場景。
建議讀者先了解一下單列索引的内部結構，本文就不展開了，可以參考我之前寫的一些文章。
<a href="https://github.com/digoal/blog/blob/master/201605/20160528_01.md">《深入淺出postgresql b-tree索引結構》</a>
<a href="https://github.com/digoal/blog/blob/master/201606/20160610_01.md">《b-tree和b+tree》</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/201612/20161231_01.md">《從難纏的模糊查詢聊開 - postgresql獨門絕招之一 gin , gist , sp-gist , rum 索引原理與技術背景》</a>
在沒有multi column index時，如果我們有多個列的查詢條件，通常可以使用選擇性好的列，或者多個列索引的組合。
postgresql 使用多個列索引組合查詢時，可以使用多列查詢結果的ctid bitmap and or ，篩選出最終符合多列條件的ctid。
不僅适用于多列的查詢條件，也适用于單列的多個查詢條件。
例如
<a href="https://www.postgresql.org/docs/9.6/static/indexes-bitmap-scans.html">https://www.postgresql.org/docs/9.6/static/indexes-bitmap-scans.html</a>
combining multiple indexes
currently, only the b-tree, gist, gin, and brin index types support multicolumn indexes.
up to 32 columns can be specified. (this limit can be altered when building postgresql; see the file pg_config_manual.h.)
目前postgresql的b-tree, gist, gin, and brin索引方法，支援多列索引。
目前支援最多32個列的多列索引，實際上可以更大（通過調整pg_config_manual.h可以做到更大，但是還有另一個限制，indextuple不能超過約1/4的資料塊大小，也就是說複合索引列很多的情況下，可能會觸發這個限制）。
multicolumn indexes
<a href="https://www.postgresql.org/docs/current/static/indexes-multicolumn.html">https://www.postgresql.org/docs/current/static/indexes-multicolumn.html</a>
由于b-tree, gin , gist, brin都支援multi column索引，但是這幾種索引的内部存儲方式不一樣，是以不同的組合查詢的效率也不一樣。
例如a,b,c三列的組合索引，select * from tbl where a=? and b>? 以及 where b=?，這兩種查詢組合，哪個效率高？和索引方法有大大的關系。
b-tree多列索引支援任意列的組合查詢
a multicolumn b-tree index can be used with query conditions that involve any subset of the index's columns, but the index is most efficient when there are constraints on the leading (leftmost) columns.
雖然b-tree多列索引支援任意列的組合查詢，但是最有效的查詢還是包含驅動列條件的查詢。
the exact rule is that equality constraints on leading columns, plus any inequality constraints on the first column that does not have an equality constraint, will be used to limit the portion of the index that is scanned.
對于b-tree的多列索引來說，一個查詢要掃描索引的哪些部分呢？
從驅動列開始算，按索引列的順序算到非驅動列的第一個不相等條件為止（沒有任何條件也算）。
constraints on columns to the right of these columns are checked in the index, so they save visits to the table proper, but they do not reduce the portion of the index that has to be scanned.
for example, given an index on (a, b, c) and a query condition where a = 5 and b >= 42 and c < 77, the index would have to be scanned from the first entry with a = 5 and b = 42 up through the last entry with a = 5.
（where a = 5 and b >= 42 and c < 77），從a=5, b=42開始的所有索引條目，都會被掃描。
index entries with c >= 77 would be skipped, but they'd still have to be scanned through.
其他例子
（where b >= 42 and c < 77），所有索引條目，都會被掃描。隻要不包含驅動列，則掃描所有索引條目。
（where a = 5 and c < 77），a=5的所有索引條目，都會被掃描。
（where a >= 5 and b=1 and c < 77），從a=5開始的所有索引條目，都會被掃描。
this index could in principle be used for queries that have constraints on b and/or c with no constraint on a — but the entire index would have to be scanned, so in most cases the planner would prefer a sequential table scan over using the index.
建議有頻繁的複合查詢，并且複合查詢帶有驅動列以及其他列的查詢時，可以考慮使用多列索引。
gist多列索引支援任意列的組合查詢。
a multicolumn gist index can be used with query conditions that involve any subset of the index's columns.
conditions on additional columns restrict the entries returned by the index, but the condition on the first column is the most important one for determining how much of the index needs to be scanned.
注意與b-tree不一樣的地方，驅動列的選擇性決定了需要掃描多少索引條目，掃描多少條目與非驅動列無關（而b-tree是與非驅動列也有關的）。
a gist index will be relatively ineffective if its first column has only a few distinct values, even if there are many distinct values in additional columns.
如果驅動列的選擇性不好、其他列的選擇性很好，即使查詢條件同時包含了 驅動列以及其他列 ，也需要掃描很多索引條目，因為掃描多少索引條目和其他列無關。
這麼說，并不建議使用gist多列索引。
如果一定要使用gist多列索引，請一定要把選擇性好的列作為驅動列。
gin多列索引支援任意列的組合查詢。
并且任意查詢條件的查詢效率都是一樣的。
a multicolumn gin index can be used with query conditions that involve any subset of the index's columns.
unlike b-tree or gist, index search effectiveness is the same regardless of which index column(s) the query conditions use.
brin多列索引支援任意列的組合查詢。
如果有brin組合查詢的必要(比如多個與ctid線性相關的列的範圍查詢，無所謂線性的方向)，任何時候都建議使用brin的multi column index，除非想針對不同的列使用不同的pages_per_range（比如有些列10個塊的範圍和另外一些列100個塊的範圍覆寫差不多，那麼建議它們使用不同的pages_per_range）
a multicolumn brin index can be used with query conditions that involve any subset of the index's columns.
like gin and unlike b-tree or gist, index search effectiveness is the same regardless of which index column(s) the query conditions use.
the only reason to have multiple brin indexes instead of one multicolumn brin index on a single table is to have a different pages_per_range storage parameter.
多列索引每個列的operator class必須和實際查詢比對，在建立索引時可以指定。
of course, each column must be used with operators appropriate to the index type; clauses that involve other operators will not be considered.
multicolumn indexes should be used sparingly.
in most situations, an index on a single column is sufficient and saves space and time.
indexes with more than three columns are unlikely to be helpful unless the usage of the table is extremely stylized.
前面分析了b-tree, gin都支援任意組合查詢。
但是b-tree推薦使用包含驅動列的查詢條件，如果查詢條件未包含驅動列，則需要掃描整個複合索引。
而gin則通吃，可以輸入任意組合列作為查詢條件，并且效率一緻。
index on (a,b,c)
b-tree 對于包含驅動列a查詢條件的sql，效率可能比較好，不包括a查詢條件的sql，即使走索引，也要掃描整個索引的所有條目。
而gin 則無論任何查詢條件，效果都一樣。
這是為什麼呢？必須從索引的内部存儲組織結構來分析。
btree 對被索引列按建立索引時指定的順序排序，然後建立b樹。
如create index idx on tbl using btree (a,b desc nulls first,c desc, e);
是以b樹中的key實際上就是被索引列的組合對象，這個結構決定了什麼查詢能用上這個複合索引。
要達到最高效的使用這種複合索引，必須帶上驅動列的條件。
如果order by要用上索引，那麼必須order by的寫法要與建立索引時指定的順序一緻。
例如select * from tbl where a=? order by a,b desc nulls first;
gin 的複合索引很有趣，它将所有列展開，然後将展開後的資料（列id+值）排序并建立b樹。
是以在gin的複合索引中，b樹的key實際上是列id+值。
這樣的樹，以任意組合進行查詢，效率都一樣。
where a=? 與 where b=? 效率一樣，而且和b-tree的單列索引的效率幾乎一緻（當索引層級一緻時）。
where a=? and b=? 與 where b=? and c=? 效率一樣(複合索引查兩次，在内部使用bitmapand取得結果)。
僅僅當多列組合查詢時，gin效率可能比不上b-tree的帶驅動列的查詢（因為b-tree索引不需要bitmapand，而gin需要内部bitmapand）。
建立一個測試表，包含3個字段
插入100萬記錄，其中c2,c3的值固定
建立gin複合索引
查詢c1=1，效率與單列索引一緻
這個查詢結果也可以說明另一個問題，不同列并不是單純展開後直接建構b樹，它依舊添加了列id進來，是以即使c3=1有100萬記錄，并不影響c1=1的掃描page數。
查詢c2=?，效率與單列索引一緻
查詢c3=?，效率與單列索引一緻
gin任意組合（不需要限定驅動列）多列查詢的隐含bitmapand, bitmapor操作
沒有驅動列，一樣高效無比
1. 由于btree index, 多列值根據建立索引的ddl指定順序sort後，多列的值組合後作為一個key存儲在b樹中。
例如4條記錄如下
btree 中的key排序後分布(有多少條記錄，就有多少key)
2. gin multi column index 建構了一個包含多種資料類型的b-tree ， 将多列的資料展開後，排序後分布 (key的數量為每列的count distinct總和)
更形象的比喻
比如有三幅撲克牌（每幅54張牌），每一幅代表一列，如果要建立3列的複合索引，那麼b-tree會建立出54個條目的b樹，而gin會建立出包含162個條目的b樹。
請看這個例子，可以說明這個情況
b-tree 要高效的使用複合索引，必須帶驅動列的查詢條件。
gin 使用複合索引，可以任意組合查詢條件，當有多列查詢條件時，使用隐含的bitmapand or bitmapor。
什麼情況下，gin比btree慢？
通常，多列查詢時，如果使用了驅動列，那麼b-tree索引會更快一些，因為它不需要使用bitmapand or bitmapor，而gin需要。
其他情況，gin都比btree的複合查詢快。
通過前面的分析，我們已經摸清楚了gin的複合索引結構（展開式b樹），并且也知道gin是key+ctid list的類b+tree樹組織形式，它可以有很高的壓縮比，也可以高效的查詢單key。
那麼gin具備這些特性後，有哪些獨門秘籍呢？
1. 任意組合查詢，都可以達到很高效，你不需要建立多個b-tree索引了，一個gin搞定它(不必擔心gin的io，有fastupdate技術支撐，并且讀寫(entry合并)不堵塞)。
比如淘寶的搜尋頁面，使用者可能根據任意屬性，勾選任意條件進行查詢。
建立一張測試表, 6個字段
插入1000萬随機記錄
建立gin多列索引
資料樣例
查詢測試
任意單一字段
任意2字段
任意3字段
任意4字段
不再舉例，都能用上索引
2. 由于ctid list組織，是以可以做到很好的壓縮，前面講的posting list compress就是這個功效。是以它節約空間，提升效率。
3. 使用btree_gin插件，可以對任意标量資料類型建立gin索引，前面已有例子。
4. gin對多值類型（如數組、文本、全文檢索）的支援就不多說了，那是gin的發源地，支援非常棒。
注意，目前gin還不支援sort，是以如果你有大資料量的order by limit 小資料輸出需求，建議還是使用b-tree。
postgresql 資料庫，了解越多，才會更加随心所欲，駕馭自如。
<a href="https://www.postgresql.org/docs/9.6/static/btree-gin.html">https://www.postgresql.org/docs/9.6/static/btree-gin.html</a>
<a href="https://www.postgresql.org/docs/9.6/static/btree-gist.html">https://www.postgresql.org/docs/9.6/static/btree-gist.html</a>
<a href="https://www.postgresql.org/docs/9.6/static/pageinspect.html">https://www.postgresql.org/docs/9.6/static/pageinspect.html</a>