PostgreSQL学术之美-从数据相关性看索引扫描IO放大问题
PostgreSQL学术之美-从数据相关性看索引扫描IO放大问题
PostgreSQL是学术派的数据库，这体现在它架构设计的方方面面，例如多表连接动态规划、改进的内存置换时钟扫描算法、空间索引等，PG甚至将优化器的各类代价因子放开成参数供我们调整，这真是很开放的举动。
今天主要聊聊数据离散读、相关性、io放大的问题。
先来看看什么是数据相关性，线性相关性是统计学的概念，反映了变量之间的线性相关程度，比如职工收入水平与工作年限，商品销量与销售价格之间。线性相关系数处于-1到1之间，计算公式如下：
其中，Cov(X,Y)为X与Y的协方差，Var[X]为X的方差，Var[Y]为Y的方差
在PG里，这种相关性体现在数据表的物理存储顺序和逻辑存储顺序的相关性上。相关性越高，索引扫描的离散读概率越低，相关性越低，索引扫描的离散读概率越高，这也是造成io放大的原因。
这里的离散读指的是数据块的离散读，PG里索引扫描如果无法使用仅索引扫描（index only scan），那么索引扫描会回表，回表查询涉及到数据块io的问题，和mysql聚簇索引不同的是，如果按照索引扫描的顺序读取数据块，而数据的值如果在存储上是离散的，那么可能造成数据块的离散读，增加了io的次数，引起io放大。当然pg也提供了cluster的命令来进行数据对某个索引的聚簇，但是该命令会申请排他锁。
在PG的统计信息pg_stats表中correlation列也记录了表的每一列的线性相关性信息，pg也提供了corr(a1,a2)函数来计算a1和a2之间的线性相关性：
test=# \d pg_stats
View "pg_catalog.pg_stats"
Column | Type | Collation | Nullable | Default
------------------------+----------+-----------+----------+---------
schemaname | name | | |
tablename | name | | |
attname | name | | |
inherited | boolean | | |
null_frac | real | | |
avg_width | integer | | |
n_distinct | real | | |
most_common_vals | anyarray | | |
most_common_freqs | real[] | | |
histogram_bounds | anyarray | | |
correlation | real | | |
most_common_elems | anyarray | | |
most_common_elem_freqs | real[] | | |
elem_count_histogram | real[] | | |现在做一个实验，创建一个表，两列分别模拟相关和离散，来看看区别。
test=# create table test(c1 int,c2 int);
CREATE TABLE
test=# insert into test select generate_series(1,5000000),random()*5000000;
INSERT 0 5000000两个列分别创建索引，并收集统计信息
test=# create index on test(c1);
CREATE INDEX
test=# create index on test(c2);
CREATE INDEX
test=# analyze test;
ANALYZE查看两个列的线性相关性
test=# select tablename,attname,correlation from pg_stats where tablename='test';
tablename | attname | correlation
-----------+---------+--------------
test | c1 | 1
test | c2 | 0.0051113297
(2 rows)可以看到c1列由于是完全有序的，所以相关系数为1，完全正相关，c2由于是离散的，所以相关性很低。
基于c1查询
test=# explain (analyze,buffers,timing) select * from test where c1<10000;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Index Scan using test_c1_idx on test (cost=0.43..331.84 rows=9852 width=8) (actual time=0.030..4.583 rows=9999 loops=1)
Index Cond: (c1 < 10000)
Buffers: shared hit=75
Planning:
Buffers: shared hit=4
Planning Time: 0.191 ms
Execution Time: 5.867 ms
(7 rows)基于c2查询
test=# explain (analyze,buffers,timing) select * from test where c2<10000;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=211.11..18234.34 rows=10152 width=8) (actual time=8.075..25.962 rows=10038 loops=1)
Recheck Cond: (c2 < 10000)
Heap Blocks: exact=8081
Buffers: shared hit=8118
-> Bitmap Index Scan on test_c2_idx (cost=0.00..208.57 rows=10152 width=0) (actual time=4.197..4.197 rows=10038 loops=1)
Index Cond: (c2 < 10000)
Buffers: shared hit=37
Planning:
Buffers: shared hit=4
Planning Time: 0.164 ms
Execution Time: 27.075 ms
(11 rows)可以看到c2的查询走了bitmap index scan，bitmap index scan就是为了解决数据块离散io问题引入的索引扫描算法，关于bitmap index scan后续再单独讨论，这里为了屏蔽bitmap index scan的影响，将enable_bitmapscan参数关闭，重新查看执行计划
test=# set enable_bitmapscan=off;
SET
test=# explain (analyze,buffers,timing) select * from test where c2<10000;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Index Scan using test_c2_idx on test (cost=0.43..33341.09 rows=10152 width=8) (actual time=0.029..18.066 rows=10038 loops=1)
Index Cond: (c2 < 10000)
Buffers: shared hit=10073
Planning:
Buffers: shared hit=4
Planning Time: 0.185 ms
Execution Time: 19.195 ms
(7 rows)从上面的执行计划对比可以看到，基于c1字段走索引扫描时，优化器评估的启动代价为0.43，总代价为331.84，buffer io为75次，而基于c2字段走索引扫描时，优化器评估的启动代价为0.43，总代价为33341.09，buffer io为10073次。
可以看到两者的差距在于buffer io的次数，当数据块没有按照索引聚簇分布很离散时，在使用索引扫描时可能造成大量的重复块多次访问，造成io的放大，影响性能，为了解决这个问题，PostgreSQL引入bitmap index scan，关于bitmap index scan和index scan的内容后面再单独展开。
腾讯云开发者
