Re: Bitmap index thoughts

On 12/27/06 3:10 AM, "Gavin Sherry" <swm(at)linuxworld(dot)com(dot)au> wrote:

> On Wed, 27 Dec 2006, Heikki Linnakangas wrote:
>
>> Gavin Sherry wrote:
>>> On Tue, 26 Dec 2006, Heikki Linnakangas wrote:
>>>> for typical bitmap index use cases and most of the needed pages should
>>>> stay in memory, but could we simplify this? Why do we need the auxiliary
>>>> heap, couldn't we just store the blk+offset of the LOV item directly in
>>>> the b-tree index item?
>>>
>>> The problem is, the b-tree code is very much tied to the heap. I don't
>>> want to modify the b-tree code to make bitmap indexes work (better).
>>> What's really tempting is to just manage our own balanced tree within the
>>> bitmap index file(s) itself. It would start from the metapage and simply
>>> spill to other 'special' index pages when necessary. The problem is, we do
>>> not have b-tree code generic enough that it would allow us to do this
>>> trivially -- consider concurrency and WAL in particular, which we
>>> currently get for free. I guess this is why I've been ignoring this issue
>>> :-).
>>
>> Maybe we could reuse the code in ginbtree.c. Looks like Teodor & Oleg
>> had the same problem :).
>>
>> Modifying the nbtree code doesn't seem that difficult either. AFAICS,
>> the only places where the heap is from within nbtree code is in index
>> building and uniqueness checks.
>
> I'll take a look and think about it.
>

I will take a look at it as well. I would also like to add eventually the
values for bm_last_tid_location in all bitmap page to the lov heap.
Combining this with the attribute values, we can easily jump into a specific
bitmap page. This will be useful during vacuuming and insertion after
vacuuming -- we can jump into a page to modify a bit. I am not sure if this
will affect the use of the btree code without the heap. But if we can get
rid of the lov heap, that would be great.

>>
>>>> And instead of having separate LOV pages that store a number of LOV
>>>> items, how about storing each LOV item on a page of it's own, and using
>>>> the rest of the page to store the last chunk of the bitmap. That would
>>>> eliminate one page access, but more importantly, maybe we could then get
>>>> rid of all the bm_last_* attributes in BMLOVItemData that complicate the
>>>> patch quite a bit, while preserving the performance.
>>>
>>> That's an interesting approach. We would still need a concept of
>>> last_word, at the very least, and probably last_comp_word for convenience.
>>
>> Why?
>
> The two last words of the bitmap vector, stored in the LOV item, provide a
> few things: they buffer the addition of new matches in the vector and they
> ease the calculation of the current position of the end of the vector.
> Jie, do you want to add more?
>
> I think we could do this differently by calculating everything based on
> the other data stored in the lov item and data page (last_tid_location and
> num_hrl_words_used, from memory). But, I'm not sure. Jie?

Sure. When appending a new bit into an existing bitmap, the last two words
are needed to compute new HRL words, and they are the only words affected by
this new appending bit. So we need a way to know these two words easily.
Like Gavin said, separating them from other words is for convenience.

Also, we won't be able to get rid of bm_last_setbit. We need bm_last_setbit
to tell us how many zeros are there between two bit 1s. There is no other
way to know this.

Thanks,
Jie