From: Jie Zhang <jzhang@greenplum.com>
To: Hannu Krosing <hannu@skype.net>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Gavin Sherry <swm@linuxworld.com.au>
Cc: pgsql-hackers@postgresql.org, "Luke Lonergan" <LLonergan@greenplum.com>
Subject: Re: On-disk bitmap index patch
Date: Mon, 24 Jul 2006 17:47:59 -0700
Message-ID: <C0EAB84F.8FB4%jzhang@greenplum.com> (raw)
In-Reply-To: <1153749575.2909.3.camel@localhost.localdomain>
On 7/24/06 6:59 AM, "Hannu Krosing" <hannu@skype.net> wrote:
> Ühel kenal päeval, P, 2006-07-23 kell 20:25, kirjutas Tom Lane:
>> Gavin Sherry <swm@linuxworld.com.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.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: jzhang@greenplum.com, hannu@skype.net, tgl@sss.pgh.pa.us, swm@linuxworld.com.au, LLonergan@greenplum.com
Subject: Re: On-disk bitmap index patch
In-Reply-To: <C0EAB84F.8FB4%jzhang@greenplum.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox