数据库内核月报 - 2015 / 05-PgSQL · 社区动态 · 9.5 新功能BRIN索引

虽然PG 9.4发布不过半年时间,下一个大版本9.5却已经进入人们的视野。按目前的情况,2015年上半年可能发布beta版本,下半年正式发布PG 9.5。9.5里面最令人瞩目的一个新功能恐怕是BRIN索引了。下面这个commit加入了对BRIN索引的支持:

commit: 7516f5259411c02ae89e49084452dc342aadb2ae
author: Alvaro Herrera alvherre@alvh.no-ip.org
date: Fri, 7 Nov 2014 16:38:14 -0300
BRIN: Block Range Indexes

BRIN is a new index access method intended to accelerate scans of very
large tables, without the maintenance overhead of btrees or other
traditional indexes. They work by maintaining “summary” data about
block ranges. Bitmap index scans work by reading each summary tuple and
comparing them with the query quals; all pages in the range are returned
in a lossy TID bitmap if the quals are consistent with the values in the
summary tuple, otherwise not. Normal index scans are not supported
because these indexes do not store TIDs.

BRIN即Block Range Indexes,顾名思义,就是对数据块区段所做的索引。其实它的设计思路很简单,就是通过扫描整个表,记录下每个固定区段(例如第1到128号数据块)所含数据被索引字段的最大值和最小值,依次存入索引空间。当处理某个查询,需要找到符合查询条件的记录时,可以使用BRIN索引,跳过与查询条件不符合的区段,加速查找。下面我们分析一下这种新型索引的使用方法和内核实现。

使用

下面我们创建一个有一百万记录的表,然后为其建立BRIN索引,再在表上做查询:

postgres=# create table t AS SELECT generate_series(1,100000000) AS id;
SELECT 100000000
postgres=# \timing
Timing is on.
postgres=# create index idx_brin on t using brin(id);
CREATE INDEX
Time: 72766.822 ms

postgres=# explain analyze select * from t where id = 507654;
                                                     QUERY PLAN
-----------------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=52.01..56.02 rows=1 width=4) (actual time=26.046..41.431 rows=1 loops=1)
   Recheck Cond: (id = 507654)
   Rows Removed by Index Recheck: 28927
   Heap Blocks: lossy=128
   ->  Bitmap Index Scan on idx_brin  (cost=0.00..52.01 rows=1 width=0) (actual time=6.408..6.408 rows=1280 loops=1)
         Index Cond: (id = 507654)
 Planning time: 8.265 ms
 Execution time: 42.575 ms
(8 rows)

Time: 67.897 ms

可见,使用BRIN避免了全表扫描,执行时间为67ms左右。下面我们对比一下,如果不使用BRIN,耗时多少(注意,我们做下面操作之前,清空了操作系统pagecache,并重启了PG):

postgres=# drop index idx_brin;
DROP INDEX

postgres=# explain analyze select * from t where id = 507654;
                                              QUERY PLAN
----------------------------------------------------------------------------------------
 Seq Scan on t  (cost=0.00..1692478.00 rows=1 width=4) (actual time=194.665..35124.454 rows=1 loops=1)
   Filter: (id = 507654)
   Rows Removed by Filter: 99999999
 Planning time: 6.345 ms
 Execution time: 35125.633 ms
(5 rows)

执行时间35s左右!原因在于,使用BRIN索引时,实际只读取了一个区段里的数据块,而全表扫描时,则读取所有数据块。

实现

存储结构

BRIN索引的存储结构如下图所示:

BRIN索引由一组相同结构的索引块组成,每个索引块含有固定数目的索引记录,每条记录里面含有一个指向最值块的指针。最值块里面的每条记录存放了区段最大和最小值,及其对应的数据区段起始块的块号。要想定位某个数据块对应的BRIN索引记录,可以按下面的公式,计算索引块号和索引记录的位置:

索引块号 =(数据块号 / 每个区段包含的块数) / 每个索引块含有的索引记录数
索引记录的位置 = (数据块号 / 每个区段包含的块数)% 每个索引块含有的索引记录数

