数据库内核月报

虽然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索引适用于下面的场景：

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

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

数据库内核月报－ 2015 / 05

PgSQL · 社区动态 · 9.5 新功能BRIN索引

使用

实现

小结