1

So as far as I understand, with a regular index scan (not index-only scan), Postgres will read the index and immediately fetch the referenced rows from the heap. For a bitmap index scan + bitmap heap scan (which I will just call bitmap scan, taken together), Postgres reads the index and collects the list of relevant heap pages and tuple offsets in a bitmap. Then it reads all the relevant heap pages in order.

The advantage for a bitmap scan is:

  • every heap page is only fetched once, while an index scan may need to read a heap page multiple times
  • heap pages are read in physical order, which is faster than random access, especially on magnetic disks.

With that, I would expect a bitmap scan to always be faster than a normal index scan, except maybe if a very small number of rows is needed, or if the bitmap doesn't fit into working memory.

But now I'm optimizing a query that uses bitmap scans by default, but switches to regular index scans when I set random_page_cost to 1 (i.e, tell postgres that random page access costs the same as sequential page access). The db runs on an SSD, so random_page_cost==1 is warranted. But the regular index scan is almost twice as fast as the bitmap index scan, which I didn't expect. This is a pair of tables with timeseries data for multiple sensors. Selecting all the data for one sensor takes ± 20 seconds with an index scan, and ± 40 seconds with a bitmap scan. That is for reading 75k rows from tables containing either 50M or 15M rows in total.

So when and why is a regular index scan ever faster than a bitmap scan?

EDIT: EXPLAIN plans

By request, here are EXPLAIN (ANALYZE,BUFFERS) plans with track_io_timing enabled. However I am not too interested in the specific performance of this query, this question is about bitmap scans vs index scans in general.

There are two tables, both with the same columns:

timestamp   timestamp with timezone PRIMARY KEY
station_id  character varying(50) PRIMARY KEY
value       numeric(10) NOT NULL

Both have an additional index on station_id.

The query:

SELECT *
FROM
    -- This first part doesn't do anything in this example,
    -- but this query was reduced from a more complex one 
    -- with parameters. This part is needed to make Postgres
    -- choose a hash join in both cases. If you forcibly disable
    -- merge join and nested loop join, running just the second
    -- subquery should give similar results.
    (select * from unnest(array['station_1']) stations(station_id) 
        where station_id = 'station_1'
    ) as stations
    join lateral (
        SELECT *
        FROM series_measurements_gauge AS gauge
            INNER JOIN series_measurements_radar AS radar
        USING (timestamp, station_id)
        WHERE station_id = stations.station_id
            AND (gauge.value > 0 OR radar.value > 0)
            AND gauge.value != 'NaN'::NUMERIC
            AND radar.value != 'NaN'::NUMERIC
        order by timestamp desc
    ) windowed
    using (station_id)

The explain plan with SET random_page_cost TO 1.0;:

