Re: Question about indexes

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> That seems a bit too lossy for me, 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.

That would make it really hard to ever clear the bits. What do you do when you
vacuum and one of the tuples is no longer needed. You can't be sure you can
clear the bit in the index because there could be multiple tuples represented
by the bit being set. You would have to test the condition on the other tuples
covered by the bit to see if it can be cleared.

--
greg