Re: On-disk bitmap index patch

On 7/24/06 6:59 AM, "Hannu Krosing" <hannu(at)skype(dot)net> wrote:

> Ühel kenal päeval, P, 2006-07-23 kell 20:25, kirjutas Tom Lane:
>> Gavin Sherry <swm(at)linuxworld(dot)com(dot)au> writes:
>>> On Sun, 23 Jul 2006, Tom Lane wrote:
>>>> However, the main problem I've got with this is that a new index AM is a
>>>> pretty large burden, and no one's made the slightest effort to sell
>>>> pghackers on taking this on.
>>
>>> For low cardinality sets, bitmaps greatly out perform btree.
>>
>> If the column is sufficiently low cardinality, you might as well just do
>> a seqscan --- you'll be hitting most of the heap's pages anyway. I'm
>> still waiting to be convinced that there's a sweet spot wide enough to
>> justify supporting another index AM. (I'm also wondering whether this
>> doesn't overlap the use-case for GIN.)
>
> IIRC they quoted the cardinality of 10000 as something that is still
> faster than btree for several usecases.
>
> And also for AND-s of several indexes, where indexes are BIG, your btree
> indexes may be almost as big as tables but the resulting set of pages is
> small.

Yeah, Hannu points it out very well -- the bitmap index works very well when
columns have low cardinalities and AND operations will produce small number
of results.

Also, the bitmap index is very small in low cardinality cases, where the
btree tends to take up at least 10 times more space.