ITPub博客

首页 > 数据库 > PostgreSQL > PostgreSQL DBA(53) - Index(BRIN)

PostgreSQL DBA(53) - Index(BRIN)

翻译 PostgreSQL 作者:husthxd 时间:2019-07-11 14:28:21 0 删除 编辑

本节简单介绍了PostgreSQL中的BRIN索引,包括BRIN索引的基础知识和结构等.

简介
BRIN是块范围索引Block Range Index的简称,其设计思想是避免在绝对不匹配的Page中查找,而不是快速找到匹配的行,利用相对于Btree极少的空间来获取可相对较好的查询效率,BRIN能够在TB级别上面的表上创建索引,而索引和维护开销则很小。
BRIN在列值与其在表中的物理位置相关性较大时工作得很好,比如序列值,但在相关性不大的列值上性能较差比如随机值上.
BRIN索引的工作原理是:首先把数据表划分为多个范围每个范围有多个pages,索引存储range的概要信息,如最大最小值等.如查询条件包含该列,而条件值不在范围中,那么整个范围都会跳过,反之,需要扫描所有pages中的所有行来进行匹配.
BRIN可以视为分区&顺序扫描的加速器而不是Index.

结构
第一(准确来说是第0)页存储的是元数据,通过元数据定位带有摘要信息的pages.在这些页面上的每一索引行包含每一个范围的摘要信息.
在meta page和摘要信息之间的pages称为反向范围映射revmap(reverse range map),revmap实际上是指向索引行的TIDs指针数组.

对于某些范围,revmap中的指针没有指向索引行,这意味着仍没有摘要信息.

索引扫描
与其他AM指向数据行不同,BRIN不会通过TID逐个返回行而是通过构建bitmap来访问.有两种类型的bitmap pages,一种是精确的指向行,另外一种是不精确的执行page,这里使用的是不精确的page.
扫描算法不复杂,顺序访问ranges map,通过指针确定包含range摘要信息的索引行,所有range的pages都会添加到bitmap中,结果bitmap的使用方法与普通的bitmap的一样.

索引更新
在page中新增新版本行,需要确定包含该行的range并使用ranges映射找到含有摘要信息的索引行,这些操作都是简单的算术运算.举个例子,range大小为4在page 13上新增一行其值为42,range的编号(从0开始)为13/4 = 3,因此在revmap中使用偏移为3的指针.
该range最小值为31,最大值为40,由于新值42超出范围,更新最大值为42,但如果新值在范围之内,索引不需要更新.

在索引创建后,所有可用范围的摘要信息都会计算,但在表扩展后,新pages可能会超出限制,这时候有两种可用的方法:
1.不在马上更新索引.在vacuum的时候才更新,或者通过函数brin_summarize_new_values更新;
2.以autosummarize选项创建索引,则马上更新索引,该参数默认为off.
在新范围出现时,revmap的大小会增长.在通过其他page增长时,现存的行版本会移到其他pages上.

在删除行时,不需要做任何操作.最大和最小值可能已经不存在了,但为了检测这一点需要遍历range中的所有值,这样不太值得.索引的正确性不会影响扫描的正确性,只是对性能有所影响而已:需要扫描比实际更多的pages.PG提供了brin_desummarize_range和brin_summarize_new_values函数手工重新计算摘要信息,但如何检测到这样的需求?起码传统方法是做不到的.

更新行,只需要删除过期版本新增一个新的即可.

使用
测试数据:


testdb=# create table t_brin(id int,randomnum int);
CREATE TABLE
testdb=# 
testdb=# truncate table t_brin;
TRUNCATE TABLE
testdb=# insert into t_brin select x,random()*10000000 from generate_series(1,10000000) as x;
INSERT 0 10000000
testdb=# 
testdb=# create index idx_t_brin_id on t_brin using brin(id);
CREATE INDEX
testdb=# create index idx_t_brin_randomnum on t_brin using brin(randomnum);
CREATE INDEX
testdb=# create index idx_t_brin_btreeid on t_brin using btree(id);
CREATE INDEX
testdb=# 
testdb=# select pg_size_pretty(pg_table_size('t_brin'));
 pg_size_pretty 
----------------
 346 MB
