PostgreSQL BRIN索引内核代码优化思考

xiaoxiao2022-05-18 212

背景

BRIN是PostgreSQL 9.5新增的块级索引接口，存储了被索引字段在块级别的边界值（最大值、最小值）以及其他统计信息。

当需要对某个字段进行检索时，需要扫描整个BRIN索引（这个是BRIN索引内核层面将来值得优化的点）。然后跳过不符合条件的HEAP PAGE，扫描复合条件的HEAP PAGE。实现数据过滤的目的。

原理所致，对于建立BRIN索引的字段，相关性越好，BRIN索引的过滤性就越好。

BRIN同时还支持多种类型、多列字段等。

1、多列

2、单列

3、空间数据类型

如果你还对BRIN不了解，可以阅读我写过的一些案例文章。

《PostGIS空间索引(GiST、BRIN、R-Tree)选择、优化 - 阿里云RDS PostgreSQL最佳实践》

《自动选择正确索引访问接口(btree,hash,gin,gist,sp-gist,brin,bitmap...)的方法》

《PostgreSQL 并行写入堆表，如何保证时序线性存储 - BRIN索引优化》

《PostgreSQL 10.0 preview 功能增强 - BRIN 索引更新smooth化》

《PostgreSQL 聚集存储与 BRIN索引 - 高并发行为、轨迹类大吞吐数据查询场景解说》

《PostgreSQL 物联网黑科技 - 瘦身几百倍的索引(BRIN index)》

《PostgreSQL 9.5 new feature - lets BRIN be used with R-Tree-like indexing strategies For "inclusion" opclasses》

《PostgreSQL 9.5 new feature - BRIN (block range index) index》

BRIN索引支持的参数pages_per_range的作用是多少个块统计一次边界值。

本文将以下面这个场景中的案例为例，讲解一下BRIN索引的pages_per_range参数的设置算法，以及BRIN索引列的优化，BRIN索引的内核优化思路等。

《万亿(100TB)级电商广告 - PostgreSQL单机如何实现毫秒级圈人》

brin扫描原理

BRIN索引的扫描原理很简单，扫描BRIN的元数据，根据元数据和用户输入的条件进行比较，过滤不符合条件的HEAP PAGE，只扫描需要扫描的HEAP PAGE。

BRIN索引列的相关性优化

由于BRIN是块级索引，如果块的边界范围很大，或者说块与块之间的重叠度很高，那么BRIN索引的过滤性就很差。

因此BRIN仅仅适合存储与值线性相关性很好的列。

pg_stats.correlation可以观察列的线性相关性。

当然我们也可以人为的修改它的存储，改变它的线性相关性（排序存储是最简单的方法），甚至可以改变局部的线性相关性。你想知道更深层次原理的话，请参考如下文章。

《解密上帝之手 - 阿里云HDB for PostgreSQL数据库metascan特性(存储级、块级、batch级过滤与数据编排)》

多个条件扫描可以优化的点

当我们的查询条件是多个查询条件时，PostgreSQL会将多个索引的扫描合并成一个，跳过不符合条件的。这既是bitmapAnd, bitmapOr。

《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》

但是由于目前PostgreSQL BRIN索引的扫描需要扫描整个BRIN索引，因此每个条件都需要扫描一次，那么当BRIN本身比较大时，条件一多时间就会成倍增加。

BRIN索引的扫描方式，是PostgreSQL未来内核层面可以优化的点，比如将BRIN的边界再按树组织一下，不需要每次都全扫（太过暴力）。目前PostgreSQL没有做，也许是没有人有在几百亿的单表上建单块粒度(pages_per_range=1)的BRIN索引。

实际上我后面会来给大家展示这个问题。大伙就知道我为什么要优化pages_per_range参数了。

BRIN索引参数pages_per_range选择推荐算法

pages_per_range是粒度，默认为128（表示每128个数据块统计一次边界），决定了两件事情。