"Nested Loop  (cost=108636.01..108672.92 rows=1638 width=46) (actual time=21093.479..21095.271 rows=8063 loops=1)"
"  Buffers: shared hit=2440 read=98925 written=52"
"  I/O Timings: read=20491.173 write=0.407"
"  ->  Function Scan on unnest stations  (cost=0.00..0.05 rows=1 width=32) (actual time=0.007..0.010 rows=1 loops=1)"
"        Filter: (station_id = 'station_1'::text)"
"  ->  Sort  (cost=108636.01..108640.11 rows=1638 width=27) (actual time=21093.469..21094.032 rows=8063 loops=1)"
"        Sort Key: gauge.""timestamp"" DESC"
"        Sort Method: quicksort  Memory: 822kB"
"        Buffers: shared hit=2440 read=98925 written=52"
"        I/O Timings: read=20491.173 write=0.407"
"        ->  Result  (cost=34932.45..108548.56 rows=1638 width=27) (actual time=3243.803..21086.255 rows=8063 loops=1)"
"              One-Time Filter: (stations.station_id = 'station_1'::text)"
"              Buffers: shared hit=2440 read=98925 written=52"
"              I/O Timings: read=20491.173 write=0.407"
"              ->  Hash Join  (cost=34932.45..108548.56 rows=1638 width=27) (actual time=3243.801..21083.338 rows=8063 loops=1)"
"                    Hash Cond: (gauge.""timestamp"" = radar.""timestamp"")"
"                    Join Filter: ((gauge.value > '0'::numeric) OR (radar.value > '0'::numeric))"
"                    Rows Removed by Join Filter: 69061"
"                    Buffers: shared hit=2440 read=98925 written=52"
"                    I/O Timings: read=20491.173 write=0.407"
"                    ->  Index Scan using series_measurement_gauge_station_id_idx on series_measurements_gauge gauge  (cost=0.56..73416.75 rows=76164 width=24) (actual time=0.457..17735.138 rows=77253 loops=1)"
"                          Index Cond: ((station_id)::text = 'station_1'::text)"
"                          Filter: (value <> 'NaN'::numeric)"
"                          Rows Removed by Filter: 92"
"                          Buffers: shared hit=428 read=33054"
"                          I/O Timings: read=17474.535"
"                    ->  Hash  (cost=34430.41..34430.41 rows=40118 width=24) (actual time=3242.824..3242.825 rows=77216 loops=1)"
"                          Buckets: 131072 (originally 65536)  Batches: 1 (originally 1)  Memory Usage: 5247kB"
"                          Buffers: shared hit=2012 read=65871 written=52"
"                          I/O Timings: read=3016.639 write=0.407"
"                          ->  Index Scan using series_measurement_radar_station_id_idx on series_measurements_radar radar  (cost=0.43..34430.41 rows=40118 width=24) (actual time=2.383..3210.465 rows=77216 loops=1)"
"                                Index Cond: ((station_id)::text = 'station_1'::text)"
"                                Filter: (value <> 'NaN'::numeric)"
"                                Rows Removed by Filter: 10"
"                                Buffers: shared hit=2012 read=65871 written=52"
"                                I/O Timings: read=3016.639 write=0.407"
"Planning:"
"  Buffers: shared hit=48"
"Planning Time: 0.447 ms"
"Execution Time: 21095.783 ms"

The explain plan with SET random_page_cost TO 4.0;:

