虽然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索引的存储结构如下图所示: ![存储结构](https://box.kancloud.cn/2015-09-24_5603953ca769b.png "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带来的性能、易用性方面的变化,我们拭目以待。