Re: Choice of bitmap scan over index scan

> Postgres is being conservative. The plan it uses (bitmap index scan)
> will perform much better than an index scan when the data is not in the
> cache, by maybe an order of magnitude, depending on your hardware setup.
>
> The index scan may perform better at the moment, but the bitmap index
> scan is safer.

Suppose you make a query that will need to retrieve 5% of the rows in a
table...

If the table is nicely clustered (ie you want the latest rows in a table
where they are always appended at the end with no holes, for instance),
bitmap index scan will mark 5% of the pages for reading, and read them
sequentially (fast). Plain index scan will also scan the rows more or less
sequentially, so it's going to be quite fast too.

Now if your table is not clustered at all, or clustered on something
which has no correlation to your current query, you may hit the worst case
: reading a ramdom sampling of 5% of the pages. Bitmap index scan will
sort these prior to reading, so the HDD/OS will do smart things. Plain
index scan won't.

- worst case for bitmap index scan is a seq scan... slow, but if you have
no other choice, it's OK.
- worst case for plain index scan is a lot worse since it's a random
seekfest.

If everything is cached in RAM, there is not much difference (plain index
scan can be faster if the bitmap "recheck cond" is slow).