雖然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帶來的性能、易用性方面的變化，我們拭目以待。