5

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.

Improve this question

3 Answers 3

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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

BRIN is lossy. You're saying you want to compare an index that's by design supposed to do a re-check, to one that doesn't, in a race that prohibits a re-check.

That being said, even a re-checking BRIN can outperform a B-Tree rigged for index-onlies. Here's a 2x advantage with almost 3x size advantage on a 2M-row table: it really just needs large tables and huge ranges, so you were already on the right track.
demo at db<>fiddle

select setseed(.42);--make the test repeatable
set max_parallel_workers=0;--disable parallelism, simplifying plans
set max_parallel_workers_per_gather=0;

create table t as
select i::int
     , random()*1e4 AS x
from generate_series(1, 2e6::int) i;

create index btree_x on t(i)
  include(x);--enabling index-only scan with x as lightweight payload
analyse t;

explain analyze verbose
select count(x)
     , sum(x)
     , stddev(x)
from t
where i < 4e5::int;
QUERY PLAN
Aggregate (cost=18171.28..18171.29 rows=1 width=24) (actual time=214.113..214.115 rows=1 loops=1)
Output: count(x), sum(x), stddev(x)
-> Index Only Scan using btree_x on public.t (cost=0.43..15195.62 rows=396754 width=8) (actual time=0.061..161.754 rows=399999 loops=1)
Output: i, x
Index Cond: (t.i < 400000)
Heap Fetches: 399999
Planning Time: 0.198 ms
Execution Time: 214.156 ms 
drop index btree_x;
create index brin_x on t using brin(i);
analyse t;
QUERY PLAN
Aggregate (cost=19235.31..19235.32 rows=1 width=24) (actual time=102.723..102.724 rows=1 loops=1)
Output: count(x), sum(x), stddev(x)
-> Bitmap Heap Scan on public.t (cost=113.14..16218.26 rows=402274 width=8) (actual time=0.086..53.080 rows=399999 loops=1)
Output: i, x
Recheck Cond: (t.i < 400000)
Rows Removed by Index Recheck: 2561
Heap Blocks: lossy=2176
-> Bitmap Index Scan on brin_x (cost=0.00..12.58 rows=423529 width=0) (actual time=0.072..0.073 rows=21760 loops=1)
Index Cond: (t.i < 400000)
Planning Time: 0.231 ms
Execution Time: 102.778 ms

struggling to come up with a query where elapsed time with BRIN index vs BTREE index is orders of magnitude faster

You could continue tweaking and scaling this up but I don't think it'll be easy to hit the orders of magnitude level of difference.

Improve this answer

3 Comments

Nothing new under the sun
I checked that article before posting but did not find an answer to my question. Maybe I missed it and you can point it to me.
You asked for an "example where query with BRIN index runs much faster than with BTREE". The article offers that example in the "Measuring the Differences" section: take the second query, bump the range to 100000 according to the table at the end of that section and for sequentially stored values, BRIN takes 68 ms, lower than B-Tree's 85 ms. Further, setting pages_per_range to 16 or 32, also gets BRIN's score of 11 ms below B-Tree's 13 ms for queries targetting a 1e4 range.
2

Posting this to elaborate a bit on what Zegarek already highlighted.

If we add included columns to the BTREE then BRIN can actually outperfom BTREE.

What was interesting is to compare how performance changes when we make those included columns wider. So I ran below test with the width 100, 200 and 500.

set max_parallel_workers_per_gather=0;

drop table if exists ttt0;
create table ttt0 as
select i::int, i::text || repeat('x', 100) x
from generate_series(1, 2e6::int) i;

create index btree_x on ttt0(i) include(x);
create index brin_x on ttt0 using brin(i);
analyse ttt0;

reset enable_seqscan;
reset enable_indexscan;
set enable_bitmapscan = off;

explain (analyze, buffers)
select count(x) from ttt0 where i < 4e5::int;

set enable_seqscan = off;
set enable_indexscan = off;
reset enable_bitmapscan;

explain (analyze, buffers)
select count(x) from ttt0 where i < 4e5::int;

JIT starts to kick in with the width 500 and it makes BRIN performance much worse. If we disable JIT then things are back to normal and BRIN continues to outperform BTREE.

-- !!!!!!!!!! 100

RESET
RESET
SET
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=42186.93..42186.94 rows=1 width=8) (actual time=131.530..131.531 rows=1 loops=1)
   Buffers: shared hit=13679
   ->  Index Only Scan using btree_x on ttt0  (cost=0.43..41185.36 rows=400625 width=107) (actual time=0.020..106.956 rows=399999 loops=1)
         Index Cond: (i < 400000)
         Heap Fetches: 399999
         Buffers: shared hit=13679
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.090 ms
 Execution Time: 131.557 ms
(10 rows)

SET
SET
RESET
                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=40703.95..40703.96 rows=1 width=8) (actual time=90.339..90.342 rows=1 loops=1)
   Buffers: shared hit=6914
   ->  Bitmap Heap Scan on ttt0  (cost=113.92..39702.39 rows=400625 width=107) (actual time=0.185..60.036 rows=399999 loops=1)
         Recheck Cond: (i < 400000)
         Rows Removed by Index Recheck: 897
         Heap Blocks: lossy=6912
         Buffers: shared hit=6914
         ->  Bitmap Index Scan on brin_x  (cost=0.00..13.76 rows=407398 width=0) (actual time=0.170..0.171 rows=69120 loops=1)
               Index Cond: (i < 400000)
               Buffers: shared hit=2
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.089 ms
 Execution Time: 90.380 ms
(14 rows)

-- !!!!!!!!!! 200

