Postgresql – Mapping between each bit in a bitmap index and tuple-pointers

bitmap-indexpostgresql

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".

Best Answer

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

Related Question