Re: Bitmap index status

Gavin & Heikki,

>>
>> The handling of stream and hash bitmaps looks pretty complicated to me.
>> All the bitmap-related nodes have logic to handle both types slightly
>> differently. It all seems to come down to that if a subnode (or
>> amgetbitmap in a bitmap index scan node) returns a StreamBitmap, the
>> caller needs to call the subnode many times, until it returns a NULL.
>> With a HashBitmap, the caller only calls the subnode once.
>>
>> I think amgetbitmap should be called just once per index scan, and it
>> should return either a hash bitmap or a stream bitmap. The same applies
>> to all the executor nodes that return bitmaps, they would only return a
>> single HashBitmap or StreamBitmap, and the upper node would call
>> tbm_iterate repeatedly on that.
>>
>> StreamBitmap would contain a callback (filled by the indexam) that
>> tbm_iterate would call to fill the next TBMIterateResult.
>
> Right, this was the approach taken by an earlier version of the patch I
> had worked on. It was significantly uglified by the need to keep the index
> state around and to be careful about what amrescan might do behind out
> back. I will, however, introduce the idea again because it makes the code
> much cleaner and more logical, as you seem to suggest.
>

I have been thinking about this approach some more. I do agree that this is
more attractive now. The following includes some more detailed design.
Please let me know if you have any comments. (My apologies to Gavin. You
talked to me about this approach before. But you introduced some on-disk
bitmap specific code into the tidbitmap.c, which prevented me from looking
more in this direction.)

Essentially, we want to have a stream bitmap object that has an iterator,
which will be able to iterate through the bitmaps. The BitmapIndexscan,
BitmapAnd, BitmapOr will be executed once and return a streamp bitmap or a
hash bitmap. The BitmapHeapscan then calls tbm_iterate() to iterate through
the bitmaps.

The StreamBitmap structure will look like below.

struct StreamBitmap {
NodeTag type; /* to make it a valid Node */
PagetableEntry entry; /* a page of tids in this stream bitmap */

/* the iterator function */
void (*next)(StreamBitmap*);
Node* state; /* store how this stream bitmap generated,
and all necessary information to
obtain the next stream bitmap. */
};

Two new state objects will look like below. At the same time, we introduce
three new node types: T_StreamBitmapAND, T_StreamBitmapOR,
And T_StreamBitmapIndex, to define different states.

/*
* Stores the necessary information for iterating through the stream bitmaps
* generated by nodeBitmapAnd or nodeBitmapOr.
*/
struct StreamBitmapOp {
NodeTag type; /* handles T_StreamBitmapAND and T_StreamBitmapOR */
List* bitmaps;
};

/*
* Stores some necessary information for iterating through the stream
* bitmaps generated by nodeBitmapIndexscan.
*/
struct StreamBitmapIndex {
NodeTag type; /* handle T_StreamBitmapIndex */
IndexScanDesc scan;
BlockNumber nextBlockNo;/* next block no to be read */
};

Then we will have the iterator functions like the following:

void StreamBitmapAndNext(StreamBitmap* node) {
tbm_intersect_stream(((StreampBitmapOp*) node->state)->bitmaps, node);
}

void StreamBitmapOrNext(StreamBitmap* node) {
tbm_union_stream(((StreampBitmapOp*) node->state)->bitmaps, node);
}

void StreamBitmapIndexNext(StreamBitmap* node) {
StreamBitmapIndex* sbi = (StreamBitmapIndex*) node->state;
amgetbitmap(sbi->scan, NULL, sbi->nextBlockNo);
}

What do you think?

Thanks,
Jie