RESET
RESET
SET
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=70148.37..70148.38 rows=1 width=8) (actual time=218.600..218.601 rows=1 loops=1)
   Buffers: shared hit=1 read=12502
   ->  Index Only Scan using btree_x on ttt0  (cost=0.43..69150.62 rows=399097 width=210) (actual time=0.612..193.148 rows=399999 loops=1)
         Index Cond: (i < 400000)
         Heap Fetches: 0
         Buffers: shared hit=1 read=12502
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.111 ms
 Execution Time: 218.628 ms
(10 rows)

SET
SET
RESET
                                                           QUERY PLAN                                                           
--------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=66734.94..66734.95 rows=1 width=8) (actual time=143.774..143.775 rows=1 loops=1)
   Buffers: shared hit=1 read=12162 written=5
   ->  Bitmap Heap Scan on ttt0  (cost=118.81..65737.20 rows=399097 width=210) (actual time=1.072..112.776 rows=399999 loops=1)
         Recheck Cond: (i < 400000)
         Rows Removed by Index Recheck: 1281
         Heap Blocks: lossy=12160
         Buffers: shared hit=1 read=12162 written=5
         ->  Bitmap Index Scan on brin_x  (cost=0.00..19.04 rows=400831 width=0) (actual time=0.761..0.761 rows=121600 loops=1)
               Index Cond: (i < 400000)
               Buffers: shared hit=1 read=2
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.080 ms
 Execution Time: 143.807 ms
(14 rows)


-- !!!!!!!!!! 500

RESET
RESET
SET
                                                                 QUERY PLAN                                                                 
--------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=102648.83..102648.84 rows=1 width=8) (actual time=628.547..628.549 rows=1 loops=1)
   Buffers: shared read=30774 written=3
   ->  Index Only Scan using btree_x on ttt0  (cost=0.55..101653.92 rows=397964 width=510) (actual time=1.454..595.347 rows=399999 loops=1)
         Index Cond: (i < 400000)
         Heap Fetches: 0
         Buffers: shared read=30774 written=3
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.116 ms
 JIT:
   Functions: 3
   Options: Inlining false, Optimization false, Expressions true, Deforming true
   Timing: Generation 0.229 ms (Deform 0.000 ms), Inlining 0.000 ms, Optimization 0.252 ms, Emission 2.779 ms, Total 3.260 ms
 Execution Time: 628.854 ms
(14 rows)

SET
SET
RESET
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=164379.97..164379.98 rows=1 width=8) (actual time=1080.068..1080.069 rows=1 loops=1)
   Buffers: shared read=28548 written=2
   ->  Bitmap Heap Scan on ttt0  (cost=126.63..163385.06 rows=397964 width=510) (actual time=5.875..1045.626 rows=399999 loops=1)
         Recheck Cond: (i < 400000)
         Rows Removed by Index Recheck: 284
         Heap Blocks: lossy=28544
         Buffers: shared read=28548 written=2
         ->  Bitmap Index Scan on brin_x  (cost=0.00..27.14 rows=399627 width=0) (actual time=1.043..1.044 rows=285440 loops=1)
               Index Cond: (i < 400000)
               Buffers: shared read=4
 Planning:
   Buffers: shared read=1
 Planning Time: 0.108 ms
 JIT:
   Functions: 5
   Options: Inlining false, Optimization false, Expressions true, Deforming true
   Timing: Generation 0.360 ms (Deform 0.110 ms), Inlining 0.000 ms, Optimization 0.342 ms, Emission 4.077 ms, Total 4.778 ms
 Execution Time: 1080.523 ms
(18 rows)

-- !!!!!!!!!! 500
-- set jit=off;

RESET
RESET
SET
                                                                 QUERY PLAN                                                                 
--------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=103063.75..103063.76 rows=1 width=8) (actual time=414.979..414.980 rows=1 loops=1)
   Buffers: shared read=59297
   ->  Index Only Scan using btree_x on ttt0  (cost=0.55..102064.73 rows=399610 width=510) (actual time=7.033..386.442 rows=399999 loops=1)
         Index Cond: (i < 400000)
         Heap Fetches: 399999
         Buffers: shared read=59297
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.093 ms
 Execution Time: 415.006 ms
(10 rows)

SET
SET
RESET
                                                           QUERY PLAN                                                            
---------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=164386.88..164386.89 rows=1 width=8) (actual time=217.692..217.693 rows=1 loops=1)
   Buffers: shared read=28548
   ->  Bitmap Heap Scan on ttt0  (cost=127.04..163387.85 rows=399610 width=510) (actual time=0.778..186.223 rows=399999 loops=1)
         Recheck Cond: (i < 400000)
         Rows Removed by Index Recheck: 284
         Heap Blocks: lossy=28544
         Buffers: shared read=28548
         ->  Bitmap Index Scan on brin_x  (cost=0.00..27.14 rows=399674 width=0) (actual time=0.748..0.748 rows=285440 loops=1)
               Index Cond: (i < 400000)
               Buffers: shared read=4
 Planning:
   Buffers: shared read=1
 Planning Time: 0.087 ms
 Execution Time: 217.725 ms
(14 rows)
Improve this answer

1 Comment

The reason I included non-key columns in the B-Tree was to rig it for index-only scans and still demonstrate an all-default BRIN outperforming it despite being incapable of index-onlies. I'm helping B-Tree and BRIN still wins. What your post is showing is weighing B-Tree down - that technically works too, it's a perfectly valid example of what your question requested. Heavy included columns drag B-Tree down, but you can also reduce fillfactor to blow it up with empty space, or make sure BRIN's freshly built and table's clustered using it, while you make sure B-Tree's old and bloated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.