Requesting an example where query with BRIN index runs much faster than with BTREE

Question

It's very easy to see that BRIN indexes require orders of magnitude less space than BTREE indexes.

However, I'm struggling to come up with a query where elapsed time with BRIN index vs BTREE index is orders of magnitude faster. Frankly speaking, it's quite challenging to find a query which runs even twice faster.

The only requirement is that all necessary data for query result is in the index - i.e. no table look-ups are required.

In below test case I read 1M rows from index on column which has perfectly correlated data with physical storage (pg_stats.correlation = 1).

drop table if exists ttt;
create table ttt(a int, b int);
insert into ttt select i, i from generate_series(1, 1e7) i;

create index brin_ttt on ttt using brin(b) with (pages_per_range = 128);
create index btree_ttt on ttt(b);

analyze ttt;
set max_parallel_workers_per_gather = 0;

select relname, pg_size_pretty(pg_relation_size(oid)) size
from pg_class c
where c.relname in ('brin_ttt', 'btree_ttt', 'ttt');

-- run below a few times to cache required blocks

set enable_indexscan = off; 
explain (analyze, buffers) select count(*) from ttt where b > 1e7::int - 1e6::int;

reset enable_indexscan;
explain (analyze, buffers) select count(*) from ttt where b > 1e7::int - 1e6::int;

Still btree gives result faster - 167ms vs 190ms.

set enable_indexscan = off; 
explain (analyze, buffers) select count(*) from ttt where b > 1e7::int - 1e6::int;

reset enable_indexscan;
explain (analyze, buffers) select count(*) from ttt where b > 1e7::int - 1e6::int;
SET
                                                           QUERY PLAN                                                            
---------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=59199.58..59199.59 rows=1 width=8) (actual time=190.156..190.158 rows=1 loops=1)
   Buffers: shared hit=4442
   ->  Bitmap Heap Scan on ttt  (cost=254.47..56785.71 rows=965548 width=0) (actual time=0.518..132.440 rows=1000000 loops=1)
         Recheck Cond: (b > 9000000)
         Rows Removed by Index Recheck: 3392
         Heap Blocks: lossy=4440
         Buffers: shared hit=4442
         ->  Bitmap Index Scan on brin_ttt  (cost=0.00..13.09 rows=982659 width=0) (actual time=0.108..0.109 rows=44400 loops=1)
               Index Cond: (b > 9000000)
               Buffers: shared hit=2
 Planning:
   Buffers: shared hit=11
 Planning Time: 0.138 ms
 Execution Time: 190.184 ms
(14 rows)

RESET
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=29903.40..29903.40 rows=1 width=8) (actual time=167.632..167.633 rows=1 loops=1)
   Buffers: shared hit=2736
   ->  Index Only Scan using btree_ttt on ttt  (cost=0.43..27489.53 rows=965548 width=0) (actual time=0.045..111.415 rows=1000000 loops=1)
         Index Cond: (b > 9000000)
         Heap Fetches: 0
         Buffers: shared hit=2736
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.107 ms
 Execution Time: 167.657 ms
(10 rows)

I played with pages_per_range parameter and with different ranges in where clause but BRIN still does not outperform BTREE.

Answer 1

It will be difficult to find an example where a BRIN index is faster than a B-tree index. BRIN indexes are expected to be slower. The main point about BRIN indexes is that they are much smaller than B-tree indexes and should be cheaper to maintain.