Re: [PATCHES] WIP: bitmap indexes

On Mon, 14 Aug 2006, Tom Lane wrote:

> Gavin Sherry <swm(at)linuxworld(dot)com(dot)au> writes:
> > One of the main reasons for the uglification of the executor in Jie's
> > original patch was that she wanted to avoid the inefficiency of
> > translating the on disk bitmap representation to the TID bitmap
> > representation.
>
> Offhand that seems like micro-optimization, at least as stated -- you
> want to think about number of page fetches rather than exactly how a
> bitmap is represented. I've still not got round to reading the patch
> in detail, but after thinking about it in the shower on a few mornings,
> it seems to me that the key concept we'd like to implement is that a
> bitmap index can provide its data in a page-by-page fashion without the
> overhead of fabricating the bitmap in-memory as btree forces us to do.
> That is, the current implementation involves doing the whole index scan
> and building a bitmap in memory, which we then read out page-wise for
> the heap scan. The weak spot of this approach is that the in-memory
> bitmap can get unreasonably large. With a bitmap index, you can pass
> data back in a page-by-page fashion: here are the TID indexes to hit on
> this page, then here are the TID indexes to hit on the next page, etc.
> Correct me if I'm wrong, but isn't the patch's present hacking on the
> executor intended to make it happen like this?

Not really. It reads ahead on the bitmap index and passes back the bitmap
words. The other executor routines are hacked up to process the data in
this format.

If I understand your idea correctly, we could change this to read, say, a
page of the index at a time, store this internally in the state object we
pass around, and we can then read out of this the TIDs on a given heap
page which match the query. Once we process all the bitmap data, we just
pull more.

>
> The main architectural idea I have at the moment is that this should all
> be private between tidbitmap.c and the bitmap index AM. I think we
> could perhaps have a flavor of tidbitmap that is "serial access" as
> opposed to the present random-access, ie, instead of keeping the whole
> bitmap in memory, you have a function pointer that you can call to
> demand the next bitmap page in sequence. tidbitmap.c will need to
> manage both kinds of bitmaps and be prepared to do ANDs and ORs across
> both types, but just at the moment I see no showstopper reason why this
> can't work.
>
> Or is that exactly what you said already? It's late here and I'm a
> bit tired...

This is better than what I had in mind. It seems to me that part of this
which will be a litle ugly is dealing with "key in (1,2,3,...)"
transformation. Let me think about it...

Thanks,

Gavin