Date: Tue, 25 Jul 2006 15:54:48 +1200
From: Mark Kirkwood <markir@paradise.net.nz>
Subject: Re: On-disk bitmap index patch
In-reply-to: <C0EAB84F.8FB4%jzhang@greenplum.com>
To: Jie Zhang <jzhang@greenplum.com>
Cc: Hannu Krosing <hannu@skype.net>, Tom Lane <tgl@sss.pgh.pa.us>,
	Gavin Sherry <swm@linuxworld.com.au>, pgsql-hackers@postgresql.org,
	Luke Lonergan <LLonergan@greenplum.com>
Message-id: <44C59608.6030207@paradise.net.nz>
MIME-version: 1.0
Content-type: text/plain; format=flowed; charset=ISO-8859-1
Content-transfer-encoding: 7bit
User-Agent: Thunderbird 1.5.0.4 (X11/20060704)
References: <C0EAB84F.8FB4%jzhang@greenplum.com>

Jie Zhang wrote:
> 
> On 7/24/06 6:59 AM, "Hannu Krosing" <hannu@skype.net> wrote:
> 
>>
>>
>> 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.
> 
> 

The smallness of the bitmap index also means that some queries will 
require much less work_mem to achieve good performance e.g consider:

  TPCH dataset with scale factor 10 on my usual PIII HW, query -
  select count(*) from lineitem where l_linenumber=1;

This executes in about 100 seconds with work_mem = 20M if there is a 
bitmap index on l_linenumber. It takes 3832 seconds (!) if there is a 
btree index on the same column. Obviously cranking up work_mem will even 
up the difference (200M gets the btree to about 110 seconds), but being 
able to get good performance with less memory is a good thing!

Cheers

Mark