以 PostgresSQL 為例了解資料庫的 Query Plans
前陣子因為閱讀了 DDIA (Designing Data-Intensive Applications)這本經典著作的第三章節 — 儲存與檢索，而花了一點時間去了解資料庫底層的架構與運作機制，學習資料庫較底層的相關知識可以讓身為開發者的我們在要為資料庫進行效能調校時能夠有足夠的基礎，例如 query 要怎麼寫效能會比較好？index 怎麼下可以達到最好的效果…等等，因此我認為是十分值得研究的主題。
這篇文章我將以 PostgresSQL 為例，探究資料庫在不同條件與狀況下實際上是如何執行資料的儲存與查詢。
PostgresSQL 的資料儲存結構
相較於 MySQL 有分為 Clustered Index 與 Secondary Index 的索引結構（關於聚集索引的概念可以參考這篇文章），PostgresSQL 在設計上並沒有 Clustered Index Tree ，在 PostgresSQL 中實際的資料是儲存在稱為 Heap 的無序結構之中，這也就意味著在 Heap 空間中對於儲存的資料是沒有順序保證的。
而我們在 PostgresSQL Table 中建立的索引 (index)，則會建立出一個對應的 B-Tree 索引結構（PostgresSQL 也有支援其他種類的索引結構），Tree 的節點（Node）中會儲存一個指向 Heap 中對應完整資料的 Page 所在位置的指標。所以當資料庫在執行 query 時決定使用索引查詢，就會從索引樹狀結構直接拿到指標位置去 Heap Storage 裡面對應的 Page 取出資料。
行前準備：Container & Seed Data
了解了 PostgresSQL 最基本的索引查詢機制與儲存結構後，我們才能往下繼續探討，不過在這之前得先準備一些 Seed Table 與 Data 才能方便演示。
首先透過 Docker 建立一個 Postgres Container Instance
接著進入該 Container 的 Postgres psql Cli
建立名為 for_demo 的 table，並且包含 a, b, c 三個欄位，其中 a 為 SERIAL 的 PK，可以看到 PostgresSQL 預設會為 Primary Key 建立 B Tree 索引
接著使用 generate_series 塞入 seed data
可以發現這個 table 就被成功塞入大量的 seed data 囉！
資料庫表的掃描計畫 Table Query Plans
雖然我們可以為 Table 的欄位建立 index，不過這並不代表資料庫在執行查詢時就ㄧ定會選擇使用索引結構來做查詢，實際上資料庫會透過 SQL Planner/Optimizer 來決定出它認為效率最高的查詢方式。這也就代表理解 Planner 的決策方式可以讓我們在撰寫 SQL Query 或是建立索引時避免不必要或是無用的行為。
在 PostgresSQL 中，對於資料庫 Table 的 Query Plans 大致上可以分為以下幾種（其實種類並不只這些，但以下幾種是最常見的，而不同的資料庫也會有不一樣的 Query Plans 分類）：
- Seq Scan
- Index Scan
- Index Only Scan
- Bitmap Heap Scan
Seq Scan
Seq(Sequential) Scan 就是按照表的資料的排序從頭到尾一次掃描與檢索，每次掃描都會需要遍歷所有的資料，雖說是最簡單最基本的掃表方式，但是執行的成本卻比較大。
想要知道 SQL Planner 最後選擇什麼方式執行掃描，可以在 query 語句前加上 explain，以剛剛建立的 for_demo table 為例：
由於我們沒有在 query 裡加上條件語句，所以 SQL Planner 會選擇 Seq Scan 的方式去查詢。
Index Scan
所謂 Index Scan 就是會先走訪索引的樹狀結構，並從該結構中找到符合 query 要求的節點，在文章上半段有提過這些節點還存有要查詢的資料在 Heap 空間裡的指標，得到指標後就可以再到 Heap 空間具體的 Page 去抓取資料。
要特別注意的是 Index Scan 等於是執行了兩次的 I/O 操作，首先到索引結構，再到 Heap 空間中的 Page 找想要的資料。
因此並不是有下索引 SQL Planner 就ㄧ定會選擇 Index Scan，例如以下針對索引欄位的範圍查詢
SQL Planner 判斷與其執行大量的 I/O 操作，不如使用 I/O 量較小的 Seq Scan，整體效能可能會更高。
Index Only Scan
有沒有辦法可以減少索引的 I/O 操作呢？有的！
Index Scan 需要兩次 I/O 的主因是資料庫在索引結構中找不到 SQL Query 要求抓取的資料，因此必須再到 Heap 去抓取，那如果索引結構剛好就有 query 要的資料呢？
因為 a 這個欄位的資料本身就存在索引結構中，因此 SQL Planner 選擇使用 Index Only Scan，直接到索引結構中抓取資料而不需要再到 Heap 空間，可以省下一次的 I/O。
除了剛好要抓取索引欄位的資料外，PostgresSQL 也在第 11 版支援了 INCLUDE clause，讓開發者可以在建立索引時把某些欄位的資料也帶到索引結構中。
我們再針對欄位 b 建立一個索引，不同的是這次加上 INCLUDE clause 將 c 欄位也放到索引中，此時如果透過欄位 b 的索引抓取 c 欄位的資料，就可以使用 Index Only Scan 抓取。
雖然這麼做看似美好，不過使用 INCLUDE clause 會增加 memory 的使用量，因此在使用上還需要再進一步權衡一下利弊。
Bitmap Heap Scan
Bitmap Heap Scan 並不是每個資料庫都支援，像 MySQL 在筆者撰寫這篇文的當下就是尚未支援的。
Bitmap Scan 常發生於對多個單列索引使用組合查詢(And | Or)的 SQL 語句中。例如上方圖片筆者就是分別欄位 b 與 欄位 c 建立單列索引，並使用 and 組合語句來查詢。
那 Bitmap Scan 究竟是如何運作的呢？它會在記憶體中對 query 的查詢條件中的每個索引建立一個 bitmap 串，這個 bitmap 串中每個 bit 對應一個 Heap Page，如果 Heap Page 有符合條件的 Row，該 bit 就會被標記為 1，反之則為 0。
|1000000000010000000100001100| bitmap b而根據 SQL Query 條件中索引列的多寡，會組成多個 bitmap 串，以上方圖片以 b 與 c 兩個單列索引來舉例：
|1000000000010000000100000100010001| bitmap b
|0000010000010001000100000100010000| bitmap c
And (當然也有可能是 Or 運算)
|0000000000010000000100000100010000| Combined bitmapScan the heap only for matching pages (1)
最後資料庫只會針對 Combined 後是 1 的 bit 去做查詢。
Bitmap Scan 與 Index Scan 的差別是 Index Scan 是先去掃描一遍索引，從索引中找出符合要求的指標，再回到 Heap 中具體的 Page 去抓取。而 Bitmap Scan 可以解決「Index Scan 每當從索引獲取指標，就會立即訪問 Heap 的 Page，導致一個 Page 有可能被重複多次訪問的問題。」Bitmap Scan 一次性的從索引結構中獲取所有的 Pointer，並使用記憶體中的 Bitmap 資料結構進行排序，最後按照順序訪問 Heap Page，因此可以避免 Page 多次被放問的問題。
當然 Bitmap Scan 有它的優點也有缺點，它透過建立 bitmap 的方式將 Index Scan 對 Heap 上的 Page 的 Random I/O 轉換成順序行為，以減少 I/O 操作的消耗。而它的缺點則是它是透過增加 CPU 與 Memory 的消耗來換取 I/O 操作的節省，因此這樣的犧牲也需要做一個權衡。
結論
雖然說 SQL Planner 會幫我們選出它認為最高效率的 query plan，不過透過本文我們可以發現其實開發者撰寫的 SQL query 與下 Index 的方式其實都有機會左右 SQL Planner 的決策，這也是我認為應該去理解資料庫底層運作機制的原因之一。這篇文章只是簡單介紹在 PostgresSQL 中幾種常見的 query plans，實際上除了還有其他種 query plans 沒有提到以外，開發者也可以對資料庫設置一些額外的設定，例如禁止資料庫使用 Bitmap Scan…等等，這就需要開發者對於資料庫與專案實際情況有更深度的理解才能做出正確的判斷與調教了，就請有興趣的讀者自行研究囉！