"Nested Loop  (cost=272182.23..272219.14 rows=1638 width=46) (actual time=57709.314..57711.121 rows=8063 loops=1)"
"  Buffers: shared hit=1041 read=100324 written=1189"
"  I/O Timings: read=55283.990 write=16.970"
"  ->  Function Scan on unnest stations  (cost=0.00..0.05 rows=1 width=32) (actual time=0.007..0.010 rows=1 loops=1)"
"        Filter: (station_id = 'station_1'::text)"
"  ->  Sort  (cost=272182.23..272186.32 rows=1638 width=27) (actual time=57709.303..57709.851 rows=8063 loops=1)"
"        Sort Key: gauge.""timestamp"" DESC"
"        Sort Method: quicksort  Memory: 822kB"
"        Buffers: shared hit=1041 read=100324 written=1189"
"        I/O Timings: read=55283.990 write=16.970"
"        ->  Result  (cost=80099.49..272094.78 rows=1638 width=27) (actual time=38642.951..57701.677 rows=8063 loops=1)"
"              One-Time Filter: (stations.station_id = 'station_1'::text)"
"              Buffers: shared hit=1041 read=100324 written=1189"
"              I/O Timings: read=55283.990 write=16.970"
"              ->  Hash Join  (cost=80099.49..272094.78 rows=1638 width=27) (actual time=38642.950..57698.167 rows=8063 loops=1)"
"                    Hash Cond: (gauge.""timestamp"" = radar.""timestamp"")"
"                    Join Filter: ((gauge.value > '0'::numeric) OR (radar.value > '0'::numeric))"
"                    Rows Removed by Join Filter: 69061"
"                    Buffers: shared hit=1041 read=100324 written=1189"
"                    I/O Timings: read=55283.990 write=16.970"
"                    ->  Bitmap Heap Scan on series_measurements_gauge gauge  (cost=1053.96..192849.32 rows=76164 width=24) (actual time=11.281..18961.484 rows=77253 loops=1)"
"                          Recheck Cond: ((station_id)::text = 'station_1'::text)"
"                          Filter: (value <> 'NaN'::numeric)"
"                          Rows Removed by Filter: 92"
"                          Heap Blocks: exact=33368"
"                          Buffers: shared hit=440 read=33041 written=1189"
"                          I/O Timings: read=18250.155 write=16.970"
"                          ->  Bitmap Index Scan on series_measurement_gauge_station_id_idx  (cost=0.00..1034.92 rows=79781 width=0) (actual time=5.150..5.151 rows=77392 loops=1)"
"                                Index Cond: ((station_id)::text = 'station_1'::text)"
"                                Buffers: shared hit=113"
"                    ->  Hash  (cost=78544.05..78544.05 rows=40118 width=24) (actual time=38629.094..38629.096 rows=77217 loops=1)"
"                          Buckets: 131072 (originally 65536)  Batches: 1 (originally 1)  Memory Usage: 5247kB"
"                          Buffers: shared hit=601 read=67283"
"                          I/O Timings: read=37033.835"
"                          ->  Bitmap Heap Scan on series_measurements_radar radar  (cost=451.37..78544.05 rows=40118 width=24) (actual time=46.071..38527.975 rows=77217 loops=1)"
"                                Recheck Cond: ((station_id)::text = 'station_1'::text)"
"                                Filter: (value <> 'NaN'::numeric)"
"                                Rows Removed by Filter: 10"
"                                Heap Blocks: exact=67821"
"                                Buffers: shared hit=601 read=67283"
"                                I/O Timings: read=37033.835"
"                                ->  Bitmap Index Scan on series_measurement_radar_station_id_idx  (cost=0.00..441.34 rows=40121 width=0) (actual time=31.258..31.258 rows=77227 loops=1)"
"                                      Index Cond: ((station_id)::text = 'station_1'::text)"
"                                      Buffers: shared hit=19 read=44"
"                                      I/O Timings: read=19.450"
"Planning:"
"  Buffers: shared hit=22"
"Planning Time: 0.393 ms"
"Execution Time: 57712.895 ms"

Environment

After posting this question initially, I found out that this query is quite slow because it runs on Amazon RDS with 3000 IOPS and 125 MB/s throughput. When I run the same query on my local laptop, the query times drop from 20s/50s to 0.7s/1.4s (after a few repeats, so the data is mostly cached. The first (uncached) run took 16s instead of 0.7s). So RDS is an order of magnitude slower than my local machine, most likely due to the IOPS limit and limited caching.

My own conclusions from the explain plans

Both plans read about the same number of rows in their respective scans, and also the same number of blocks. The main difference is that one of the bitmap heap scans also writes 1189 blocks, and strangely enough the other bitmap heap scan doesn't even though it reads a lot more blocks. But one thousand is small compared to the 100k total blocks read, so I don't think that can explain a 2x slowdown.

Reiterating: I am not so interested in optimizing this query itself, I want to understand the performance trade offs between index scans and bitmap scans and how a bitmap scan can be twice as slow as an index scan.

Improve this question
5
  • @jjanes I added the explain plans with track_io_timing, but I don't see the answer in them. Do you?
    – JanKanis
    Commented Dec 5 at 14:24
  • How reproducible is this? If switch back and forth between the two settings of random_page_cost in quick succession do the actual timings remain stable? Because is sure looks like the difference in actual times is just because the regular index scan on radar got lucky and found all the data it needed already in memory, while the bitmap did not and had to read that data from disk. (when I say in memory, I mean in file-system cache, not in shared_buffers)
    – jjanes
    Commented Dec 5 at 21:20
  • What is the value of pg_stats.correlation for 'station_id' attribute?
    – jjanes
    Commented Dec 5 at 21:44
  • @jjanes I ran the explain queries multiple times while writing the original question and adding the explain outputs, and the performance difference was more or less stable as far as I remember. But I will try that again with an eye on the blocks written. I wasn't aware of the BUFFERS option before. The table contains timeseries data and receives live updates from the production system. So pg_stats.correlation on 'station_id' is very low (0.023) while it is very high on 'timestamp' (0.999).
    – JanKanis
    Commented Dec 7 at 9:48
  • @jjanes the above correlations are for the 'series_measurements_gauge' table. For the 'series_measurements_radar' table they are similar: 0.054 for station_id and 0.9999 for timestamp.
    – JanKanis
    Commented Dec 7 at 10:08

