Re: Proposal: Improve bitmap costing for lossy pages

Hi Dilip,

Recently I was thinking about this too, when working on the index-only
count(*) patch for indexes supporting amgetbitmap [1]. That patch
teaches bitmap heap scan node to skip heap fetches under certain
conditions. Exact tidbitmap pages are a prerequisite for this, so the
lossines of the bitmap heavily influences the cost of a scan.

I used a very simple estimation: lossy_pages = max(0, total_pages -
maxentries / 2). The rationale is that after the initial lossification,
the number of lossy pages grows slower. It is good enough to reflect
this initial sharp increase in the lossy page number.

The thing that seems more important to me here is that the tidbitmap is
very aggressive in lossifying the pages: it tries to keep the number of
entries under maxentries / 2, see tbm_lossify():
...
if (tbm->nentries <= tbm->maxentries / 2)
{
/*
* We have made enough room.
...
I think we could try higher fill factor, say, 0.9. tbm_lossify basically
just continues iterating over the hashtable with not so much overhead
per a call, so calling it more frequently should not be a problem. On
the other hand, it would have to process less pages, and the bitmap
would be less lossy.

I didn't benchmark the index scan per se with the 0.9 fill factor, but
the reduction of lossy pages was significant.

Regards,
Alexander Kuzmenkov

[1]
https://www.postgresql.org/message-id/flat/251401bb-6f53-b957-4128-578ac22e8acf%40postgrespro(dot)ru#251401bb-6f53-b957-4128-578ac22e8acf(at)postgrespro(dot)ru