1、BRIN索引的精确度。pages_per_range=1，说明边界精确到1个数据块。pages_per_range越小，精度越高，过滤性就越好（注意过滤性越好取决于列的线性相关性很好的情况下，否则就是白瞎）。

2、BRIN索引本身的大小。pages_per_range越小，BRIN索引本身就越大。BRIN越大，单次走BRIN索引扫描BRIN块的成本就越高。

那么pages_per_range到底设置为多大合适呢？

根据我的经验，311GB的表，设置为512是不错的选择。越小的表，pages_per_range设置可以越小。

311GB的表，如果pages_per_range=1，BRIN索引本身就有1.6GB这么大了。扫一下很费劲。当设置为512时，大概只有几MB。扫一下很快（虽然过滤性可能差了，但是BRIN是每个条件都要扫一次的）。

DEMO

1、pages_per_range=1

2、pages_per_range=128

postgres=# \d bi_user_tmall_vis1 Unlogged table "public.bi_user_tmall_vis1" Column | Type | Collation | Nullable | Default --------+---------+-----------+----------+--------- uid | bigint | | | bid | bigint | | | cnt | integer | | | Indexes: "idx_bi_user_tmall_vis1" brin (bid, cnt) WITH (pages_per_range='128') public | idx_bi1 | index | postgres | bi_user_tmall_vis1 | 13 MB | postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100); QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=2071.47..28408.93 rows=7351 width=20) (actual time=61.110..62.974 rows=4 loops=1) Output: uid, bid, cnt Recheck Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Rows Removed by Index Recheck: 20092 Heap Blocks: lossy=128 Buffers: shared hit=2236 -> Bitmap Index Scan on idx_bi1 (cost=0.00..2069.63 rows=20096 width=0) (actual time=61.100..61.100 rows=1280 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=2108 Planning time: 0.072 ms Execution time: 62.994 ms (11 rows) postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100) or (bid=2000 and cnt <10000) or (bid=12000 and cnt <10000); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=6324.38..242299.15 rows=153721 width=20) (actual time=184.909..191.652 rows=138 loops=1) Output: uid, bid, cnt Recheck Cond: (((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) OR ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) OR ((bi_user_tmall_vis1.bid = 12000) AND (bi _user_tmall_vis1.cnt < 10000))) Rows Removed by Index Recheck: 60150 Heap Blocks: lossy=384 Buffers: shared hit=6708 -> BitmapOr (cost=6324.38..6324.38 rows=180864 width=0) (actual time=184.896..184.896 rows=0 loops=1) Buffers: shared hit=6324 -> Bitmap Index Scan on idx_bi1 (cost=0.00..2069.63 rows=20096 width=0) (actual time=61.600..61.600 rows=1280 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=2108 -> Bitmap Index Scan on idx_bi1 (cost=0.00..2069.73 rows=80384 width=0) (actual time=61.522..61.522 rows=1280 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=2108 -> Bitmap Index Scan on idx_bi1 (cost=0.00..2069.73 rows=80384 width=0) (actual time=61.773..61.773 rows=1280 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 12000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=2108 Planning time: 0.091 ms Execution time: 191.684 ms (19 rows)

3、 pages_per_range=256

