Hannu Krosing <[EMAIL PROTECTED]> 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, 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. regards, tom lane ---------------------------(end of broadcast)--------------------------- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html