36

I'll try to explain my misunderstandings by the following example.

I didn't understand fundamentals of the Bitmap Heap Scan Node. Consider the query SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100'; the plan of which is this:

Bitmap Heap Scan on customers  (cost=25.76..61.62 rows=10 width=13) (actual time=0.077..0.077 rows=2 loops=1)
  Recheck Cond: (((username)::text < 'user100'::text) AND (customerid < 1000))
  ->  BitmapAnd  (cost=25.76..25.76 rows=10 width=0) (actual time=0.073..0.073 rows=0 loops=1)
        ->  Bitmap Index Scan on ix_cust_username  (cost=0.00..5.75 rows=200 width=0) (actual time=0.006..0.006 rows=2 loops=1)
              Index Cond: ((username)::text < 'user100'::text)
        ->  Bitmap Index Scan on customers_pkey  (cost=0.00..19.75 rows=1000 width=0) (actual time=0.065..0.065 rows=999 loops=1)
              Index Cond: (customerid < 1000)

My understanding of this node:

As explained there, the bitmap heap scan reads table blocks in sequential order, so it doesn't produce random-table-access overhead which happens as doing just Index Scan.

After Index Scan has been done, PostgreSQL doesn't know how to fetch the rows optimally, to avoid unneccessary heap blocks reads (or hits if there is a hot cache). So to figure it out it generates the structure (Bitmap Index Scan) called bitmap which in my case is being generated by generating two bitmaps of the indexes and performing BITWISE AND. Since the bitmap has been generated it now can read the table optimally in a sequential order, avoiding unnecessary heap I/O-operations.

That's the place where a lot of questions come.

QUESTION: We have just a bitmap. How does PostgreSQL knows by just a bitmap anything about rows' physical order? Or generates the bitmap so that any element of it can be mapped to the pointer to a page easily? If so, that explains everything, but it's just my guessing.

So, can we say simply that the bitmap heap scan -> bitmap index scan is like a sequential scan but only of the appropriate part of the table?

  • I wrote an explanation of some of this here: stackoverflow.com/q/33100637/398670 – Craig Ringer Oct 28 '15 at 7:31
  • @CraigRinger It seems I didn't explain correctly what I didn't understand. Of course, as you explained we have a bitmap by which PostgreSQL reads the table sequentially. I don't understand how it can figure out the actual block designated by a specific bitmap e.g. 001001010101011010101. Or it actually doesn't matter and all we have to know is just it can find a block by it's bitmap in quite fast way...? – St.Antario Oct 28 '15 at 7:37
  • Ah, you might be misunderstanding what "bitmap" means here. Let me follow up in an edit. – Craig Ringer Oct 28 '15 at 7:38
  • @CraigRinger Maybe, I took the defintion from there. – St.Antario Oct 28 '15 at 7:39
52

How does PostgreSQL knows by just a bitmap anything about rows' physical order?

The bitmap is one bit per heap page. The bitmap index scan sets the bits based on the heap page address that the index entry points to.

So when it goes to do the bitmap heap scan, it just does a linear table scan, reading the bitmap to see whether it should bother with a particular page or seek over it.

Or generates the bitmap so that any element of it can be mapped to the pointer to a page easily?

No, the bitmap corresponds 1:1 to heap pages.

I wrote some more on this here.


OK, it looks like you might be misunderstanding what "bitmap" means in this context.

It's not a bit string like "101011" that's created for each heap page, or each index read, or whatever.

The whole bitmap is a single bit array, with as many bits as there are heap pages in the relation being scanned.

One bitmap is created by the first index scan, starting off with all entries 0 (false). Whenever an index entry that matches the search condition is found, the heap address pointed to by that index entry is looked up as an offset into the bitmap, and that bit is set to 1 (true). So rather than looking up the heap page directly, the bitmap index scan looks up the corresponding bit position in the bitmap.

The second and further bitmap index scans do the same thing with the other indexes and the search conditions on them.

Then each bitmap is ANDed together. The resulting bitmap has one bit for each heap page, where the bits are true only if they were true in all the individual bitmap index scans, i.e. the search condition matched for every index scan. These are the only heap pages we need to bother to load and examine. Since each heap page might contain multiple rows, we then have to examine each row to see if it matches all the conditions - that's what the "recheck cond" part is about.

One crucial thing to understand with all this is that the tuple address in an index entry points to the row's ctid, which is a combination of the heap page number and the offset within the heap page. A bitmap index scan ignores the offsets, since it'll check the whole page anyway, and sets the bit if any row on that page matches the condition.


Graphical example

Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.


Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not

Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+

Once the bitmaps are created a bitwise AND is performed on them:

+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
            |       |              |
            v       v              v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+

The bitmap heap scan then seeks to the start of each page and reads the page:

+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
            |       |              |
            ------------------------
            only these pages read

and each read page is then re-checked against the condition since there can be >1 row per page and not all necessarily match the condition.

  • Ah, that's what they meant by populating the bitmap. – St.Antario Oct 28 '15 at 7:50
  • @St.Antario I've added graphics to explain – Craig Ringer Oct 28 '15 at 7:58
  • Let me clarify one more thing about bitmap-scan. You said that we have a 1:1 bitmap to heap pages and we can determine a heap page by a bit index in the bitmap. Since the relation may contain pages on a disk in a not sequential order (non clustered) it's not quite clear how we can determine the address of a page by just offset in a bitmap. I presume, the planner knows how to compute a page address by offset for a given relation. Is that true? – St.Antario Mar 30 '16 at 6:18
  • 1
    So we have to put all pages that are on a drive. Moreover, relation's data might be spreaded on two or more drives (therefore it's hard to imagine any linear order of relation's pages), so determining the actual offset of the next page is difficult. Because I believe that by "offset" you meant the actual physical offset corresponding to a physical position on a drive. – St.Antario Mar 30 '16 at 6:29
  • 2
    PostgreSQL doesn't care in the slightest about drives. It only cares about files on the file system. The logical file for the relation is linear and contiguous, and that's what the bitmap is over. (There might be multiple extents to the file, but they're treated as if they're appended continuously, and the bitmap is over all of them). You're looking at the wrong abstraction level. (On a side note, the bitmap in a bitmap index scan isn't computed by the planner either, it's part of the btree index access method and related more to the executor than planner). – Craig Ringer Mar 30 '16 at 6:36
3

Please refer my blog post https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 for details description of bitmap scan in PostgreSQL.

Overall quick functionality overview of bitmap scan:

  1. Bitmap Heap scan ask for a tuple from Bitmap Index Scan.

  2. Bitmap Index Scan scan the index as per the condition almost in the same way as done in normal Index Scan. But instead of returning TID (consisting of page no and offset within that) corresponding to heap data, it adds those TID in a bitmap. For simple understanding, you can consider this bitmap contains hash of all pages (hashed based on page no) and each page entry contains array of all offset within that page.

  3. Then Bitmap Heap Scan reads through the bitmap to get heap data corresponding to stored page number and offset. Then it check for visibility, qualification etc and returns the tuple based on outcome of all these checks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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