(1 row)
testdb=# select pg_size_pretty(pg_table_size('idx_t_brin_id'));
 pg_size_pretty 
----------------
 48 kB
(1 row)
testdb=# select pg_size_pretty(pg_table_size('idx_t_brin_btreeid'));
 pg_size_pretty 
----------------
 214 MB
(1 row)

brin索引只有48KB,而Btree索引是214M,是BRIN索引大小的4565倍!

在顺序列上执行查询:


testdb=# analyze t_brin;
ANALYZE
testdb=# explain analyze verbose select * from t_brin where id = 102345;
                                                            QUERY PLAN
-------------------------------------------------------------------------------------------------
 Index Scan using idx_t_brin_btreeid on public.t_brin  (cost=0.43..8.45 rows=1 width=8) (actual time=0.221..0.222 rows=1 loop
s=1)
   Output: id, randomnum
   Index Cond: (t_brin.id = 102345)
 Planning Time: 0.521 ms
 Execution Time: 0.266 ms
(5 rows)
testdb=# drop index idx_t_brin_btreeid;
DROP INDEX
testdb=# explain analyze verbose select * from t_brin where id = 102345;
                                                          QUERY PLAN 
-------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on public.t_brin  (cost=12.03..41657.45 rows=1 width=8) (actual time=4.049..7.630 rows=1 loops=1)
   Output: id, randomnum
   Recheck Cond: (t_brin.id = 102345)
   Rows Removed by Index Recheck: 28927
   Heap Blocks: lossy=128
   ->  Bitmap Index Scan on idx_t_brin_id  (cost=0.00..12.03 rows=28902 width=0) (actual time=0.137..0.137 rows=1280 loops=1)
         Index Cond: (t_brin.id = 102345)
 Planning Time: 0.344 ms
 Execution Time: 7.666 ms
(9 rows)

等值查询,PG选择Btree索引,cost为8.45,执行时间0.266 ms;
删除Btree索引,使用BRIN索引,cost为41657.45,执行时间为7.666 ms,是Btree的28倍.虽然慢了1个数量级,但绝对时间并不长,耗费的空间却少了3个数量级.

在随机值列上执行查询:


testdb=# explain verbose select * from t_brin where randomnum = 102345;
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Gather  (cost=1000.00..97331.41 rows=2 width=8)
   Output: id, randomnum
   Workers Planned: 2
   ->  Parallel Seq Scan on public.t_brin  (cost=0.00..96331.21 rows=1 width=8)
         Output: id, randomnum
         Filter: (t_brin.randomnum = 102345)
(6 rows)
testdb=# set enable_seqscan=off;
SET
testdb=# explain verbose select * from t_brin where randomnum = 102345;
                                           QUERY PLAN                                           
------------------------------------------------------------------------------------------------
 Gather  (cost=1023.07..97354.49 rows=2 width=8)
   Output: id, randomnum
   Workers Planned: 2
   ->  Parallel Bitmap Heap Scan on public.t_brin  (cost=23.07..96354.29 rows=1 width=8)
         Output: id, randomnum
         Recheck Cond: (t_brin.randomnum = 102345)
         ->  Bitmap Index Scan on idx_t_brin_randomnum  (cost=0.00..23.07 rows=9999977 width=0)
               Index Cond: (t_brin.randomnum = 102345)
(8 rows)

PG不会使用该列上的BRIN索引而是选择了全表扫描,禁用顺序扫描后,使用brin索引,成本与全表扫描相差无几,说明在随机值列上的BRIN索引基本没有效果.


testdb=# select attname, correlation from pg_stats where tablename='t_brin' order by correlation desc nulls last;
  attname  | correlation  
-----------+--------------
 id        |            1
 randomnum | 0.0016428155
(2 rows)

查询统计信息,id列相关性是1,而随机值列相关性是0.0016428155,相差巨大.

参考资料
Indexes in PostgreSQL — 9 (BRIN)

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/6906/viewspace-2650223/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
长期从事政务、金融等行业产品研发和架构设计工作,ITPUB数据库版块资深版主,对Oracle、PostgreSQL有深入研究。现就职于广州云图数据技术有限公司,系统架构师。

注册时间:2007-12-28

  • 博文量
    1309
  • 访问量
    3785838