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](mailto: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带来的性能、易用性方面的变化，我们拭目以待。