PostgreSQL 数据离散性 与 索引扫描性能(btree & bitmap index scan)
背景
PostgreSQL中数据的扫描方法很多，常见的有：
1、全表顺序扫描(seqscan)
2、索引+回表扫描(index scan)
3、索引扫描(index only scan)
4、bitmap扫描(bitmap index + block sorted heap scan)
那么对于同一张表，返回同样的记录数，不同的索引，效率有什么差别呢？
回答是和数据的存储线性相关性有关。(PostgreSQL的bitmap scan就是用来解这个问题的)
例子
1、构造一份数据，1000万记录，其中一个字段存储线性相关（时序），另一个字段乱序。
postgres=# create table corr_test(c1 int, c2 int);
CREATE TABLE
postgres=# insert into corr_test select generate_series(1,10000000) , random()*10000000;
INSERT 0 10000000
2、创建索引
postgres=# create index idx_corr_test_1 on corr_test (c1);
CREATE INDEX
postgres=# create index idx_corr_test_2 on corr_test (c2);
CREATE INDEX
3、记录如下
postgres=# select count (distinct c1), count(distinct c2) from corr_test ;
-[ RECORD 1 ]---
count | 10000000
count | 6321273
4、查看两个字段的存储线性相关性(correlation)
《PostgreSQL 计算 任意类型 字段之间的线性相关性》
《PostgreSQL 统计信息之 - 逻辑与物理存储的线性相关性》
postgres=# analyze corr_test ;
ANALYZE
postgres=# select * from pg_stats where tablename='corr_test';
-[ RECORD 1 ]----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname | public
tablename | corr_test
attname | c1
inherited | f
null_frac | 0
avg_width | 4
n_distinct | -1
most_common_vals |
most_common_freqs |
histogram_bounds | {264,92701,193390,294012,388058,485346,593684,685077,789274,894145,997995,1089782,1200355,1283219,1378625,1483703,1579768,1686405,1784210,1881611,1986283,2081148,2174498,2283021,2374024,2488115,2595505,2692236,2786642,2885331,2986908,3084688,3189282,3286800,3391763,3498828,3590785,3680583,3783899,3899023,3986142,4086260,4182787,4279303,4376024,4474895,4557993,4658238,4769987,4860761,4952944,5060715,5167068,5268284,5368289,5478782,5576872,5682785,5777336,5882893,5979896,6092909,6192493,6283722,6386922,6481272,6590049,6684505,6784638,6877767,6977433,7073017,7169473,7267987,7374703,7467565,7572386,7674582,7770014,7866422,7977399,8086125,8193108,8289676,8391245,8493604,8600614,8697894,8800583,8899375,9003507,9112105,9205179,9296198,9397346,9498380,9594476,9690568,9788951,9895128,9999848}
correlation | 1 # 线性相关
most_common_elems |
most_common_elem_freqs |
elem_count_histogram |
-[ RECORD 2 ]----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname | public
tablename | corr_test
attname | c2
inherited | f
null_frac | 0
avg_width | 4
n_distinct | -0.51138
most_common_vals | {426318,766194,855444,1149657,1200975,1220163,1365550,2088174,2140281,2763150,3056426,3112825,3121883,3155120,3215926,3301333,3560657,4426775,4594877,4777035,5252068,5677480,5854408,6189177,6218589,6244509,6302874,6739846,6791877,7114618,7339405,7868148,8246024,8401824,8581341,8804281,9126954,9441793,9478704,9596435,9695680,9878570,9971294}
most_common_freqs | {6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05}
histogram_bounds | {271,106225,201567,294497,392824,494367,588776,678500,770927,868980,969487,1070023,1163902,1263888,1370143,1469104,1560941,1663822,1774042,1878441,1968698,2062914,2165452,2269587,2379207,2488012,2588110,2687086,2794150,2901621,3008186,3110180,3209342,3310782,3405087,3496885,3595592,3703924,3809056,3912808,4005481,4106138,4198143,4299460,4389301,4488847,4586914,4678114,4783071,4874577,4967846,5068838,5157910,5258764,5360550,5461419,5549937,5652323,5748370,5850884,5956837,6062955,6164560,6260734,6359909,6464077,6563959,6656376,6757534,6846335,6939362,7033698,7137829,7252307,7356135,7453579,7553301,7656348,7766475,7860057,7960997,8067532,8176088,8278098,8378888,8473638,8589748,8697667,8797619,8894596,8999418,9101559,9200533,9305406,9394744,9497708,9598103,9699825,9803509,9901242,9999667}
correlation | 0.00410469 # 线性不相关
most_common_elems |
most_common_elem_freqs |
elem_count_histogram |
这两个字段的相关性反差非常明显，C1字段的存储完全线性相关，C2字段完全不相干。
如果按索引顺序扫描这张表，使用C1索引，由于存储线性相关，因此在HEAP上的BLOCK扫描也几乎是线性的。
然而C2字段由于存储完全不相关，如果使用C2字段的索引扫描，会导致IO重复扫描，导致放大。
5、强制模拟索引扫描：
postgres=# set enable_seqscan=off;
SET
postgres=# set enable_bitmapscan =off;
SET
线性扫描，扫描71573个数据块
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from corr_test where c1 between 1 and 10000000;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_corr_test_1 on public.corr_test (cost=0.43..274413.40 rows=10000033 width=8) (actual time=0.017..1919.720 rows=10000000 loops=1)
Output: c1, c2
Index Cond: ((corr_test.c1 >= 1) AND (corr_test.c1 <= 10000000))
Buffers: shared hit=71573
Planning time: 0.142 ms
Execution time: 2771.570 ms
(6 rows)
离散扫描，每个BLOCK几乎都被重复扫描了140次，一个BLOCK刚好存储140条记录，说明这140条记录在顺序上完全离散。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from corr_test where c2 between 1 and 10000000;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using idx_corr_test_2 on public.corr_test (cost=0.43..36296.14 rows=50000 width=8) (actual time=0.029..6563.525 rows=9999999 loops=1)
Output: c1, c2
Index Cond: ((corr_test.c2 >= 1) AND (corr_test.c2 <= 10000000))
Buffers: shared hit=10027095
Planning time: 0.089 ms
Execution time: 7421.801 ms
(6 rows)
6、PostgreSQL对于这种数据，会使用位图扫描，位图扫描的原理是从索引中得到HEAP BLOCK ID，然后按HEAP BLOCK ID 排序后顺序扫描。
排序扫描后，按两个字段的索引扫描，扫描的BLOCK就一样多了。不会有重复扫描的现象。
postgres=# set enable_bitmapscan =on;
SET
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from corr_test where c1 between 1 and 10000000;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on public.corr_test (cost=2844700.77..3038949.27 rows=10000033 width=8) (actual time=440.230..1691.523 rows=10000000 loops=1)
Output: c1, c2
Recheck Cond: ((corr_test.c1 >= 1) AND (corr_test.c1 <= 10000000))
Heap Blocks: exact=44248
Buffers: shared hit=71573
-> Bitmap Index Scan on idx_corr_test_1 (cost=0.00..2842200.77 rows=10000033 width=0) (actual time=433.548..433.548 rows=10000000 loops=1)
Index Cond: ((corr_test.c1 >= 1) AND (corr_test.c1 <= 10000000))
Buffers: shared hit=27325
Planning time: 0.144 ms
Execution time: 2510.658 ms
(10 rows)
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from corr_test where c2 between 1 and 10000000;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on public.corr_test (cost=2844700.76..3038949.24 rows=10000032 width=8) (actual time=688.150..1939.259 rows=9999998 loops=1)
Output: c1, c2
Recheck Cond: ((corr_test.c2 >= 1) AND (corr_test.c2 <= 10000000))
Heap Blocks: exact=44248
Buffers: shared hit=71573
-> Bitmap Index Scan on idx_corr_test_2 (cost=0.00..2842200.75 rows=10000032 width=0) (actual time=681.488..681.488 rows=9999998 loops=1)
Index Cond: ((corr_test.c2 >= 1) AND (corr_test.c2 <= 10000000))
Buffers: shared hit=27325
Planning time: 0.147 ms
Execution time: 2758.621 ms
(10 rows)
但是大家请注意BITMAP SCAN会引入一个recheck的过程，因为按BLOCK顺序扫描时，只有BLOCK ID，并不知道这个BLOCK里面哪条记录是匹配的。所以必须要recheck。
因此BITMAP SCAN降低了IO放大，但是引入了recheck。
在成本评估时，起作用的两个成本因子：
1、random_page_cost，离散扫描成本，乘以要扫描的块数。
2、cpu_operator_cost，函数或操作符的基本成本，评估的记录数乘以这个值再乘以函数或操作符的基本成本系数(pg_proc.procost)。
PostgreSQL还提供了一个cluster接口，允许用户强制数据按索引顺序分布，支持btree,gist索引。
postgres=# cluster corr_test using idx_corr_test_2 ;
按c2字段索引重组数据后，在C2字段的线性相关性变成了1，而C1字段就乱序了。
postgres=# select correlation from pg_stats where tablename='corr_test' and attname='c2';
-[ RECORD 1 ]--
correlation | 1
postgres=# select correlation from pg_stats where tablename='corr_test' and attname='c1';
-[ RECORD 1 ]------------
correlation | -0.00256875
postgres=# select ctid,c1,c2 from corr_test limit 10;
ctid | c1 | c2
--------+---------+----
(0,1) | 4088697 | 2
(0,2) | 51611 | 3
(0,3) | 2990090 | 3
(0,4) | 5416221 | 3
(0,5) | 7579331 | 4
(0,6) | 2370036 | 6
(0,7) | 1473765 | 10
(0,8) | 1190875 | 13
(0,9) | 5966135 | 13
(0,10) | 7936308 | 13
(10 rows)
小结
PostgreSQL使用索引扫描时，如果索引顺序与数据存储顺序的相关性很差，会导致HEAP BLOCK扫描的放大（由于乱序导致一个BLOCK被多次读取）。
使用bitmap scan，可以消除HEAP BLOCK扫描的放大问题（按BLOCK ID排序后扫描一遍），但是会引入一个问题，需要rechek。
所以仅仅当评估满足条件的记录数与BLOCK内实际含的记录数相比，比例较大时，使用bitmap scan带来的效果非常好，如果比例较小，那么就当operator带来的消耗比扫描IO带来的消耗小时更划算。
(例如评估出来满足条件的有1000条，扫描100个BLOCK每个BLOCK有50条记录，那么实际上比例就是0.2=1000/(100*50))
除了考虑数据存储的离散性，索引页本身的组织也是离散的，详见：
《PostgreSQL 黑科技 - 空间聚集存储, 内窥GIN, GiST, SP-GiST索引》
https://www.postgresql.org/docs/10/static/pageinspect.html
参考
《PostgreSQL pg_stats used to estimate top N freps values and explain rows》
《PostgreSQL 统计信息pg_statistic格式及导入导出dump_stat - 兼容Oracle》
《PostgreSQL pg_stat_ pg_statio_ 统计信息(scan,read,fetch,hit)源码解读》
《PostgreSQL 计算 任意类型 字段之间的线性相关性》
《PostgreSQL 统计信息之 - 逻辑与物理存储的线性相关性》