索引顺序扫描引发的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