從MySQL的MRR開始

開始之前，先從MySQL入手，看一下MySQL中的MRR機制原理，也就是Multi-Range Read。
MySQL中在按照非聚集索引的範圍查找且需要回表的情況下，比如select * from t where c2>100 and c2<200;c2為非聚集索引。
如果直接根據非聚集索引（二級索引）鍵中的聚集索引鍵去回表，會產生大量的隨機性IO讀取（圖1）。
為了避免頻繁的回表造成的隨機IO，讀取完非聚集索引上符合條件的key值之後，對key值對應的聚集索引鍵（圖2的rowid）排序，然後根據排序後的聚集索引鍵順序地回表，從而避免大量的隨機性IO。
因為MySQL的Innodb表都是聚集表，那麼圖2中的rowid排序後，是順序性的映射到聚集索引的page，從而避回表過程中的隨機性IO。

（圖1） （圖2）

以上原理清楚後，繼續引申出來另外一個經典的問題：
MySQL中的Innodb總是聚集索引表，或者SqlServer中的聚集表，非聚集索引為什麼要拿聚集索引鍵（而非物理地址）作為其行指針？
對於聚集表，表中數據的物理位置因為需要保證按聚集索引建有序，同時意味著其真正的物理的rowid可能會發生變化（比如聚集索引非線性寫入的時候，會導致葉分裂，頁分裂會導致原始記錄的物理位置變化），此時非聚集索引的行指針rowid也要做修改，這樣會導致聚集表中的數據發生物理位置變化的時候，非聚集索引也要做相應的變化，如果非聚集索引用對應的聚集索引鍵做指針的話，就不會發生該問題。

由以上兩個問題做鋪墊，來看看Postgresql中如何處理類似的問題。

Postgresql中的點陣圖掃描（bitmap scan）

如果遇到類似於上述的查詢（select * from t where c2>100 and c2<200;c2為非聚集索引的）情況下，查詢結果是一個範圍，那麼Postgresql在回表的過程中，如何避免類似於上述圖1中的隨機性IO？
先弄清楚Postgresql的數據存儲特點，Postgresql表的數據都是以堆表（heap）的形式存儲的，因此Postgresql中不存在所謂的聚集索引，同時意味著其記錄在物理結構上可以是無序存儲，不會產生所謂的頁分裂（page split）。
那麼Postgresql中的行指針，這裡稱作rowid，正常情況是不會因為新數據的寫入導致類似於MySQL或者sqlserver中的頁拆分（page split）。
然後再說Postgresql的bitmap scan，bitmap scan的作用就是通過建立點陣圖的方式，將回表過程中對標訪問隨機性IO的轉換為順行性行為，從而減少查詢過程中IO的消耗。
先從一個非常簡單的demo入手，如下查詢，是一個典型的根據非聚集索引且需要回表的查詢，滿足以上的條件。
可以看到在對idx_c5上執行了一個Bitmap Index Scan，由於Bitmap Index Scan記錄的是符合條件的記錄所在的block，而非記錄的指針，然後對這些block排序後再進行回表，Bitmap Index Scan之後有一個Recheck Cond是因為解析block的時候需要Recheck 。
參考這裡：The bitmap is one bit per heap page. The bitmap index scan sets the bits based on the heap page address that the index entry points to.

最後，bitmap scan之後，對錶的訪問，總是通過bitmap Heap Scan完成。也就是執行計劃的第一行。
這裡的bitmap scan與上文中提到的MySQL中的MRR的思路算是一致的，都是通過中間一個緩存來避免隨機性的IO訪問，提升查詢效率。
與基於聚集索引的總是從B+樹的根節點通過二分法查找訪問相比，對於postgresql中的這種直接基於物理Id的訪問，從這一點上看，效率並不一定低。

bitmap scan的訪問優化是基於代價考慮的，對於類似的查詢，不總是一定走bitmap scan，如下，當訪問的數據範圍足夠小的時候，可能不會走bitmap scan。

另外，bitmap scan的優化可以是基於不同欄位或者不同篩選條件的，比如 where a>m and b>n（BitmapAndPath），亦或是where a>x or b>y（BitmapOrPath）這種訪問方式，都可以通過bitmap scan來優化實現。

只不過筆者這裡還有一個問題，因為postgresql中對行的update都是直接刪除原始記錄，然後新寫入一條記錄來實現的，只要這條記錄的物理頁面不變，那麼非聚集索引的行指針就不變，如果這個記錄的物理頁面發生了變話，是不是索引的指針也會發生變化？

相關參數

正常情況下，是否用到bitmap scan優化，postgresql 優化器是可以選擇出來一種最優的方式來執行的，但不保證總是可以生成最優化的執行計劃，可以通過禁用bitmap scan或者 seqscan來嘗試對比和調優。
任何優化都是一個系統工程，而不是一個單點工程，通過不同資源的消耗比例來提升整體性能，bitmap scan也並非完美無瑕，其優化理念是通過bitmap 的生成過程中增加記憶體和CPU欄位消耗來減少IO消耗。
如果是高性能存儲或者有充足的記憶體，並不一定總是發生物理IO，那麼IO並不一定會是瓶頸，相反機械地去做bitmap的生成的話，反倒是一種浪費。
此時可以根據具體的IO能力，比如磁碟的隨機讀和順序讀代價參數，或者是禁用bitm scan等，來做整體上的優化方案。

參考
https://dba.stackexchange.com/questions/119386/understanding-bitmap-heap-scan-and-bitmap-index-scan
https://blog.csdn.net/weixin_33672400/article/details/89734245