Re: Bitmap table scan cost per page formula

On Tue, Dec 19, 2017 at 10:25 PM, Justin Pryzby <pryzby@telsasoft.com> wrote:
> In this old thread: https://www.postgresql.org/message-id/CAGTBQpZ%2BauG%2BKhcLghvTecm4-cGGgL8vZb5uA3%3D47K7kf9RgJw%40mail.gmail.com
> ..Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
>> Correct me if I'm wrong, but this looks like the planner not
>> accounting for correlation when using bitmap heap scans.
>>
>> Checking the source, it really doesn't.
>
> ..which I think is basically right: the formula does distinguish between the
> cases of small or large fraction of pages, but doesn't use correlation.  Our
> issue in that case seems to be mostly a failure of cost_index to account for
> fine-scale deviations from large-scale correlation; but, if cost_bitmap
> accounted for our high correlation metric (>0.99), it might've helped our case.

I think this is a different and much harder problem than the one
Haisheng Yuan is attempting to fix.  His data shows that the cost
curve has a nonsensical shape even when the assumption that pages are
spread uniformly is correct.  That should surely be fixed.  Now, being
able to figure out whether the assumption of uniform spread is correct
on a particular table would be nice too, but it seems like a much
harder problem.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company