And in addition,

If you submitted the query:

SELECT * FROM addresses WHERE state = 'OH'
AND areacode = '614'

Then, with bitmap indexes, the bitmaps are just logically ANDed 
together, and the final bitmap determines the matching rows.

Mike Mascari
mascarm@mascari.com

-----Original Message-----
From:	mlw [SMTP:markw@mohawksoft.com]

Bruce Momjian wrote:

> > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> >
> > > Here is a small list of big TODO items.  I was wondering which 
ones
> > > people were thinking about for 7.2?
> >
> > A friend of mine wants to use PostgreSQL instead of Oracle for a 
large
> > application, but has run into a snag when speed comparisons 
looked
> > good until the Oracle folks added a couple of BITMAP indexes.  I 
can't
> > recall seeing any discussion about that here -- are there any 
plans?
>
> It is not on our list and I am not sure what they do.

Do you have access to any Oracle Documentation? There is a good 
explanation
of them.

However, I will try to explain.

If you have a table, locations. It has 1,000,000 records.

In oracle you do this:

create bitmap index bitmap_foo on locations (state) ;

For each unique value of 'state' oracle will create a bitmap with 
1,000,000
bits in it. With a one representing a match and a zero representing 
no
match. Record '0' in the table is represented by bit '0' in the 
bitmap,
record '1' is represented by bit '1', record two by bit '2' and so 
on.

In a table where comparatively few different values are to be indexed 
in a
large table, a bitmap index can be quite small and not suffer the N * 
log(N)
disk I/O most tree based indexes suffer. If the bitmap is fairly 
sparse or
dense (or have periods of denseness and sparseness), it can be 
compressed
very efficiently as well.

When the statement:

select * from locations where state = 'MA';

Is executed, the bitmap is read into memory in very few disk 
operations.
(Perhaps even as few as one or two). It is a simple operation of 
rifling
through the bitmap for '1's that indicate the record has the 
property,
'state' = 'MA';



Thu, 7 Jun 2001 15:34:17 -0400
Mike Mascari <mascarm@mascari.com>
RE: Re: 7.2 items
> And in addition,
> 
> If you submitted the query:
> 
> SELECT * FROM addresses WHERE state = 'OH'
> AND areacode = '614'
> 
> Then, with bitmap indexes, the bitmaps are just logically ANDed 
> together, and the final bitmap determines the matching rows.

Message added to TODO.detail.  The use of AND seems like a very nice
optimization possible with bitmap indexes.  Thanks.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Thu, 7 Jun 2001 16:05:19 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Re: 7.2 items