Mapping between each bit in a bitmap index and tuple-pointers Bitmap Indexes are described here, but I don't understand some part of it.


  A plain indexscan 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.  The bitmap scan improves locality of
  reference to the table at the cost of more bookkeeping overhead to
  manage the "bitmap" data structure --- and at the cost that the data
  is no longer retrieved in index order, which doesn't matter for your
  query but would matter if you said ORDER BY.


To visit the table tuples, you need to know the tuple-pointers. Then there must be a mapping between each bit in a bitmap and tuple-pointers. How is this mapping maintained?

I also don't understand what he meant by "sorts them using an in-memory "bitmap" data structure".
First of all, there is no bitmap index type. The Bitmap Index Scan is just a fast mechanism to look up and sort values from a bitmap.

The Backend Process scans the Index for all tuples, and stores them in a structure called TIDBitmap. The pointers to the tuples are sorted so they could be accessed sequential on disk.

The source of the Bitmap structure could be found in src/backend/nodes/tidbitmap.c