Re: Planner selects slow "Bitmap Heap Scan" when "Index Scan" is faster

On Fri, Apr 6, 2012 at 3:09 PM, Kim Hansen <kim(at)rthansen(dot)dk> wrote:
> Hi all
>
> On Fri, Apr 6, 2012 at 19:11, Jeff Janes <jeff(dot)janes(at)gmail(dot)com> wrote:
>> On Wed, Apr 4, 2012 at 6:47 AM, Kim Hansen <kim(at)rthansen(dot)dk> wrote:
>>> Hi All
>>>
>>> I have a query where the planner makes a wrong cost estimate, it looks
>>> like it underestimates the cost of a "Bitmap Heap Scan" compared to an
>>> "Index Scan".
>>>
>>> This it the two plans, I have also pasted them below:
>>>  Slow (189ms): http://explain.depesz.com/s/2Wq
>>>  Fast (21ms): http://explain.depesz.com/s/ThQ
>>
>> Could you do explain (analyze, buffers)?
>
> I have done that now, the log is pasted in below. It looks like every
> buffer fetched is a hit, I would think that PostgreSQL should know
> that as almost nothing happens on the server and effective_cache_size
> is configured to 8GB.

That almost nothing happens on the server does not enter into it. It
would need to know whether the last thing that did happen (no matter
how long ago that was) touched the same data that the current query
needs to touch.

effective_cache_size is only used when it is anticipated that the same
blocks will be accessed repeatedly *within the same query*.
It is not used to estimate reuse between different queries.

>
>> Did you run these queries multiple times in both orders?  If you just
>> ran them once each, in the order indicated, then the bitmap scan may
>> have done the hard work of reading all the needed buffers into cache,
>> and the index scan then got to enjoy that cache.
>
> I have run the queries a few times in order to warm up the caches, the
> queries stabilise on 20ms and 180ms.

My first curiosity is not why the estimate is too good for Bitmap
Index Scan, but rather why the actual execution is too poor. As far
as I can see the only explanation for the poor execution is that the
bitmap scan has gone lossy, so that every tuple in every touched block
needs to be rechecked against the where clause. If that is the case,
it suggests that your work_mem is quite small.

In 9.2, explain analyze will report the number of tuples filtered out
by rechecking, but that isn't reported in your version.

It looks like the planner makes no attempt to predict when a bitmap
scan will go lossy and then penalize it for the extra rechecks it will
do. Since it doesn't know it will be carrying out those extra checks,
you can't just increase the tuple or operator costs factors.

So that may explain why the bitmap is not getting penalized for its
extra CPU time. But that doesn't explain why the estimated cost is
substantially lower than the index scan. That is probably because the
bitmap scan expects it is doing more sequential IO and less random IO.
You could cancel that advantage be setting random_page_cost to about
the same as seq_page_cost (which since you indicated most data will be
cached, would be an appropriate thing to do regardless of this
specific issue).

Cheers,

Jeff