PostgreSQL index With Explain plan

create table foo as select bar::integer, lpad('',1000,'A') baz from generate_series(1,1e4) bar order by bar; -- BRIN friendly clustering
10000 rows affected

-- N.B. "Rows Removed by Index Recheck" create index foo_brin on foo using brin(bar);

vacuum analyze;

explain analyze select * from foo where bar between 1 and 100;
QUERY PLAN
Bitmap Heap Scan on foo  (cost=13.01..323.85 rows=99 width=1008) (actual time=0.069..0.825 rows=100 loops=1)
  Recheck Cond: ((bar >= 1) AND (bar <= 100))
  Rows Removed by Index Recheck: 796
  Heap Blocks: lossy=128
  ->  Bitmap Index Scan on foo_brin  (cost=0.00..12.99 rows=99 width=0) (actual time=0.050..0.050 rows=1280 loops=1)
        Index Cond: ((bar >= 1) AND (bar <= 100))
Planning time: 0.163 ms
Execution time: 0.866 ms

drop table foo;

create table foo as select bar::integer, lpad('',1000,'A') baz from generate_series(1,1e4) bar order by random(); -- _not_ BRIN friendly
10000 rows affected

create index foo_brin on foo using brin(bar);

vacuum analyze;

-- N.B. "Rows Removed by Index Recheck" explain analyze select * from foo where bar between 1 and 100;

QUERY PLAN
Bitmap Heap Scan on foo  (cost=13.01..323.85 rows=99 width=1008) (actual time=0.127..5.581 rows=100 loops=1)
  Recheck Cond: ((bar >= 1) AND (bar <= 100))
  Rows Removed by Index Recheck: 9900
  Heap Blocks: lossy=1429
  ->  Bitmap Index Scan on foo_brin  (cost=0.00..12.99 rows=99 width=0) (actual time=0.100..0.100 rows=15360 loops=1)
        Index Cond: ((bar >= 1) AND (bar <= 100))
Planning time: 0.073 ms
Execution time: 5.626 ms