[Bizgres-general] Mapping from bitmap array position to heap location (was : A bitmap index access method is available...)

[Mark Kirkwood]

Hi,

I've been reading the code - and am a little confused about how the 
mapping from a given bitmap bit-position to its corresponding location 
in the heap relation is being done.

 From the code (src/backend/access/bitmap/bitmapinsert.c) it seems that 
the mapping is:

   tidoffset = ((uint64)blocknum *
                         (1<<(8*sizeof(OffsetNumber))))
                         + ((uint64)offset);

with inverse (src/backend/access/bitmap/bitmapsearch.c):

   blocknum = tidoffset / (1<<(8*sizeof(OffsetNumber)));
   offset = tidoffset % (1<<(8*sizeof(OffsetNumber)));

Now on my system 1<<(8*sizeof(OffsetNumber)) = 1<<16 = 65536.

Now ISTM that this makes for a very sparse mapping (i.e. a great many 
possible bit positions do not correspond to actual blocknum|offset 
combinations). I also thought (incorrectly as it transpires) that this 
could make the bitmap a lot bigger than it needs to be.


To experiment I patched these files to use a different mapping:

   tidoffset = ((uint64)blocknum * (MaxOffsetNumber + 1))
                         + ((uint64)offset);

with inverse:

   blocknum = tidoffset / (MaxOffsetNumber + 1);
   offset = tidoffset % (MaxOffsetNumber + 1);

Since I thought this would result in smaller bitmaps (as MaxOffsetNumber
is 2048 for this system). Well, despite that fact that it worked ok, the
resulting index sizes and query execution times were slightly *bigger*
and *slower* respectively, so I'm guessing that the original mapping
works better with compression (or perhaps |, & operations)... or am I 
missing something else (or even quite a lot else)?


cheers

Mark


P.s : I took the liberty of cc'ing a few of you who I suspected might be 
interested, hope that's ok...