Re: plans for bitmap indexes?

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.

--
greg