Re: Bitmapscan changes

On Mon, 2007-03-12 at 13:56 -0400, Tom Lane wrote:

> At this point I'm feeling unconvinced that we want it at all.  It's
> sounding like a large increase in complexity (both implementation-wise
> and in terms of API ugliness) for a fairly narrow use-case --- just
> how much territory is going to be left for this between HOT and bitmap
> indexes?

HOT and clustered indexes have considerable synergy. In many tests we've
got +20% performance with them acting together. Neither one achieves
this performance on their own, but together they work very well.

There is an overlap between clustered and bitmap indexes, but they come
at the problem from different ends of the scale. Bitmap indexes are
designed to cope well with highly non-unique data, while clustered
indexes optimise for unique or somewhat unique keys. The difference is
really bitmap for DW and clustered indexes for OLTP.

The ideas for bitmap indexes come from research and other RDBMS
implementations. Clustered indexes have also got external analogs - the
concepts are very similar to SQLServer Clustered Indexes and Teradata
Primary Indexes (Block Index structure), as well as being reasonably
close to Oracle's Index Organised Tables.

Clustered indexes offer a way to reduce index size to 1-5% of normal
b-tree sizes, yet still maintaining uniqueness checking capability. For
VLDB, that is a win for either OLTP or DW - think about a 1 TB index
coming down to 10-50 GB in size. The benefit is significant for most
tables over a ~1 GB in size through I/O reduction on leaf pages.

--
  Simon Riggs
  EnterpriseDB   http://www.enterprisedb.com