2 Answers 2

Reset to default
1

The advantage for a bitmap scan is:

every heap page is only fetched once, while an index scan may need to read a heap page multiple times

If effective_cache_size is large compared to the number of distinct pages believed to be being fetched, then it assumes every repeat visit to a page will still be in cache, and will be free. So large settings of effective_cache_size will destroy this expected benefit of bitmap scans over regular index scans. I think this is actually a bit of bad planning, as while reading a page repeatedly from the filesystem cache is certainly cheaper than reading it from disk, but is still far more expensive than "free". I would say at least 5x a cpu_operator_cost would be appropriate, but that is not easy to implement the way the code is organized.

I can't tell from the plans how often it thinks a page will be revisited or how large effective_cache_size is, but presumably it thinks the benefit to be had is pretty much non-existent due to one reason or the other.

heap pages are read in physical order, which is faster than random access, especially on magnetic disks.

Maybe, but setting random_page_cost=1 pretty much stomps that flat. Even if random_page_cost were more than 1, a regular index scan can still get some expected benefit of reading pages in sequence, if pg_stats.correlation is not zero.

With that, I would expect a bitmap scan to always be faster than a normal index scan, except maybe if a very small number of rows is needed,

The overhead of manipulating and traversing a bitmap is about 1.1 cpu_operator_cost per expected index tuple. 0.1 of this is the expected cost of building the bitmap, and 1.0 of this is the expected cost of rechecking the tuples. In your case, rechecking is not actually needed, but the planner estimates as-if it will be. If there is no other benefit to be had, as seems to be the case in your situation, then this smallish cost is enough to make the bitmap disfavored to the regular index scan.

That is all for the cost estimates. As far as the actual performance, it looks to me like that is an accident of what order you ran your queries in. Either one query happened to find all of its data already in memory, or maybe one query depleted your IO "credits" and then the next execution got throttled.

The main difference is that one of the bitmap heap scans also writes 1189 blocks, and strangely enough the other bitmap heap scan doesn't

That is probably just because that scan encountered a lot of dirty blocks which had to be written so they could be replaced with the data it needed. The next scan didn't encounter dirty blocks, so it could evict the blocks it needed to without writing them out first. This again calls into question the reproducibility. On an otherwise quiescent system, how did all of those blocks get dirtied in the first place? Something else must have been going on at the same time, or shortly before, you ran these queries.

Improve this answer
2
  • The database in question receives live updates from the production system. The table contains timeseries data for about 150 stations, so it receives about 150 new rows per 5 minutes. I remember the difference between the two scan types being more or less consistent during repeated runs of the analyze query, but that was before I was aware of the BUFFERS option. So I will see if I can get the query to run without writes, or if they are a consistent feature of the bitmap scan plan.
    – JanKanis
    Commented Dec 7 at 10:10
  • The effective_cache_size is almost 2 GB, so if that setting is correct all 800 MB of read blocks should fit in cache.
    – JanKanis
    Commented Dec 7 at 10:14
0

The disadvantage of a bitmap index scan is that you have to build a bitmap in memory that contains a bit per table row. If the index scan only fetches few rows from the table, that is not worth the effort.

Improve this answer
2
  • That is also what I would think. For this query it needs about a 6 MiB bitmap (or 8 MiB according to the explain plan), so I would think that is insignificant compared to the 800 MiB of data that the query reads, and doesn't explain the 2x performance difference.
    – JanKanis
    Commented Dec 5 at 15:40
  • @JanKanis The estimated cost of building a bitmap is low, but is enough to break the tie if the values would otherwise be very similar. The actual performance is a rather different question than the difference in costs estimates, and I suspect it is not even reproducible for this example.
    – jjanes
    Commented Dec 5 at 21:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.