public | idx_bi | index | postgres | bi_user_tmall_vis1 | 6624 kB | postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where bid=1 and cnt between 1 and 100; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=1038.00..53587.92 rows=7351 width=20) (actual time=30.259..33.742 rows=4 loops=1) Output: uid, bid, cnt Recheck Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Rows Removed by Index Recheck: 40188 Heap Blocks: lossy=256 Buffers: shared hit=1310 -> Bitmap Index Scan on idx_bi (cost=0.00..1036.16 rows=40192 width=0) (actual time=30.251..30.251 rows=2560 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=1054 Planning time: 0.061 ms Execution time: 33.759 ms (11 rows) postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100) or (bid=2000 and cnt <10000) or (bid=12000 and cnt <10000); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=3223.91..265138.74 rows=153721 width=20) (actual time=90.760..105.509 rows=138 loops=1) Output: uid, bid, cnt Recheck Cond: (((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) OR ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) OR ((bi_user_tmall_vis1.bid = 12000) AND (bi _user_tmall_vis1.cnt < 10000))) Rows Removed by Index Recheck: 120438 Heap Blocks: lossy=768 Buffers: shared hit=3930 -> BitmapOr (cost=3223.91..3223.91 rows=200960 width=0) (actual time=90.746..90.746 rows=0 loops=1) Buffers: shared hit=3162 -> Bitmap Index Scan on idx_bi (cost=0.00..1036.16 rows=40192 width=0) (actual time=30.838..30.838 rows=2560 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=1054 -> Bitmap Index Scan on idx_bi (cost=0.00..1036.23 rows=80384 width=0) (actual time=29.966..29.966 rows=2560 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=1054 -> Bitmap Index Scan on idx_bi (cost=0.00..1036.23 rows=80384 width=0) (actual time=29.940..29.940 rows=2560 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 12000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=1054 Planning time: 0.131 ms Execution time: 105.555 ms (19 rows)

4、pages_per_range=512

public | idx_bi | index | postgres | bi_user_tmall_vis1 | 3336 kB | postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where bid=1 and cnt between 1 and 100; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=521.47..105255.40 rows=7351 width=20) (actual time=16.024..25.791 rows=4 loops=1) Output: uid, bid, cnt Recheck Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Rows Removed by Index Recheck: 80380 Heap Blocks: lossy=512 Buffers: shared hit=529 read=511 -> Bitmap Index Scan on idx_bi (cost=0.00..519.63 rows=80384 width=0) (actual time=16.010..16.010 rows=5120 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=528 Planning time: 0.238 ms Execution time: 25.822 ms (11 rows) postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100) or (bid=2000 and cnt <10000) or (bid=12000 and cnt <10000); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=1674.17..315338.06 rows=153721 width=20) (actual time=47.115..78.014 rows=138 loops=1) Output: uid, bid, cnt Recheck Cond: (((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) OR ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) OR ((bi_user_tmall_vis1.bid = 12000) AND (bi _user_tmall_vis1.cnt < 10000))) Rows Removed by Index Recheck: 241014 Heap Blocks: lossy=1536 Buffers: shared hit=2608 read=512 -> BitmapOr (cost=1674.17..1674.17 rows=241151 width=0) (actual time=47.099..47.099 rows=0 loops=1) Buffers: shared hit=1584 -> Bitmap Index Scan on idx_bi (cost=0.00..519.63 rows=80384 width=0) (actual time=16.167..16.167 rows=5120 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=528 -> Bitmap Index Scan on idx_bi (cost=0.00..519.63 rows=80384 width=0) (actual time=15.494..15.494 rows=5120 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=528 -> Bitmap Index Scan on idx_bi (cost=0.00..519.63 rows=80384 width=0) (actual time=15.437..15.437 rows=5120 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 12000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=528 Planning time: 0.145 ms Execution time: 78.062 ms (19 rows)

5、pages_per_range=sqrt(pg_class.relpages)=6384

public | idx_bi | index | postgres | bi_user_tmall_vis1 | 312 kB | postgres=# create index idx_bi on bi_user_tmall_vis1 using brin (bid,cnt) WITH (pages_per_range='6384'); CREATE INDEX postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100) or (bid=2000 and cnt <10000) or (bid=12000 and cnt <10000); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=252.98..3620468.00 rows=153721 width=20) (actual time=4.027..138.993 rows=138 loops=1) Output: uid, bid, cnt Recheck Cond: (((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) OR ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) OR ((bi_user_tmall_vis1.bid = 12000) AND (bi _user_tmall_vis1.cnt < 10000))) Rows Removed by Index Recheck: 1002150 Heap Blocks: lossy=6384 Buffers: shared hit=1662 read=4848 -> BitmapOr (cost=252.98..252.98 rows=3006577 width=0) (actual time=4.010..4.010 rows=0 loops=1) Buffers: shared hit=126 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.373..1.373 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=42 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.325..1.325 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=42 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.310..1.310 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 12000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=42 Planning time: 0.307 ms Execution time: 139.046 ms (19 rows) postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100) or (bid=2000 and cnt <10000) ; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=132.06..2459840.30 rows=80537 width=20) (actual time=2.735..112.409 rows=65 loops=1) Output: uid, bid, cnt Recheck Cond: (((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) OR ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000))) Rows Removed by Index Recheck: 1002223 Heap Blocks: lossy=6384 Buffers: shared hit=6468 -> BitmapOr (cost=132.06..132.06 rows=2004385 width=0) (actual time=2.720..2.720 rows=0 loops=1) Buffers: shared hit=84 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.401..1.401 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=42 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.318..1.318 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 2000) AND (bi_user_tmall_vis1.cnt < 10000)) Buffers: shared hit=42 Planning time: 0.126 ms Execution time: 112.449 ms (16 rows) postgres=# explain (analyze,timing,costs,buffers,verbose) select * from bi_user_tmall_vis1 where (bid=1 and cnt between 1 and 100); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on public.bi_user_tmall_vis1 (cost=47.73..1258330.06 rows=7351 width=20) (actual time=1.381..97.717 rows=4 loops=1) Output: uid, bid, cnt Recheck Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Rows Removed by Index Recheck: 1002284 Heap Blocks: lossy=6384 Buffers: shared hit=6426 -> Bitmap Index Scan on idx_bi (cost=0.00..45.90 rows=1002192 width=0) (actual time=1.368..1.368 rows=63840 loops=1) Index Cond: ((bi_user_tmall_vis1.bid = 1) AND (bi_user_tmall_vis1.cnt >= 1) AND (bi_user_tmall_vis1.cnt <= 100)) Buffers: shared hit=42 Planning time: 0.109 ms Execution time: 97.744 ms (11 rows)

不同pages_per_range的对比

索引精度单表数据量单表大小索引大小1个条件2个条件3个条件pages_per_range=164亿311GB1.6GB8.2秒--pages_per_range=12864亿311GB13MB62毫秒-191毫秒pages_per_range=25664亿311GB6MB33毫秒-105毫秒pages_per_range=51264亿311GB3MB25毫秒-78毫秒pages_per_range=sqrt(pg_class.relpages)=638464亿311GB300KB97毫秒112毫秒139毫秒

虽然精度高，但是由于目前PG BRIN索引扫描方式是全扫的，所以索引本身越大，扫描索引本身的成本占比就越高，8.2秒就是这样来的。

当精度调成512时，单个条件变成了25毫秒，而索引大小只有3MB。

开不开心，意不意外。

BRIN内核优化思考

为了降低BRIN索引本身的扫描开销，我们可以把BRIN索引的边界，再生成一颗树，通过树来扫描，提高速率，而不是全扫的方式。

那么以后我们就只需要考虑精度=1的就可以了。因为这样过滤性是最好的，同时BRIN索引本身的扫描成本又是很低的。从而使BRIN索引的效率在海量数据的情况下，大幅度提升。

小结

本文主要讲了BRIN索引的原理，扫描的原理，精度参数的原理，以及如何选择精度参数，还讲了如何通过调整内核优化BRIN索引扫描的方法来降低BRIN索引本身的成本。

好了，祝大家玩得开心。你懂PostgreSQL多少，她就能给你多少，PG是一个可玩性很强的企业级开源数据库，加油。

BRIN索引的特性，可以用来支撑万亿级别甚至更大体量的海量数据筛选，同时索引的存储、对写入造成的影响等几乎为0。绝对属于黑科技级别的特性。

参考