标签
PostgreSQL , 数据离散性 , 扫描性能 , 重复扫 , bitmap index scan , 排序扫描
https://github.com/digoal/blog/blob/master/201804/20180402_01.md#%E8%83%8C%E6%99%AF 背景
PostgreSQL中数据的扫描方法很多，常见的有：
1、全表顺序扫描(seqscan)
2、索引+回表扫描(index scan)
3、索引扫描(index only scan)
4、bitmap扫描(bitmap index + block sorted heap scan)
那么对于同一张表，返回同样的记录数，不同的索引，效率有什么差别呢？
回答是和数据的存储线性相关性有关。(PostgreSQL的bitmap scan就是用来解这个问题的)
https://github.com/digoal/blog/blob/master/201804/20180402_01.md#%E4%BE%8B%E5%AD%90 例子
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 统计信息之 - 逻辑与物理存储的线性相关性》 《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法 - PostgreSQL index scan enlarge heap page scans when index and column correlation small.》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
)。
https://github.com/digoal/blog/blob/master/201804/20180402_01.md#%E5%B0%8F%E7%BB%93 小结
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 B-Tree索引结构》 《PostgreSQL 黑科技 - 空间聚集存储, 内窥GIN, GiST, SP-GiST索引》 https://www.postgresql.org/docs/10/static/pageinspect.html![数据库设计理论及应用（4）——概念结构设计1．概念模型 2．销售子系统的分E-R图 3．视图的集成 4．设计基本E-R图[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)