虽然PG 9.4发布不过半年时间，下一个大版本9.5却已经进入人们的视野。按目前的情况，2015年上半年可能发布beta版本，下半年正式发布PG 9.5。9.5里面最令人瞩目的一个新功能恐怕是BRIN索引了。下面这个commit加入了对BRIN索引的支持：
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索引适用于下面的场景：
- 非常大的表，如果创建B树索引，会占用较大空间；采用BRIN，不失为一种时间换空间的方法（BRIN比B树索引处理查询时会慢一些）；
- 经常大批量尾部插入的表，这些表如果创建了B树索引，会引起索引尾部更新的互斥；而使用BRIN索引，尾部数据块的索引记录只在满了一个区段时才进行一次插入，减少了互斥的情况。
BRIN是PG 9.5一个令人期待的新功能，对于BRIN将给PG带来的性能、易用性方面的变化，我们拭目以待。
