Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

Hi to everybody,

following the useful feedback that we received from this list, we
would like to submit the patch for Bitmap Indexes for the november
CommitFest (joint work of me with Gabriele Bartolini, starting from
Gavin Sherry's patch).

There are two open issues (a bug that we are catching and something
missing in the catalog), but we think that it is worth to submit the
patch, for two reasons: because we are confident to fix the open
issues soon, and moreover because bitmap index seem to have their
non-trivial use cases (index creation is significantly faster than in
other types, and they occupy far less disk space, while queries are
only slightly faster).

What we have done:

 * We refactored Gavin Sherry's patch
   http://archives.postgresql.org/pgsql-patches/2007-05/msg00013.php
   using the new access method interface; in particular, we eliminate
   a large part of the code, which has been obsoleted by the new
   access method API.

   Now the interaction of the patch with the existing code is
   significantly smaller, and essentially limited to the catalog
   entries and the access method API.

 * We fixed some wrong behaviours due to the fact that the patch
   relies on some assumptions that are no longer true because of the
   evolution of PostgreSQL (HOT tuples break the assumption that
   during index scan tuples are scanned in TID increasing order).

 * We added a chapter to the manual, plus some references to bitmap
   index in the remaining test;

 * In a separate archive we enclose some performance tests (time and
   disk size), which show that bitmap index behave slightly better
   than btree in terms of speed, especially in certain cases specific
   of the index type (low-cardinality); the main advantage (according
   to some feedback that we received from this list) is that bitmap
   indexes are significantly smaller than any other type.

Current issues:

 * Our workaround for HOT tuples has still one bug; we are currently
   working on it and we expect to fix it soon. This bug can be
   reproduced by looking at the "rows" column of the performance test.

 * Two regression tests are failing (oidjoins and opr_sanity), due to
   incomplete catalog entries. We expect to fix it very soon.

Now I am going to add the patch to the wiki page.

Best regards,
Dr. Gianni Ciolli - 2ndQuadrant Italia
PostgreSQL Training, Services and Support
gianni.ciolli@2ndquadrant.it | www.2ndquadrant.it