In-Memory Bitmap Index in Postgres

I have written twice already that bitmap indexes are not implemented in Postgres. But somebody may as why then explain writes that it used Bitmap Index Scan? However, that is not on-disk index I wrote about. One of the most interesting analysis of performance I found is at Depesz.com, which is a blog of a Polish database administrator who has been working with Postgres for ages.

But coming back to the topic, what is this bitmap index in Postgres? It is something I have already wrote about in , but created dynamically in memory.

Without a loss or generality let us assume that a query uses two indexes A and B. If possible Postgres creates a memory block, which is basically a bitmap, with zeroes indicating that the record should be omitted, and ones that it should be returned. What is so special about it is that for this operation Postgres is using the information only from the index, and not looking up the data in table. If it can do it for many indexes then combining them is simple “and” or “or” operations on bits, which are very fast.

Why is it faster than usual index scan?

  • It uses information only from the indexes not looking up the values in table.
  • It does everything in memory, so combining two indexes means only a scan through two indexes and performing a bitwise operation.

What could be there more?
If the bitmap indexes were implemented as “on-disk” instead of “in-memory”, then the database could compress it reducing the number of I/O operations even more.

To summarize the differences a quote from postgres.org mailing list:

“A plain Index Scan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory “bitmap” data structure, and then visits the table tuples in physical tuple-location order.” — Tom Lane at postgresql.org