BRIN indexes: Correlation, correlation, correlation

Since BRIN indexes have been introduced in PostgreSQL 9.5, many people have gladly adopted this new index type. A lot has been written about this new feature and a lot of positive feedback has been reported. While BRIN indexes are clearly a success and definitely a win, some people tend to exagerate and use them ways too frequently.

Correlation, it is about correlation

BRIN indexes are cheap, but this does not mean that they are always beneficial. In case the correlation of a column is low, BRIN indexes can be no gain or even a small loss. Here is an example showing what can happen:


test=# CREATE TABLE t_test AS

SELECT         *

FROM generate_series(1, 1000000) AS id;

SELECT 1000000

Time: 422.647 ms

test=# VACUUM ANALYZE t_test;

VACUUM

Time: 144.370 ms

We generate a simple PostgreSQL table containing 1 million lines.

Then we select a random row:


test=# SELECT count(*) FROM t_test WHERE id = 533455;

count

-------

1

(1 row)



Time: 44.555 ms

The sequential scan takes around 44 ms and returns exactly one row.

Now let us try the same thing using a BRIN index:


test=# CREATE INDEX idx_brin ON t_test USING brin(id);

CREATE INDEX

Time: 148.036 ms

test=# SELECT count(*) FROM t_test WHERE id = 533455;

count

-------

1

(1 row)

Time: 2.983 ms

In this case the scan is a lot faster and completes within around 3 ms. This is pretty nice.

Here is the execution plan:


test=# explain analyze SELECT count(*) FROM t_test WHERE id = 533455;

QUERY PLAN



------------------------------------------------------------------------------------------------

Aggregate  (cost=16.02..16.03 rows=1 width=8)

(actual time=2.514..2.514 rows=1 loops=1)

  Bitmap Heap Scan on t_test  (cost=12.01..16.02 rows=1 width=0)

(actual time=1.228..2.511 rows=1 loops=1)

Recheck Cond: (id = 533455)

Rows Removed by Index Recheck: 28927

Heap Blocks: lossy=128

  Bitmap Index Scan on idx_brin  (cost=0.00..12.01 rows=1 width=0)

(actual time=0.029..0.029 rows=1280 loops=1)

Index Cond: (id = 533455)

Planning time: 0.059 ms

Execution time: 2.541 ms

(9 rows)

As we can see PostgreSQL does a bitmap scan to fetch the data. The number of blocks read is 128 (exactly the desired number of blocks).

When correlation goes down …

However, the situation is quite different in case correlaton goes down. Remember: A normal BRIN index calculates the minumum and the maximum value in a range of 128 blocks. In case data is sorted the index performs nicely because many 128 x 8k areas can be excluded from the scan.

The situation changes dramatically if the data is shuffled (= correlation is low). In this case a chunk of 128 blocks (= 1 MB) will most likely contain a value close to the absolute minimum and the absolute maximum of the column so the scan cannot exclude a sufficient number of chunks:


test=# CREATE TABLE t_random AS SELECT * FROM t_test ORDER BY random();

SELECT 1000000

Time: 1321.911 ms

test=# VACUUM ANALYZE t_random ;

VACUUM

Time: 146.827 ms

test=# CREATE INDEX idx_brin_random ON t_random USING brin(id);

CREATE INDEX

Time: 140.131 ms

As we can see in the next listing this query needs many more blocks than the previous one:


test=# explain analyze SELECT count(*) FROM t_random WHERE id = 533455;

QUERY PLAN



---------------------------------------------------------------------------------------------------

Aggregate  (cost=16.02..16.03 rows=1 width=8)

(actual time=86.122..86.122 rows=1 loops=1)

  Bitmap Heap Scan on t_random  (cost=12.01..16.02 rows=1 width=0)

(actual time=73.613..86.117 rows=1 loops=1)

Recheck Cond: (id = 533455)

Rows Removed by Index Recheck: 999999

Heap Blocks: lossy=4425

  Bitmap Index Scan on idx_brin_random  (cost=0.00..12.01 rows=1 width=0)

(actual time=0.314..0.314 rows=44800 loops=1)

Index Cond: (id = 533455)

Planning time: 0.102 ms

Execution time: 86.173 ms

(9 rows)



Time: 86.621 ms

In this example the query runtime sky rockets. So does the number of blocks needed.

Conclusion

BRIN indexes are only effective if a column is somewhat “sorted”. In many cases this happens naturally. However, it is certainly not always the case.

Hans-Juergen Schoenig
Hans-Jürgen Schönig has 15 years of experience with PostgreSQL. He is consultant and CEO of the company „Cybertec Schönig & Schönig GmbH“ (www.cybertec.at, www.postgresql-support.de), which has served countless customers around the globe.