例如,如果一条数据记录所在数据块块号为1000,而在缺省情况下BRIN索引每个区段包含的块数为128(可以在创建索引时,通过WITH (pages_per_range = xxx)子句来修改),而每个索引块的索引记录数固定(约为8K/6),这样可以很容易按照公式找到对应索引记录。而由索引记录里面存放的指针,可以读取到对应最值块和最值记录。

索引构建

BRIN索引的构建过程比较简单,需要对原表做一次全表扫描,每扫描完一个区段,相应的索引块和最值块也构建完成。值得注意的是,对于最后一个区段,如果所含的块数不足,则不会为其构建最值记录;而是等到数据块数达到一个完整区块时,才为其计算最值。这样的设计,有利于提高从表尾部大规模插入数据时的性能。

查询操作

使用BRIN索引处理查询时,PG会从头开始,检查所有的索引记录,并用索引记录指向的最值记录与查询条件相比较,从而判断对应区段是否可能包含符合查询条件的数据;最后得到所有相关区段列表,再顺序读取这些区段中的数据块进行比较,返回实际符合查询条件的数据记录。

插入操作

BRIN索引插入操作的接口函数为brininsert,在一个数据记录被插入到数据块后被调用。其过程主要是利用数据块号,按照上面提到的定位过程,找到对应的最值记录,然后比较最值和插入的数据记录值。如果最大值小于该数据记录值,或最小值大于数据记录值,则更新最大或最小值。值得注意的是,插入操作如果要更新索引或最值记录,是要锁定整个块的,这样多个并行插入对索引的修改是很容易冲突的,就是说BRIN索引会一定程度上降低并行插入的性能。

删除和更新操作

BRIN索引的所有接口函数可以在pg_am.h中找到。但令人疑惑的是,只有插入(insert)的接口函数,没有针对删除(delete)或更新(update)的函数。其实,和PG其他类型的索引类似,BRIN索引也是不需要执行删除操作的。删除一条数据记录时,BRIN索引不做修改。即使在对一个表做VACUUM操作时,也同样不需修改BRIN索引(注意,对于其他索引如B树索引,在VACUUM操作时会修改索引删除无效索引记录)。另一方面,对于更新操作,相当于一次删除加一次插入操作,由于不需要对索引做删除操作,实际只做了一次索引插入。

小结

通过上面分析,不难看出,这种BRIN索引适用于下面的场景:

  1. 非常大的表,如果创建B树索引,会占用较大空间;采用BRIN,不失为一种时间换空间的方法(BRIN比B树索引处理查询时会慢一些);
  2. 经常大批量尾部插入的表,这些表如果创建了B树索引,会引起索引尾部更新的互斥;而使用BRIN索引,尾部数据块的索引记录只在满了一个区段时才进行一次插入,减少了互斥的情况。

BRIN是PG 9.5一个令人期待的新功能,对于BRIN将给PG带来的性能、易用性方面的变化,我们拭目以待。

时间: 2024-09-26 23:15:02

数据库内核月报 - 2015 / 05-PgSQL · 社区动态 · 9.5 新功能BRIN索引的相关文章

MySQL内核月报 2015.03-MySQL · 捉虫动态· pid file丢失问题分析

现象 mysql5.5,通过命令show variables like '%pid_file%'; 可以查到pid文件位置,例如/home/mysql/xx.pid.但发现在此目录下找不到此pid文件. 背景知识 mysql pid文件记录的是当前mysqld进程的pid. 通过mysqld_safe启动mysqld时,mysqld_safe会检查PID文件,未指定PID文件时,pid文件默认名为$DATADIR/`hostname`.pid pid文件不存在,不做处理 文件存在,且pid已占用

MySQL内核月报 2015.01-MySQL · 捉虫动态· 设置 gtid_purged 破坏AUTO_POSITION复制协议

bug描述 Oracle 最新发布的版本 5.6.22 中有这样一个关于GTID的bugfix,在主备场景下,如果我们在主库上 SET GLOBAL GTID_PURGED = "some_gtid_set",并且 some_gtid_set 中包含了备库还没复制的事务,这个时候如果备库接上主库的话,预期结果是主库返回错误,IO线程挂掉的,但是实际上,在这种场景下主库并不报错,只是默默的把自己 binlog 中包含的gtid事务发给备库.这个bug的造成的结果是看起来复制正常,没有错误

MySQL内核月报 2015.01-MySQL · 捉虫动态· replicate filter 和 GTID 一起使用的问题

