索引順序掃描引發的heap scan IO放大, 背後的統計學原理與解決辦法

postgresql , 優化器 , 索引掃描 , 堆掃描 , io放大

通過b-tree索引掃描可能會帶來了巨大的heap page scan數目，即io的放大.

為什麼呢？

請接下去看完本文揭曉答案。

io放大的後果：

如果資料庫的單個資料塊（block_size）很大的話, 這種情況帶來的負面影響也将被放大. 例如32k的block_size顯然比8k的block_size掃描開銷更大.

本文将講解一下索引掃描引發的heap page scan放大的原因, 以及解決辦法。 告誡大家注意這樣的事情發生，以及如何對付。

測試環境的成本因子如下 :

我們先建立一個測試表, 插入一些測試資料, 建立一個索引 :

我們檢視這個表和索引占用了多少資料塊.

接下來分析以下查詢, 我們看到走索引掃描, 并且掃描的資料塊是13547個. (10209 +3338).

掃描的資料塊和實際表占用的資料塊和索引塊相當.

這裡使用索引掃描為什麼沒有帶來heap page掃描的放大呢? 原因和值的順序與實體存儲順序一緻.

如下, 那麼索引掃描的時候沒有發生塊的跳躍 :

接下來我們插入随機資料, 使得索引掃描時發生heap page的跳躍.

查詢目前的id列的順性, 非常小, 說明這個值非常的離散.

從資料分布結果中也能看到這點.

按以下順序掃描, 顯然會出現大量的資料塊的跳躍.

目前這個表和索引占用的資料塊如下 :

接下來我們執行這個sql, 發現走索引掃描了, 但是顯然shared hit變得非常的大, 原因就是每掃描一個索引條目, 對應到heap page number都是跳躍的. 造成了heap page掃描的放大. 具體放大多少行呢, 和差出來的行差不多.

heap page scan放大評估和索引掃描了多少條目有關, 但至少有98229個條目 :

如果純随機掃描, 那麼将要掃描98229次heap page. 也就不難了解這裡的buffers: shared hit=97837.

但是實際上, postgresql的優化器似乎沒有關注這些開銷, 因為我們看到的成本隻有2035.38 (這裡和random_page_cost以及effective_cache_size 大于整個表和索引的空間有關)

接下來把random_page_cost設定為2和1, 兩個cost相減, 看看到底優化器評估了多少個塊掃描.

相減得到293, 即優化器認為index scan需要掃描293個資料塊.

接下來我把enable_indexscan關閉, 讓優化器選擇bitmap scan.

從bitmap scan的結果可以看到, 實際掃描的塊為292個, 相比index scan少掃描了9.7萬多資料塊. 并且實際的執行時間也是bitmap scan要快很多.

本例postgresql在計算index scan的random page的成本時, 評估得到的index scan成本小于bitmap index scan的成本, 然而實際上當correlation 很小時, index scan會掃描更多次的heap page, 成本遠遠大于bitmap scan.

本例發生這樣的情況, 具體的原因和我們的成本因子設定有關系, 因為錯誤的設定了random_page_cost以及表和索引的大小小于effective_cache_size, postgresql在使用這樣的成本因子計算成本時, 出現了bitmap scan大于index scan成本的結果.

是以設定正确的成本因子非常重要, 這也是我們需要校準成本因子的原因.

例子 :

預設的成本因子如下

表和索引的大小如下

把random_page_cost校準為10, 這個在一般的硬體環境中都适用.

預設選擇了全表掃描

關閉全表掃描後, 選擇了bitmap scan

關閉bitmap scan後選擇了index scan, index scan的cost遠遠大于評估到的bitmap scan. 因為我們使用了正确的成本因子.

當錯誤的設定了random_page_cost=1=seq_page_cost時, 執行計劃會有所改變(改變出現在effective_cache_size大于表和索引的大小時).

重新進入psql, 所有因子重回預設值.

目前看來還正确

當effective_cache_size還是小于表和索引時, 執行計劃依舊正确

當effective_cache_size大于表和索引的大小時, index scan的成本低于bitmap scan的成本了.

如果這個時候再把random_page_cost調回正常值10, 則執行計劃回歸正常.

本例說明了成本因子的重要性. 千萬不能随意設定, 即使完全記憶體命中, random_page_cost也應該大于seq_page_cost.

我在前一篇blog中測試了這樣的場景, 完全記憶體命中的場景可以設定 random_page_cost=1.6; seq_page_cost=1;

<a href="https://github.com/digoal/blog/blob/master/201311/20131126_03.md">《優化器成本因子校對 - postgresql explain cost constants alignment to timestamp》</a>

b-tree掃描，對于線性相關性不好的列，會放大heap scan 的io消耗，使用bitmap可以解決。

線性相關性的知識如下

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

<a href="https://github.com/digoal/blog/blob/master/201502/20150228_01.md">《postgresql 統計資訊之 - 邏輯與實體存儲的線性相關性》</a>

1. 當字段的存儲與值線性相關性差時，使用index scan會導緻大量的heap scan io放大。

2. bitmap index scan巧妙的解決了放大的問題，bitmap index scan對index item按照ctid(heap行号)排序後再取資料，避免了單個heap page的重複io。

3. 使用cluster對heap資料按索引順序進行重排，也可以解決heap scan io放大的問題。

3. src/backend/optimizer/path/costsize.c