Re: Question about indexes

Tom Lane kirjutas L, 31.01.2004 kell 01:02:
> Hannu Krosing <hannu(at)tm(dot)ee> writes:
> > Another idea would be using bitmaps where we have just one bit per
> > database page and do a seq scan but just over marked pages.
>
> That seems a bit too lossy for me,

I originally thought of it in context of data-warehousing and persistent
bitmap indexes. there the use of these same bitmaps for clustering would
un-lossify this approach.

> but I really like your later idea
> about folding. Generalizing that a little, we can choose any fold point
> we like. We could allocate, say, one 32-bit word per page and set the
> (i mod 32) bit when item i is fingered by the index. After retrieving
> the heap page, we'd need to test all the valid rows that have item
> numbers matching a set bit mod 32. On typical tables (with circa 100
> items per page) this would require testing only about 3 rows per page.
> ORing and ANDing of such bitmaps still works, with the understanding
> that it's lossy and you have to double check each retrieved tuple.
>
> If the fold point is above about 100, your idea of keeping track of
> whether we actually set any wrapped-around bits would become useful,
> but below that I think we'd just be wasting a bit.

Not only wasting bits, but also making the code hairier - we can't just
do simple ANDs and ORs.

--------------
Hannu