[Bizgres-general] Re: Non equality operators and bitmap indexes (was : A bitmap index access method is available...)

[Jie Zhang]

On 12/31/05 7:37 PM, "Mark Kirkwood" <markir at paradise.net.nz> wrote:

> Simon Riggs wrote:
>> On Wed, 2005-12-28 at 23:02 -0800, Jie Zhang wrote:
>> 
>> 
>>> There are three known encoding schemes for the bitmap index: the equality
>>> scheme (each bitmap is associated with each one of all distinct values), the
>>> interval scheme (each bitmap is associated with several distinct values that
>>> lie within an interval), and the range scheme (each bitmap is associated
>>> with distinct values that are less/greater than a given value). Each of
>>> these schemes has different performance advantages for different queries.
>>> Currently, we only support the equality scheme. I think that the better way
>>> is to let users decide which encoding scheme to use. Any comments on this?
>> 
>> 
>> You should be able to do as Mark suggests, irrespective of the coding
>> scheme used. (More work....)
>> 
> 
> Exactly - range encoding makes it *easier* to do non equality
> comparisons, but you certainly can do 'em with equality encoding too (it
> does take more bitmap operations as I understand it). I have been reading:
> 
> http://www.cs.brown.edu/courses/cs227/Papers/Indexing/ioannidis98.pdf
> 
> which seems to cover this stuff quite well!
> 

I agree that the range queries can be answered by only using equality
encoding scheme. But this may mean to scan several bitmaps, with the range
of 2 to half of number of distinct values. If we fix on one encoding scheme,
the range encoding seems to be more appealing, since it always needs to scan
two bitmaps. It is more costly for equality queries than equality encoding.
But it is certainly cheaper in range queries.

Happy New Year to you too.

Best,
Jie