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(dot)ciolli(at)2ndquadrant(dot)it | www.2ndquadrant.it