Re: plans for bitmap indexes?

On K, 2004-10-13 at 00:09, Greg Stark wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>
> > SELECT * FROM people WHERE orientation = 'gay' AND gender = 'male' AND city =
> > 'San Francisco';
>
> There are actually two TODOs here.
>
> 1) a "bitmap scan" that would be usable with any type of index. The tuple
> locations can be read in for each criteria and sorted by location and built
> into bitmaps. The results can be combined using bitmap operations and the
> tuples scanned in physical order.
>
> 2) A persistent bitmap index that would enable skipping the first step of the
> above.
>
> In the case if all the columns were btree indexes it might still make sense to
> scan through all the indexes and combine the results before reading in the
> actual tuples. Especially if the tuples are very wide and each column
> individually very unselective, but the combination very selective.
>
> However it would work even better if gender and orientation could be stored on
> disk in a bitmap representation. They're very low cardinality and could be
> stored quite compactly. The result would read the data faster, skip the sort,
> and be able to start returning tuples even before it finished reading the
> entire index.

We could go even further and use the same bm indexes for selecting the
page where the tuple is stored (found by AND of all bitmap indexes plus
fsm) and achieve "natural" clustering

If this is done consistently we need only 1 bit/page in our index
(straight bitmap for 1GB fits in 16384 kb or 4 database pages)

This approach may result in poor utilisation of database pages for small
tables, but one would not use bitmap indexes for small tables in the
first place.

--------------
Hannu