開這篇之前，其實本來是想要了解 PostgreSQL 10 裡實現索引的原理，畢竟在了解原理的情況下，比較容易想像在什麼情況下索引能夠具有優勢、什麼情況索引幫不上忙。不過花了一段時間搜尋…也不能說沒有找到，但沒有找到我想要的類型。所以這篇雖然標題在講 PostgreSQL 的 B-tree 索引，但實際上會先紀錄的是一般關聯式資料庫以 B-tree 做索引時的狀況。如果想參考看看我找到的其他在談 PostgreSQL B-tree 原理的文章，可以看看 [1-5]。
這篇當中實際會紀錄到的東西，有很大一部份並非來自 PostgreSQL 的官方文件，因此這並不一定完全就是 PostgreSQL 實現的方法，嚴格來說其實這個標題並不是太合適。不過理想上….應該不會差太多….吧！此外這篇文章紀錄的事項，除了我個人的觀點以外，有許多部份是來自 USE THE INDEX, LUKE! [7] 這個網站的解說。因此如果想要有條理地細讀，推薦可以直接去閱讀這個網站的內容。
然後呢，理想上我是想要依序了解所有 PostgreSQL 的索引結構，並分別做點紀錄。所以它有可能會是個系列文，這篇作為系列文的第一篇就會參雜一些奇怪的廢話了。但…也不保證真的會寫出來就是，以前有編號的系列文絕大多數都虎頭蛇尾了 Orz，所以這次索性不編號了。
為什麼要使用索引？
雖然表面上看起來這個問題好像挺蠢的，但我覺得這其實是個很重要的問題。
A：「為什麼要使用索引呢？」
B：「因為使用索引就會比較快呀」
A：「那為什麼使用索引就會比較快呢？」
B：「….這你去問資料庫呀，它就是會比較快」
好吧，這個例子其實蠻諷刺的就是，但實際上的確會遇到這種狀況。不了解索引的本質，而是把索引直接當成「比較快」的代名詞，通常都會導致悲劇。
本質上來說，索引（index）跟資料列（data row）沒有什麼分別，硬要說的話索引其實也是一種資料列，最多就只是索引通常是資料列的映射（projection），所以通常比較短。而索引會存取地比較快，很大的原因也是在於因為索引比較短。因此不要嘗試想要在索引上面把所有欄位都建進去呀～～～（暈）。
索引除了長度比較短以外，另外一個重點就是索引的資料會利用各種資料結構，擺放成容易被搜尋的樣式。這樣一來，在索引上面只要是符合資料結構特性的查詢方式，就可以比較快速地忽略掉那些根本不可能是搜尋目標的資料，節省 I/O 時間。
所以要依靠索引達到變快的效果，最重要的關鍵點就是索引必須要「能多小就多小」、以及「使用符合索引結構特性的查詢方法」。
不使用索引的查詢都是不好的嗎？
雖然一般我們都期待查詢能夠正確使用索引，可以讓查詢速度變快。但實務上在某些狀況下，FULL TABLE SCAN 有可能會比查詢索引來得更有效率。具體來說，當我們需要從資料庫中取得龐大的資料量的時候，FULL TABLE SCAN 就有可能比透過索引來得更好。這是因為一般在查詢索引時，索引在儲存媒體上的存放通常並非連續位置，也就是說資料庫引擎是以像是在存取 Linked List 的模式一個一個接著查詢，每次也就只能讀取一個 block 而已。而 FULL TABLE SCAN 雖然是需要把所有資料都讀出來，但讀取時資料庫引擎有可能可以利用系統的黑科技，在一個 read operation 中讀取多個 block，因而導致實際上可能會用更少的 read operation 就完成所有資料的讀取。
實務上來說，因為現代的關聯式資料庫多半有 Query Optimizer 這類工具，會自行判斷送進來的 SQL 敘述然後選擇合適的方法存取，所以在真的適合 FULL TABLE SCAN 的場合，倒也不用擔心資料庫會傻傻地透過索引來查詢。只是如果看到資料庫真的在進行 FULL TABLE SCAN，也不用急著開罵（不管對象是資料庫系統還是寫那段 SQL 敘述的人…），先稍微想一下這是不是符合對資料庫而言最佳效率的行為吧。
B-tree 索引
B-tree 的特性
B-tree 的最重要的特性在於，所有存放在 B-tree 上的資料都位在 leaf node，因此在 B-tree 中存取任意資料都是固定時間（時間取決於 B-tree 的高度），這點應該學習過資料結構的人都了解。所以這也就代表著，當使用 B-tree 做索引的時候，思考的問題就是資料庫是否能夠適當地利用樹狀結構很快找到想要的資料。
索引的查詢過程
在資料庫查詢索引的時候，雖然想像上就是在 B-tree 中從 root node 一路走到 leaf node，也就是完成一次垂直的 tree traversal 就好，但實務上不僅止於此。索引的查詢其實含括了三個動作 [8]：
- 從 root node 依序尋訪節點直到 leaf node
- 沿著 leaf node 尋訪 sibling nodes
- 依據收集來的資料列資訊（ROW ID），取得資料表中的資料
通常 SQL 指令執行地很慢，問題都是在於要嘛無法利用索引，要嘛雖然利用了索引，但在索引中無法快速鎖定目標資料列有哪些。也就是說，問題多半出在第二和第三步驟。
具體來說，就是當 SELECT 的敘述是要回傳超過一個結果的時候，這時在 B-tree 上的走訪就無法單純只依靠步驟一找到目標，而是需要從步驟一找到的目標，往前或者往後再找其他也同時符合條件的結果。而這時索引的查詢效率就會受到影響，也就是是否能夠在短短幾次 leaf node 的走訪中就能很快知道哪裡該停下來。如果說查詢沒有辦法很快知道到底該在哪裡停下，那麼它就會需要走訪完整個 B-tree 的 leaf node，導致查詢效能變差。
B-tree 的多欄位索引（Multicolumn Index）
在 PostgreSQL 中，只有 B-tree、GiST、GIN 和 BRIN 這幾種索引能夠支援多欄位索引，不過因為這篇只談 B-tree，所以其他的就….期待有緣吧 XD。
多欄位索引表示的是一個索引包含了超過一個欄位。在這種狀況下，因為欄位會以指定的順序被放在索引的 B-tree 節點上，因此實際會導致欄位順序有可能顯著地影響索引的存取效率。其中，PostgreSQL 的官方文件 [9] 明白地表示使用者可以用索引欄位的「任意子集合」來做查詢，不過基於 B-tree 結構的限制，按照索引欄位的順序會具有更好的效能。這裡說的「按照索引欄位的順序」，指的是例如索引包含了 A、B、C、D 四個欄位，搜尋 A = ? AND C = ? 的效率會大幅地高於搜尋 B = ? AND D = ?。換言之，盡可能讓越左邊的欄位包含在 SQL 敘述的條件中越好，可能的話最左邊的索引欄位務必要包含在內。
接著先參考看看 USE THE INDEX, LUKE! 網站在解釋多欄位索引時使用的範例 [10]：
在這個範例當中，假設我們建立一張表格並用了複合主鍵，複合主鍵包含了員工 ID 和子公司 ID（因為每個子公司的員工 ID 有可能會重複）。這時複合主鍵本身會形成一個多欄位索引，概念上會像是以下的 SQL 敘述建出來的索引：
CREATE UNIQUE INDEX employee_pk
ON employees (employee_id, subsidiary_id)這個索引的順序是 (employee_id, subsidiary_id)，此時如果想要查 subsidiary_id = 20 時，圖中也可以看出在樹的 branch 上完全無法了解是否存在 subsidiary_id = 20 的紀錄，因為 branch 中沒看到並不能代表它不存在。此時索引就會陷入必須要從第一個 leaf node 掃到最後一個 leaf node 才能了解到底有多少紀錄滿足要求，這個索引查詢就會陷入效能不佳的狀況。不過即使如此，在一個資料夠大（例如每筆紀錄都很長）的資料庫上，如果查詢本身滿足條件的紀錄很少，那麼即使查詢導致要掃過整個索引表，很多時候也還是比 FULL TABLE SCAN 來得有效率。這也是為什麼 PostgreSQL 官方文件說它可以這麼做的原因，因為通常來講即使這樣導致索引的使用效率不佳，在一般狀況下還是比最糟的方法好。
縱上所述，在 USE THE INDEX, LUKE! [10] 提醒了在使用多欄位索引時最重要的考量：
The most important consideration when defining a concatenated index is how to choose the column order so it can be used as often as possible.
另外，因為這裡的例子是複合主鍵，因此順帶提一下關於 unique index。unique index 的組成就是 B-tree，實際上在 PostgreSQL 當中也只有 B-tree 能建立 unique index。而從上面的解釋中可以看到，因為欄位具有唯一性，因此可以確保大多數的查詢都可以在需要極少的 leaf node scan 狀況下就能完成查詢。由此可知，在欄位具有唯一性的特性時，查詢的效能相對來說會比較高。不過 PostgreSQL 當中在一般狀況是不需要自行建立 unique index 的，因為當欄位被宣告成唯一時，PostgreSQL 就會自動建立對應的 unique index 了。
B-tree 多欄位索引的排序
接著討論在 SELECT 敘述中常常會使用到的 ORDER BY。從上面的 B-tree 的圖中其實可以注意到，在 B-tree 當中欄位是依照特定的順序放置的。因此可以很容易想像到，如果在查詢時的 ORDER BY 指令是依照跟索引存放的順序完全相同、或者完全相反時，效能會是最好的，這點在 PostgreSQL 的官方文件中也有特別提到。這是因為如此一來，資料庫從索引上經由 leaf node traversal 取得資料後，不需要再執行額外的排序動作，資料的順序就已經滿足 Query 的要求。
這裡特別提到「順序完全相同或者完全相反」，是因為在多欄位的狀況中需要同時考慮所有查詢欄位的順序。以官方文件 [11] 的例子來說，假設 CREATE INDEX 的欄位是 (x, y)，這代表的意思是 x 和 y 都按照正序由小到大排序，也就是像上面的例圖那樣的狀況。這時這個索引適合的 ORDER BY 指令就是 ORDER BY x, y 或者是 ORDER BY x DESC, y DESC，即要嘛兩個都要正序、要嘛兩個都要反序，這樣資料庫才能依靠索引本來的擺放順序來回應。如果說查詢的時候是要求 x 正序 y 反序這種，那麼索引的順序就沒有幫助了，資料庫就必須要在從索引查完之後自行重新排序一次，因而造成效率下降。
B-tree 多欄位索引的範圍查詢
再來談到範圍查詢，其實嚴格來說上面兩個小節已經可以想像到範圍查詢的行為會是什麼了。B-tree 索引的查詢的基本原則就是先垂直地從樹根往樹葉走，走到樹葉後開始往前或後尋訪其他的樹葉，直到可以確認後面不可能再出現符合條件的樹葉為止。因此，大體上會有以下幾種考量：
- 如果索引建立的欄位順序是 (a, b, c)，那麼最理想的查詢條件會是類似
a = ? AND b = ? AND c BETWEEN ? AND ?或者a = ? AND b BETWEEN ? AND ?或者a BETWEEN ? AND ?這幾種。換言之，範圍查詢最好都是落在最後面的欄位。這是因為在 B-tree 的樹狀結構中，我們可以很容易依靠樹幹上的節點資訊，去除掉多數根本不需要查詢的節點。 - 如果查詢的順序是 c BETWEEN ? AND ? 這種，跳過前面的欄位的查詢，本質上就像上頭的範例那樣，索引建立是 (employee_id, subsidiary_id)，但是查詢時只查 subsidiary_id = 20。這時可以先概略把 B-tree 想像成我們有 N 個不同的籃子，每個籃子都以 employee_id 為編號，例如 employee_id = 123 的籃子，裡面會有所有 employee_id = 123 的索引紀錄。當我們要在籃子間查詢 subsidiary_id = 20 的時候，我們沒辦法透過籃子本身的訊息來做任何篩選，因為無法證明有任何一個籃子不可能有 subsidiary_id = 20 的紀錄，因此這時我們會需要把每個籃子都翻遍了才能知道結果。對應到 B-tree 上的狀況，就是我們幾乎得遍訪整個 B-tree 絕大多數的 leaf node 才能確定滿足要求的紀錄有哪些，此時就會造成索引查詢的效率下降。因此，對索引中排第一個的欄位有條件限制，可以具有最高效篩選的效果。接著如果能依序對第二個、第三、第四、…的欄位也有條件限制就更好。
多個索引的合併
這我不確定是不是 PostgreSQL 獨有的黑科技，還是其實各個資料庫都有類似的黑科技。不過從開發者的角度來說，我個人應該盡可能避免需要期待資料庫使用這種方法的狀況。因為一方面這是一種預測問題，其實無法保證資料庫每次對同樣的查詢都會採取同樣的策略，另一方面做這件事本身就會有連帶的效能耗損，例如如果 SQL 敘述中包含了 ORDER BY，那麼資料庫在採取合併多個索引的狀況，無論如何都必須自行重新排序等等。
參考資料
- PostgreSQL - Part VII. Internals
- Introduction to PostgreSQL physical storage
- PostgreSQL 9种索引的原理和应用场景
- 深入浅出PostgreSQL B-Tree索引结构
- PostgreSQL 数据离散性 与 索引扫描性能(btree and bitmap index scan)
- Multicolumn index and performance
- USE THE INDEX, LUKE!
- USE THE INDEX, LUKE! > Slow Indexes, Part I
- PostgreSQL - 11.3. Multicolumn Indexes
- USE THE INDEX, LUKE! > The Where Clause > Concatenated Indexes
- PostgreSQL - 11.4. Indexes and ORDER BY
沒有留言:
張貼留言