问题描述 当单个 MySQL 实例的数据增长到很多的时候,就会考虑通过库或者表级别的拆分,把当前实例的数据分散到多个实例上去,假设原实例为A,想把其中的5个库(db1/db2/db3/db4/db5)拆分到5个实例(B1/B2/B3/B4/B5)上去. 拆分过程一般会这样做,先把A的相应库的数据导出,然后导入到对应的B实例上,但是在这个导出导入过程中,A库的数据还是在持续更新的,所以还需在导入完后,在所有的B实例和A实例间建立复制关系,拉取缺失的数据,在业务不繁忙的时候将业务切换到各个B实例.

MySQL内核月报 2015.02-MySQL · 捉虫动态· 变量修改导致binlog错误

背景 MySQL 5.6.6 版本新加了这样一个参数--log_bin_use_v1_row_events,这个参数用来控制binlog中Rows_log_event的格式,如果这个值为1的话,就用v1版的Rows_log_event格式(即5.6.6之前的),默认是0,用新的v2版本的格式,更详细看官方文档.这个参数一般保持默认即可,但是当我们需要搭 5.6->5.5 这要的主备的时候,就需要把主库的这个值改为1,不然5.5的备库不能正确解析Rows_log_event.最近在使用这个参数的时

MySQL内核月报 2015.01-MySQL · 捉虫动态· mysql client crash一例

背景 客户使用mysqldump导出一张表,然后使用mysql -e 'source test.dmp'的过程中client进程crash,爆出内存的segment fault错误,导致无法导入数据. 问题定位 test.dmp文件大概50G左右,查看了一下文件的前几行内容,发现: 问题定位到第一行出现了不正常warning的信息,是由于客户使用mysqldump命令的时候,重定向了stderr.即: mysqldump ...>/test.dmp 2>&1 导致error或者warn

MySQL内核月报 2015.01-MySQL · 捉虫动态· InnoDB自增列重复值问题

问题重现 先从问题入手,重现下这个bug 这里我们关闭mysql,再启动mysql,然后再插入一条数据 我们看到插入了(2,2),而如果我没有重启,插入同样数据我们得到的应该是(4,2). 上面的测试反映了mysqld重启后,InnoDB存储引擎的表自增id可能出现重复利用的情况. 自增id重复利用在某些场景下会出现问题.依然用上面的例子,假设t1有个历史表t1_history用来存t1表的历史数据,那么mysqld重启前,ti_history中可能已经有了(2,2)这条数据,而重启后我们又插入

阿里数据库内核月报:2015年05月

# 01 MySQL · 引擎特性 · InnoDB redo log漫游 # 02 MySQL · 专家投稿 · MySQL数据库SYS CPU高的可能性分析 # 03 MySQL · 捉虫动态 · 5.6 与 5.5 InnoDB 不兼容导致 crash # 04 MySQL · 答疑解惑 · InnoDB 预读 VS Oracle 多块读 # 05 PgSQL · 社区动态 · 9.5 新功能BRIN索引 # 06 MySQL · 捉虫动态 · MySQL DDL BUG # 07 MyS

阿里数据库内核月报:2015年04月

# 01 MySQL · 引擎特性 · InnoDB undo log 漫游 # 02 TokuDB · 产品新闻 · RDS TokuDB小手册 # 03 TokuDB · 特性分析 · 行锁(row-lock)与区间锁(range-lock) # 04 PgSQL · 社区动态 · 说一说PgSQL 9.4.1中的那些安全补丁 # 05 MySQL · 捉虫动态 · 连接断开导致XA事务丢失 # 06 MySQL · 捉虫动态 · GTID下slave_net_timeout值太小问题 #

阿里数据库内核月报:2015年08月

# 01 MySQL · 社区动态 · InnoDB Page Compression # 02 PgSQL · 答疑解惑 · RDS中的PostgreSQL备库延迟原因分析 # 03 MySQL · 社区动态 · MySQL5.6.26 Release Note解读 # 04 PgSQL · 捉虫动态 · 执行大SQL语句提示无效的内存申请大小 # 05 MySQL · 社区动态 · MariaDB InnoDB表空间碎片整理 # 06 PgSQL · 答疑解惑 · 归档进程cp命令的core