I've found that the real reason for the poor Bitmap Scan performance was related not only with sparsity of the rows/pages to be rechecked, but also with the value of starting ID from which the scan begins:
create table test as select generate_series(1, 100000) id, repeat('x', 90) val;
alter table test add constraint test_pkey primary key (id);select count(*) tup_per_page from test group by (ctid::text::point)[0] order by count(*) desc limit 5;
tup_per_page -------------- 65 65 65 65 65 (5 rows) select * from test where id between X and 100000 and val != ''effective_io_concurrency=0; id between 0 and 100000; Execution time: 524.671 ms effective_io_concurrency=1; id between 0 and 100000; Execution time: 420.000 ms effective_io_concurrency=0; id between 0 and 100000; Execution time: 441.813 ms effective_io_concurrency=1; id between 0 and 100000; Execution time: 498.591 ms effective_io_concurrency=0; id between 0 and 100000; Execution time: 662.838 ms effective_io_concurrency=1; id between 0 and 100000; Execution time: 431.503 ms
effective_io_concurrency=0; id between 10 and 100000; Execution time: 1210.436 ms effective_io_concurrency=1; id between 10 and 100000; Execution time: 1056.646 ms effective_io_concurrency=0; id between 10 and 100000; Execution time: 578.102 ms effective_io_concurrency=1; id between 10 and 100000; Execution time: 396.996 ms effective_io_concurrency=0; id between 10 and 100000; Execution time: 598.842 ms effective_io_concurrency=1; id between 10 and 100000; Execution time: 555.258 ms
effective_io_concurrency=0; id between 50 and 100000; Execution time: 4017.999 ms effective_io_concurrency=1; id between 50 and 100000; Execution time: 383.694 ms effective_io_concurrency=0; id between 50 and 100000; Execution time: 535.686 ms effective_io_concurrency=1; id between 50 and 100000; Execution time: 570.221 ms effective_io_concurrency=0; id between 50 and 100000; Execution time: 852.960 ms effective_io_concurrency=1; id between 50 and 100000; Execution time: 656.097 ms
effective_io_concurrency=0; id between 64 and 100000; Execution time: 385.628 ms effective_io_concurrency=1; id between 64 and 100000; Execution time: 712.261 ms effective_io_concurrency=0; id between 64 and 100000; Execution time: 1610.618 ms effective_io_concurrency=1; id between 64 and 100000; Execution time: 438.211 ms effective_io_concurrency=0; id between 64 and 100000; Execution time: 393.341 ms effective_io_concurrency=1; id between 64 and 100000; Execution time: 744.768 ms
effective_io_concurrency=0; id between 65 and 100000; Execution time: 846.759 ms effective_io_concurrency=1; id between 65 and 100000; Execution time: 514.668 ms effective_io_concurrency=0; id between 65 and 100000; Execution time: 536.640 ms effective_io_concurrency=1; id between 65 and 100000; Execution time: 461.966 ms effective_io_concurrency=0; id between 65 and 100000; Execution time: 1810.677 ms effective_io_concurrency=1; id between 65 and 100000; Execution time: 545.359 ms
effective_io_concurrency=0; id between 66 and 100000; Execution time: 663.920 ms effective_io_concurrency=1; id between 66 and 100000; Execution time: 5571.118 ms effective_io_concurrency=0; id between 66 and 100000; Execution time: 683.056 ms effective_io_concurrency=1; id between 66 and 100000; Execution time: 5883.359 ms effective_io_concurrency=0; id between 66 and 100000; Execution time: 472.809 ms effective_io_concurrency=1; id between 66 and 100000; Execution time: 5461.794 ms
effective_io_concurrency=0; id between 100 and 100000; Execution time: 647.292 ms effective_io_concurrency=1; id between 100 and 100000; Execution time: 7810.344 ms effective_io_concurrency=0; id between 100 and 100000; Execution time: 773.750 ms effective_io_concurrency=1; id between 100 and 100000; Execution time: 5637.014 ms effective_io_concurrency=0; id between 100 and 100000; Execution time: 726.111 ms effective_io_concurrency=1; id between 100 and 100000; Execution time: 7740.607 ms
effective_io_concurrency=0; id between 200 and 100000; Execution time: 549.281 ms effective_io_concurrency=1; id between 200 and 100000; Execution time: 5032.522 ms effective_io_concurrency=0; id between 200 and 100000; Execution time: 692.631 ms effective_io_concurrency=1; id between 200 and 100000; Execution time: 5138.669 ms effective_io_concurrency=0; id between 200 and 100000; Execution time: 793.342 ms effective_io_concurrency=1; id between 200 and 100000; Execution time: 5375.822 ms
effective_io_concurrency=0; id between 1000 and 100000; Execution time: 596.754 ms effective_io_concurrency=1; id between 1000 and 100000; Execution time: 5278.683 ms effective_io_concurrency=0; id between 1000 and 100000; Execution time: 638.706 ms effective_io_concurrency=1; id between 1000 and 100000; Execution time: 5404.002 ms effective_io_concurrency=0; id between 1000 and 100000; Execution time: 730.667 ms effective_io_concurrency=1; id between 1000 and 100000; Execution time: 5761.312 ms
effective_io_concurrency=0; id between 2000 and 100000; Execution time: 656.086 ms effective_io_concurrency=1; id between 2000 and 100000; Execution time: 6156.003 ms effective_io_concurrency=0; id between 2000 and 100000; Execution time: 768.288 ms effective_io_concurrency=1; id between 2000 and 100000; Execution time: 4917.423 ms effective_io_concurrency=0; id between 2000 and 100000; Execution time: 500.931 ms effective_io_concurrency=1; id between 2000 and 100000; Execution time: 5659.255 ms
effective_io_concurrency=0; id between 5000 and 100000; Execution time: 755.440 ms effective_io_concurrency=1; id between 5000 and 100000; Execution time: 5141.671 ms effective_io_concurrency=0; id between 5000 and 100000; Execution time: 542.174 ms effective_io_concurrency=1; id between 5000 and 100000; Execution time: 6074.953 ms effective_io_concurrency=0; id between 5000 and 100000; Execution time: 570.615 ms effective_io_concurrency=1; id between 5000 and 100000; Execution time: 6922.402 ms
effective_io_concurrency=0; id between 10000 and 100000; Execution time: 469.544 ms effective_io_concurrency=1; id between 10000 and 100000; Execution time: 6083.361 ms effective_io_concurrency=0; id between 10000 and 100000; Execution time: 706.078 ms effective_io_concurrency=1; id between 10000 and 100000; Execution time: 4069.171 ms effective_io_concurrency=0; id between 10000 and 100000; Execution time: 526.792 ms effective_io_concurrency=1; id between 10000 and 100000; Execution time: 5289.984 ms
effective_io_concurrency=0; id between 20000 and 100000; Execution time: 435.503 ms effective_io_concurrency=1; id between 20000 and 100000; Execution time: 5460.730 ms effective_io_concurrency=0; id between 20000 and 100000; Execution time: 454.323 ms effective_io_concurrency=1; id between 20000 and 100000; Execution time: 4163.030 ms effective_io_concurrency=0; id between 20000 and 100000; Execution time: 674.382 ms effective_io_concurrency=1; id between 20000 and 100000; Execution time: 3703.045 ms
effective_io_concurrency=0; id between 50000 and 100000; Execution time: 226.094 ms effective_io_concurrency=1; id between 50000 and 100000; Execution time: 2584.720 ms effective_io_concurrency=0; id between 50000 and 100000; Execution time: 1431.037 ms effective_io_concurrency=1; id between 50000 and 100000; Execution time: 2651.834 ms effective_io_concurrency=0; id between 50000 and 100000; Execution time: 345.194 ms effective_io_concurrency=1; id between 50000 and 100000; Execution time: 2328.844 ms
effective_io_concurrency=0; id between 75000 and 100000; Execution time: 120.121 ms effective_io_concurrency=1; id between 75000 and 100000; Execution time: 2125.927 ms effective_io_concurrency=0; id between 75000 and 100000; Execution time: 115.865 ms effective_io_concurrency=1; id between 75000 and 100000; Execution time: 1616.534 ms effective_io_concurrency=0; id between 75000 and 100000; Execution time: 138.005 ms effective_io_concurrency=1; id between 75000 and 100000; Execution time: 1651.880 ms
effective_io_concurrency=0; id between 90000 and 100000; Execution time: 66.322 ms effective_io_concurrency=1; id between 90000 and 100000; Execution time: 443.317 ms effective_io_concurrency=0; id between 90000 and 100000; Execution time: 53.138 ms effective_io_concurrency=1; id between 90000 and 100000; Execution time: 566.945 ms effective_io_concurrency=0; id between 90000 and 100000; Execution time: 57.441 ms effective_io_concurrency=1; id between 90000 and 100000; Execution time: 525.749 ms
For some reason, with dense bitmap scans, when Bitmap Heap Scan / Recheck starts not from the first page of the table, the effective_io_concurrency=0 consistently and significantly outperforms effective_io_concurrency=1.
Regards, Vitaliy
<<attachment: starting-id-test.zip>>
