[Bizgres-general] Bitmap Indexes : Block packing calculation error

[Mark Kirkwood]

I think I finally understand why we are seeing the bitmap indexes occupy 
more on-disk space than you would expect.

In bitmap.h the max number of bitmap words to fit in a block of size 
BLCKSZ is calculated:

#define BM_MAX_NUM_OF_HRL_WORDS_PER_PAGE \
     ((BLCKSZ - \
     MAXALIGN(sizeof(PageHeaderData)) - \
     MAXALIGN(sizeof(BMBitmapOpaqueData)))/BM_HRL_WORD_SIZE)

Now this is incorrect, as BM_HRL_WORD_SIZE is in *bits*, so we really 
need to do:

#define BM_MAX_NUM_OF_HRL_WORDS_PER_PAGE \
     ((BLCKSZ - \
     MAXALIGN(sizeof(PageHeaderData)) - \
     MAXALIGN(sizeof(BMBitmapOpaqueData)))/(BM_HRL_WORD_SIZE/BITS_PER_BYTE))


This necessitates a change in the calculation of the header and word 
split to ensure that the total byte usages of these dont exceed
     BLCKSZ - \
     MAXALIGN(sizeof(PageHeaderData)) - \
     MAXALIGN(sizeof(BMBitmapOpaqueData))

I made a patch that I *think* has this all correct :-)

The results look promising (the last 3 indexes are the bitmap ones):

original:
      relname     | relpages
-----------------+----------
  bitmaptest      |    93458
  bitmaptest_id   |    21899
  bitmaptest_val0 |    18283
  bitmaptest_val1 |    18282
  bitmaptest_val2 |    51173

patched:
      relname     | relpages
-----------------+----------
  bitmaptest      |    93458
  bitmaptest_id   |    21899
  bitmaptest_val0 |     2105
  bitmaptest_val1 |     2106
  bitmaptest_val2 |     5918

retrieval performance is also much better, e.g: 3 queries

SELECT count(*)
FROM bitmaptest
WHERE val0 = 1
AND   val1 = 4
AND   val2 = 79
;
--
SELECT count(*)
FROM bitmaptest
WHERE val0 = 7
AND   val1 = 5
;
--
SELECT count(*)
FROM bitmaptest
WHERE val0 = 5
;

original:

9 s
20 s
17 s

patched:

5 s
14 s
14 s


cheers

Mark
-------------- next part --------------
--- bizgres/src/include/access/bitmap.h	Mon Dec 12 20:54:58 2005
+++ bizgresp/src/include/access/bitmap.h	Thu Jan 26 15:02:08 2006
@@ -130,9 +130,9 @@
 #define BM_MAX_NUM_OF_HRL_WORDS_PER_PAGE \
 	((BLCKSZ - \
 	MAXALIGN(sizeof(PageHeaderData)) - \
-	MAXALIGN(sizeof(BMBitmapOpaqueData)))/BM_HRL_WORD_SIZE)
+	MAXALIGN(sizeof(BMBitmapOpaqueData)))/(BM_HRL_WORD_SIZE/BITS_PER_BYTE))
 #define BM_MAX_NUM_OF_HEADER_WORDS \
-	(BM_MAX_NUM_OF_HRL_WORDS_PER_PAGE/BM_HRL_WORD_SIZE)
+	(BM_MAX_NUM_OF_HRL_WORDS_PER_PAGE/(BM_HRL_WORD_SIZE + 1))
 #define BM_NUM_OF_HRL_WORDS_PER_PAGE \
 	(BM_MAX_NUM_OF_HEADER_WORDS*BM_HRL_WORD_SIZE)